12行で書ける継続付きインタプリタ

javascript

どうも、継続がよくわからないので、とても短いサンプルを作ってみました。

["mul", 3, ["add", 1, 4]]

のようなjsonデータを読み込み、実行すると15を返すような
インタプリタを作ると以下のようになります。

function eval(s){
	if (s instanceof Array) {
		switch(s[0]){
		case "add": return eval(s[1]) + eval(s[2]);
		case "mul": return eval(s[1]) * eval(s[2]);
		}
	}
	return s;
}

ここで、このプログラムを継続渡しスタイル(CPS)に書き換えて
継続を実装してみました。

function eval(s,k){
	if (k == null) k = function (u){return u}
	if (s instanceof Array) {
		switch(s[0]) {
		case "add": return eval(s[1],function(u){return eval(s[2],function(v){return k(u+v)})})
		case "mul": return eval(s[1],function(u){return eval(s[2],function(v){return k(u*v)})})
		case "cont": return ["#cont",s[1], k]
		case "#cont": return eval(s[1],s[2])
		}
	}
	return k(s);
}

12行です。


処理の続き（継続）は全て関数に突っ込んで次の関数に渡しています。
contがあった場合はそれを#contと言う名前で配列に入れて返しています。
#contの場合は配列の中身を実行するだけです。

Array.prototype.toString = function(){return"["+this.join(",")+"]"}
function log(x){document.write(x+"<br>")}
log(c = eval(["add",["cont",["mul",4,5]],10]))
log(d = eval(["add",["cont",["mul",4,2]],5]))
log(eval(c))
log(eval(d))
log(eval(c))
log(eval(d))

のようにして実行すると、

[#cont,[mul,4,5],function(u){return eval(s[2],function(v){return k(u+v)})}]
[#cont,[mul,4,2],function(u){return eval(s[2],function(v){return k(u+v)})}]
30
13
30
13

と出ます。最初の２つで継続を作成して、後の４行で交互に継続を呼び出しています。