gauche.partcont - 部分継続 ¶Gaucheは内部的に、部分継続(限定継続と呼ばれることもあります)を ネイティブでサポートしています。このモジュールはその機能を 一般的に使えるように公開するものです。
註: 部分継続はふたつのオペレータ、resetとshiftを使います。
これらは元の論文で導入された名前ですが、既に用語として定着した感があります。
ライブラリ関数名としては一般的に過ぎる名前なので、よりわかりやすい名前を
つけようかとも考えたのですが、部分継続を話題にする際にはこれらの用語が
使われるのが普通なので、最終的にこの名前をキープすることにしました。
プログラム中で他の識別子とぶつかったり紛らわしい場合は、モジュールのimport
時に:prefixインポート指示子(モジュールの使用参照)を
次のように使うと良いでしょう。
;; Add prefix pc: to the 'reset' and 'shift' operators. (use gauche.partcont :prefix pc:) (pc:reset ... (pc:shift k ....) )
{gauche.partcont}
現在の継続を保存し、expr … を空の継続を伴って実行します。
空の継続はshiftオペレータが捕捉する継続の終端になります。
暗黙の限定継続について:
Gaucheは内部的に、reset相当の操作を行う場合があります。
CルーチンがSchemeを継続渡し形式でない方法で呼び出す場合です。
(C APIをご存知の方へ: Scm_EvalRec(), Scm_Apply*Rec(),
Scm_Eval()、およびScm_Apply()が相当する関数です。)
これらの関数はCの呼び出し側へ、値をたかだか1度だけ返すことが期待されています。
Schemeの継続は無限エクステントを持ち、一度返ったルーチンから再び返ることが
あり得るため、こういったC関数とは相性が良くありません。
これらの関数を呼び出す時に、Gaucheは限定継続を自動的に作成します。
例えば、goshのmain関数はSchemeのREPLを
Scm_Eval()を通じて呼び出します。ということは、
REPL全体がresetで囲まれているということです。
従ってresetの外側でshiftを呼び出すと、そのshiftの
継続はREPL全体の継続と同じになります。すなわち、goshが終了するということです。
暗黙の限定継続に気づかないと、この振る舞いにはびっくりするかもしれません。
他に暗黙の限定継続が作られる例をいくつかあげます。
仮想ポートのハンドラ (gauche.vport - 仮想ポート参照)、
writeやdisplayから呼ばれるobject-applyメソッド、
glut-display-funcにより登録されたGUIコールバック
(詳しくはGauche-glのマニュアル参照)などです。
そのような暗黙の限定継続を心配する必要は滅多にありません。Cで実装された 組み込み関数や拡張関数のほとんどは継続渡し形式でSchemeを呼んでいるため、 通常継続も限定継続も制限なく使うことができます。
{gauche.partcont}
この式からもっとも最近のresetにより切り取られた空の継続までの継続を
手続きに包み、それをvarに束縛します。
そしてもっとも近いreset式の継続を伴ってexpr …を実行します。
すなわち、expr …を実行後、その結果の値はもっとも最近のreset
の戻り値を待っている式に直ちに渡されます。
varに束縛されている部分継続が実行されると、それに渡された値は
shiftの戻り値を待っている継続に直ちに渡されます。
その部分継続の実行が終了すると、その結果の値はvarを呼び出した式の
戻り値となります。
{gauche.partcont}
これはshiftのラッパーです。
(shift k expr …)は(call/pc (lambda (k) expr …))
等価です。call/ccと似た形の呼び出し形式の方が便利な場合があるので
用意しました。
さてと… もしあなたが、継続の国の血を引く珍しい種族の一員でなければ、 たぶんここまで読んできて、脳みそがこんがらがっていることでしょう。 何が起きているか、厳密ではないが直感的な説明を試みてみます。
手続きAが式Bを呼び出すとします。AがBの戻り値を受け取ってさらに計算を続ける場合、 Bが戻ってからの残りの計算部分をA’として分離することにすれば、全体の制御の流れは 次のように一本の鎖で表現できるでしょう。
A -> B -> A'
A -> Bは手続き呼び出しで、B -> A'は手続きからのリターンですが、
手続き呼び出しとリターンは本質的には同じものでしたね。
Bはその中から別の手続きCをさらに呼び出しているかもしれません。 コードのある部分に着目した場合、そこにある制御の鎖を 次のようにイメージすることができるでしょう。
... -> A -> B -> C -> .... -> C' -> B' -> A' -> ...
魔法の手続きcall/ccは、そのフォームの直後に来る鎖の先頭
(下の図で*で示されている部分)を取り上げて、それを
与えられた手続きに引数として渡すものです (下の図のk)。
従って、kが呼び出されると、制御は直ちに*へとジャンプします。
... -> A -> B -> (call/cc -> (lambda (k) ... ) ) -> B' -> A' -> ...
| ^
\-----------> *
call/ccで難しいのは、制御の鎖の片方しか取り出せないことです。
もう一方、鎖の右側がどこにつながっているのか、コードは知ることができません。
そもそも、鎖の右側に何が来るかは、プログラム全体を知らないとわからないのです。
この、グローバルな性質が、call/ccを扱い辛いものにしています。
resetプリミティブはこの継続の鎖を切断します。
元の鎖 (下の図のxで示される端) は保存され、
reset式の継続自体は宙ぶらりんになります (下の図のoで示される端)。
... -> A -> B -> (reset ... ) -> o
x -> B ' -> A' -> ...
ここでひとつ規則を導入します。制御がoの端に達した場合、
直近に保存されたxの端から制御を再開するとします。
従って、単にresetを挿入するだけでは、目に見える違いは生じません。
resetの中にshiftを挿入したらどうなるでしょう。
resetの内部の鎖にshiftを形式的に挿入してみるとこうなります。
... -> (reset -> X -> Y -> (shift k ... ) -> Y' -> X' ) -> o
実際には次のような動作となります。
shiftは、resetの終端までの仕事の残りの部分を取り出し、
それを変数kに束縛します。
shift自身の継続は、空の継続となります。したがってshiftから抜けると、
shift以降対応するresetまでの操作はスキップされます。
... -> (reset -> X -> Y -> (shift k ... ) ---------> ) -> o
|
\-------> Y' -> X' ) -> o
別の言い方をすれば、resetフォームをひとつの仕事の単位とすれば、
その中のshiftは、その仕事の残りの部分を一時保存して
仕事を中断して戻ってくるのです。
例を見てみます。次に示すwalker引数は、 「手続きと何らかのコレクションを取り、手続きをコレクションの各要素に 適用してゆく」という手続きとします。 walkerの戻り値は無視します。
(define (inv walker)
(lambda (coll)
(define (continue)
(reset (walker (lambda (e) (shift k (set! continue k) e)) coll)
(eof-object)))
(lambda () (continue))))
walkerの典型的な例はfor-eachです。手続きとリストを取り、
リストの各要素に手続きを適用するからです。
for-eachを上のinvに渡すと、for-eachを
裏返した手続きが得られます。どういうことでしょう?
下のやりとりを見てみましょう。
gosh> (define inv-for-each (inv for-each)) inv-for-each gosh> (define iter (inv-for-each '(1 2 3))) iter gosh> (iter) 1 gosh> (iter) 2 gosh> (iter) 3 gosh> (iter) #<eof>
リストをinv-for-eachに渡すと、呼ばれる度にリストの各要素を順に返す
イテレータ手続きが得られます。というのも、iterが呼ばれる度に、
invの中で作られたshiftはリストの残りの部分をたどって行く
という仕事の残りをcontinueに束縛して、現在の要素eを返すからです。
walkerはリストを取る必要はありません。次に示すfor-each-leafは
木を取って、fをペアでない要素に適用してゆく手続きです。
(define (for-each-leaf f tree) (match tree [(x . y) (for-each-leaf f x) (for-each-leaf f y)] [x (f x)]))
これもfor-eachと同じように裏返すことができます。
gosh> (define iter2 ((inv for-each-leaf) '((1 . 2) . (3 . 4)))) iter2 gosh> (iter2) 1 gosh> (iter2) 2 gosh> (iter2) 3 gosh> (iter2) 4 gosh> (iter2) #<eof>
util.combinationsモジュール (util.combinations - 組み合わせ参照) には、
コレクションの全ての並べ替えに対して与えられた手続きを呼び出す手続きがあります。
それをinvに渡せば、呼ばれる度に並べ替えを返す手続きが得られます。
gosh> (define next ((inv permutations-for-each) '(a b c))) next gosh> (next) (a b c) gosh> (next) (a c b) gosh> (next) (b a c) gosh> (next) (b c a) gosh> (next) (c a b) gosh> (next) (c b a) gosh> (next) #<eof>