継続マラソン - 継続の実装方法を考える6

Scheme

迷っていることを書き出してみる。

継続の単位は?

  • 手続き呼出しが最小単位
  • 1つのScheme Objectの eval が最小単位

どちらだろうか。


実験(Gauche)

(define a 3)
(define cont '())
(+ ((lambda () (set! a (+ a 1)) (+ 1 2))) (call/cc (lambda (c) (set! cont c) 1)) 3) ;; => 7
(cont 1) ;; => 7
a ;; => 4

この結果だけを見ると、 「+ 手続きの1番目引数の評価以降」の継続を取り出していることが分かる。
つまり「1つのScheme Objectの eval が最小単位」が正解ということになる。

継続スタック/引数スタック

ノートに殴り描きしながら考えたことで、継続スタックの他に、引数スタックが必要であること、それぞれがどういう関係であるか明白に理解できた。
この方法を使えば、特殊形式以外の場合の手続き呼出しは、きれいに表現できそうだ。
逆に言えば、特殊形式の場合には両スタックへの積みかたに気をつかわなければいけなさそう。


Continuation の取り出しとは 継続スタックポインタ / Environment / 引数スタックポインタを保存しておくことであるというのが現時点での結論。
両スタックは単方向リストを採用することで、継続の取り出しが行われていない場合は GC されることを期待できる。
継続の取り出しが行われていない場合は、現在のスタックポインタ以降しか必要とされていない（参照されていない）ということになるはず。

迷い

  • 今までの形式と新しい実装の両方をすぐに切替えられる何かが必要。
  • 引数スタックを保持するので引数は eval されてから渡ることが前提になるが特殊形式はどう処理しよう。
    • 特殊形式の場合はひきすうすタックに積むときに eval しない。というのはどうだろうか。

進めかた

  • Continuation をためるのに良い場所を考える
  • Continuation の実行をする良い場所を考える
  • 組み込んでみる
  • call/cc 構文をサポートする

うーん。今の実装を結構壊さないと出来ない気がするぞ。
svn copy でブランチを作ろう