スクリプト言語で関数の自己再帰の最適化

Three implementation models for Schemeの、4.7節の改善の可能性の、4.7.3項の末尾再帰最適化を考えてみた。

これは、Schemeだとループ構文がないので関数内で自分自身への末尾再帰を使うことになるけど、この関数が他で使われなければ再帰呼び出しをジャンプにすることができる、というもの（さらに、自分自身の呼び出しで引数の数のチェックとかをコンパイル次に済ませることができる）（あとrecurのように直接呼び出される場合にはクロージャの生成もしないようにできるとのことだけど、ここでは無視）。

まあSchemeじゃない、普通のスクリプト言語の場合ループ構文あるし、あまりそういうスタイルで書かないから意味ないかな？と思ったんだけど、この最適化って末尾じゃなくてもできるね。そうした場合、自己再帰でフィボナッチ関数とか階乗とかがあてはまる。

例えば

function fib(n) {
  if (n < 2) {
    return n;
  } else {
    return fib(n - 1) + fib(n - 2);  // 自己再帰
  }
}

とかいったばあい、fib関数の本体をコンパイル時に、自分自身への再帰があった場合には戻り先アドレスなどをスタックに積んでおいて、自分自身の関数本体のVMコードにジャンプする命令を出力するようにする。実装方法としては、関数のコンパイルに入るときにスコープを作成して、そのスコープに関数の名前をつけておき、関数呼び出しが現在のスコープ名だった場合には自己再帰と判断できる。その場合、グローバル変数のルックアップが省けるので、ちょっとお得、かもしれない。

グローバル変数が書き換えられる場合でも、大抵の場合には問題ない。例えば後から

fib = function(n) { ... };

などと上書きしてしまった場合には、古いコードへのアクセスがなくなるので問題ない。問題が起きるのは別の変数に代入した場合、

old_fib = fib;
fib = function(n) { ... };

この場合、old_fibを呼び出した場合に、更新されたfibの呼び出しが行われず、old_fibが使われることになる。まあそれでも、そういうもんだと決めてしまえば、動作的にはそれほど問題なさそう。

ので、ベンチマーク的には効果あるかも、と思って実装してみた。元の論文でのVM形式だとそういう変更は結構難しい。それはVMコードがリスト形式で、コンパイル時の処理がリスト生成によって行われているので、後に実行されるものから先にコンパイルされてしまい、前に戻るためのコードがまだ生成されてないから。例えば大雑把にはlambda式のコンパイルは

(list 'close  ;; 'クロージャ生成 VMオペコード
      (compile body))  ;; [1] クロージャ本体のコンパイル

という具合になっていて、自己再帰をジャンプにしたいときには[1]で作られるリストに続くようなリストを作りたいわけだけど、本体のコンパイル時にはまだそのリストは作られてないので、こういうふうに綺麗には書けないことになる。いったんダミーのリストを作っておいて、あとで破壊的操作でリストに代入することになり、ソースは汚くなる。

VMコードがリストじゃなくて配列形式の場合にはそこまで面倒ではなくて、単に関数のコード生成時にラベルを作成してスコープに設定しておき、本体のコンパイルで事故再帰があった場合にはそれを参照すればいい、だけだった。また、末尾自己再帰でジャンプになる形じゃなくて、自己呼び出しの場合には、VMが現在実行中のクロージャを保持しているので、ラベルも使わずに現在実行中のクロージャの本体に飛べばよいだけだった。

気になる速度は、それほど速くならなかった。よく考えればグローバル変数のルックアップといってもハッシュであればO(1)なので、それほど重くないのかもしれん。とほほ。