「末尾最適化」を正しく理解する

コンパイラ

以下の記事でPythonやRubyの末尾再帰関数をループに変換する手法が「末尾再帰最適化」や「末尾呼び出し最適化」として紹介されているのですが、これらの用語を使うのは間違いです。
紹介されている手法(動的束縛を利用して制御フローを変形する手法)自体は大変面白いですね。
Pythonで末尾再帰最適化をする。
Rubyで末尾再帰最適化をする。

参考文献として以下を挙げておきます。
William D. Clinger "Proper Tail Recursion and Space Efficiency"
ちゃんと読み直していないので、以下の説明に間違いがあるかも知れません。その場合はご指摘お願いします。

まず「末尾呼び出し(Tail Call)」は関数の一番最後の式(末尾式)であって、関数呼び出しであるものを指します。

void foo() {
    bar();
    baz(); /* 末尾呼び出し */
}

末尾呼び出しは再帰呼び出しでなくても良いので、本来は末尾再帰より広い概念です。しかし、末尾最適化が必要になるのはほとんどの場合再帰関数なので、[訂正]関数呼び出しが再帰するか否かを判断する事は困難である(コールグラフの構築が難しい)から、末尾呼び出しを無条件で末尾再帰と呼ぶこともあるようです。

関数を呼び出す際には色々な用途でメモリ確保が発生します。

  • 戻り先アドレスをどこかに積む
  • 関数引数を確保する
  • 呼び出し元のローカル変数を退避する
  • 呼び出された関数のローカル変数を確保する
  • クロージャの自由変数を確保する

等です。
末尾呼び出しの場合はこれらを除去できるわけですが、どれほど効率的な実装になっているかよっていくつかのクラスに分類されます。

Improper Tail RecursionとProper Tail Recursion

末尾呼び出し時に戻り先の継続を渡すような実装をImproper(誤った) Tail Recursion、生成しない実装をProper(正しい) Tail Recursionと言います。「戻り先の継続を生成して渡す」というのは、大抵の実装では現在の環境(ローカル変数等)を保存し、戻り先アドレスをスタックに積み、関数をコールしてからリターンするようなものを指します。
Improper Tail Recursionでは、環境の確保などをいくら工夫して0にしても戻りアドレスは除去できないので必ずメモリが増加し、いつかメモリが足りなくなります。

一方のProper Tail Recursionは現在の環境を破棄し、関数コールの代わりにただのジャンプを行うような実装を指します。
この場合、一切のメモリの増加を防ぐことができます。

さらに細かいクラス分けについておおざっぱに説明します。

Improper Tail Recursionのクラス

  • S-Stack
    • 環境の一部をスタック上に直接確保する実装。
  • S-GC
    • 環境をヒープに確保し、ポインタ一つを保存する実装。この場合関数コールから戻らずとも、死んだデータはGCにより解放できるので、S-Stackよりメモリ効率が良いクラスです。

Proper Tail Recursionのクラス

  • S-Tail
    • 上で書いたProper Tail Recursionの最低限の条件を満たした実装。
  • S-Evlis
    • S-Tailの条件に加え末尾呼び出しをまたいだ環境の退避を除去した実装。ヒープに退避された環境は二度とアクセスされないので、除去できます。
  • S-Free
    • S-Tailの条件に加えクロージャ変換を用いる実装。環境の退避が最小限になります。
  • S-SFS (Safe for Space)
    • S-Freeに加え、条件分岐などでも変数の生存解析を使う方法。環境の退避がさらに減ります。

さて、一般的には末尾呼び出しをProper Tail Recursionで実装をすることを末尾最適化をすると言います。
上のPythonやRubyの例は関数コールを除去しているわけではないので末尾最適化には該当しません。関数の呼び出し関係を書き換える別種の変換になります。
実際、この方法でも末尾再帰関数であればスタックの増加を防げているわけですが、f(),g(),h(),..と異なる関数を次々と末尾呼び出しするような場合にはスタックの増加を抑える事はできないなどの点で末尾最適化とは異なっています。