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

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

概要

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

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

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

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

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

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

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

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

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

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

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

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