継続渡し形式
階乗factから始めましょう。
;; 階乗の普通の定義
(define (fact n)
(if (= n 0)
1
(* n (fact (- n 1)))))
上記の階乗factの定義は
- 引数nが0なら1を返す(基底条件)
- それ以外ならn-1の階乗にnを掛けたものを返す(再帰条件)
となっています。
これをfactから直接値を返すのではなく、
返すべき値を継続手続きと呼ばれるものに渡します。
継続手続き自体は特別な関数ではありません。
単に、本来返り値を返すところで、その手続きに「あとはよろしく」と
残りの処理を委ねてしまいます。
そういう使い方をされる手続きのことです。
;; 継続渡し形式の階乗の定義
(define (fact/cps n cont)
(if (= n 0)
(cont 1)
(fact/cps (- n 1) (lambda (a) (cont (* n a))))))
factとfact/cpsは何が違うのでしょうか?
あるいは、どういう関係にあるのでしょう?
例えば、
(* 2 (fact 10))
という計算は、fact/cpsを使えば次の式と等価です。
(fact/cps 10 (lambda (a) (* 2 a)))
最初のfact式の例で(fact 10)式の返り値を待ち受けている処理(続きの計算)は
(lambda (a) (* 2 a))で表現できるもの(返り値aをもらって2倍する処理)で、
それが、fact/cpsにとっての継続手続きになっています。
なんだ、やってることは同じじゃないか?と思われれば、
継続渡し形式はとりあえず理解できたと思って良いでしょう。
ただ、継続渡し形式では続きの計算を引数として渡しているので、
cont1 cont2 ... という具合に複数の続きの計算を渡すことが可能です。
例えば、
;; 除算
(define (divide num den)
(/ num den))
この様に除算を定義するところを、以下の様に複数の継続手続きを渡せます。
;; 継続渡し形式の除算
(define (divide/cps num den pass fail)
(if (= den 0)
(fail num den pass fail)
(pass (/ num den))))
passとfailは共に継続手続きです。
次の様な使用方法が考えられるでしょう。
;; 非零の分母要求する除算
(divide/cps 10 0
(lambda (a) (format #t "answer is ~a~%" a))
(lambda (n d p f)
(format #t "> ")
(flush)
(divide/cps n (read) p f)))
これは分母が0である内はプロンプトを出して入力を促し、
非零の入力を受けとると除算を行って、
答を"answer is ..."という形式で表示してくれます。
passを成功継続、failを失敗継続と呼ぶことがありますが、
3つ以上の継続手続きを渡すことも可能なのはあきらかです。
それともう一つ、継続渡し形式で書けば、現在実装中の関数(今の場合階乗fact)が、
どういう形で結果を返すのが良いかの設計を遅らせることが出来ます。
最終的に印字させることにしたのなら、
;; 結果の印字出力
(fact/cps 10 (lambda (a) (format #t "answer is ~a~%" a)))
とすればいいし、そのまま返すだけであれば、
継続手続きとしてidentity(つまり(lambda (a) a))を渡すだけです。
;; fact/cpsでfactを定義
(define (fact n)
(fact/cps n identity))
call/ccは普通の関数
[[Scheme]]にはcall/ccという呪文があって、
大域脱出だの例外機構だのマルチスレッドさえ実装できる。
とんでもなく柔軟な制御を可能にするらしい。
そう聞いてネット上のドキュメントを漁った方も多いのではないでしょうか。
しかし、call/ccは決して怪しい動作をするものではなく、
ある意味、とても普通の関数です。
setjmp/longjmpのように、
ちょっと奇妙なジャンプをするようなものという先入観もこの際捨ててしまいましょう。
まず、このことを理解してもらうために、call/ccなどと省略せずに、
call-with-current-continuationという正式名称に注目しましょう。
きっと意識してなかった人も居るんじゃないでしょうか。
[[Scheme]]でファイルの入出力をしたことのある人なら
この名前の先頭についているcall-withというprefixを見てピンとくるでしょう。
そう、call/ccは他に類を見ない孤独で特殊な存在なんかではなく、
良く見かけるcall-with系関数の仲間なんです。
call-with系関数
いくつか具体的な関数を紹介して感覚をつかんでもらえればよいでしょう。
まず、あるファイルから読み込みを行う時に使う関数です。
;; call-with-input-fileの使用例
(define (count-chars file-name)
(call-with-input-file file-name
(lambda (in)
(let loop ((c (read-char in))
(count 0))
(cond ((eof-object? c) count)
(else (loop (read-char in) (+ count 1))))))))
count-charsは引数として渡された文字列をファイル名とみなして、
そのファイルをオープンして一文字ずつ読み込み、文字数をカウントしています。
注目してもらいたい関数はcall-with-input-fileです。
この関数は、
- 第一引数のファイルをオープンして、入力ポートを作り出す。
- 入力ポートを引数にして第二引数の手続きを呼び出す。
という処理を行っています。
このcall-with-input-fileの処理はキモだけを抽出すると、次のコードになります。
;; とんでもなく杜撰なcall-with-input-fileの実装(コアのみ)
(define (call-with-input-file file-name proc)
(proc (open-input-file file-name)))
つまり、call-with-input-fileは
ファイルから入力ポートを作り出し、それを渡してprocをcallする
という関数なのです。
call procedure with input fileという感じでしょうか。
実際にはclose-input-portで使い終わった入力ポートの後始末をする必要がありますが、
ここでは省略しています。
call-with-input-fileが別のprocedureをcallする、
という流れだけ理解してください。
要はfileをopenしたりcloseしたりのお膳立て(あるいは環境整備)はするけど、
自分では何も処理せずに、procedureにやらせるだけです。
では、出力の場合も見ておきましょう。
;; call-with-output-fileの使用例
(define (write-message file-name)
(call-with-output-file file-name
(lambda (out)
(format out "I'm Schemer")
(newline out)
(flush out))))
やはり注目してもらいたいのは、call-with-output-fileの使い方です。
- 第一引数のファイルをオープンして出力ポートを作り出す。
- 出力ポートを引数にして第二引数の手続きを呼び出す。
すでに説明したcall-with-input-fileと見比べてください。
もちろん処理の方もほとんど同じで次の様になります。
;; とんでもなく杜撰なcall-with-output-fileの実装(コアのみ)
(define (call-with-output-file file-name proc)
(proc (open-output-file file-name)))
call-with-output-fileもcall procedure with output fileと読めるでしょう。
これも実際にはclose-output-portで使用済みのポートを後始末するべきです。
ここでは代わりに、write-message中でflushすることで書き出していますが、
あくまで簡単にしてキモだけ見てもらうためです。
やはり、call-with-output-fileが別のprocedureをcallしているという
流れだけ理解してもらえれば十分です。
処理系によっては、これ以外にも文字列ポートやソケットなど
多くのcall-with系の関数が標準で提供されているものもありますが、
基本はどれも同じです。
[[Gauche]]であれば、replに対して次の様にすれば仲間が確認できます。
;; call-withのゆかいな仲間たち
gosh> (apropos 'call-with)
call-with-current-continuation (scheme)
call-with-input-file (scheme)
call-with-input-file (user)
call-with-input-string (gauche)
call-with-output-file (scheme)
call-with-output-file (user)
call-with-output-string (gauche)
call-with-string-io (gauche)
call-with-values (scheme)
gosh>
call-with-string-ioの様にprocに入力と出力の2つのポートを渡すものもありますが、
call-with系の関数はprocをcallする関数であるという点では変わりません。
その時にprocに何を渡すかによってバリエーションがあるだけなのです。
call-with-procedure
call-with系の関数は、一般化して言うなら、
fooの素からfooを生成し、procにfooを渡して呼び出す
関数ということになるでしょう。
call-with-input-fileやcall-with-output-fileでは、
fooは入力ポートや出力ポートであり、
「fooの素」は文字列で与えられたファイル名ということになります。
call-with-string-ioならfooは入力ポートと出力ポートの組です。
では、仮にcall-with-procedureという関数を作るとしたら、
どんな風になるかを考えてみましょう。
call-with-procedureという名前からすれば、
procedureの素からprocedureを生成し、procにprocedureを渡して呼び出す
という関数になりますね。
まぎらわしいがprocはcall-with-procedureの第二引数で与えられる手続きです。
procedureは、そのcallされるprocという手続きに渡される引数で、fooにあたります。
ちゃんと区別してください。
まず、procedureの素とは何で表現されるべきでしょうか?
そう。lambda式を使うのが妥当でしょう。
そうすると、次の様に言い換えられそうです。
lambda式からprocedureを生成し、procにprocedureを渡して呼び出す
;; call-with-procedureの実装
(define (call-with-procedure lambda-expr proc)
(proc lambda-expr))
例えばこんな風に使えるようになるでしょう。
;; (* 2 (fact 10))
(call-with-procedure (lambda (a) (* 2 a)) (lambda (p) (p (fact 10))))
もちろん、こんな風に渡されたprocedureそのものを返してもいいですし、
;; 継続手続きを返すのみ
(call-with-procedure (lambda (a) (* 2 a)) (lambda (p) p))
新たに関数合成したものを返してもかまいません。
;; 継続手続きを関数合成して、出来た関数を返す。
(call-with-procedure (lambda (a) (* 2 a)) (lambda (p) (compose p p)))
渡されたprocedureを手続きとして使わなければならない法などありません。
単にリストにして返すことだって一向にさしつかえありません、
;; 継続手続きをリストにして返す
(call-with-procedure (lambda (a) (* 2 a)) (lambda (p) (list p p)))
それどころか、そもそも引数を使わなくても別に文句を言われる筋合いはありません。
;; 継続手続きを使わない
(call-with-procedure (lambda (a) (* 2 a)) (lambda (p) "Hello World!"))
これはcall-with-input-fileやcall-with-output-fileでも言えることで、
渡されたinやoutなどのポートを使わなくたって一向にかまいません。
まるで意味はないですが。
call-with-continuation-procedure
では、もう一歩進めてcall-with-continuation-procedureを定義してみましょう。
;; call-with-continuation-procedureの定義
(define (call-with-continuation-procedure cont proc)
(proc cont))
どうでしょうか?
call-with-procedureと変わらないじゃないかって?
それはその通りです。
すでに説明した通り、継続手続きなんてのはただの関数なんだから当然です。
せいぜいcall-with-continuation-procedureという名前から、
contというlambda式によって生成される手続きが
(リストのメンバや関数合成の素などでなく)
procの中で継続手続きとして使われるんだろう、
と期待できる程度のことでしかないのです。
call-with-current-continuation
では、本題のcall/cc、つまりcall-with-current-continuationに話を移すことにしましょう。
といっても、もうほとんどゴールに辿り着いていますが。
先程説明したcall-with-continuation-procedureは、
継続手続きをプログラマが自分でlambda式として書いています。
(* 2 (fact 10))
この式の部分式である(fact 10)から見ると、(fact 10)式の続きの計算は
(lambda (a) (* 2 a))になります。
それを継続手続きとして渡してやると考えれば、
;; (* 2 (fact 10))
(call-with-continuation-procedure (lambda (a) (* 2 a))
(lambda (cont) (cont (fact 10))))
こんな風に書けることになります。
(fact 10)の続きの計算を手動で作成している点が面倒ですが、
このレベルならまだ書けなくはないでしょう。
仮に、factがすでに定義済みなら、この式はfact/cpsの定義にできます。
;; fact/cpsをcall-with-continuation-procedureを使って定義する
(define (fact/cps n cont)
(call-with-continuation-procedure cont (lambda (c) (c (fact 10)))))
ここまでは分かってもらえたでしょうか?
さて、続きの計算はいたるところにあります。
あらゆる評価の時点において、その続きの計算というものが存在します。
しかし、その時点を特定すれば、
続きの計算は自動的に(一意に)決まることになります。
今の例で言えば、(fact 10)式の評価の時点において、
その続きの計算、すなわち継続は(lambda (a) (* 2 a))となります。
だとすれば、現在の継続に限定するなら、
プログラマが第一引数のlambda式を書く必要などないはずです。
(* 2 (call-with-continuation-procedure (lambda (* 2 a))
(lambda (cont) (cont (fact 10)))))
と書く代わりに、call-with-continuation-procedure式の返りを待っている
続きの計算、つまり(lambda (a) (* 2 a))を自動的に取り出し、
call-with-continuation-procedureの第一引数に渡してもらえれば簡単になります。
それが、call-with-current-continuation、いわゆるcall/ccなのです。
つまり、call/ccではこうなります。
(* 2 (call/cc (lambda (cont) (cont (fact 10)))))
contには(lambda (a) (* 2 a))が渡ってくると考えられますね。
fooの素に相当する現在の継続の素を改めて書く必要はなくなりました。
;; call/ccの継続渡し形式への書き換えを試みてみる
(* 2 ((lambda (cont) (cont (fact 10)))
(lambda (a) (* 2 a))))
しかし、よくよく考えると、(* 2 ...)式の続きの計算はどうなるのでしょう?
厳密に考えれば、read-eval-print-loopがあるはずですから、
次のread-eval-printが延々待ってるハズです。
これは以降の説明でも重要な点で、無視できないので仕方がありません。
PRINT-AND-NEXT-REPLというものを便宜的に持ち込むことにしましょう。
というわけで、次のようにすることにします。
;; call/ccの継続渡し形式への書き換えを試みてみる(PRINT-AND-NEXT-REPL導入版)
(* 2 ((lambda (cont) (cont (fact 10)))
(lambda (a) (PRINT-AND-NEXT-REPL (* 2 a)))))
call/cc式の外側にある2倍を行う処理もそのまま残留しています。
もし、
;; 継続渡し形式への変換と混同しちゃった版
((lambda (cont) (cont (fact 10)))
(lambda (a) (PRINT-AND-NEXT-REPL (* 2 a))))
という風な継続渡し形式への変換を予想された方は注意してください。
call/ccは継続渡し形式に変換する関数ではなく、
あくまで、call/cc式自身の継続(自分の値を待っている計算)を自動的に作り、
それをcall/ccの引数であるprocedureに渡して、
そのprocedureをcallするという関数です。
(分からなくなったら、call-with-input-fileに戻ってください。
入力ポートの生成が継続の生成に置き換わっただけです。)
contに(lambda (a) (PRINT-AND-NEXT-REPL (* 2 a)))を束縛して適用すれば、
(* 2 ((lambda (a) (PRINT-AND-NEXT-REPL (* 2 a))) (fact 10)))
となり、さらに評価すれば以下の様になります。
(* 2 (PRINT-AND-NEXT-REPL (* 2 (fact 10))))
この処理は(* 2 (fact 10))の結果を印字したら次のread-eval-print-loopに行きます。
一番外の2倍をする処理は行われません。
もし、PRINT-AND-NEXT-REPLが無ければ、処理されてしまい結果は違ってきます。
継続渡し形式への変換では導入してなかったものを、
このタイミングで導入した理由が分かってもらえたでしょうか。
ここで振り返ってもらいたいのですが、決っしてcall/cc式自体は勝手にジャンプしたり、
妙な制御構文になっていたりしていないのです。
他のcall-with系の関数となんら変わらない評価をおこなっています。
ただ、callされた手続きに継続が渡ってきて、その継続が手続きとして使われたら、
(そう、使わなくたって一向に構わないってことに注意しましょう。
使われなければ、call/cc式は単に値を返すだけです。
それはcall-with-input-fileなど他の全ての関数となんら変わりません。)
その継続の呼び出しによりジャンプするように見えるかもしれません。
しかし、それだってcall/ccに限った話ではなく、
他の関数を呼び出すところでは常に起こっていることなのです。
call/cc式自体はどこにもジャンプなどしません。
今度はその渡ってきた継続を使わない例で動作を追ってみましょう。
(+ 1 (call/cc (lambda (cont) 2)) 3)
この式でcontは(lambda (a) (PRINT-AND-NEXT-REPL (+ 1 a 3)))になります。
call/cc式はこの継続を渡して(lambda (cont) 2)をcallします。
(+ 1 ((lambda (cont) 2) (lambda (a) (PRINT-AND-NEXT-REPL (+ 1 a 3)))) 3)
やはり機械的に変換され、contは使われないので
;; 結局、継続を使わなかった
(+ 1 ((lambda (_) 2) _) 3)
となり、結果としては(+ 1 2 3)から6が返ります。
評価順序と継続
継続を保存しておいて、あとからその継続を呼び出すまでの間に、
環境の中の値を書き換えた場合はどうなるのでしょうか?
継続がなんとなく分かってくると、今度はそういう疑問を持つようになるようです。
結論から言えば、当然環境の値が変わってれば変わっていますし、
その環境のどこにも過去の値の履歴なんかは残っていません。
[[Gauche]]の様にCLOS系のオブジェクトシステムを持つ処理系で、
オブジェクトのスロット値を書き換えた場合も当然同じです。
しかし、(変更前の)過去の値が取得できたんだけどなぁ?
と首を捻るような経験をした人もいるでしょう。
その謎を解くには、今まで説明してきた評価の流れを
もう少し注意深く考えて修正する必要があります。
;; 環境破壊実験の準備
(define k #f) ;; 継続保存用
(define x 1) ;; (大域)環境に定義
(+ x (call/cc (lambda (cont) (set! k cont) 2)) 3)
ここでcontに渡る継続はどう表現されるものになるでしょうか?
ここまでの話についてこれた方なら機械的に変換してほとんど即答できますね。
(lambda (a) (PRINT-AND-NEXT-REPL (+ x a 3)))です。
(当然kにも同じ継続が保存されています)
保存した継続はこんな風に使えます。
;; まず動作確認
(k 2) => (+ 1 2 3) => 6
(k 20) => (+ 1 20 3) => 24
kが(lambda (a) (PRINT-AND-NEXT-REPL (+ x a 3)))なのですから
この評価結果は理解できますね。
では、xの値を書き換えてみましょう。
;; いざ環境破壊
(set! x 10)
さて、準備が出来ました。
この状態で(k 2)などとするとどうなるでしょう?
;; 環境破壊の影響を観測してみる
(k 2)
実は結果は処理系によって違うかもしれないのですが、
現在の[[Gauche]]では6になります。
ちょっと奇妙な現象ですね。
これは(+ 1 2 3)の結果です。
つまり、xの値は書き換え前の値1のままで、
なんだか過去に戻ったかの様な錯覚に陥いります。
この経験がおそらく最初の疑問になるのでしょう。
ではもう少し変更して、振る舞い調べてみましょう。
;; 環境破壊実験の準備2
(define k #f) ;; 継続保存用
(define x 1) ;; (大域)環境に定義
(define z 3) ;; (大域)環境に定義
(+ x (call/cc (lambda (cont) (set! k cont) 2)) z)
この後で、今度はxとzを変更してみることにします。
;; 環境破壊
(set! x 10)
(set! z 30)
これならどうでしょう?
;; 環境破壊の結果は?
(k 20)
これも結果は処理系によって違ってきますが、現在の[[Gauche]]では51を返します。
これは(+ 1 20 30)の結果です。
つまり、xは変更前の過去の値が、zは変更後の新しい値が得られていることになります。
どうでしょう、これなら分かるのではないでしょうか。
保存した継続kは今までの説明のまま機械的に変換すると、
(lambda (a) (PRINT-AND-NEXT-REPL (+ x a z)))になるはずなのですが、
これは正確ではなかったということです。
;; 実は不正確だった継続
(lambda (a) (PRINT-AND-NEXT-REPL (+ x a z)))
正しくは、(今の[[Gauche]]では)継続kは
(lambda (a) (PRINT-AND-NEXT-REPL (+ 1 a z)))だったのです。
なぜなら、call/cc式を評価する前にxは評価されて1を得ていたからです。
;; より正確な継続
(lambda (a) (PRINT-AND-NEXT-REPL (+ 1 a z)))
つまり、[[Gauche]]では左から順に引数を評価するために、
;; 引数の評価順とcall/ccの位置
;; (1) xが評価される
;; (2) call/cc式が評価される
;; (3) zが評価される
;; (4) +が3つの値に適用される
(+ x call/cc式 z)
のcall/cc式を評価する前に、すでにxの値が環境から取り出されて1になっていて、
call/cc式の継続(続きの計算)には
「環境からxの値を取り出す」という計算は含まれてないのです。
だから継続kにはxは関係ないし、1がxの値だったということも知らないと思っていいでしょう。
逆に「zの値を環境から取り出す」という計算は含まれていますから、
継続を呼び出すとその時点でのzの値である30を取り出すわけです。
もっと言えば、(lambda (a) (PRINT-AND-NEXT-REPL (#<subr +> 1 a z)))で、
もし、継続を保存後に(set! + *)とか(set! + max)などと変更しても、
やはり加算を行ないます。
いまや+は#<subr *>や#<subr max>になっているにもかかわらずです。
(つまり、すでに加算を行う気マンマンでcall/cc式の評価に突入してたのです。
同じ様に言えば、継続は「1とaとzを加算する気マンマン」なのであって、
「xとaとzを+するつもり」だったわけではありません。)
結局環境を書き換えれば、当然変わっているのですが、
「環境から値を取り出すという計算」がcall/cc式の評価前に済んでしまっているか、
それとも継続(続きの計算)に含まれていて、
継続起動後に処理されるかが差を生むだけのことなのです。
当然オブジェクトのスロット値を書き換えている場合も同様です。
そのスロットの値を取り出す前にcall/cc式が評価されるのか、
それともcall/cc式の継続に含まれるのかが鍵を握ります。
くどいようですが、継続とは続きの計算のことで、
重要なのはどの時点の継続かということです。
ある時点の続きにはどういう計算が含まれるかを理解せずに
継続を使いこなすのは難しいと思ってください。
実は[[Scheme]]では引数の評価順序は未定義なので、
そもそも上の例のような場所でcall/ccを使うのは正しくありません。
(実際、処理系によっては違う結果を得てしまった人も居るはずです。
これは移植性のないコードを書いていることの証拠です。)
しかし、どういう順序でどんな計算が進むかの知識が重要であることは変わりません。
その意味では、[[Scheme]]は比較的評価規則は単純で、
演算の優先順位などもないので動作を読みやすくなってます。
継続を学ぶにはもってこいの言語なのです。
しかし、一旦マクロなどで評価規則が複雑なものを導入して、
それと併せて使うと、その動作を予測するのは急に困難になります。
環境を書き換えずに継続を呼んでも、
なんら変化の無い計算を繰り返すだけなのであまり意味がありません。
(継続に渡す引数を変えれば、それなりの変化は楽しめますが。)
とすれば、継続を使う局面では環境の書き換えと無縁ではいられませんし、
実際処理系が値の書き換えを許している以上は、評価順序に詳しくなければ
使いこなせないということになります。
(生成した継続自身を外側の環境に保存したり、
新しく生成した継続で書き換えるような環境の変更も良く見かけます。)
そう考えると、恐らく複雑な構文や演算子の優先順などがある言語処理系で
継続を導入しても、結局誰にも使いこなせずに不要になってしまうかもしれません。
では、練習問題です。次はどうなるか確認してみてください。
;; 環境破壊実験の準備3
(define k #f) ;; 継続保存用
(define x 1) ;; 環境に定義
((identity +) x (call/cc (lambda (cont) (set! k cont) 2)) x)
あまり変わっていないですが、
;; 環境破壊
(set! x 10)
(set! + max)
;; さて結果は?
(k 2)
(k 2)を評価したらどうなるでしょう？
(lambda (a) (PRINT-AND-NEXT-REPL (#<subr +> 1 a x)))ですから13?
実は今の[[Gauche]]では
(lambda (a) (PRINT-AND-NEXT-REPL ((identity +) 1 a x)))なので10が返ってきます。
最初の(identity +)が引数の評価より後なのです。
実は+などの様な組込み関数を使わずに
ユーザ定義関数を使う場合にも最後に評価されます。
というか、むしろ実際には逆で組込み関数の場合に最適化のために
引数が評価されるより前に#<subr +>に評価済みになっているのです。
なお、この挙動は-fno-inlineオプションを付けてgoshを起動しても変わってきます。
継続は続きの計算です。
ならば、続きの計算が何であるかを知ることが
継続を使いこなす上での必須のスキルと言って良いでしょう。
仮に[[Scheme]]で継続を使いこなせても、別の言語処理系の上で使いこなすには、
その言語の評価順などの知識が必要になります。
もちろん継続についての理解はどこに行っても通用するので学ぶことは意義があります。
call/ccパズル
call/ccパズルというものがあります。
以前comp.lang.schemeというニュースグループで話題になったプログラムです。
このコードが何をするかを予想してみろ、というのですがそう簡単ではありません。
;; call/ccパズルお題
(let* ((yin ((lambda (foo) (newline) foo)
(call/cc (lambda (bar) bar))))
(yang ((lambda (foo) (write-char #\*) foo)
(call/cc (lambda (bar) bar)))))
(yin yang))
しかし、このパズルの動作を理解するのはちょっとした自信にもなると思いますので
ここでは少し説明してみることにします。
まずコードの本質的な部分を剥き出しにするために少しだけ簡略化しましょう。
2行目の(lambda (bar) bar)はcall/ccが自動的に作成した継続をそのまま返しています。
いわゆるidentityという関数です。
それが、1行目のlambda式のfooに束縛され、ここでもそのままfooが返されています。
最終的には、それがyinに束縛されます。
つまりyinにはcall/ccが作成した継続が束縛されます。
従って((lambda (foo) (newline) foo) (call/cc (lambda (bar) bar)))の部分は
(call/cc identity)と置き換えても動作そのものは変わりません。
なぜわざわざこんなややこしいことをしているかと言うと、
一種のデバッグプリントのためです。
つまり、このcall/ccで作成した継続がどこかで(あるいはどこであれ)
callされると(newline)を通過するので、
改行が表示されることで継続が起動された瞬間が目に見えるわけです。
このことは、
;; 最初の束縛部分に注目
(EXTERNAL-EXPR ((lambda (foo) (newline) foo) (call/cc (lambda (bar) bar))))
で、call/ccが作成する継続が、
;; 最初のcall/cc式の継続
(lambda (a)
(EXTERNAL-EXPR ((lambda (foo) (newline) foo) a)))
となることからも分かります。
見ての通り(newline)が続きの計算に含まれています。
同じ様にyangの方も4行目のcall/ccで作成された継続がcallされると
'*'という文字が印字されることで継続が起動されたことを教えてくれます。
これは継続が起動された瞬間が見えるので、
call/cc(に限らず大抵の式)のデバッグに使える一般的な手法です。
是非覚えておきましょう。
(もちろんcall/cc式が素直に値を返した場合にも通過します。)
ともかく、ここを省略するとコードは少し簡単になって次の様になります。
;; STEP 0
(let* ((yin (call/cc identity))
(yang (call/cc identity)))
(yin yang))
これならなんとか全体が見通せるでしょう。
ポイントは、let*のローカル束縛の評価順序です。
yinに束縛される継続l#<continuation yin>は
;; #<continuation yin>
(lambda (a)
(PRINT-AND-NEXT-REPL
(let* ((yin a)
(yang (call/cc identity)))
(yin yang))))
一方yangに束縛される継続#<continuation yang>は不正確ですが、
;; #<continuation yang>っぽいもの
(lambda (a)
(PRINT-AND-NEXT-REPL
(let* ((yin #<continuation yin>)
(yang a))
(yin yang))))
正しくするなら、ちょっと形が変わってしまうが仕方がありません。
;; #<continuation yang>
(lambda (a)
(PRINT-AND-NEXT-REPL
(let ((yang a))
(#<continuation yin> yang))))
こうなると思って良さそうです。
yinに束縛される継続には
「新たに継続を作成してyangに束縛するという計算」が含まれていますが、
yangに束縛される継続ではyinはすでに無く、作成済みの継続が見えます。
その意味でyinとyangは対等ではありません。
この立場の違いは、そのまま評価順序からきています。
では、(yin yang)を評価してみましょう。
おっと、その前に確認しておきます。
そもそも、ここに至るまでに、yinのためのcall/ccが評価されるので、
この段階で改行が一発入ります。
yangのためのcall/ccも評価されるので、*が一発入っているのでお忘れなく。
;; ここまでの結果
*I
では、気を取り直して(yin yang)の評価です。
;; STEP 1
(#<continuation yin> #<continuation yan>)
では、#<continuation yin>だけ上記の継続手続きで置き換えてみると次式になります。
;; STEP 1'
((lambda (a)
(PRINT-AND-NEXT-REPL
(let* ((yin a)
(yang (call/cc identity)))
(yin yang))))
#<continuation yang>)
では適用してみましょう。
;; STEP 2
(PRINT-AND-NEXT-REPL
(let* ((yin #<continuation yang>)
(yang (call/cc identity)))
(yin yang)))
今度はこの評価をすることになります。
yinには先程と同じ#<continuation yang>が束縛されます。
#<continuation yin>ではないので注意してください。
そして、#<continuation yang>がyinに束縛される所で、改行が入ります。
元コードでは、((lambda (a) (newline) a) #<continuation yang>)だからです。
;; ここまでの結果
*
I
次は、call/cc式が評価されて新たな継続#<continuation yang'>が得られます。
新たに作られるので'(ダッシュ)を付けておきました。
区別さえできるなら、インデックスを振っても良いでしょう。
ともあれ、call/cc式が評価された直後はこうなります。
;; STEP 3
(PRINT-AND-NEXT-REPL
(let ((yang #<continuation yang'>))
(#<continuation yang> yang)))
元々のコードで言えば、yangに束縛される時点で*が表示されるはずです。
;; ここまでの結果
*
*I
#<continuation yang'>を継続手続き風に書くとどうなるでしょう?
;; #<continuation yang'>っぽいもの
(lambda (a)
(PRINT-AND-NEXT-REPL
(let* ((yin #<continuation yang>)
(yang a))
(yin yang))))
正確には、
;; #<continuation yang'>っぽいもの
(lambda (a)
(PRINT-AND-NEXT-REPL
(let ((yang a))
(#<continuation yang> yang))))
では、(yin yang)を評価します。
;; STEP 4
(#<continuation yang> #<continuation yang'>)
#<continuation yang>を継続手続き風の式で置き換えます。
;; STEP 4'
((lambda (a)
(PRINT-AND-NEXT-REPL
(let ((yang a))
(#<continuation yin> yang))))
#<continuation yang'>)
これを適用すると、
;; STEP 5
(PRINT-AND-NEXT-REPL
(let ((yang #<continuation yang'>))
(#<continuation yin> yang')))
今度はyangには#<continuation yang>が束縛されますが、ここで*が入ります。
;; ここまでの結果
*
**I
すると、次に評価すべき式は
;; STEP 6
(#<continuation yin> #<continuation yang'>)
となり、同様に#<continuation yin>を継続手続き風の式に置き換えると、
;; STEP 6'
((lambda (a)
(PRINT-AND-NEXT-REPL
(let* ((yin a)
(yang (call/cc identity)))
(yin yang))))
#<continuation yang'>)
適用すれば、
;; STEP 7
(PRINT-AND-NEXT-REPL
(let* ((yin #<continuation yang'>)
(yang (call/cc identity)))
(yin yang)))
ここで、yinに束縛される瞬間改行が入り、
さらに新たな継続#<continuatiogn yang''>を生成してyangに束縛するところで
*が入ります。
;; ここまでの結果
*
**
*I
では、引き続き評価しましょう。
;; STEP 8
(#<continuation yang'> #<continuation yang''>)
繰り返しで、だいぶ退屈してきたかもしれないが続けます。
;; STEP 8'
((lambda (a)
(PRINT-AND-NEXT-REPL
(let ((yang a))
(#<continuation yang> yang))))
#<continuagion yang''>)
適用すると、
;; STEP 9
(PRINT-AND-NEXT-REPL
(let ((yang #<continuagion yang''>))
(#<continuation yang> yang)))
yangに継続が束縛されるところで*が入ります。
;; ここまでの結果
*
**
**I
次はこの式の評価です。
;; STEP 10
(#<continuagion yang> #<continuation yang''>)
#<continuagion yang>を継続手続き風の式で置換すると、
;; STEP 10'
((lambda (a)
(PRINT-AND-NEXT-REPL
(let ((yang a))
(#<continuation yin> yang))))
#<continuation yang''>)
適用すると、
;; STEP 11
(PRINT-AND-NEXT-REPL
(let ((yang #<continuation yang''>))
(#<continuation yin> yang)))
yangに束縛されるところで、'*が入ります。
;; ここまでの結果
*
**
***I
そして、再び、#<continuation yin>のcallになる。ということは改行が期待できますね。
;; STEP 12
(#<continuation yin> #<continuation yang''>)
置き換えると、
;; STEP 12'
((lambda (a)
(PRINT-AND-NEXT-REPL
(let* ((yin a)
(yang (call/cc identity)))
(yin yang))))
#<continuation yang''>)
適用すると、
;; STEP 13
(PRINT-AND-NEXT-REPL
(let* ((yin #<continuation yang''>)
(yang (call/cc identity)))
(yin yang)))
yinに束縛されるところで、改行が入り、
call/cc式を評価して新たな継続#<continuation yang'''>が作成され、
yangに束縛されると、*が入ります。
ここまでで打ち止めとしましょう。
;; ここまでの結果
*
**
***
*I
このまま続ければ、一行毎に*の数が一個ずつ増加していくのが確認できます。
改行はyinへの束縛が起こった瞬間であり、*はyangへの束縛が起こった瞬間です。
上記の結果は、まさにそのデバッグプリントなのです。
;; STEP 0 (再掲)
(let* ((yin (call/cc identity)) ;; call/cc-yin式
(yang (call/cc identity))) ;; call/cc-yang式
(yin yang))
印字出力を見落とさないように動作を追うのは大変ですが、
是非一度手を動かしてやってみてください。
ポイントは、次の点でしょうか。
- 改行や*が印字されるのは継続が束縛されるタイミングである。(デバッグプリント)
- 最初のcall/cc-yin式はただ一度だけ評価され、#<continuation yin>を生成し、
あとは同じ継続が使い回される。
- 次のcall/cc-yang式は#<continuation yin>がcallされた時にのみ、
評価されて新しい継続を生成する。
では、(yin yang)のトレースをまとめて眺めてみましょう。
;; STEP 1
(#<continuation yin> #<continuation yang>)
;; STEP 4
(#<continuation yang> #<continuation yang'>)
;; STEP 6
(#<continuation yin> #<continuation yang'>)
;; STEP 8
(#<continuation yang'> #<continuation yang''>)
;; STEP 10
(#<continuagion yang> #<continuation yang''>)
;; STEP 12
(#<continuation yin> #<continuation yang''>)
;;
(#<continuation yang''> #<continuation yang'''>)
;;
(#<continuation yang'> #<continuation yang'''>)
;;
(#<continuation yang> #<continuation yang'''>)
;;
(#<continuation yin> #<continuation yang'''>)
;;
(#<continuation yang'''> #<continuation yang''''>)
;;
(#<continuation yang''> #<continuation yang''''>)
;;
(#<continuation yang'> #<continuation yang''''>)
;;
(#<continuation yang> #<continuation yang''''>)
;;
(#<continuation yin> #<continuation yang''''>)
じっと見て規則性を確認してください。
#<continuation yin>が出てきたらlet*の最初の束縛から呼ばれるところで、
改行が印字されます。
後は、#<continuation yang>や#<continuation yang'>などが
束縛される回数だけ*が印字されます。
面倒かもしれませんが、是非一度は手を動かして動作を追ってみて下さい。
お手元マルチスレッド
ちょっと継続を使って遊んでみましょう。
これを通して継続の力の一端に触れた気になっていただければ嬉しいです。
まずはファイルから一行読み込むだけのプログラムから始めることにします。
;; サンプルファイルから一行読み込む
(let ((in (open-input-file "sample.txt")))
(read-line in))
これを少し改造してみます。
(define k #f) ;; 継続保存用
(let ((in (open-input-file "sample.txt")))
(read-line (call/cc (lambda (cont)
(set! k cont)
in))))
call/cc式はkに継続を保存しますが、その継続cont自体は使わずに、inだけを返します。
つまり、最初のコードと動作は変わりません。
;; 保存された継続
(lambda (a)
(PRINT-AND-NEXT-REPL
(let ((in #<inport>))
(read-line a))))
保存された継続はこんな風になるでしょう。
正確にはinに束縛するところはすでに完了していますし、
[[Gauche]]ならread-lineも評価済みなので、次式のようになっています。
;; 保存された継続
(lambda (a)
(PRINT-AND-NEXT-REPL
(#<subr read-line> a)))
さて、ここで継続を保存しておいたので、
いつでもサンプルファイルから一行読み込むという処理が呼び出せます。
プロンプトから(k in)を何度か呼ぶと次々に行が返されるはずです。
途中で(k in)以外の式を評価しても問題ありません。
そんなの当然じゃないか?と思われれば、あなたはすっかり継続に馴染んでいます。
しかし、良く良く考えると、これは結構スゴいことです。
プログラマが手動でスレッド切り換えをしているようなものですからね。
では、もう少しその雰囲気を味わっていただきましょう。
;;----------------------------------------
;; 準備
;;----------------------------------------
;; バッファの用意
(define buf "")
;; 読み込み処理の継続保存用
(define kin #f)
;; 書き出し処理の継続保存用
(define kout #f)
;; 入力ポート保存用
(define inp #f)
;; 別の入力ポート
(define in2 (open-input-file "Another-in.txt"))
;; 出力ポート保存用
(define outp #f)
;; 別の出力ポート
(define out2 (open-output-file "sample-out2.txt"))
;; 読み込みのための継続捕捉
(let* ((in (open-input-file "Continuation.txt"))
(line (read-line (call/cc (lambda (cont)
(set! inp in)
(set! kin cont)
in)))))
(set! buf (string-append buf "\n" line)))
;; 書き出しのための継続捕捉
(let ((out (call/cc (lambda (cont)
(let ((out (open-output-file "sample-out.txt")))
(set! outp out)
(set! kout cont)
out)))))
(display buf out)
(flush out)
(set! buf "")
(display "write and buf clear."))
;;----------------------------------------
;; 評価
;;----------------------------------------
;; (1) 読み込みを何度か適当に評価して
(kin inp)
;; (2) たまに気が向いたら書き出ししよう
(kout outp)
;; (3) さらにたまに気が向いたら別のポートを読み込めばファイルのマージもできる
(kin in2)
;; (4) さらにたまに気が向いたら別のポートに書き出せはファイルの分割もできる
(kout out2)
最初の方の準備が済んだら、(1)(2)(3)(4)を適当な順序で複数回実行してみてください。
作業した順でファイルを(行単位でですが)マージしたり分割したりできるようになりました。
そしてたまに(kout outp)とか(kout out2)とすると
バッファリングした情報を書き出せているので、そのタイミングで
sample-out.txtやsample-out2.txtを確認しながら評価してみてください。
これはタスクの切り換えを自分でやっていると思えば、ごくごく当たり前の結果なんですが、
継続は保存してから呼び出されるまでの間、完全に休眠しており、
その間にいかなる式の評価でもはさむことが出来ます。
そして、kinやkoutなどの継続を起動すると、
あたかもずっとそれをやっていたかの様に続きの計算を粛々と行うのです。
すでに、手動でのスレッド切替は体感できたと思いますので、
キューを用意しておき、(lambda () (kin inp))などをキューイングして、
順次デキューして評価したり、新たに(lambda () (kout outp))などを生成して
エンキューすれば、マルチスレッドもどきは簡単に作れてしまいます。
スケジューリングの実験も手軽にできると思うので、
どんどんコードを書き換えて試してみてください。
これが、いかなる制御構造の実現も可能にする継続の力です。
by えんどうやすゆき
