継続マラソン - 継続の実装方法を考える3
Schemeを作ろう 第3回で触れられている方法。
ではどうしたか。結局私は、内部構造を本当にバカ正直にに継続の連続にしました
これについて考えてみようと思います。ただ僕の理解が正しいかは自信なし。
シンプルな例から考えるのが良いだろう。
考え方
(+ 1 2)
を処理系が評価する場合を考える。
継続を取り出せそうな場所は5ヶ所ありそう。
<<1>>(+ <<2>> 1 <<3>> 2 <<4>>) <<5>>
それぞれの場所での継続を列挙すると
<<1>> | 関数を呼び出そうとする | 引数1を評価 | 引数2を評価 | 1と2を引数に+を評価 | 結果を返す | 次の式を評価 |
<<2>> | 引数1を評価 | 引数2を評価 | 1と2を引数に+を評価 | 結果を返す | 次の式を評価 | |
<<3>> | 引数2を評価 | 1と2を引数に+を評価 | 結果を返す | 次の式を評価 | ||
<<4>> | 結果を返す | 次の式を評価 | ||||
<<5>> | 次の式を評価 |
となります。
表にしてみると分かったのだけど、継続はスタック構造から1つずつ pop されて順々に実行されていくと考えられなくもない。
<<3>>での継続を取り出してみる
自分がインタプリタになったつもりで<<3>>の継続を取り出し、再開できるか考えてみる。
インタプリタは実行対象のS式をメモリ上に保持しており、S式を順々に見ていき今から行おうとすることを継続のスタックに積んでいく。
積まれた継続は、すぐにシステムにより取り出されて実行される。(ただしスタックから削除されるわけではなくてスタックポインタがずれる感じ)
スタックに積む人とスタックに積まれたものを実行する人が交互にお仕事をして実行を進めるイメージ。
さて<<3>>で call/cc に出会うとシステムは、<<3>>が継続スタックの中のどこにあったかを保存する。
そして先に進む。<<3>>で取り出した継続から再開する場合は、継続のスタックポインタを保存してあったものに設定し、システムはそこから実行を再開する。
本当にうまくいくかな
なんとなくうまく行きそうだけどまだまだ頭の中でモヤモヤしている。
- 内部的な継続の最小単位は何? 評価?/手続き呼びだし?
- 今の実装とすり合わせできる?
- 実装の想像がまだつかない
などなど考え中。