スタックベースVMのスクリプト言語での末尾呼び出しの実装方法

2013-04-24
自由変数への代入の続きで、末尾呼び出しの実装方法。今回も[Three implementation models for Scheme](http://www.cs.indiana.edu/~dyb/papers/3imp.pdf)の、4.6節を参考にする。

VMをスタックベースにした場合、末尾呼び出しのときにその呼び出された関数への変数バインディングをスタックから取り除かなければいけないが、参照が生き残る可能性があるので簡単にはいかない?ちょっと英文がよくわからなかった。結局のところ、末尾呼び出しの場合は新しいコールフレームの作成をせずに、呼び出す関数への引数をスタックに積むコードを通常の関数呼び出しと同じように出力して、実際にapply(関数の命令の先頭にジャンプ)する前に自分自身に渡された引数を取り除いてやればいい。この論文のVMでは、戻り先の命令やフレームポインタは関数への引数より前に積まれているので、簡単にシフトできる。

どの式が末尾呼び出しかという判定は、論文ではコンパイルの関数が次に実行すべき命令を常に持っていて、それがreturnだったら、というように判定している。自作のスクリプト言語で構文木を構築した場合はどうしたらいいかとちょっと悩んだが、なんのことはない、再帰で伝搬していけばいいだけだった。

関数定義の場合は、関数本体の最後の式に「末尾だよ」、という設定を行う。またはreturn式だったら戻す値に末尾設定を行う。

末尾だと指定されたノードは、自分の種類によってそれをどう伝搬させるかを定義する。ノードが関数呼び出しだったら、めでたくそいつは末尾呼び出しと判定される。if式だったらthenノードとelseノードの両方に伝搬させる。他のノードの場合は伝搬させない。例えば二項演算とかであればその左右のノードは末尾とはならないので、伝搬を打ち切る。