トランポリン
gotoが使えない言語での末尾呼出し最適化はどうするのかと思っていたらこれを発見。
ベース言語が末尾呼出し最適化を保証してくれない場合によく使う手としてトランポリンがあります。
各関数を、結果を返すのではなく、その関数の継続手続きを返すように書いておきます。そして、sub run { my ($proc) = @_; for (;;) { $proc = $proc->(); } }みたいにひたすら返って来た継続を呼び出しつづけるドライバを書いて駆動します。
http://d.hatena.ne.jp/tociyuki/20061116/1163674424
これだとベース言語のスタックを消費しません。
なるほど、呼び出し先からさらに関数を呼んでしまうとスタックが残ったままになってしまうので、
いったんrunに戻ってきてもらうことによってスタックから取り除いてから次の呼び出しをするわけか。
function run(proc){ while(typeof(proc)=='function') proc=proc(); } function fact(n,cont){ if(n==0) return(function(){cont(1);}); else return(function(){return fact(n-1,function(r){cont(n*r);});}); } run(fact(4,alert));
というわけで、JavaScriptで書いてみた。
factが使う継続(cont/1)とrunが使う継続(proc/0)は別物という理解でいいのかな?