プログラム中の末尾再帰に関するメモ

「萌香」のコードを整理しようと思ってコードを読んだんですが、「末尾再起の最適化に関するメモ」というコメントがなにを書いてるんだかさっぱりわからない。ポルナレフAAを貼りたくなるぐらい何がなんだかわからない。なんか悪い薬でもやってたんだろうか。

きっと末尾再帰っぽいことがようやくできて舞い上がっていたんだろう。黒歴史として早く葬りたい。

解読してみる。

--- begin 本文 ---
末尾再帰の最適化に関するメモ

本プログラムには変数のフレームのスタックと継続のスタックが存在します。
Lexical scopeのクロージャなので、クロージャの再帰呼出しではフレームの
スタックが積まれることはありません。
(その呼出しへの参照が残っていた場合、そこに保持されている。)

クロージャの呼出し時に
フレームの退避 --> クロージャの実行 --> フレームの復帰
と行うと、クロージャの実行時に末尾再帰呼出しがあった場合
フレームの退避 --> クロージャの実行 -->
フレームの退避 --> クロージャの実行 --> フレームの復帰 --> フレームの復帰
となります。
ここで、フレームの退避はlexical scopeクロージャの場合フレームの
新規作製であり、作製されたフレームはクロージャの実行の終了とともに
GCによって回収されるようになります。

結局クロージャの実行時にフレームの復帰の継続がどんどん増えていくことに
なります。
フレームの復帰は最後のものだけ行えばよく、
末尾再帰の場合、フレームの復帰の継続を作製する場合、次の継続に
フレームの復帰があった場合継続の作製は行う必要はありません。

以上のことから、フレーム復帰の継続の作製を抑制すれば末尾再帰の
最適化になることになります。
--- end 本文 ---

--- 本プログラムには変数のフレームのスタックと継続のスタックが存在します。
これは単なる事実。ここでいう継続のスタックで保持されているものには次の関数呼び出しで使われる引数の保持先(return valueの戻し先)等様々なものがある。(わかりにくくてすみません。あとで整理する。)　なので厳密な「継続のスタック」ではないかも知れない。

--- Lexical scopeのクロージャなので、クロージャの再帰呼出しではフレームのスタックが積まれることはありません。
「クロージャの再帰呼び出し」ではなく「クロージャの呼び出し」。ちなみに現在の実装ではフレームを積んでおきながら、呼び出しと同時にクロージャ定義時のフレームの参照に変更している。あとでなおす。

--- (その呼出しへの参照が残っていた場合、そこに保持されている。)
「その」と「そこ」が何を指しているかわからない。

--- クロージャの呼出し時にフレームの退避 --> クロージャの実行 --> フレームの復帰と行うと、クロージャの実行時に末尾再帰呼出しがあった場合フレームの退避 --> クロージャの実行 -->フレームの退避 --> クロージャの実行 --> フレームの復帰 --> フレームの復帰となります。
ここで、フレームの退避はlexical scopeクロージャの場合フレームの新規作製であり、作製されたフレームはクロージャの実行の終了とともにGCによって回収されるようになります。
ここでいう「フレームの退避」はフレームチェインに新しいフレームを作成すること。(新しいフレームは既存のフレームチェインにつなげられる) なんで「退避」と言う言葉を使ったのかわからない。 今考えると「フレームの退避」「フレームの復帰」は必要ないっぽい。(現在見えている変数フレームは継続スタックに保持されているじゃん) あとでなおす。

--- 結局クロージャの実行時にフレームの復帰の継続がどんどん増えていくことになります。フレームの復帰は最後のものだけ行えばよく、末尾再帰の場合、フレームの復帰の継続を作製する場合、次の継続にフレームの復帰があった場合継続の作製は行う必要はありません。

--- 以上のことから、フレーム復帰の継続の作製を抑制すれば末尾再帰の最適化になることになります。
現在の実装ではフレームの復帰が連続する場合その継続の作成を抑制しているがフレームの復帰は必要ないっぽい。あとでなおす。