JavaScript で Scheme 作った - にょきにょきブログ

簡易 Scheme を JavaScript で実装した。基本的な関数の呼び出しや定義が行える。
完全に再現したわけでは無いので、Scheme 方言言語 Tetorang と呼ぶことにしよう。

使用はこちら。
http://512bit.org/scheme/scheme.html
Google Chrome で動きます。ぎりぎり FireFox でも動くかも。IE では多分動きません。

使い方

Scheme っぽい言語の REPL。
下部のテキストエリアに scheme 文を打つと、その文と実行結果が上に表示される。実行方法はテキストエリア上で Shift+Enter.
「Shift + Enter で実行」って文の右にグレーで数値が表示されていて、これは括弧の深さを表す。(テキストエリア上で (((()))) とか打つと動作がわかると思う。) この機能は括弧が多い scheme で、括弧の個数がわかりにくなるのでつけた機能。

ではこの REPL で使える書き方の紹介。

シンボル定義

define を使う。

(define x 10)

こんな風に定義して、REPL に x と打ち込めばちゃんと 10 が返される。

関数定義もOK.

// フィボナッチ数を求める関数 fib の定義
(define (fib x)
	(cond ((eq 0 x) 0)
    	((eq 1 x) 1)
        (#t 
        	(+ 
            	(fib (- x 1)) 
                (fib (- x 2))))))

関数呼び出し

上で定義した関数 fib の呼び出し。

> (fib 8)
34

car や cdr の基本関数も使える。使用可能な関数は

(functions)

で出てくる。

同様に、関数でない定義、つまり単なる値の定義は

(values)

で出せる。

特殊形式の利用

使える特殊形式

define
if
cond
lambda
apply
let
quote

quote は省略記法'(クオート)が使える。

> 'string
quote

lambda はこんな感じ。

> ((lambda (x) (* x x)) 3)
9

apply.

> (apply + '(1.1 2.2 3.3))
6.6

可変長引数

ドット記法による可変長引数のサポート。

(define (add . x)
	( accumulate + 0 x ))

上のように add を定義するとこんな風に引数の数に制限なしで使える。

> (add 1 2 3 4 5)
15

できないこと

マクロの定義、使用はできない。宿題。

実装詳細

さて今回作った言語 Tetorang の実装方法を紹介する。といってもそれほど複雑なことはしておらず、Scheme で表されるリストを JavaScript の配列に変換して順当に処理、という感じ。

例

(define (add x y)
    (+ x y))

こんなコードがあったとする。これを、JavaScript 上ではこんな風に扱う。

["define",["add","x","y"],["+","x","y"]]

このパース処理で 100 行くらい。あまり適切な表現ではないが、コードとの対比という意味でこの JavaScript 配列に変換されたコードを Tetorang バイナリと呼ぶことにしよう。

このパース処理付近はどうでもいいとして、JavaScript の配列に変換された Tetorang コードを実行するには execute 関数に投げればよい。execute 関数が Tetorang 実装の肝で、これが全てと言っても良い。

第一引数は Tetorang バイナリ。第二引数はシンボルテーブル。Tetorang バイナリを実行中、シンボルの解決をする時に第二引数からシンボルを探す。つまり、名前空間となっている。

execute = function( tree, symbols ){
    if( symbols == undefined )
        symbols = new Symbols();

    depth++;
    if( depth > 10000 )
        throw("maybe infinity loop. aborted.");

	DEBUG && console.log(printResult( tree ));

    // nil
    if( isNil( tree ) )
        return 'nil';
        
    // string
    if( isString( tree ) )
        return tree.substring(1, tree.length - 1);

    // value
    if( isValue( tree ) )
        return tree;
        
    // symbol
    if( isSymbolName( tree ) )
        return findSymbol( tree, symbols );
        
    // special form
    if( isSpecial( tree ) )
        return Special[ tree[0] ]( tree, symbols );
    
    // builtin function
    if( isBuiltinFunc( tree, symbols ) ) {
        var lambda = execute( tree[0], symbols );
        var args = tree.slice(1).map( function(v){ return execute(v,symbols); });
        return lambda.apply( symbols, args );
    }

    // user defined function            
    if( isUserDefinedFunc( tree, symbols ) ){
        var lambda = execute( tree[0], symbols );
        var newSymbols = bindArguments( lambda[0], tree, symbols );
        return execute( lambda[1], newSymbols );
    }
    
    throw( "unknown object : " + tree );
};

isList や isValue 等は容易に想像がつくと思うので省略する。ちょっと複雑な関数呼び出しは、ユーザー定義関数を呼び出す際に呼び出される bindArguments 関数だろう。これは、

(define (f x) (car x))

のような関数を呼び出す際に仮引数 x に実引数を束縛する関数だ。

シンボルテーブルの実態である Symbols オブジェクトを new して新たなテーブルを作成する。そしてその新たなシンボルテーブル、newSymbols に対して、仮引数と実引数のペアをシンボルテーブルに登録する。(registerSymbol 関数)

bindArguments = function( parameter, tree, symbols ){
    var newSymbols = new Symbols();
    newSymbols.prototype = symbols;
    for( var i=0; i<parameter.length; i++ ) {
        if( parameter[i] == '.' ) {
            // 可変長引数 これ以降をリストにまとめて渡す
            var ends = [];
            for( i++; i < tree.length; i++ ){
                var ret = execute( tree[i], symbols );
                ret = isNil(ret) ? 'nil' : ret;
                ends.push(ret);
            }
            registerSymbol( parameter[parameter.length-1], ends, newSymbols );
            break;
        }
        var ret = execute( tree[i+1], symbols );
        ret = isNil(ret) ? 'nil' : ret;
        registerSymbol( parameter[i], ret, newSymbols );
    }
    return newSymbols;
};

可変長引数は少々汚いコードだが、やっていることは仮引数中に . (ドット) が現れたらそれ以降の実引数をリストにして束縛しているというコードだ。

次に、基本関数や nil, #t 等をシンボルテーブルテーブルに登録する。

registerSymbol( 'nil', 'nil' );
registerSymbol( '#t', '#t' );
registerSymbol('car', function(list){
    if( arguments.length != 1 )
        throw("'car' requires 1 arguments.");

    if( isNil(list) )
        return 'nil';

    if( !(list instanceof Array) )
        throw("car invalid argument : "+list);

    return list[0];
});