Kashiwa Scheme(のスタック)にごみ集めが付きました
先日述べたとおり、Kashiwa SchemeはSchemeからCへのトランスレータであり、
Schemeの(CPS変換された)手続きはCの関数に変換されます。
しかし、そのCの関数ではreturnにたどり着くことはなく、スタックは伸び続けます。
(詳しくは元ネタのこの論文を読んでください)
とまあ、本当にスタックが伸び続けたらいつかは死んでしまう訳で、
実際のところはスタックが一定より伸びた所で手を打ちます。
具体的には、スタック上にある『必要なもの』だけをヒープにコピーして、
longjmpを呼び出してスタックを巻き戻してから処理を再開します。
変換されたCの関数というのは以下のような形をしています
static void fun112_(env_t* penv113_, lobject g108_) {
cont_t clos125_;
env_t* cenv114_;
check_stack(fun112_, penv113_, 1, g108_);
... (略) ...
}
見ての通り、先頭でcheck_stackという関数を呼んでいます。
この関数は、スタックがどれほど伸びたかを確認します。
そして、スタックが閾値より伸びていた場合、
最後に呼ばれた関数(この場合fun112_)とその引数の値をヒープに保存して、
先ほど保存した引数からたどれるオブジェクトをすべてヒープにコピーします。
コピーが終了すると、longjmpでスタックを巻き戻し、
ヒープに保存した情報(最後に呼ばれた関数と引数)を使って処理を再開します。
「関数はreturnにたどり着かないため、呼び出し元に戻ることはない」
ということは
「最後に呼ばれた関数とその引数さえ覚えておけば処理を再開できる」
というわけです。
ただし、スタックに作ったSchemeのオブジェクトは、
『必要があれば』ヒープに移動する必要があります。
逆に言えば不要なものは捨ててしまうわけです。
この「オブジェクトのスタックからヒープへのコピー」という処理は、
スタックを”from space”、ヒープを”to space”としたcopying GCとみなせます。
ここでCheneyのアルゴリズムを用いると、
これ以上スタックを消費することもなく、安心してごみ集めを行えるわけです。
今回書いたのはこのスタックにおけるごみ集めだけで、
ヒープにおけるごみ集めはまだ書いてません。
まあ、こちらはただのごみ集めになるのであまり面白みもなさそうです。
面白いのが、スタックからヒープへのコピーという処理は、
スタックをyoung領域、ヒープをold領域とした世代別GCとも見なせる点です。
……と、ここまで書いた時点で、ヒープからスタックへの参照を、
remember setに入れて覚えておく必要がありそうな気がしてきたけど、
そんな処理は書いてないぞ。なんてこった。ライトバリアとか書きたくないぞ。