スクリプト言語でのクロージャの実装方法

スクリプト言語を作る際のクロージャの実装方法、特に変数バインディングにヒープじゃなくてスタックを使うバーチャルマシンでの実装方法について調べた。

参考にしたのは Three Implementation Models for Scheme の４章スタックベースモデルの4.4節ディスプレイクロージャ。

論文の３章ではヒープベースモデルという、スタティックスコープのチェーンをヒープ上に持つ方式の説明があって、その方式だとクロージャが生成されたスコープを抜けてもそのクロージャが参照する環境がヒープ上にあるので特に問題なく変数バインディングを保持できる。 しかしこの方式だと関数呼び出しごとにヒープ確保が必要になってしまい実行速度が犠牲になってしまう。 そこで４章でスタックベースモデルという、スタティックチェーン（関数への引数）などをスタックに配置する実装が説明される。

しかし関数への引数をスタック上に持つようにすると、クロージャを生成したスコープを抜けた時点でコールフレームが削除されてしまうので変数バインディングが破壊されてしまう問題がある。

4.4節での解決方法は、クロージャを生成するときに、内部で使われる自由変数を調べて、そのコピーをヒープ上に確保してクロージャに保持する、というもの。 代入がなければ値は変更されないのでこの方法で解決できる（代入がある場合の変更は4.5節でなされる）。

論文ではSchemeを使っていてLisp系だとパースはすでに完了しているので、コンパイルの段階で内部で使われる自由変数を走査して調べているが、Lisp系じゃない自前のスクリプト言語を作るときにはどうせパースを行う必要があるので、そのときに変数の参照を調べることにする。

例えば次のようなコードがあった場合、

function(f) {  // (A) 束縛:f
  function(x) {  // (B) 束縛:x
    function(y) {  // (C) 束縛:y
      f(y)
    }  // 参照:f,y => 自由:f
  }  // 参照:f => 自由:f
}  // 参照:f => 自由:なし

パースは外側のfunction→内側のfunctionと進むが、パースが進んで最も内部のfunction (C)にきたとする。 functionの本体をパースして、参照された変数すべてをその関数が参照しているということを記録していく(f, y)。 その中で自分のパラメータ(y)じゃないものを(C)のlambda式の自由変数とする(f)。

functionのパースを抜けるときに、自由変数は外側のfunctionから参照する、ということを伝えるため、上のブロックに参照を伝搬させる。 ここでは関数(B)にfへの参照を追加する。 そして同様に(B)のfunctionのパースを抜けるときに、参照がfで束縛変数がxなので自由変数がfとなる。

一番外側のfunctionの(A)も同様に行われ、ここでfは束縛されているため、自由変数はなしとなる。

コード生成時には、関数で使われる自由変数をコピーするコードを生成する。 実際にはクロージャの自由変数となる値をスタックに積んでいき、クロージャの生成時にそれらをヒープから確保したバッファにコピーする。 (A)は自由変数がないので特に何もなし、(B)はローカル変数fをコピーしてクロージャを生成する。 (C)はクロージャ(B)に閉じ込められたfをさらにコピーしてクロージャが生成される。

生成されるバーチャルコードは次のようになる：

# クロージャ(A)の生成
close 0        # 自由変数なしでクロージャ(A)を生成
# クロージャ(A)の本体コード
refer-local 0  # fを参照
argument       # スタックに積む
close 1        # 自由変数1つでクロージャ(B)を生成
# クロージャ(B)の本体コード
refer-free 1   # (B)に保持された自由変数fを参照
argument       # スタックに積む
close 1        # 自由変数1つ
# クロージャ(C)の本体コード
...

VMの実行時には現在実行中のクロージャを保持しておき、refer-freeでクロージャから値を取り出すようにする。 関数呼び出し時にはリターンアドレス、フレームポインタとともにクロージャもスタックに積み、リターン時に復帰させるようにする。