JavaScriptでTrampolined Style
Trampolined Style (Steven E. Ganz et al. International Conference on Functional Programming, 1999)をざっと読んだ。ICFP…。
Trampolined Style（カタカナだとトランポリンスタイルでいいのかな？ああ、なんだか形態素解析が難しそう…）というのは、関数の書く際のスタイルの一種だ。通常、関数を呼び出す時にはなんらかの値が返ってくる事を我々は期待する（事が多い）が、Trampolined Styleで書かれた関数（以下、めんどくさいのでTrampolined Functionとでも書こう）は、最後まで計算を行わず、ちょっと計算を進めて、残りの計算を行うための関数を返す。その関数を実行すると、またその続きを計算するための関数が返ってきて…という事が繰り返され、最後に計算が完了し、値が返ってくる。
もちろん、関数だけを返してしまうと、戻したい値が関数である場合と区別が付けられないので、なんらかの手段で区別が付けられるようにする必要がある。この論文ではレコード型を使っているが、ここら辺は使用しているプログラミング言語にあわせて、適当な仕組みを使えばいいだろう。
Trampolined Styleで関数を書くことにより得られる利点には以下のようなものがある
- 末尾再帰の最適化が行われない処理系であっても、末尾再帰関数がスタックオーバーフローにならない
- 複数のTrampolined Functionを順繰りに走らせる事によって、並行に実行を行っているようにみせかけることができる（並列じゃなくて並行だろ、というコメントをいただいて書き直しました。）
他にも論文の後半にはステップ実行やらブレークポイントやらが実装できるよーと言う話がでてくるんだけど、まぁそりゃーできるよねー、という程度で、あんまり真剣に読んでない。
プログラムをTranpolined Styleで書き直すことができる条件としては、Tail Formであるようなプログラムは全てTrampolined Styleにできるので、CPSでプログラムを書くことで、Trampolined Styleへと変換することができる、と書いてある。Tail Formというのは非プリミティブな関数がTail Positionにしか存在しないプログラムだと書いてある。Tail Positionの文は長かったのできちんと日本語で意味が取れてないけど、たぶん普通に末尾位置の事だろう。
まぁ、CPSで書かれていれば、Trampolined Styleへと変換することが簡単であることは、容易に想像がつく。
というような事を踏まえた上で、JavaScriptでTrampolined Styleな階乗を求める関数を書いてみる。論文では、Trampolined Styleで関数を書くための補助関数として、returnとbounceという2つを定義している。returnは値を返すための関数で、bounceは残りの計算を行う関数を返す関数である。returnはJavaScriptでは予約語なはずなので、ここではbackという関数名にしよう。まずは、階乗を計算するfactを定義する。
function fact (n) {
return fact_tramp(n, 1);
}
function fact_tramp (n, acc)
{
var rest_func =
function () {
return fact_tramp(n-1, n * acc);
};
if (n == 1) {
return back(acc);
} else {
return bounce(rest_func);
}
} 階乗計算の本体はfact_trampの方になっている。nが1ならばaccを返し、そうでない場合は残りの計算を進めるための関数を返す。rest_funcが残りの計算を進めるための関数である。名前を付けなくてもいいんだけど、bounceの引数に直接関数を書いたらひどく読みにくかったので、別の場所に書くためにここでは名前を付けた。
で、次にbackとbounceを実装してみよう。JavaScriptには構造体は無いので、適当にオブジェクトを作って返すことにする。
function back (val) {
done = new Object;
done.done = true;
done.value = val;
return done;
}
function bounce (cont) {
doing = new Object;
doing.done = false;
doing.func = cont;
return doing;
}これはコード見たまんまなので、あんま説明することはなさそうだ。で、最後まで値を求める関数pogo_stickを書く。余談だが、pogo-stickというのは日本でいうホッピングだそうだ。ホッピング、懐かしいな…。
function pogo_stick (calc) {
if (calc.done) {
return calc.value;
} else {
return pogo_stick(calc.func());
}
}calc.doneがtrue、つまり実行が終わったら値を返し、そうでない場合は返ってきた関数を一回だけ実行し、それを引数として再帰呼び出しを行う。で、これを使って実際に階乗を計算するのは以下のような感じになる。
print(pogo-stick(fact(5)));
なんか、それぞれを取り出すと、あんま難しいことはなかった。これだけではあんまり面白くないので、次に2つの関数を交互に実行するseesawという関数を実装してみる。
function seesaw (calc1, calc2) {
if (calc1.done) {
return calc1.value;
} else {
return seesaw(calc2, calc1.func());
}
}ポイントはseesawを再帰呼び出ししている部分で、ここでcalc1.func()が一回呼ばれることで、計算が進む。しかし、Trampolined Styleで書かれた関数が今のところfact一個しかないので、実行してもあんまり面白くない。まぁ、以下のような感じで実行できる。
print(seesaw(fact(5), fact(3)));
seesawは一個計算が終了したらその時点で値を返すので、fact(3)の結果が返ってくることになる。fact(5)の代わりに永遠に計算が終わらないような関数を食わせても、seesawはちゃんと値を返す。ただし、関数がTrampolined Styleで書かれていれば、という条件がつくけれど。ここまでくれば、3つ以上の関数を順繰りに実行する関数trampolineを書く事は難しくないが、階乗ばっかり計算させても全然面白くないので、今日はここら辺にしておく。明日元気があれば、もうちょっと別なTrampolined Styleの関数を書いて、応用例を示してみたい。
