継続マラソン - 継続の実装方法を考える
setjmp/longjmp を使う方法。
ケース1
a(x)->b(x)->c(x)->d(x)のように関数を深い方向に呼び出しているとします。
a(x) {
//ここで継続を取り出す
// ここ(setjmp)
//
b(x);
}
b(x) {
c(x);
}
c(x) {
d(x);
// d(x)の結果次第で
// longjmpする
}
setjmp時のスタックの状況
=================== ←スタックポインタ aの戻りアドレス =================== x of a ===================
longjmp時のスタックの状況
=================== ↑ dの戻りアドレス ここは不定 =================== ここは不定 x of d ↓ =================== ←スタックポインタ cの戻りアドレス =================== x of c =================== bの戻りアドレス =================== x of b =================== ★ aの戻りアドレス =================== x of a ===================
setjmp をした時点でのスタックポインタを含めたレジスタを保存しておけば longjmp 時に★の場所にスタックポインタ戻してやれば良い。
これは jmp の向きが浅い方向なのでOK。
ケース2
a(x) {
b(x);
// longjmpする
}
b(x) {
c(x);
}
c(x) {
d(x);
//ここで継続を取り出す
// ここ(setjmp)
//
}
これはうまく動きません。
setjmp時のスタックの状況
=================== ↑ dの戻りアドレス ここは不定 =================== ここは不定 x of d ↓ =================== cの戻りアドレス =================== x of c =================== bの戻りアドレス =================== x of b =================== aの戻りアドレス =================== x of a ===================
longjmp時のスタックの状況
=================== ↑ dの戻りアドレス ここから不定 =================== x of d =================== ★ cの戻りアドレス =================== x of c =================== bの戻りアドレス =================== ここまで不定 x of b ↓ =================== ←スタックポインタ aの戻りアドレス =================== x of a ===================
longjmp時に★の不定部分にスタックポインタが指定されるので動くかどうかは怪しいです。
このように深い方向への longjmp は通常うまく動きません。
ケース2をうまく動かすには
ケース2がうまく動かないのはスタックが関数から戻ることで再利用されて不定になってしまうからです。
なので
- setjmp 時に現在のスタックポインタから一番奥までをヒープなどにコピーしておく
- longjmp 時にはそれをスタックに展開する
ということをやれば、うまく動きそうな気がします。
恐いのは、解放済みのメモリにアクセスしてしまうことですが、GCを利用して自前で delete しないことを守れば、ヒープ上に参照が残っているので GCされることはなさそうです。
さてメリット/デメリットを自分の分かる限りで書いてみようと思います。
メリット
- 独自のsetjmp/longjmp を作るだけで処理系の実装とわりと独立する
- 実装が簡単そう
- call/cc を使ったときだけコストがかかる(合っている?)
