Trampolined Style
再帰をloopに変換することで、Stack Over Flowを防ぐ1つの手段
runtimeで末尾再帰の最適化をemulateしている
概要
言語仕様として末尾再帰の最適化がない言語では、再帰の数が増えすぎるとStack Over Flowを起こす
そこで、Trampoline関数なるものを利用し、一工夫加えることでloopに変換させることができる
例
jsconst countDown = (num) => {
console.log(num);
if (num === 1) return 1;
return countDown(num - 1);
};
countDown(30000);wandboxで実行したら17500あたりまでログを吐いた後にMaximum call stack size exceededが起きた
Trampoline関数を用意して微修正する
jsconst countDown = (num) => {
console.log(num);
if (num === 1) return 1;
return () => countDown(num - 1); // 関数を返すように修正
}
// trampoline function
const trampoline = fn => (...args) => {
let result = fn(...args)
while (typeof result === 'function') {
result = result()
}
return result
}
const tramped = trampoline(countDown);
console.log(tramped(30000)); //耐える countDown は、終了条件では値を返す
それ以外は、再帰しつつ「関数」を返す
trampoline は関数を返す「
fn をloop構造に変換した関数」を返すここでは、その関数を
tramped と呼ぼう tramped 自体は1回しか呼ばれていない再帰の回数だけ
while が回っている再帰の終了条件となる結果が、最後の
result に入ってそれが返ってくる全く同じ挙動をするのに、スタックを全く積まないのでoverflowしない
速度的には、
trampoline を使わずに countDown を手動でloopに書き直したほうが速いそれはそう
countDown は、再帰の回数だけ関数呼び出しすることになることには変わりないJSはこの説明に良い例だが、実際JSで再帰書くことはほぼないだろう
概念の理解の助けになる
末尾再帰の最適化がされない言語の例
e.g. Python, C#, JavaScript
PureScriptは基本は最適化されるが条件が重なるとされない場合がある
例えば上記のような
countDown を実装し、 log を仕込むとstack over flowするこの条件の真意は理解できてない #??
TrampolineモナドやFreeモナドなどを使えば回避できる
ちなみにJSの場合は、
どの辺が「トランポリン」なのか？
この解答のvisualizeがわかりやすい
最適化なしの再帰呼び出しの場合、
最後までstackが積み上げられたあと、popされていくので、
時間を横軸、stackを縦軸に絵を描くと、ピラミッド型になる
一方で、loopで関数呼び出しするようにすれば、
loopのたびごとに、1push、1popが行われる
同様に絵を描くと、stack上でぴょんぴょんしてる感じになる
この感じが「トランポリン」なのらしい
関連
1999
Haskellではtorampolineは不要？
hsはコンパイラが最適化してくれるから、というのはわかるが、それだけだとpursの説明がつかない
遅延評価かどうかも関係してくるんだろうか
JSでのstack over flowの他の回避法
長い
generatorを使う
参考
Low-levelとHigh-levelで指すものが異なるらしい
このノートに書いたものは後者にあたる