Javascriptで継続渡し

id:nozom:20060317#1142577630の続き。世界で最も誤解された言語とも呼ばれるJavascriptを使って継続渡しを書いてみた。

なお、Javascriptの処理系としてRhino*1を使った。参考文献は『入門Javascript』(ISBN:4756138713)。

function fib(n) {
    if ((n == 1) || (n == 2))
        return 1;
    else
        return fib(n - 1) + fib(n - 2);
}

function fib_cps(n, k) {
    if ((n == 1) || (n == 2))
        return k(1);
    else
        return fib_cps(n - 1, function(v1) {
            return fib_cps(n - 2, function(v2) {
                return k(v1 + v2);
            });
        });
}

function fib_test() {
    for (var i = 1; i < 10; i ++) {
        var n = fib_cps(i, function(v) { return v; });
        print("Fibonacci(" + i + ") = " + n);
    }
}

fib_test();

実行結果

% java -jar js.jar fib.js
Fibonacci(1) = 1
Fibonacci(2) = 1
Fibonacci(3) = 2
Fibonacci(4) = 3
Fibonacci(5) = 5
Fibonacci(6) = 8
Fibonacci(7) = 13
Fibonacci(8) = 21
Fibonacci(9) = 34

このように、Javascriptは極めてSchemeっぽく書くこともできることがわかった。（実際何度も括弧を付ける位置を間違えた）

Schemerから見たJavascriptの特徴(とりあえず気付いたものだけ):

• 括弧の位置が違う
• 要素の区切りにカンマが必要
• 演算子は中間記法
• lambda→function
• 多値がない
• 値を返すにはreturnが必要
• リストがない(代わりにArrayを使う)
• map系の関数がない
• call/ccがない(Rhinoには継続の実験的なサポートがあるらしい*2 )

この辺のことに気をつければ、JavascriptはLispの亜種だと思っても問題なさそう。

*1:Rhino - Java による JavaScript http://www.mozilla-japan.org/rhino/

*2:RhinoWithContinuations - Cocoon Wiki http://wiki.apache.org/cocoon/RhinoWithContinuations