Loxでのクロージャの実装手法
VM版でのクロージャは25章 - Closureで解説されている。
まずVM版がどうやってローカル変数を扱っているかというと、VMに値のスタックを持っていて、値を積んだり取り出したりして行っている。 クロージャを実装しない段階ではスコープの開始・終了や関数呼び出しによるローカル変数の生存期間と、スタック上に配置された値の生存期間が一致している。 スタックを使用することで、新しいローカル変数の追加や関数呼び出し時にも特にヒープ確保を発生させずに行うことができて効率がよい。
しかしクロージャでローカル変数をキャプチャできると話が変わってくる。 スコープを抜けた後にもローカル変数にアクセスできる可能性が出てくるので、その変数はスタック上に置いておくことができなくて、ヒープに逃がす必要がある。
すべてのローカル変数をヒープに確保すると遅くなってしまうので、キャプチャされるものだけにしたい。 しかしLoxは1パスコンパイラで構文木を生成せずに直接バイトコードを出力するので、変数が後々キャプチャされるかどうかを定義時点で知ることができない。 そこでUpvalueという方法を使う。
Upvalueによるキャプチャ
ネストした関数をコンパイルする際に、外側の関数で定義されたローカル変数を参照した場合、その関数が使用とする自由変数として登録する。
実行時にクロージャを生成する際に、関数の自由変数ごとにUpvalueをヒープ上に生成する。
Upvalueには対象の自由変数が格納されているスタック位置へのポインタを保持する（クロージャ生成時には自由変数のスコープは生きているので、スタック上に存在する）。
キャプチャされた変数もその変数が属している関数スコープ内では普通のローカル変数と同様にアクセスされる。
キャプチャしたクロージャ内からアクセスされるときにはUpvalueを通して間接的に行われる。
キャプチャされた変数がスコープから抜けてスタックから取り除かれる際には、スタック上に配置されていた値をUpvalue内部にコピーして、ポインタがそれを指すように変更する。
これによって値がスタックからヒープに移され、スコープを抜けてスタックが解放された後にもアクセスすることができるようになる。
ネストされた関数でのキャプチャ
コンパイル時に関数が使用する自由変数をどこからキャプチャするか、という情報を調べる。 一つ外側の関数で定義されたローカル変数の場合、内側の関数が使用する自由変数として登録する。
もっと外側の関数のローカル変数の場合には、再帰的に登録する。 なので直接参照していなくても内部の関数で使用されている自由変数は同様に登録される。
Upvalueを管理する
キャプチャされた変数に対する代入が他の箇所でも反映されるようにするために、個々の変数に対するUpvalueは1つである必要がある。
これを管理するために、VMスタック上のローカル変数に対するUpvalueをリンクリストで保持する。
リンクリストは降順に並ぶようにしておく。
クロージャ生成時にUpvalueを生成するかどうかを、リンクリストをたどって対象のスロットに対するUpvalueがあるかどうか調べる。
あればそれをそのまま使用する。
なければ新たに生成する。
リンクリストをたどるのは対象のスロットのポインタまでで済むので、それほど深くならない、はず。
スコープから抜けてUpvalueに値を逃がすには、リンクリストをたどって解放しようとするスロットに対するUpvalueがあったら、VMスタックからUpvalueに値をコピーしてやる。
雑感
Upvalueを使った自由変数のキャプチャによって、1パスコンパイラでありながらレキシカルスコープを達成できている。
しかも実装が巧妙に作られている。
参考
UpvalueはLuaによって実装されたとのこと。 LuaのVMはレジスタマシンとのことだけど、Upvalueの方法は非常に参考になる：
- pdf: The Implementation of Lua 5.0
- pdf: Closures in Lua