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 )

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