Let's start Scheme

2011-09-24

call/cc実装論文

Chez Schemeに使われている(らしい)call/ccの実装論文を読んでいるのだが、これで動く理由が分からない。
正確にはこれをSagittariusに適用できるか分からないか。

これが正しい理解かは微妙だが、大雑把に言えば継続が捕捉された時点のスタックポインタ以前のスタックを凍結、スタックフレームに以前のスタックポインタを足す。っで、捕捉された継続が呼び出されたら凍結されたスタックを現在のスタックに置き換える。
確かにこの方法なら作成時にスタックのコピーが無いので作成はほぼノーコスト。でもこれってcall/ccから脱出するとき困らんかな?
call/ccから脱出するときにどうしてもスタックのアンダーフローが検出されるので捕捉された継続を戻す必要がでる気がする。それともなんらか別の方法でその辺は何とかしてるのかな?

思考レベルだがこれを適用する際に問題になりそうなのは積みかけのフレームだと思ってる。例えば以下のケース:
(+ 1 (call/cc (lambda (c) 2)) 3)
というのがあったとして、call/ccが呼ばれた際のスタックは以下のようになる。(呼ばれた時点で、call/ccに渡されたlambda内ではない)
+-----------------+ <-- sp
| (lambda (c) 2)  |
+-----------------+ <-- fp
| Frame(call/cc)  |
+-----------------+ 
|       1         |
+-----------------+
|  Frame(+)       |
+-----------------+
Sagittariusでは上記のすべてが別ヒープにコピーされて、継続が呼び出された際にスタックに戻される。スタックVMで実装する際の一番重たい実装方法だ(よね?)
っで、上記の論文を考えると、数値2が返された段階でアンダーフローが検出される。その際上記のスタックは凍結されているので動かせない、つまり新スタックフレームに既に積まれた数値1とFrame(+)を積む必要がある。
あぁ、アンダーフローが検出された際って新スタックフレームは空であることが保障されているのでフレームポインタのことを考えなければ単にコピーするだけか。ヒープ割り当ててコピーする処理がコピーだけになったと思えば、悪くないだろうか?
理想としてはcall/ccの呼び出しで捕捉された継続が呼び出されないと分かっているなら(上記の例みたいな)、スタックを凍結せずそのままってのが一番だわな。この辺はコンパイラに頼るほかないが。

ブランチ切ってやってみるか。

No comments:

Post a Comment