kahua.partcont

[module] kahua.partcont

部分継続(partial continuation)を実装するモジュールです。

部分継続は、アプリケーションサーバの中でcall/ccのように暗黙の継続を捕捉したい場合に役立ちます。例えば、

深い再帰の途中でそれまでの結果をユーザに見せたい
長い計算を一度中断してユーザに継続するかどうかを問い合わせたい

といったような場合です。

ここで、残念ながらcall/ccを直接使うことはできません。アプリケーションサーバ内でcall/ccを使って捕捉した継続は、その将来の計算全てを含みます。すなわち、「call/ccから戻って、ページを組み立てて、そのページを現在クライアントとつながっているポートへと送り出す」ということです。

仮に、残りの計算をこのような継続に包み込んだ上で、現在までの途中結果をページに組んでユーザに見せたとしましょう。そのページはクライアントとつながっているポートを通じて、クライアントへと送られ、ユーザの手元に表示されます。

ユーザがその計算の続きを要求すれば、その要求はhttpに乗ってkahuaサーバへと送られ、そこで先程捕捉しておいた継続が再開されます。捕捉されていた残りの計算が行われ、ページが組み立てられて、そのページがポートを通じて... ちょっと待って。この継続から参照されているポートは、先程のリクエストに対してリプライを返すためのポートです。既にそのリプライは終わっており、ポートは閉じられているのです。ユーザは新たに接続したポートで残りページを待っています。先程捕捉した継続は、その「新たなポート」のことを知りません。

これは、call/ccが、その時点から全ての未来の計算を捕捉してしまうために起こる問題です。kahuaサーバの計算過程にとっては、ユーザへのリクエストとリプライという部分はいわば「縁の下」の話であって、つかまえたい継続というのは「計算の続きをやって、ページを作る」ところまででいいのです。

部分継続を使うことで、この問題は素直に記述できます。

部分継続には、二つのプリミティブがあります。

[macro] reset/pc expr

このマクロは、部分継続の「出発点」をマークするプリミティブです。継続をマークした後に、式exprを評価します。

「継続をマークする」ということが何を意味するかは今は置いておいて、exprの評価が進んで結果が返って来た時の制御の流れをイメージして下さい。2つの制御ポイントに注目します。

exprから、制御が戻って来て、reset/pcがそれを受け取る
reset/pcが、自身を呼び出した式へと制御を返す

expr中に、以下に述べるcall/pcプリミティブが無かった場合、この制御は素直に流れます。すなわち、exprからの戻り値をreset/pcが受け取り、それをそのまま呼び出した式へと渡します。

[procedure] call/pc proc

直前のreset/pcまでの部分継続kを作成し、それを引数としてprocを呼び出します。procの継続は直前のreset/pcの継続になります。

...と書いてもイメージが湧かないので、もうすこし具体的に説明してみましょう。 procは1引数の手続きなので、直接procをlambdaで書けばこんなふうになります。

  (call/pc (lambda (k) body ...))

body ... を素直に実行して最後まで到達したら、この式はreset/pcから返る(reset/pcの第2の制御点にlongjmpする、という感じです)
部分継続 k を呼び出すと、それはcall/pcから返ります。そのあと計算を続行して、reset/pcの第1の制御点、つまりexprからreset/pcに戻るところで、kの呼び出しから戻って来ます。

通常はkをbody内で末尾呼び出しにしておいて、kから戻ったところでreset/pcから戻るようにしておきます。

ポイントは、reset/pc以降の計算の継続と、kからreset/pcまでの継続が切り離されていることです。

kahua.serverモジュールは、アプリケーションサーバからアプリケーションコードを呼び出す直前にreset/pcで継続をマークしています。したがって、アプリケーションコードの中では、call/ccを使うかわりにcall/pcを使って、アプリケーションロジック内で閉じた継続を捕まえることができます。クライアントとの接続やデータベースとの接続といったものはreset/pcの外側で行われるため、call/pcで捕捉した継続の中には含まれません。

部分継続の使用例としては、Kahuaディストリビューション中にある examples/nqueen/ 等を参照して下さい。

[macro] let/pc k body ...

 (call/pc (lambda (k) body ...))

の簡略版です。

なお、このモジュールの実装は、下の論文を参考にしています。

Martin Gasbichler and Michael Sperber: Final Shift for Call/cc: Direct Implementation of Shift and Reset, ICFP 02, October 2002. http://citeseer.ist.psu.edu/gasbichler02final.html

この論文では、基本的なオペレータはreset, shiftと呼ばれています。基本的に

  (reset expr) == (reset/pc expr)
  (shift k expr) == (call/pc (lambda (k) expr))

ですが、reset/pc, call/pcは多値も扱えます。

Kahua Release

kahua-web Release

Security Advisory

Event Log

Documentation

For developers

Site info

Related Site

[module] kahua.partcont

[macro] reset/pc expr

[procedure] call/pc proc

[macro] let/pc k body ...