3impを参考に作っている自作のLispコンパイラで効率のいいループの実現方法を考えてたんだけど、どうもインチキ感が拭えない。と思っていたところ、4.7節「できそうな改善」の4.7.3項「末尾再帰最適化」に、方法は書いてないけど案としては書いてあった(ここの「末尾再帰最適化」というのは末尾呼び出し最適化でスタックを消費しない、というのとは違くて、再帰というところがポイントになっている。)

それによれば、最適化しない場合の、関数を探して引数の数をチェックして…、という処理を省いて直接のジャンプにできる、とのこと。さらにいえばその関数が(named letのように)直接呼び出される場合、クロージャの生成も避ける事ができ、一般的な言語のループ構造に適用される最適化も行うことができる、とのこと。

これをどうやったら実現できるのか考えてたんだけど、なんとなく実装方法がわかった。問題は 1.末尾再帰をジャンプにする、 2.クロージャを作らない(もしくはスタック上に作る)、 3.ボックス化しない、という3つに分けられる。

1の末尾再帰をジャンプに置き換えるために必要な条件として、そのループ用の関数を保持する変数への代入が1回しかないことが挙げられる。1回しか代入がなくてしかもラムダ式だったらその後内容は変化しないので、コンパイル時にジャンプの飛び先を決めることができる。

2のクロージャを作らないために必要な条件としては、そのループ用の関数が呼び出しにしか使われていないこと。その関数が他の関数への引数として使われてたり、戻り値として返されたりしていたら、他のところに保持されたりしてスコープを超えて生き延びる可能性があるので、クロージャを作る必要がある。

3のボックス化は、Schemeの変数のスコープのルール上、ループ用の関数のためのローカル変数を用意して、それに対して代入を行うことで、その関数内から自分自身を見れるようにしている。で代入があると継続で捕獲される可能性があるのでボックス化されてしまう、というわけ。1と2の条件を両方満たした場合には、ボックス化を避ける事ができる。

問題はどうやってこれらの条件をチェックするかということ。3impで示されるコンパイラは、いわば1パスコンパイラといったところで、S式を直接解析してコードを出力していくようになっている。S式なのでreadした段階で構文木のようなツリー構造は得られているものの、その他の情報はまったくない。自由変数の参照や変数への代入を調べるために、その都度内側のブロックをたどって調べたり、外側から引数として与えてもらったりしている。

この方式でも上記の条件のチェックはできないことはないのかもしれないけど、S式をいちいちたどって調べるのが大変なことと、スコープ全体の情報を得るのが難しいこと、ジャンプの飛び先といったコンパイル後の情報を得るのが難しいので、大変なことが予想される。

そこでいったんS式から内部情報を持つツリー構造に変換して、その後コンパイルしてコード生成をするという、2パス方式に変更してはどうかと思いいたった。そうすれば構文解析も1回で済んで何度も構文をたどらずに済むし、中間情報も利用できるようになる。

というわけで、ここで3imp型のコンパイラの構造から決別することにした。これは僕にとってとても大きなことで、ちょっと今まで想定してなかったので驚いている。でもそういう方法もあるよということで。