実装Note - 末尾呼び出しの最適化

minilangは, 末尾呼び出しをループに展開します。

概要

例えば、呼び出し元⇒メソッド1⇒メソッド2というメソッド呼び出しで、メソッド1の最後の文でメソッド2を呼び出しているとします。

通常は、メソッド2の実行が完了した後、一瞬、メソッド1に戻ってきて、それから呼び出し元へ戻ります。メソッド1のローカル変数の内容は、メソッド1から呼び出し元に戻るまで維持されます。

このとき、メソッド1からメソッド2を「呼び出す」(call) のではなく、メソッド2の先頭へジャンプしても、実行には影響はありません。

minilangでは、メソッドの末尾で別のメソッドを呼び出す場合に、呼び出す側(この例ではメソッド1)の環境(ローカル変数など)を解放してからその別のメソッドを呼び出すようにします。

再帰してもメモリを消費しないようになるので、再帰の形でループを書いてもいいようになります。解決したい問題によっては、再帰で書いたほうがプログラムが簡潔になることがあるので、有用です。

もっと一般化した考え方は、次が分かりやすいと思います。ただし、継続だと、メモリを消費しないという目標と両立しない。

スタックトレース

末尾呼び出しの最適化をおこなうと、その場所の部分だけ、スタックトレースが短くなります。

上の例で、メソッド2の中で例外が発生すると、呼び出し元⇒メソッド2、のようなスタックトレースになります。

メモリを消費しないために最適化するので、これはしょうがない。

return/break文

Rubyのreturn/break文は、ラムダ式のなかに書かれると、メソッド呼び出しをいくつも突き抜けてレキシカルな外側まで脱出することがあります。

returnの引数のメソッド呼び出しのなかでもreturn/break文が書かれることがあるので、先に評価する必要があります。最適化が難しい。

rescue ... ensure

begin ~ rescue ~ ensure では、末尾呼び出しの最適化がある場合とない場合とで実行順序を変えないためには、常に、メソッド呼び出しを(最適化せずに)評価する必要があります。