About partial continuation

[Hamayama]

• しばらく、部分継続の実行を (ep->cont に戻るのではなく)
  vm->cont に追加する形にできないか試していたのですが、
  難しいようです。

• 現状の、戻るタイプの部分継続の実行では、
  promptTag がない reset / shift のみであれば、
  何とかつじつまを合わせることができるのですが、
  promptTag があると、対応ができません。

• 例えば、

  (require racket/control)
  ;(use gauche.partcont)
  (define tag1 (make-continuation-prompt-tag 'tag1))
  (define tag2 (make-continuation-prompt-tag 'tag2))
  (define k1 #f)
  (define k2 #f)
  (reset-at tag1 ;; --- (A)
   (display "[r01]")
   (reset-at tag2
    (display "[r02]")
    (shift-at tag2 k
     (set! k1 k))
    (display "[s01]")
    (shift-at tag1 k
     (set! k2 k))
    (display "[s02]")))
  (reset-at tag1 ;; --- (B)
   (k1)
   (display "[r03]"))
  (k2)
  ;; ==> [r01][r02][s01][s02][r03] ;; OK
  ;; ==> [r01][r02][s01][s02]      ;; NG
  

  のようなケースで、(k1) の実行では、k2 は、
  (B) の方の reset-at との間を切り取らねばなりません。
  しかし、戻るタイプの部分継続の実行では、
  (A) の方の reset-at との間を切り取ってしまいます。
  結果として、(k2) の実行で、
  [r03] が表示される/されないの違いが出ます。

• Add call-with-composable-continuation experimentally #1259 では、
  promptTag のサーチは、追加するタイプの部分継続で行い、
  実際の部分継続の実行は、戻るタイプの継続のままにするという、
  ハイブリッドな形で、かなりのテストを通すことはできました。
  しかし、prompt-at / control-at を実装しようとすると、
  部分継続の実行時に、より奥の promptTag まで実行する必要があるため、
  どうしても実現できませんでした。
  それに、仕組みも複雑になってしまったので、後々の保守を考えても厳しいように思います。

• 現状の Gauche では、部分継続の切り取りと追加をしようとした場合に、
  つなぎめの部分の処理をうまく書くことができませんでした。

• ひとつのハードルが、DENV で、
  戻る場合には DENV をごっそり捨てられるというのは分かるのですが、
  部分継続の切り取りと追加をしようとした場合に、
  中にある情報をある継続点まで切り取って保存したり、
  それを別な継続に追加することが困難なようにみえました。

• また他のハードルのひとつが、ループ時のメモリリークで、
  だいたい、ep や resetChain でつかまえた情報が解放されなくて発生するようでした。
  これは、つかまえた情報を削っていくと直ることが多かった。
  (最初、Scm_VMPushCC() を使ったら末尾再帰でなくなるのでだめなのかと思ったのですが、
  それは関係なかった)

• 他のハードルのひとつが、戻るタイプの例外処理との組み合わせで、
  guard や call/cc と部分継続の実行を組み合わせた場合に、
  無限ループになったり SEGV したりしました。

• またリベンジしたいですが、しばらくは休もうかと・・・

[shirok]

ありがとうございます。
現在のPromptTagの実装はわりと無理やりだったりしますし、EscapePointも当初の目的とは違う使いかたをしているので、本来はアクティベーションレコードの持ち方をゼロから考え直す方がすっきりするかもしれないとは思うんですが、動く状態を保ったまま移行するのはかなりトリッキーです。私もバックバーナーで考えてみます。

[Hamayama]

• Add call-with-composable-continuation experimentally v2 #1263 で、
  部分継続の実行を、継続を追加する形の実装に作り直しました。

• パフォーマンスは悪くなったと思いますが、
  gauche.partcont を use しなければ、既存への影響はないと思います。

• 現状、SRFI-226 の仕様通りになっていない部分が多々あります。
  例えば、

  (guard (c [(eqv? c 42) c])
    (+ 1
       (call-with-continuation-prompt
         (lambda ()
           (raise 42))))) ; ==> 43
  

  があります。現状、Gauche では 42 になります。
  多分、call/cc の部分継続の仕様を満たすと、
  guard の外側ではなく prompt の外側に脱出するようになるのだと思いますが、
  理解が難しいです。

• そして、仕様の難しさもありますが、
  参照実装の階層構造が深すぎて、実装の理解が難しいということもあります。
  Racket の control.ss も同じような感じでした。

• マニュアルに「将来のリリースで全てをカバーする予定です。」とありますが、
  これを全部実装するのは、かなり難しいと思います。
  また、メンテナンスが困難になったり、既存との互換性がなくなることも考えられます。
  現時点では、割に合わないような気がします。

• あと、現状の Gauche ですが、
  save_cont_1() で、BOUNDARY_FRAME でないときは、
  ScmPromptData がヒープにコピーされないという問題があります。
  Scm_VMCallWithContinuationPrompt() で作成するプロンプトでは、
  BOUNDARY_FRAME のマークが付かないため、
  スタックにデータが取り残されて、上書きされておかしくなる可能性があります。
  もうマーカーに使えるビットがないので、ちょっと直し方が分かりませんでした。
  (Add call-with-composable-continuation experimentally v2 #1263 では、
  SHIFT_MARKER が不要になったので、そのビットを使って対応しました)

[Hamayama]

• Add call-with-composable-continuation experimentally v2 #1263 で、
  しばらく作業しましたが、既存の処理との整合性がなかなか取れず、クローズしました。

• ある程度は動いたのですが、ユーザーが不具合を回避しながら使う必要がある、
  という感じでした。

• 基本的に、戻るタイプの継続と、追加するタイプの継続は、共存ができない気がします。
  (どんどん継続を追加していっているのに、はるか前の継続に戻られてしまう・・・)
  現状の Gauche の実装は、戻るタイプに特化しているようにみえる。

• また、追加するタイプの継続は、遅くなりやすいようでした。
  (ただ、Racket の実装を見ると、キャッシュ等を使用していて、
  改善は可能なようにも見えました)

• あと、プロンプトタグによる複雑さの増加があります。
  複数のタグのたすきがけのようなケースが出るため、テストが難しいです。

• prompt tag, dynamic handler, exception handler, parameter, thread
  等の組み合わせをテストする必要があります。
  現状、きちんとケースを洗い出してテストしている実装は、ないようにみえます。

• Gauche の tests/partcont.scm にあるように、SRFI-226 と Racket でも、
  結果が違うものがあります。
  ある程度は Racket の方が正しそうですが、例えば、
  https://srfi-email.schemers.org/srfi-226/msg/30386128/
  で報告されているものは、Racket の (prompt の) 実装の方がおかしいような気もします。

• 今後については、少し休んでから、
  現状ベースで見つかっている不具合がいくつかあるので、
  それを修正するくらいにしようかと思っています。

[Hamayama]

• この間のコミットですが、Revert して別ブランチにしていただけないでしょうか。
  https://github.com/shirok/Gauche/compare/57574c1..dd9020f

• 理由は、部分継続が動作していないことと、複雑で試行錯誤がやりにくくなるからです。

• テストだけは通っているのが恐ろしいですが、AI ですかね?

• この実装は、結局、過去につながる継続をつかんでいるので、切り取れていない。
  追加するタイプの継続を入れないのであれば、meta-continuation はいらないと思う。
  逆にいれるのであれば、相当複雑なものを抱え込むことになる。
  SRFI-226 の参照実装には、効率を無視して分かりやすさを優先したと明記されている。
  現在の過去に戻るタイプの実装と同じパフォーマンスを出すには、
  Racket の src/cs/rumble/control.ss と同様な実装になると思うが、
  このソースコードのコミッタは実質世界で一人のみであり、
  かなり部分継続にくわしい研究者である。

• 理解も覚悟も足りない状態で、複雑なものをどかんと入れないでほしい。
  (そもそも、4 年以上も放置していたのに、何でこちらが作業しているタイミングで、
  master ブランチに入れてきたのでしょう・・・)

• できれば、DENV の方を先に何とかしてほしい、
  Parameter と exception handler ですが、
  Continuation mark (=DENV) を使って実現するのであれば、チェーンが不要のはず。
  逆にチェーンを解消できないのであれば、DENV から外して、
  vm と escapePoint に戻して、vm->denv = ep->denv としているところで、
  操作するようにしてほしい。
  (切り取らないのであれば、現状でも大丈夫かもしれませんが・・・)

[Hamayama]

• あと、現在の実装ですが、まだ改善できると思っていて、
  marker を自然に消したり、バグを直したりしたいと思っています。
  仕事もあるので、もう少し時間がほしい・・・
  (reset / shift のみなら、戻るタイプの継続のみで、
  かなりシミュレートできるということだと思う)

[Hamayama]

すいません、変なことを書きました。

そちらでの対応は、(当然ですが) 一切不要です。

こちらは、変更前のコミットに対して、ある程度作業をして、
ひと段落にしようと思います。

ご迷惑をおかけしました。

[shirok]

metacontinuationを使ってcontinuation frameをsegmented にするのとresetChainを消すのはずっと前からのアイディアで、こちらを先に解決してからこの上にHamayamaさんのアイディアを順に乗せていこうと思ってたんですが(実際、作業中です)、事前に相談して進めるべきでしたね。申し訳ないです。
部分継続で動作しなくなった例があったらテストにして投げてください。

[shirok]

ScmMetaCont 導入からのコミットをmetacontinuationブランチに移して、masterの方はそれ以前の状態に戻しました。

parameterとexceptionHandlerチェインについてはDENVで解決すべきで、現状こんがらがってるのはrewindの方に問題がある (rewindは本来abort系のプリミティブに全て任せるべき)、と考えているんですがどうでしょう。exceptionHandlerのリストを部分継続が「切り取る」というのは本来想定されているセマンティクスではないと思うんですが。

(訂正)exceptionHandlerじゃなくてdyamic handlersだ。

[Hamayama]

いろいろとお手数おかけしております。

しばらくダウンしていました。

Revert 前のソースで、私が確認して NG だったテストは、

#1263 の最初のコメントにある、
＜テスト結果＞ の (2) と (3) になります。

(2) は、Algebraic Effects という有名なもので、
ayatoy さんが Racket の部分継続を使って実装したものを、
Gauche の命令に単純に置き換えたものになっています。
部分継続の実用例として重視しています。
このテストは、NG になったときのデバッグが大変難しく、
「Gauche 側の実装が理論とあっているかどうか」を
追求していく以外に、OK にできたことがありません。

(3) は、Oleg 先生のサイトに載っている
部分継続がきちんと切り取れていないとメモリリークするというテストです。
このテストは、Racket では OK ですが、
SRFI-226 のサンプル実装や Saggitarius では NG だったと思う。
　　　　　 ↑
すいません再確認したら SRFI-226 の参照実装では OK でした。

ただ、Racket でも meta-continuation に、ホスト (Chez) の continuation は、
つかんでいるようなので、どこかで切るようにしているのか、
それとも切らなくても大丈夫な方法があるのか、よく分かっていません。
(Racket にはそもそも escapePoint がないので、
そこらへんも関係があるのかな・・・)

[Hamayama]

parameterとexceptionHandlerチェインについてはDENVで解決すべきで、
現状こんがらがってるのはrewindの方に問題がある (rewindは本来abort系のプリミティブに全て任せるべき)、
と考えているんですがどうでしょう。

この件ですが、私が最初にはまったのが、
tests/partcont.scm の「reset/shift + temporarily + parameterize」
というテストで、
確かに rewind の処理が dynamic-wind のどこかにあって、
ああここで戻しているからか、と思った記憶があります。

あと、(p 3) のようにしてパラメータを変更できてしまう件もあって、
parameter.c の Scm_PrimitiveParameterSet() で、上書きがされていて、
このせいで 差分がない → 変化がない → 戻す必要もない
みたいな理屈で、DENV ごと捨てられ、はるか前の Parameter の値が出てきたことがありました。

exceptionHandlerのリストを部分継続が「切り取る」というのは本来想定されているセマンティクスではないと思うんですが。
(訂正)exceptionHandlerじゃなくてdyamic handlersだ。

exception handler は、現状は DENV の中にチェーンが入っていて、
これをどうして良いのかはちょっと分からなかった。

dynamic handlers は、現状は DENV には入っていなくて (キーは予約されていますが) 、
Scm_VMCallPC() のところで切り取っていました。
これは、dico_leque さんがつぶやいているのを見て、入れたと思う。
これがないと、無駄な before と after の呼び出しがたくさん増えてしまいます。

「切り取る」というか、各 meta-continuation が自分の担当分だけを記憶する
というのが正解なのかもしれない。

基本的に、「つかんで戻る」という処理を全部捨てないと、
整合性が取れるようにはならないと思っていて、それはもう別ものになると思う。

そして、これが本当に良いものなのかというのが、私にはあやしく思える。
meta-continuation というデータ構造から、実現可能な制御構造が逆に決まっていて、
その枠内で仕様ができている気がする。
call/cc もいきなり使うとタグがないというエラーが出るし。
(Racket では、大外のプロンプトが何かいるらしく、エラーにならない。
tests/continuations.scm の「prompt / control (for-each)」のテストについても、
その大外のプロンプトの何かせいで、あの結果になるようでした。
あのテストは、Racket でもテスト全体を (prompt (prompt で囲っていくと結果が変わる・・・)

特に、タグによるたすきがけが、制御構造として複雑すぎる気がする。
FOR1 FOR2 ～ NEXT1 NEXT2 みたいなものが、どう動くのが正解なのか、
私にはイメージができない。

[shirok]

現在のmetacontinuationブランチでは(2)のGauche-effectsテストは全部通ります。(3)はリークしますね…

[shirok]

あー、リークするのはmetacontによるsegmented cont frame化を完全に完了してないからだな。

[Hamayama]

(3) のリークは、#1263 では、
部分継続の切り取り時に cont をコピーして NULL 終端することで解消されました。
そして、部分継続の起動時には、切り取った cont をさらにコピーして、
現在の継続の先頭に追加するようにしました。

同様に、DENV(=continuation-mark), prameter, dynamic handler, exception hadler
についても、コピーして切り取りと、
起動時は現在のものの先頭にコピーして追加する処理が必要であると考えていました。
(dynamic handler については、現状でも Scm_VMCallPC() と throw_continuation()
の Scm_Append2() でやっています。当時はそこまで理解していませんでしたが…)

そして、それらができたとして、最後にラスボスのような仕様があり、それが、
SRFI-226 の non-composable-continuation の起動時についての記述にある、
「if it is later called, aborts all active procedure calls in the then-current continuation up to but not including a continuation prompt with prompt-tag or up to but not including an active procedure call shared by the current and captured continuations, whichever comes first. Finally, the active procedure calls in the unshared portion of the captured continuation are reinstated and the arguments supplied to the call to the continuation procedure become the result values for the new current continuation.」
という部分です。直近のプロンプトタグ、もしくは…、という条件があり、
#1263 では、意味と実装方法が分からなくて未実装でした。
SRFI-226 の参照実装では、common-metacontinuation というところで対応しているようですが・・・
(Racket にも同様の記述があります)

このようにして実装していくと、既存の call/cc との競合が目に見えるようになります。
いくつかの test が無限ループして終わらなくなる。
多分、部分継続の途中に call/cc があると、過去の cont と DENV のところに巻き戻ってしまって、
ループの終了条件を満たせなくなるんだと思う。
これは、call/cc を call-with-non-composable-continuation で再定義すると直る。
guard も見直しが必要になる。

というあたりがこれまでたどったルートです。

[shirok]

metacontのアイディアは、cont->prevのチェインをpromptでNULLにして切って(segmented)、metacontのチェインの方に各segmentのつながりを持たせる、というものです。(partcont-metaの実装はオリジナルのcall/ccを基礎にmetacontを作っているのでチェインの切断ができていません)。実装が完了すれば、call/ccで取った継続も、ぶつ切りのチェインがmetacontで繋がれた形になります。

もともと最初のGaucheの部分継続実装が、resetでcont->prevをNULLにして、returnで戻ってきてprevがNULLだったら「直近に保存された継続」から再開する、というものでした (ドキュメントの部分継続の説明はその時のままです)。ただこれだとプロンプトが複数あった場合にうまくありません。

segmented continuation chainの場合、contフレーム自体は継続の起動の際に変更されるところがないので、一旦ヒープに移したら起動の際にコピーしなおす必要がありません。metacont chainの方はつなぎ直さないとならないのでコピーが必要ですが、データ量はずっと少ないです。

denvのalistも今は前のdenvフレームとは独立しています (srfi-226参照実装でmetacontinuationが空のmarksで初期化されるのと同じ。ただ、Gaucheではparametersやexception handlersチェインもdenvに入れていて、それはトラバースを楽にするために前のdenvフレームの値を持ってきてる。これがリークに影響を与えるかもしれない)。