部分継続について本気出して考えてみた
以前何度か部分継続について書いたことがあるんですが、当時は表面的な振る舞いを観察して何となく分かった気になった程度の拙い説明しか出来ませんでした。
その上、最近のプログラミングでもほとんど活用しておらず、改めて理解し直す必要を感じてきた次第です。
そこで今回は、部分継続の概念的な理解を目指し、基礎的な事柄を中心にまとめていきたいと思います。
基本的に PLT Scheme (MzScheme) の評価モデルに即して書いていくため、Scheme 一般に当てはまる話になっていない部分もあるかも知れません。その点ご了承ください。
Redex と継続
Scheme の評価モデルにおいて、
(+ 1 (+ 2 0))
という式を評価するとき、まず
(+ 2 0)
の部分が評価され、その結果の値に対して
(+ 1 [])
という残りの計算が行われます。
ここで角括弧で示した部分を reducible expression (redex) と言います。簡約 (単純化) 可能な式、という意味です。そして、もうそれ以上簡約できないところまで簡約を続けて値を得ることを「評価」と呼ぶわけです。
一方、角括弧を包む「残りの計算」の部分を「継続」と言います。
つまり、redex のある所には常に継続があるのです。両者が対概念と言うか、相補的な関係にあるものだということが分かりますね。
この redex と継続という、プログラムの評価中に当然に存在して、なおかつ分かちがたく合わさっているもののうち、継続を第一級オブジェクトとして取り出すのが Scheme の call/cc 関数です。
継続は関数なり
ここで
(+ 1 [])
という継続の意味を考えてみましょう。
角括弧で示された穴の部分には、何らかの値 (数値) が入ることが期待されます。そこで継続を、この穴の前後の文脈だと考えることができます。
しかし別の見方をすると、この「文脈」は、値を与えられるとそれに応じて値を返す働きをするわけですから、数学的な意味での関数そのものであるとも言えますね。
したがって、これは本質的に
(lambda (x) (+ 1 x))
という関数に等しいと考えられるわけです。
普通の継続と合成可能な継続
call/cc に触れる前に、MzScheme の プリミティブである call-with-composable-continuation 関数を紹介しておきます。
> (define c #f)
> (+ 1 (+ 2 (call-with-composable-continuation
(lambda (k)
(set! c k)
0))))
3ここで、call-with-composable-continuation を呼び出した位置がちょうど redex の位置で、それを包む式が継続ということになります。この場合は
(+ 1 (+ 2 []))
という文脈が k として返されます (c として保存)。
これに 0 を与えてみると、当然ながら
> (c 0) 3
という値が得られることになります。
また、c の呼び出しの外側を別の式で包むと
> (+ 1 (c 0)) 4
となり、さらに続きの計算が行われています。
一方、伝統的な call-with-current-continuation (call/cc) はどうでしょうか？
> (+ 1 (+ 2 (call-with-current-continuation
(lambda (k)
(set! c k)
0))))
3> (c 0) 3
ここまでは同じです。
が、次の式は
> (+ 1 (c 0)) 3
となります。c を呼び出した時点で脱出が起こるため、この式における継続そのものは破棄されてしまうんです。
この「脱出」が起こるというのが伝統的な継続の振る舞いであり、脱出を起こさない前者の継続のことは composable continuation と呼びます (他の継続と組み合わせたり、普通の関数と合成することも可能なため)。
もう一度、その非脱出性を確認しておきましょう。
> (+ 1 (+ 2 (call-with-composable-continuation
(lambda (k)
(k 0)))))
6となって、
(+ 1 (+ 2 []))
という計算が、k が呼ばれた場所とその外側で2回行われていることが分かりますね。
部分継続とは
脱出が起こる起こらないという話をしましたが、では起こる場合、一体どこに向かって脱出するのでしょうか？
次の例を見てください。
> (+ 1 (+ 2 (call-with-current-continuation
(lambda (k)
(k 0)))))
3composable の方を使った時は 6 が返ってきた計算ですが、こちらでは k を適用した時点で脱出が起こって、call-with-current-continuation 自体の継続が破棄されているんです。
で、どこに脱出したかということですが、結論から言うと、トップレベルに向かって脱出しています。
しかし、これは裏を返せば call/cc がトップレベルからの継続を捉えていたからだと言えるんです。
実は MzScheme における継続というのは全て部分継続 (delimited continuation) と呼ばれる種類のものです。
部分継続とは、継続全体のうち、プロンプトという特殊な継続フレーム (後述) で delimit された、つまり、区切られた部分のことです (このことから、プロンプトのことをデリミタと呼ぶ流儀もあります)。
上の例では REPL 自体が暗黙的にプロンプトに包まれているので、それと call/cc 呼び出しとの間が部分継続として切り取られていたことになります。
そして、部分継続における脱出というのは対応する (直近の) プロンプトに対して行われるので、この場合は REPL を包んでいるプロンプトに向かって脱出したというわけです。
プロンプトというものを理解するために、明示的なプロンプトを導入して実験してみましょう。
> (require scheme/control)
> (+ 1
(prompt
(+ 2 0)))
3ただ導入しただけでは begin と何の変わりもありません。
脱出してみます。
> (+ 1
(prompt
(+ 2 (abort 0))))
1トップレベルではなく prompt の位置までの脱出なので、その先の継続はちゃんと評価されていますね。
当然ながら prompt を外すと
> (+ 1
(+ 2 (abort 0)))
0となります。
また、
> (define c #f)
> (+ 1
(prompt
(+ 2
(call-with-current-continuation
(lambda (k)
(set! c k)
0)))))
3c は prompt までの継続なので、その外側の継続は入っていません。ゆえに、
> (c 0) 2
となります。
継続フレーム
MzScheme において継続は、継続フレームという構成単位の連続として実装されています。
通常の評価過程においても継続フレームは増えたり減ったりしているんですが、これを明示的に操作することで、部分継続やエラー処理などの応用的な制御構造が作られるのです。
プロンプトというのも継続フレームの一種で、プロンプト・タグという目印によって、部分継続を切り取る際の区切りを示します。
また、現在の継続を任意のプロンプトに置き換えると、その時の続きの計算は破棄され、制御がプロンプトの位置に移ります。これが脱出のメカニズムというわけです。
基本的な制御オペレータ - prompt/control, reset/shift
いちいち call-with- なんちゃらとタイプするのは面倒なので、MzScheme ではプロンプトの設定や継続の取り出しのためのオペレータが scheme/control ライブラリで提供されています。
既にその内 prompt と abort を使ったんですが、さらに幾つか例を示していくのでぜひ慣れていってください。
> (+ 1 (prompt (+ 2 (control k 0)))) 1
control で部分継続 (k) を取り出している例です。このように prompt で区切られた部分継続は control で捕捉するのが通例となっています。
control の呼び出しにより、部分継続が取り出されると同時に control 式本体の継続がプロンプトに移ります (つまり、脱出します)。
ここでは 2 を加える計算を取り出したわけですが、使わずに捨てているので単に abort したのと同じです。
k を使うと
> (+ 1 (prompt (+ 2 (control k (k 0))))) 3
となります。
繰り返し適用することもできます。
> (+ 1 (prompt (+ 2 (control k (k (k 0)))))) 5
これは脱出を伴う call/cc では出来ないんでしたね。
> (+ 1 (prompt
(+ 2 (call-with-current-continuation
(lambda (k)
(k (k 0)))))))
3最初に k を適用したところで脱出が起こるためです。
control の場合、あくまでも control の呼び出しにおいて脱出が起こるだけで、取り出された k 自体は脱出を起こさない、composable な継続だということが分かります。
次に、独習 Scheme のツリー・マッチングの問題を解いてみましょう。
prompt/control と似たペアで、reset/shift というのを使います。
(define (tree->generator t)
(reset
(let loop ((t t))
(cond ((not (list? t))
(shift k (cons t k)))
((pair? t)
(loop (car t))
(loop (cdr t)))
(else #f)))))リーフの列挙関数が既に存在した場合は、このように定義することもできます。
(define (tree->generator t)
(reset
(for-each-leaf (lambda (x)
(shift k (cons x k)))
t)
;; Mark the end of traversal
#f))すっきりしましたね。いずれにしてもループが回っている途中の状態が k として取り出され、リーフの値と共に外に放出されます。
shift が一時停止ボタン、k が再生ボタンと考えると分かりやすいかも知れません。取り出されたデータを保存しておいて、(それこそトイレ休憩をはさみつつ) REPL で手作業で回していくことだって可能です。
ループが回りきると #f が返り、終了が通知されます。
(define (same-fringe? t1 t2)
(let loop ((x (tree->generator t1))
(y (tree->generator t2)))
(or (not (or x y))
(and x y (eqv? (car x) (car y))
(loop ((cdr x) 'next)
((cdr y) 'next))))))> (same-fringe? '(1 2 3 4 5)
'(1 (((2 ((3)))) (4 (((5)))))))
#t
ちなみに。tree->generator を再掲しますが
(define (tree->generator t)
(reset
(let loop ((t t))
(cond ((not (list? t))
(shift k (cons t k)))
((pair? t)
(loop (car t))
(loop (cdr t)))
(else #f)))))これは深さ優先探索のアルゴリズムを実装したものです。ところが、これにちょっとした変更を加えるだけで、幅優先バージョンが作れてしまうんです (Biernacki et al.)。
(define (tree->generator/bf t)
(reset
(let loop ((t t))
(cond ((not (list? t))
(shift k (cons t k)))
((pair? t)
(control k
(k #f)
(loop (car t))
(loop (cdr t))))
(else #f)))))pair? の節に2行加えただけですよ。
では確かめてみましょう。
> (define (gen-for-each f g)
(when g
(f (car g))
(gen-for-each f ((cdr g) #f))))
> (define t '(1 (((2 ((3)))) (4 (((5)))))))
> (gen-for-each (lambda (x)
(display x) (newline))
(tree->generator t))
1
2
3
4
5
> (gen-for-each (lambda (x)
(display x) (newline))
(tree->generator/bf t))
1
2
4
3
5これはかなり凄いことなんじゃないでしょうか？
control と shift の違い
control で部分継続を捕捉する時は prompt で区切りを設定、shift を使うときは reset で、という風に、決まった組み合わせで使うのが慣例となっているんですが、実は prompt と reset は同じものの別名に過ぎません。
一方 control と shift は、次のような等式が成り立つ関係にあります。
(shift k k) = (control k (lambda (x) (prompt (k x))))
つまり shift は、k が適用される時にその場にプロンプトを設定するという性質があるんです。
以下の例でその効果の違いを見ることができます。
> (reset
(for-each (lambda (x)
(shift k
(cons x (k 'next))))
'(1 2 3))
'())
(1 2 3)
> (prompt
(for-each (lambda (x)
(control k
(cons x (k 'next))))
'(1 2 3))
'())
(3 2 1)いずれの場合も、k が for-each ループを最後まで回して、その先にある空リストを捉えるという動作をする点では同じです。
ではなぜ結果が異なるのか、それを理解するために、評価ステップを書き出してみましょう。
reset/shift を使った方は
(reset
(for-each (lambda (x)
(shift k
(cons x (k 'next))))
'(1 2 3))
'())
(reset
(cons 1
((lambda (v)
(reset
(for-each (lambda (x)
(shift k
(cons x (k 'next))))
'(2 3))
'()))
'next)))
(reset
(cons 1
(reset
(for-each (lambda (x)
(shift k
(cons x (k 'next))))
'(2 3))
'())))
(reset
(cons 1
(reset
(cons 2
((lambda (v)
(reset
(for-each (lambda (x)
(shift k
(cons x (k 'next))))
'(3))
'()))
'next)))))
(reset
(cons 1
(reset
(cons 2
(reset
(for-each (lambda (x)
(shift k
(cons x (k 'next))))
'(3))
'())))))
(reset
(cons 1
(reset
(cons 2
(reset
(cons 3
((lambda (v)
(reset
(for-each (lambda (x)
(shift k
(cons x (k 'next))))
'())
'()))
'next)))))))
(reset
(cons 1
(reset
(cons 2
(reset
(cons 3
(reset
(for-each (lambda (x)
(shift k
(cons x (k 'next))))
'())
'())))))))
(reset
(cons 1
(reset
(cons 2
(reset
(cons 3
(reset '())))))))のようになります。
冒頭の継続と redex の議論でいくと、redex の位置に継続が埋め込まれていくという、逆のことが起こっているようにも見えますね。
ここで重要なのは、ループごとに次の shift の脱出先が設定されているということです。言い換えると、ネストする shift の呼び出しにおいて、先行する shift で区切られた領域を後続の shift は超えられないようになっているのです。
この性質が、ローカル変数で言うところのレキシカル (静的) スコープに似ているということから、shift のことを静的な制御オペレータと呼ぶ場合があります。
後者では、ループ毎に同じ prompt の位置に脱出しますから cons の呼び出しが常に左側に積み上がっていくことになります。
(prompt
(for-each (lambda (x)
(control k
(cons x (k 'next))))
'(1 2 3))
'())
(prompt
(cons 1
((lambda (v)
(for-each (lambda (x)
(control k
(cons x (k 'next))))
'(2 3))
'())
'next)))
(prompt
(cons 1
(let ()
(for-each (lambda (x)
(control k
(cons x (k 'next))))
'(2 3))
'())))
(prompt
(cons 2
((lambda (v)
(cons 1
(let ()
(for-each (lambda (x)
(control k
(cons x (k 'next))))
'(3))
'())))
'next)))
(prompt
(cons 2
(cons 1
(let ()
(for-each (lambda (x)
(control k
(cons x (k 'next))))
'(3))
'()))))
(prompt
(cons 3
((lambda (v)
(cons 2
(cons 1
(let ()
(for-each (lambda (x)
(control k
(cons x (k 'next))))
'())
'()))))
'next)))
(prompt
(cons 3
(cons 2
(cons 1
(let ()
(for-each (lambda (x)
(control k
(cons x (k 'next))))
'())
'())))))
(prompt
(cons 3
(cons 2
(cons 1
'()))))やはりここでも shift と同様の議論が成り立って、ネストする control 呼び出しにおいて1つの領域が共有される点が、変数の動的スコープ (dynamic extent) に似ているということで、control のことを動的な制御オペレータと呼びます。
その他のオペレータ
プロンプトを毎回新たに設定する・しないという話をしましたが、実はさらに、直前に設定されたプロンプトを保つ・保たないというバリエーションもあり得るんです。このことから、次の4つのオペレータの組を得ることができます (Shan)。
- reset/shift
- prompt/control
- reset0/shift0
- prompt0/control0
後の2組がプロンプトを保たないバージョンです。
例えば前節の例で reset0/shift0 を使うと
(reset0
(for-each (lambda (x)
(shift0 k
(cons x (k 'next))))
'(1 2 3))
'())経過は略しますが
(cons 1
(cons 2
(cons 3
(reset '()))))のように評価され、結果的には同じリストが作られます。ただ、プロンプトが消えてしまうため、shift のような静的な性質は完全には保たれないことになります。
まぁ、このことに一体どんな便利な応用があり得るのかは、まだ良く分かっていない (研究されていない) んじゃないかと思います。
ただ、プロンプトを除去することが、保つことに比べて効率的だという実装面での理由があれば、このように結果が変わらない場合には 0 のバージョンを選択できる、という点ではメリットと言えるかも知れません。
[追記]
reset0/shift0 の用例を1つだけ思い付きました。Zipper というデータ構造の基本的なイテレーション関数 (fold-zipper) があるんですが、これを reset0/shift0 で定義しておくと
(define (fold-zipper kons knil zipper)
(reset0
(traverse-zipper (lambda (zipper)
(shift0 k (kons zipper (k #f))))
zipper)
knil))それに基づく関数で簡単に値の取り出し (脱出) が出来るようになるんです。
(define (find-zipper p? zipper)
(reset0
(fold-zipper (lambda (zipper _)
(and (p? (zipper-node zipper))
(shift0 k zipper)))
#f
zipper)))これは reset/shift を使用した場合は無理です。そう考えると結構便利ですよね。認識不足でした。
参考文献
PLT Scheme Reference:
1.1 Evaluation Model
9.4 Continuations
Shan, Chung-chieh. Shift to Control
Biernacki, Dariusz., et al. On the Dynamic Extent of Delimited Continuations
