この文書について
これはCommunity Scheme Wikiで公開されているcomposable-continuations-tutorial(2010年09月30日版)の日本語訳です。
誤字脱字・誤訳などがありましたらコメントあるいはメールで御指摘いただけると幸いです。
本訳は原文のライセンスに基づきCreative Commons Attribution-ShareAlike 2.0 Genericの下で公開されます。
Original text: Copyright© 2006-2010 Community Scheme Wiki
Japanese translation: Copyright© 2011 SATOH Koichi
本文
部分継続(Composable continuation)は継続区間を具象化することで制御を逆転させるものです。 ウンザリするほど複雑な概念を表す長ったらしいジャーゴンのように聞こえますが、実際はそうではありません。今からそれを説明します。
reset
とshift
という2つのスペシャルフォームを導入するところから始めましょう[1]。
(reset expression)
は特別な継続を作るなりスタックに目印を付けるなりしてからexpression
を評価します。簡単に言えば、expression
が評価されるとき、あとから参照できる評価中の情報が存在するということです。
実際にはshift
がこの情報を参照します。(shift variable expression)
は目印のついた場所、つまりreset
を使った場所にジャンプし、その場所からshift
を呼び出した場所までのプログラムの断片を保存します; これはプログラムの区間を「部分継続」として知られる組み合わせ可能な手続きに具象化し、この手続きにvariable
を束縛してからexpression
を評価します。
組み合わせ可能(Composable)という語はその手続きが呼び出し元に戻ってくるため、他の手続きと組み合わせられることから来ています。
Composable continuationの別名として例えば限定継続(Delimited continuation)や部分継続(Partial continuation)もありますが、ここでは一貫して「組み合わせ可能」という用語を使います(訳注: 日本語では「部分継続」が訳語としてメジャーなので、この語を用いることにします)。
組み合わせ可能という特性はcall-with-current-continuaton
が生成する「脱出継続」と違う部分です。
脱出継続は戻ってきません——というより、制御をプログラムの別の場所に戻す効果があります——が、部分継続は戻ってきます。
部分継続を呼び出すと、制御をshift
が呼ばれた場所に戻します。
しかしreset
に渡された式が評価された位置に制御が続けて戻るときは、reset
が呼ばれた位置に戻るのではなく、部分継続手続きが呼び出された位置に戻るのです!
別の説明としてコード変形を示してみます[2]:
(reset (...A... (shift V E) ...B...))
; -->
(let ((V (lambda (x) (...A... x ...B...))))
E)
(reset E)
; -->
E
一連の例が意味を理解するのに役立つでしょう。
まず最初に、shift
がない(reset expression)
は末尾再帰を考えなければexpression
の評価と同じです。
(+ 1 (reset (+ 2 3)))
;Value: 6
(cons 1 (reset (cons 2 '())))
;Value: (1 2)
次にshift
を加えます。shift
で作られた部分継続を呼び出さなければ、shift
は自身とそれを動的スコープで内包しているreset
の間の一切を捨てる効果があります。
(+ 1 (reset (+ 2 (shift k
;; Kは無視
3))))
;Value: 4
(cons 1 (reset (cons 2 (shift k
;; kは無視
(cons 3 '())))))
;Value: (1 3)
問題: もし(reset ... shift)
内でk
を適用したらどうなるでしょう?
次に部分継続を使ってみましょう。これは(lambda (x) (+ 2 x))
や(lambda (x) (cons 2 x))
と同じになります; これはreset
に渡した式のshift
呼び出しをすべて引数x
で置き換えた1引数関数を作ることで確認できます。これこそが「制御の逆転」の意味するところです: プログラムの評価の一部が関数として具象化されているのです。
(+ 1 (reset (+ 2 (shift k
(+ 3 (k 4))))))
; -->
(+ 1 (let ((k (lambda (x) (+ 2 x))))
(+ 3 (k 4))))
; -->
(+ 1 (+ 3 (+ 2 4)))
;Value: 10
(cons 1 (reset (cons 2 (shift k
(cons 3 (k (cons 4 '())))))))
; -->
(cons 1 (let ((k (lambda (x) (cons 2 x))))
(cons 3 (k (cons 4 '())))))
; -->
(cons 1 (cons 3 (cons 2 (cons 4 '()))))
;Value: (1 3 2 4)
さらに、部分継続は複数回呼び出すこともできます; プログラムの一部を実行する単なる関数であり、何度も同じ部分を実行することができます。
(+ 1 (reset (+ 2 (shift k
(+ 3 (k 5) (k 1))))))
; -->
(+ 1 (let ((k (lambda (x) (+ 2 x))))
(+ 3 (k 5) (k 1))))
; -->
(+ 1 (+ 3 (+ 2 5) (+ 2 1)))
;Value: 14
(cons 1 (reset (cons 2 (shift k
(cons 3 (k (k (cons 4 '()))))))))
; -->
(cons 1 (let ((k (lambda (x) (cons 2 x))))
(cons 3 (k (k (cons 4 '()))))))
; -->
(cons 1 (cons 3 (cons 2 (cons 2 (cons 4 '())))))
;Value: (1 3 2 2 4)
これらの例は多分恣意的で、実用的ではないように見えるでしょう。実際これらの例は恣意的ですが、その目的はshift
とreset
を簡潔な方法で説明するところにありました。
式変形は手作業で行うこともできますが、shift
とreset
の威力は全体的なコード変形を必要としない点にあります。
shift
とreset
は抽象の境界を越えて、字句的に手が届かないスコープの動的な制御をも逆転させることができます; つまり、部分継続はプログラムの様々な点を把握せずとも、その一部を関数に詰め込むことができるということです 。
もっと洗練された例を挙げましょう。for-each
のような手続があったとして、for-each
やその類の手続が受け付けるようなコレクションを受け取ってその要素の遅延ストリームを返す手続を作りたいとします。これはcall-with-current-continuation
3つとset!
を使って作ることができます。胃腸や心臓が弱い方は見ないほうが良いでしょう。
(define (for-each->stream-maker for-each)
(stream-lambda (collection)
(call-with-current-continuation
(lambda (return-cdr)
(for-each
(lambda (element)
(call-with-current-continuation
(lambda (return-to-for-each)
(return-cdr
(stream-cons element
(call-with-current-continuation
(lambda (return-next-cdr)
(set! return-cdr return-next-cdr)
(return-to-for-each))))))))
collection)
(return-cdr stream-null)))))
明らかにこれは不細工です。コードが入れ子の深みに降りていくのに合わせてインデントが素敵なスロープを描いていますが、このコードを考えているときに思い浮かぶことは優雅さという概念についての考えだけでしょう。
しかしながら、このパターンはshift
とreset
が抽象化しているものによく似ています。
return-cdr
はreset
で評価される式の継続を表しています; これにはコレクションを走査する間、連続した出力ストリームのcdr
を返すためにreturn-next-cdr
が代入されます。shift
同様、保存しておきたいプログラムの一部に入った時点で継続を具象化―—return-to-for-each
——し、次のreset
する位置、つまりreturn-cdr
に脱出しています。
保存した一部を使いたくなったら、あたかも部分継続を呼び出すように継続——これはストリームが次に返すcdr
の継続——をreturn-next-cdr
として具象化し、それをreturn-cdr
に代入してプログラムの一部が次にどこに戻れば良いか分かるようにしてから、return-to-for-each
を呼び出してプログラムの一部をもう一度実行しています。
これはshift
とreset
を使ってもっとずっと簡単に表現できます:
(define (for-each->stream-maker for-each)
(stream-lambda (collection)
(reset (begin
(for-each (lambda (element)
(shift k
(stream-cons element (k))))
collection)
stream-null))))
脚注
[1]
スペシャルフォームの代わりに(reset thunk)
と(shift receiver)
という手続きを使うこともできますが、簡潔さとカラム幅、それから一般的な使い方で一行に収まるようにそうしませんでした。
control
とprompt
——このページのほとんどの例で同じ結果になるもう一対のよく知られた制御演算子——もあることを覚えておいて下さい。
[2]
この変形は厳密には正しくありません、本当はもう少しreset
を置く必要があります。
詳細はこの文書の範囲から外れる上、入れ子になったshift
とreset
を使うときしか関係のないことです。
が、完備性のため、必要ならここに完全な変形を示しておきます:
(reset (...A... (shift K E) ...B...))
; -->
(let ((K (lambda (x) (reset (...A... x ...B...)))))
(reset E))
(reset E)
; -->
E
(ラムダ式の内側のreset
だけがshift
/reset
演算子とcontrol
/prompt
演算子の相違点です)
実装
Riastradh氏によるshift
とreset
の実装はcall-with-current-continuation
に基づいており、非常に重く実用には低速ですが、可搬性があります。
Oleg氏によるバージョンは継続が必要とする部分だけをキャプチャするのにトランポリンを使っています。これはメモリリークがないという利点を持ちますが、このトランポリンは「空の」継続の中に置くべきで、また期待する動作のためにcall/cc
を変更する必要があります。
PLT Scheme(訳注: Racketに改名しています)のscheme/control
ライブラリにはshift
/reset
やその他多数の制御演算子が論文へのリンク付きで収録されています。
GasbichlerとSperber両氏による論文「Final Shift for Call/cc: Direct Implementation of Shift and Reset」は様々な実装技術の詳細を掘り下げています(Sperber氏のオンラインで公開されている論文)。
コメント
コメントを投稿