Gauche:部分継続と動的環境の実験

既知の問題点

• 現状、以下の例で、フル継続の呼び出し (k2) の戻り先が、
  最外の reset の外側になる ([r21] ～ [r51] が表示されない) という問題点があります。

;(require racket/control)      ; for Racket
;(use-modules (ice-9 control)) ; for Guile
(use gauche.partcont)         ; for Gauche
(define k1 #f)
(define k2 #f)
(let ()
  (reset
   (display "[r01]")
   (shift k (set! k1 k))
   (display "[s01]")
   (call/cc (lambda (k) (set! k2 k)))
   (display "[s02]"))
  (k1)
  (reset (reset (reset (reset (reset (k2)
                                     (display "[r11]"))
                              (display "[r21]"))
                       (display "[r31]"))
                (display "[r41]"))
         (display "[r51]"))
  (display "[end]"))
;; ==> [r01][s01][s02][s02][end]#<undef>

• これは、元々の設計では、フル継続が戻ることを想定しておらず、
  reset (実体は vm.c の user_eval_inner) で作られる戻り先をすべて pop してから、
  フル継続のジャンプを行うようになっているためです。

• 本件は、#551 で対策しようとしたのですが、うまくいきませんでした (revert 済みです) 。

• フル継続が戻るケースと戻らないケースを、正確に判定できればよいのですが、
  今のところ、確実な方法が見つからない感じです。
  (判定を間違えると、既存のプログラムが動作しなくなります。。。)

• 戻り先が変なこと以外は、特に内部状態がおかしくなったりすることはないようです。

hamayama(2019/12/18 12:39:01 UTC)

• 一方、Racket (7.5 と 7.0 で確認) は、常にフル継続が戻ることを想定していると思われますが、
  弊害 (?) もあって、例えば、以下のコードがメモリを消費し続けます。
  理論的に部分継続とフル継続の関係性をつきつめていくと、こうなるのかもしれませんが。。。
  (Guile 2.2.6 と Gauche 0.9.9 では、消費しません)

• この例を見ると、フル継続が戻らないケースでは、resetChain もキャプチャ時点のものに
  更新してほしい気がします。
  (そういう考え方が、現状の不具合の要因になっているのかもしれませんが)

(require racket/control)      ; for Racket
;(use-modules (ice-9 control)) ; for Guile
;(use gauche.partcont)         ; for Gauche
(define k1 #f)
(let ()
  (call/cc (lambda (k) (set! k1 k)))
  (reset (reset (reset (reset (reset (k1)))))))

hamayama(2019/12/18 12:54:24 UTC)

Shiro(2019/12/18 14:11:21 UTC): もともとのフル継続の意味論なら、「フル継続は戻らない」で正解だと 思うんですよね。Racketの設計を把握してないですが、全ては部分継続であり、 フル継続もどこかの地点からの部分継続と扱う、みたいな意味論ならあり得るかもしれないですが。

• hamayama(2019/12/18 15:15:02 UTC): うむ。多分 Racket は、
  「全ては部分継続であり、フル継続もどこかの地点からの部分継続と扱う」方式になっていると思います。
  これは、フル継続のジャンプ後に部分継続の終端に到達してしまった場合に、
  (継続が空なので) 一体どうしたものか、というあたりから、考えられたのではないかと。
  別案としては、エラーにして終了してしまうとか、
  (Guile のように) 部分継続の終端を無視して突き抜けて実行を続ける (乱暴ですが)、ことも考えられます。
  まあ、未定義動作であると考えれば、現状の Gauche の動作も、それほど悪いものではない気もします。
  (ソースコードはシンプルですし、動作も安定していると思うので)

成果物

現状の最新の成果物は、以下の通りです。

• dynamic-test v5
  https://gist.github.com/Hamayama/c3a5424240a9eb69278dd4e6ad6d57c9
  (実験用のプロトタイプ)

• Gauche へのプルリクエスト #529 #545 #548
  https://github.com/shirok/Gauche/pull/529
  https://github.com/shirok/Gauche/pull/545
  https://github.com/shirok/Gauche/pull/548
  (実験結果を Gauche の本体に反映したもの)

• Gauche-effects
  https://github.com/Hamayama/Gauche-effects
  (応用例 (オリジナルは Racket 版です))

部分継続と動的環境の学習の起点としては、
このページの一番下にある「参考情報リスト」の [文献A] がお勧めです。

hamayama(2019/11/17 02:57:05 UTC)(2019/11/27 08:45:11 UTC)

dynamic-test v5

• 部分継続とフル継続の組み合わせ時の動作を改善したため、バージョンを 5 にしました。
  ソースは以下になります。
  https://gist.github.com/Hamayama/c3a5424240a9eb69278dd4e6ad6d57c9

• 変更点は、emu-call/cc 手続き内の emu-k の呼び出し (フル継続のジャンプ) が、
  呼び出し元に戻るケースに対応したことです。

• 通常、フル継続のジャンプが呼び出し元に戻ることはありませんが、
  部分継続の内部にジャンプした場合に限っては、部分継続の終端に到達したときにどうすべきか、
  という疑問が生じます。

• Gauche へのプルリクエスト #545 では、
  そのようなときに、resetChain の復帰と dynamic-wind の巻き戻しを行って、
  戻るようにしました。

• 今回の変更は、その動作に合わせたものです。
  (dynamic-test は、基本的に制御フローは Gauche の本体にまかせており、
  動的環境のチェーン (*dynamic-chain* と *reset-chain*) だけを、自前で管理しています)

• emu-call/pc 手続きと emu-call/cc 手続きが、似たようなソースになり、
  これで部分継続とフル継続の共存について、ひとつの形にたどり着いたように思います。

• 改めて、Racket の call/cc の説明 を見ると、
  同じような動作を説明している箇所があります。
  (フル継続から戻るときに、直近の prompt-tag (reset) の直後までジャンプする (継続の一部を捨てる)
  ような記述がありますが、
  ちょうど Gauche の部分継続の終端の処理も、直近の reset を脱出するようになっていました)

• ただ、Gauche (#545) では、Racket の call/cc と異なり、
  (1) call/cc が部分継続を生成することはない
  (2) フル継続の起動時に resetChain をキャプチャ時のもので上書きする (そして戻るときは resetChain も元に戻す)
  ようになっています。

• これは、既存の call/cc の動作をなるべく変えないで共存させるためと、
  (reset (reset (reset ...))) のような深い場所から call/cc で脱出したときに、
  resetChain が多数 push されたままになるのは、よくないのではないかということから、
  このようにしています。

hamayama(2019/11/12 13:11:59 UTC)(2019/11/13 03:23:04 UTC)

検討1 (部分継続とフル継続の組み合わせについて)

• 下記「気になる例3」「気になる例4」のような、
  部分継続 (shiftの継続) の内部にフル継続 (call/ccの継続) でジャンプするケースついて考えると、
  部分継続とフル継続の組み合わせについては、もう少し検討が必要な気がする。

• 例えば、関数の内部にフル継続でジャンプした場合を考える。
  関数からリターンするときの継続は、call/cc のキャプチャ時に確定しているため、
  同じ関数呼び出しから複数回戻ることになる。

(define k1 #f)
(define (f1) (call/cc (lambda (k) (set! k1 k))) 1000)
(let () (f1) (k1))
;; ==> 無限ループ

• 一方、部分継続の内部にフル継続でジャンプした場合を考えると、
  部分継続の終端の継続は空っぽになっている。
  そして、空の継続に到達したら、部分継続を呼び出した点に戻って、
  その続きから再開することになっている。
  だとすると、部分継続の内部にフル継続でジャンプした場合も、
  部分継続の終端に到達したら、ジャンプ元に戻って、その続きから再開するべき、なのかもしれない。
  (後で確認したところ Racket 7.0 はそうなっていた。しかし Guile 2.2.4 は無限ループ)

;(require racket/control)      ; for Racket
;(use-modules (ice-9 control)) ; for Guile
(use gauche.partcont)         ; for Gauche
(define k1 #f)
(define k2 #f)
(reset
 (shift k (set! k1 k))
 (call/cc (lambda (k) (set! k2 k)))
 1000)
(let () (k1) (reset (k2)))
;; ==> 1000

• 上記仮定を正とすると、部分継続の内部にフル継続でジャンプするときには、
  部分継続のジャンプ処理に切り替えるという実装が考えられる。

• 現状の Gauche だと、ジャンプ先が部分継続なのかどうかを判別する手段は存在しない。
  また、下記「気になる例4」のパターンを見ると、call/cc のキャプチャ時には確定しないため、
  実際にジャンプするときにチェックが必要そうである。
  例えば、継続フレームに、部分継続の内部かどうかを示すフラグが必要だろうか。

• もはや、ユースケースは存在しない感じだが、理論的な正しさを目指して、
  とりあえず実装してみようと思う。
  (フル継続のパフォーマンスに影響が出るようなら、没だが。。。)

• その後、いろいろと試してみたのですが、どうもまだ理解が足りないようです。
  (テストは通るが、Gauche-effects が壊れたり、とか。。。)
  部分継続とフル継続の関係について、調査が必要そうです (まずは Racket か) 。
  (2019/11/10 09:28:04 UTC)

• その後、プルリクエスト #545 で、
  部分継続の内部の判定をすることなく、部分継続とフル継続の共存をはかりました。

hamayama(2019/11/09 08:15:22 UTC)(2019/11/10 09:28:04 UTC)

気になる例4 (shift をスキップして部分継続に侵入)

;(require racket/control)      ; for Racket
;(use-modules (ice-9 control)) ; for Guile
(use gauche.partcont)         ; for Gauche
(define k1 #f)
(define k2 #f)
(reset
 (display "[r01]")
 (call/cc (lambda (k)
            (set! k1 k)
            (shift k (set! k2 k))))
 (display "[s01]"))
;; ==> [r01]#<closure ((call/pc #f #f) . args)>
(k2)
;; ==> [s01]#<undef>
(reset (k1))
;; ==> [s01]SEGV

• 上記は、Gauche の HEAD (コミット 1576d5f) (2019-11-7) で実行した例です。

• フル継続 (k1) を起動すると、shift がスキップされて、
  そのまま部分継続の終端に到達して、リターンしようとして SEGV が発生しています。

• これは、フル継続のときはリターンすることを考えなくてよい
  (このため vm.c の throw_cont_body 関数内で save_cont(vm) が不要)
  という前提が崩れたケースといえます。

• 対策としては、フル継続の場合でも、
  shift で区切られた reset 内にジャンプするときは、
  save_cont(vm) (フレームのヒープ領域へのコピー) を実行することが挙げられます。

• しかし、こんな例があるとは。。。

• その後、改めて見直してみると、
  (k1) は shift と 部分継続の終端の間にジャンプしており、
  そこは「気になる例3」と同じでした。

• ただ、call/cc のキャプチャ時には、まだ shift が実行されておらず、
  部分継続の内部かどうかを判定できないという点が、「気になる例3」と異なります。

hamayama(2019/11/07 15:00:07 UTC)(2019/11/07 23:59:56 UTC)

気になる例3 (部分継続の内部にフル継続 (call/cc) でジャンプ)

;(require racket/control)      ; for Racket
;(use-modules (ice-9 control)) ; for Guile
(use gauche.partcont)         ; for Gauche
(define k1 #f)
(define k2 #f)
(reset
 (display "[r01]")
 (shift k (set! k1 k))
 (display "[s01]")
 (call/cc (lambda (k) (set! k2 k)))
 (display "[s02]"))
;; ==> [r01]#<closure ((call/pc #f #f) . args)>
(k1)
;; ==> [s01][s02]#<subr "continuation">
(reset (reset (k2)))
;; ==> "vm.c", line 2692 (Scm_VMReset): Assertion failed: SCM_PAIRP(vm->resetChain)

• 上記は、Gauche の HEAD (コミット 1576d5f) (2019-11-7) で実行した例です。

• フル継続 (k2) を起動したときに、resetChain をキャプチャ時のもので上書きするのですが、
  その後、部分継続の終端に到達してリターンしたときに、resetChain が古いままとなり、
  リターン後に reset 2 個の pop をしようとして、Assertion failed となっています。

• 対策としては、部分継続の内部にフル継続 (call/cc) でジャンプするときには、
  resetChain を変更しないようにすることが挙げられます。

• そもそも、フル継続 (call/cc) のジャンプ時に、
  resetChain を上書きするべきなのかが、よく分かっていないのですが。。。
  ただ、これをしないと resetChain のゴミがたまりやすくなるので、
  まずはそのままでいこうと思います。

hamayama(2019/11/07 15:00:07 UTC)

気になる例2 (dynamic-wind の before 内に shift があるケース)

(require racket/control)      ; for Racket
;(use-modules (ice-9 control)) ; for Guile
;(use gauche.partcont)         ; for Gauche
(define k1 #f)
(define k2 #f)
(reset
 (dynamic-wind
  (lambda () (display "[d01]")
             (shift k (set! k1 k))
             (display "[+s01+]"))
  (lambda () (display "[d02]")
             (shift k (set! k2 k))
             (display "[*s02*]"))
  (lambda () (display "[d03]"))))
;; ==> [d01]
(k1)
;; ==> [+s01+][d02][d03]
(k2)
;; ==> [d01]
(k2)
;; ==> [d01]
(k1)
;; ==> [+s01+][*s02*][d03]

• 上記は、Racket 7.0 で実行した例です。(;; ==> の右側が実行結果です)

• dynamic-wind の before と after の呼び出し回数がそろうように、
  ずっとデバッグしてきましたが、
  before の中に shift を入れてしまうと、
  Racket でも before ばかりが実行されるケースが作れました。

• よく考えると、before の中に call/cc で飛び込んで、またすぐに call/cc で脱出すれば、
  before だけを実行することは可能なので、あたりまえではありますが。。。

• 1回目の (k1) と、2回目の (k1) とで、結果が変わるのも興味深いところです。
  (k2) の実行によって、k1 の内容が上書きされています。

• こうしてみると、継続の使用には、おかしなことにならないように
  ユーザー側の気遣いが必要というか、あぶなっかしさのようなものを感じます。

• この感覚は、例えば、マクロの展開中に call/cc で出たり入ったりしたらどうなるのかとか、
  もっと単純なところでは、データと思っていたものがコードとして実行できてしまって大丈夫かとか、
  そういう不安さと似たようなものがあります。

• 現実には、ほとんどのプログラミング言語が PC のデータを破壊できる訳で、
  そのような危険は承知の上で処理系を使っている。すなわち、
  プログラミング言語にはパワーとリスクの両面がある、ということになるのでしょうが。。。

hamayama(2019/09/04 13:06:12 UTC)

気になる例1 (shift の中に shift があるケース)

(require racket/control)      ; for Racket
;(use-modules (ice-9 control)) ; for Guile
;(use gauche.partcont)         ; for Gauche
(define k1 #f)
(define k2 #f)
(reset
 (dynamic-wind
  (lambda () (display "[d01]"))
  (lambda ()
    (reset
     (dynamic-wind
      (lambda () (display "[d11]"))
      (lambda ()
        (shift k (set! k1 k)
                 (display "[s01]")
                 (shift k (set! k2 k)
                          (display "[s02]"))
                 (display "[s03]")
                 1000)
        (display "[s04]"))
      (lambda () (display "[d12]")))
     2000))
  (lambda () (display "[d02]")))
  3000)
;; ==> [d01][d11][d12][s01][s02][d02]3000
(k1)
;; ==> [d11][s04][d12]2000
(k2)
;; ==> [s03]1000

• 上記は、Racket 7.0 で実行した例です。(;; ==> の右側が実行結果です)

• 1個目の shift の expr ([s01]) は、2個目の reset を脱出してから 実行されている。
  (すなわち、2個目の dynamic-wind の after ([d12]) を実行後に 実行されている)

• しかし、2個目の shift の expr ([s02]) は、reset を脱出しないで 実行されている。
  ([s01]と[s02]の間に何も呼ばれていない)

• そして、部分継続 k1 を起動すると、
  1個目の shift と 2個目の reset の間の処理が実行され 2000 が返る。

• 一方、部分継続 k2 を起動すると、
  2個目の shift と 1個目の shift の間の処理が実行され 1000 が返る。
  (reset との間ではない!)

• これらのことから、推測すると、shift の expr を実行する際に
  暗黙の reset が追加されているのではないか?
  つまり、(shift k expr ...) が (shift k (reset expr ...)) と、
  変換されて実行されている可能性がある。

• こうすることで、(reset expr ...) の部分が、元の reset を脱出後に 実行されたとしても、
  expr が新しい reset に囲まれているため、
  そこで shift を実行しても、さらに外側の reset を脱出してしまうことを防げる。

• ただ、それだったら、そもそも expr の実行時に reset を脱出しなくてよかった気がする。
  これは、実装の都合によるつじつまあわせだろうか?

hamayama(2019/09/01 11:00:49 UTC)(2019/09/05 00:50:40 UTC)

dynamic-test v4 (没)

• 動作しないテストケース「dynamic-wind + reset/shift 3-B」が見つかったため、
  修正して、バージョンを 4 にしました。ソースは以下になります。
  https://gist.github.com/Hamayama/c3a5424240a9eb69278dd4e6ad6d57c9/d0fd28c19c658e4d7ac098d0ef8d03e656d18415
  (これ (v4) はもう没です)

• emu-call/pc 手続きの処理を見直した結果、v3 の dp-reset2 は不要になり、
  <dynamic-winder> クラスと <reset-info> クラスの相互参照もなくなりました。

• ただ、どうもまだ不完全なような気もします。。。
  動的環境の切り出しを行うことで、
  dynamic-wind の before, after の余分な呼び出しがなくなるのは分かるのですが、
  どのタイミングで何をどう切り出せばよいのかが、明確になっていない感じです。
  ↑
  emu-call/pc 手続き内の %travel と emu-reset の順番を入れ換えたら、
  workaround が消えて、大分すっきりしました。(v4.04)

• (現状、Gauche に出したプルリクエスト #507 #515 の方は、
  動的環境の切り出しをしないバージョンになっています)
  ↑
  #518 で動的環境の切り出しを実装しました

• また、shift の expr は reset の外側で実行される仕様とのことで、それも対応しました。← 現状、不完全です
  https://twitter.com/gengar68/status/1131962670943416320
  (テストケース「reset/shift + parameterize 1」)

• Racket や Guile のソースを見ると、prompt (= reset) の方に、
  脱出後に実行する abort-handler という機能があり、
  その機能を使って、reset の外側で shift の expr を実行しているようです。

• 現状は、そのような機能を作っていないため、
  reset-chain を pop してから expr (= proc) を実行することで、
  つじつまを合わせるようにしました。
  (emu-call/pc 手続き内のコメント「'proc' is executed on the outside of 'reset'」のところ)
  ↑
  これは、うまくいかないケースがあったため、元に戻しました。(v4.05)
  ( https://github.com/shirok/Gauche/pull/515#issuecomment-526814133 )

• ただ、初期の実装例としてよく見かける shift-reset.scm では、
  shift の expr は reset 内で実行されているため、
  これが必須の仕様なのかは、ちょっと分からないのですが。。。

hamayama(2019/08/29 09:03:35 UTC)(2019/08/29 20:05:41 UTC)
(2019/08/31 09:11:49 UTC)

dynamic-test v3 (broken) (没)

• いくらか進展したので、バージョンを 3 にしました。ソースは以下になります。
  https://gist.github.com/Hamayama/c3a5424240a9eb69278dd4e6ad6d57c9/199f60b3292bc3c2010a47afb8413aa38af68f0d
  (これ (v3) はもう没です)

• dynamic-wind の before と after の呼び出し回数の不一致や、
  reset の管理の不具合については、ほぼなくなりました。

• テストもいくつか追加しました。
  現状、テストは Racket 7.0, Guile 2.2.4 と同じ結果になることを確認しています。
  また、ソース内の *dbg-level* を 3 にすると、動作の様子を表示できます。

• とにかく苦労したのが、emu-call/pc 手続き内の dp-reset2 のところです。
  これは、動的環境の切り出しに使うのですが、
  「shift に対応する reset 」ではなく、
  「動的環境を作成した時点の reset 」を切り出しの起点にしないと、
  テストの「dynamic-wind + reset/shift 3」(reset 1個に対して shift が2個あるケース) が通りませんでした。

• この件については、デバッグが本当に難しく、ログを出したり紙に図を描いたりして、
  やっと動作するようになりました。
  (shift は、限定継続 k の起動時に内部に reset を追加するため、
  2個目の shift はその内部の reset と対応することになります。
  しかし、動的環境の dynamic-wind は 1個目 の reset の中にあって、
  そちらの before や after を抜けなく実行する必要があります)

• ただ、このために <dynamic-winder> クラスに *reset-chain* へのポインタを持つ必要が生じ、
  <reset-info> クラスと相互参照のようになってしまったのは、気になる点です。
  (もっとよい実装方法があるかもしれない。。。)

• あと、参考情報として、emu-call/pc 手続き内の (%travel dp-k (append dc-part dp-k)) の部分を、
  (%travel dp-k dp-pc) に変更すると、動的環境の切り出しをしない実装になり、
  dp-reset2 関連の処理が不要になります。
  ただし、これだと、dynamic-wind の before, after の余分な呼び出しが発生します。
  (最初に参考にした [文献A] の方式になります)

• 今回の実装も、継続のジャンプには Gauche 本体の call/cc や call/pc を使っています。
  この方式では、http://okmij.org/ftp/continuations/against-callcc.html#memory-leak にある
  以下の例でのメモリーリークが発生しません。

(define (leak-test1 identity-thunk)
  (let loop ((id (lambda (x) x)))
    (loop (id (identity-thunk)))))
(leak-test1 (lambda () (emu-reset (emu-shift k k))))

• ただ、Gauche 本体の内部で使われている %call/pc は、
  限定継続 k の起動後に、直近の reset を脱出する仕様となっています。
  このため、現状、prompt/control の control を実現することはできません。
  (control は、限定継続 k の起動時に reset を追加しないため、関係ない reset を脱出してしまいます)
  (これについては、あちこちで見かける shift-reset.scm でもそうなっているため、
  間違いとは言えませんが、reset/shift に特化した実装ということになります)

hamayama(2019/08/12 07:06:14 UTC)(2019/08/12 11:17:16 UTC)
(2019/08/13 01:41:09 UTC)(2019/08/13 12:52:35 UTC)

dynamic-test v1 (broken) (没)

• https://github.com/shirok/Gauche/issues/477 の件ですが、
  まずは、dynamic-wind と reset/shift の動作をエミュレートするプログラムを作ってみました。

• 作成したソースは、以下になります。
  https://gist.github.com/Hamayama/c3a5424240a9eb69278dd4e6ad6d57c9/b94fc2429f12f8ae9feb90133f4545ea165e2fc4
  (これ (v1) はもう没です)

• emu-dynamic-wind, emu-call/cc, emu-call/pc, emu-reset, emu-shift が作成した手続きです。
  継続のジャンプについては、Gauche 本体の call/cc や call/pc を使っており、
  動的環境のチェーンだけを、自前で管理しています。
  (このため、Gauche 本体の dynamic-wind 等と組み合わせると、壊れます)

• 基本的な考えについては、以下を参考にしました。[文献A]
  https://web.archive.org/web/20090625182949/http://www.cs.tsukuba.ac.jp/H18Syuron/200420314.pdf
  P16 の 図4.3 にあるように、after サンクと before サンクを実行しながら
  動的環境のチェーンを移動していく travel という手続きがポイントになります。
  (作成したソースでは、%travel としました)

• しかし、reset/shift への拡張については、P17 の 4.5 の方法を実装しても、
  Racket と同じ結果にはなりませんでした。

• 試行錯誤した結果、今の emu-call/pc の実装となりました。
  emu-call/cc では、(%travel *dynamic-chain* dp-captured) となっているところを、
  emu-call/pc では、(%travel dp-reset dp-captured) として、
  reset の 動的環境ポインタ を始点としました。← これは誤りです

• また、emu-call/pc の終了時にも、reset の継続までジャンプするため、
  (%travel dp-captured dp-reset) を実行するようにしました。
  ↑
  shift (call/pc) は reset を脱出してから本体を実行するのが正しい。
  このため travel を先に実行すべき

• 多分、以下で言っていることが、こういうことだと思いますが。。。
  https://twitter.com/dico_leque/status/1132091286180179969

• とりあえず、簡単なテストは、(やっと) Racket と同じ結果が出るようになりました。
  もう少し確認して、よさそうであれば、Gauche 本体への統合を検討しようと思います。

• hamayama(2019/07/17 10:44:39 UTC): うーむ、今の実装だと、「最近のreset」がうまく取れないケースがあるもよう。
  (例えば、emu-reset 内から call/cc 等で脱出した場合に、*reset-point-chain* の push と pop の数が合わなくなる)
  これは、まだまだ穴がありそう。。。

hamayama(2019/07/15 15:42:40 UTC)

• Shiro(2019/07/18 03:36:09 UTC): shift/resetについてはcall/ccでエミュレートする実装が 論文にあります (Gaucheも当初はそれを使ってました)。挙動の比較についてはそれを参照実装に する手はあります。ただ、dynamic-windに関してはcall/ccのエミュレートでは「不必要なbefore, after thunkの実行」が生じる可能性がある気がするので、完全に一致する必要はないと 思いますが。

Gauche-effects

https://github.com/Hamayama/Gauche-effects

• https://github.com/ayatoy/racket-effects を、Gauche で動作するように改造したものです。

• 内容は、https://www.eff-lang.org/ の algebraic effects を scheme で実装したものになります。
  (正直、理論はあまり理解できていませんが。。。)

• dynamic-test をモジュール化した、emu-dynamic.scm を使用しています。

hamayama(2019/08/17 11:29:19 UTC)(2019/08/29 09:03:35 UTC)

参考情報リスト

• https://web.archive.org/web/20090625182949/http://www.cs.tsukuba.ac.jp/H18Syuron/200420314.pdf
  [文献A]
  (P14 の「4.3 call/cc と dynamic-wind の意味論」が 基本の考え方になります。
  最初、動的環境のチェーンは1本なのに、どうして枝分かれした図が出てくるのかが、
  理解できませんでした。しかし、
  1本のチェーンが伸びきったところで call/cc によってキャプチャされると、
  その後、縮んでまた伸びて call/cc でキャプチャされたものと、枝分かれの関係になることに、
  ここの説明を読んでいて 気が付きました。
  このことが分かってから、大分見通しが立ってきました。
  ただ、P17 の「4.5 メタ継続とダイナミックポイントの統合」については、
  この通り実装すると、dynamic-wind の before, after の余分な呼び出しが発生します。
  現在の Racket や Guile は、reset - shift 間の動的環境の切り出しを行うことで、
  この before, after の余分な呼び出しを行わないようになっています。)

• https://twitter.com/dico_leque/status/1132091286180179969
  (Racket の方式について)

• https://nymphium.github.io/2018/07/19/delimited-continuation%E3%81%AE%E5%A4%8F.html
  (reset/shift の定義等)

• https://github.com/rain-1/continuations-study-group/wiki/Reading-List
  (論文のリスト)

• https://rain-1.github.io/scheme-continuations.html

• https://wingolog.org/archives/2010/02/26/guile-and-delimited-continuations

• https://www.reddit.com/r/scheme/comments/b7k7wy/how_to_implement_delimited_continuation_in/

hamayama(2019/08/22 13:31:07 UTC)(2019/10/15 12:07:11 UTC)