Scheme:使いたい人のための継続入門

Scheme:使いたい人のための継続入門


使いたい人のための継続入門

とりあえず殴り書き。
くどかったり冗長な文章になってたり、重複してたり、間違ってたり、 おおいなる勘違いをしてたり、恥をカいてたりするかもしれないけどご愛敬。
藁をもつかみたい気持ちで継続を使えるようになりたい人は読んでみてください。 ただし所詮は藁です。(w

継続渡し形式

例によって階乗factから始めよう。

;; 階乗の普通の定義
(define (fact n)
  (if (= n 0)
      1
      (* n (fact (- n 1)))))

階乗factの定義は

  1. 引数nが0なら1を返す(基底条件)
  2. それ以外なら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だ。
この関数は、

  1. 第一引数のファイルをオープンして、入力ポートを作り出す。
  2. 入力ポートを引数にして第二引数の手続きを呼び出す。

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の使い方だ。

  1. 第一引数のファイルをオープンして出力ポートを作り出す。
  2. 出力ポートを引数にして第二引数の手続きを呼び出す。

すでに説明した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 n)))))

ここまでは分かってもらえただろうか?

さて、続きの計算はいたるところにある。 あらゆる評価の時点において、その続きの計算というものが存在する。 しかし、その時点を特定すれば、続きの計算は自動的に(一意に)決まることになる。
今の例で言えば、(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の継続渡し形式への書き換えを試みてみる
((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に限った話ではなく、 他の関数を呼び出すところでは常に起こっていることだ。

今度は継続を使わない例で動作を追ってみよう。

(+ 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が返る。 どうだろう、このケースで考えてもらえばcall/cc式それ自体は 決して怪しいジャンプなどしないことが分ってもらえるんじゃないだろうか。

評価順序と継続

継続を保存しておいて、あとからその継続を呼び出すまでの間に、 環境の中の値を書き換えた場合はどうなるのか?
継続がなんとなく分かってくると、今度はそういう疑問を持つようになるものらしい。

結論から言えば、当然環境の値が変わってれば、その値は変わってるし、 その環境のどこにも過去の値の履歴なんぞは残ってない。 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)))なので 破壊後の+の値である#<subr max>が計算されて(#<subr max> 1 2 10)から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に限りませんが。) 是非覚えておこう。
(もちろんcall/cc式が素直に値を返した場合にも通過する。) ともかく、ここを省略するとコードは少し簡単になって次の様になる。

;; STEP 0
(let* ((yin (call/cc identity))
       (yang (call/cc identity)))
  (yin yang))

これならなんとか全体が見通せるだろう。

ポイントは、let*のローカル束縛の評価順序だ。
yinに束縛される継続#<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))

印字出力を見落とさないように動作を追うのは大変だが、 是非一度手を動かしてやってみて欲しい。 ポイントは、次の点だろうか。

  1. 改行や*が印字されるのは継続が束縛されるタイミングである。(デバッグプリント)
  2. 最初のcall/cc-yin式はただ一度だけ評価され、#<continuation yin>を生成し、 あとは同じ継続が使い回される。
  3. 次の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))))

保存された継続kは、この様になるだろう。 正確には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))などを生成して エンキューすれば、マルチスレッドもどきは簡単に作れてしまう。 スケジューリングの実験も手軽にできると思うので、 どんどんコードを書き換えて試して欲しい。

これが、いかなる制御構造の実現も可能にする継続の力である。

継続については以上で説明を終えるが、 次はさらに進んだ話題として部分継続というものを説明するとしよう。

部分継続

ここまで読まれた方は、プログラム中にcall/cc式を見ても 以前程には緊張しなくなっただろう(と願う)。

今度は部分継続を説明しようと思う。
やれやれ、継続の次がまだあるのかとうんざりされるかもしれないが、 部分継続についても知っておくと、継続でのハマリどころを理解できると思うので、 是非頑張ってついてきて欲しい。

継続には続きの全ての計算が含まれてしまうが、 それを部分的な範囲に限定できるのが部分継続だ。
とは言っても、これだけで理解できるわけもないと思うので、 一つずつ説明していこう。

まず、継続のおさらいだが、call/cc式は、通常の関数だと説明してきた。
そして、call/cc式にはそれを待ち受ける続きの計算たる継続がある。 勿論、call/cc式に限らず、あらゆる式には、その値を待っている継続がある。
次に、call/cc式は、自身の継続を取り出して引数の手続きに渡している。 これはcall/cc特有の機能である。 (特有といっても大袈裟な話ではない。 call-with-input-fileがファイルをオープンして入力ポートを作るのが call-with-input-fileに特有の機能である。というのとなんら変わらない。)

当然、call/cc式の返りを待ち受けている継続とcall/ccが取り出す継続とは同じものだ。 しかし、これから説明する部分継続では、これが同じとはならない。

reset/pcとcall/pc

ともかく次の式を題材にして、継続渡し形式風で学んでいこう。

;; reset/pcとcall/pcの使用
(+ 1 2 (reset/pc (+ 3 4 (call/pc (lambda (cont) (cont 5))))))

まず、それぞれの継続について説明しておこう。 (ただし、処理系としてはGaucheを想定しており、 厳密には#<subr +>となっているはずだが、今回は省略する。)

  1. reset/pc式を待ち受けている継続は、 (lambda (a) (PRINT-AND-NEXT-REPL (+ 1 2 a)))である。
  2. call/pc式を待ち受けている継続は、 (lambda (a) (PRINT-AND-NEXT-REPL (+ 1 2 a)))である。
    これは、reset/pc式を待ち受けている継続と同じものだ。
  3. call/pc式が自動的に生成する継続は、 (lambda (a) (+ 3 4 a))である。

最後のは、reset/pcで続きの計算をリセットされており、 つまりcall/pc式から見ると、

(+ 3 4 (call/pc (lambda (cont) (cont 5))))

であるかの様なものだと思えば良い。 要は、reset/pcの外に待っている継続は存在しないように見えるのだ。
当然ながらcall/pcは必ずreset/pcの中でないと使えない。
call/pcはcall/ccと違って、自身の式の返りを待っている継続(二番目)と、 生成して引数に渡す継続(三番目)とが異なることに注意しよう。 また、最後の継続は(lambda (a) (PRINT-AND-NEXT-REPL (+ 3 4 a)))ではない のでやはり注意しよう。

reset/pc式は一引数を取り、その式を評価して値を返す。 その意味ではidentityと同じだと思えば良い。 もしくは一引数のbeginのようなものだろうか。 ただし、続きの計算をリセットするという処理を陰でこっそりやっている。

では、そうすると上記の式はどんな風に動作するか、順を追って調べてみよう。

;; reset/pcとcall/pcの使用(再掲)
(+ 1 2 (reset/pc (+ 3 4 (call/pc (lambda (cont) (cont 5))))))
  1. (+ 1 2 reset/pc式)の評価をする
  2. reset/pc式の評価をしようとする
  3. (+ 3 4 call/pc式)を評価する
  4. (call/pc (lambda (cont) (cont 5)))の評価をする。
  5. contは(lambda (a) (+ 3 4 a))なので、 (cont 5)は((lambda (a) (+ 3 4 a)) 5)となる。
  6. (cont 5)は結果として、(+ 3 4 5)なので、12を返す。
  7. call/pc式が12を返すが、call/pc式の待ち受けている継続は (lambda (a) (PRINT-AND-NEXT-REPL (+ 1 2 a)))だ。
  8. したがって、(+ 1 2 12)から 15を返す。

というわけで、15を得る。 では、contを呼ばないようにしてみよう。

;; reset/pcとcall/pcの使用2
(+ 1 2 (reset/pc (+ 3 4 (call/pc (lambda (cont) 5)))))

ちょっとした変更だ。 これも順に動作を追ってみる。

  1. (+ 1 2 reset/pc式)の評価をする
  2. reset/pc式の評価をしようとする
  3. (+ 3 4 call/pc式)を評価する
  4. (call/pc (lambda (cont) 5))の評価をする。
  5. これは、contが使われず、call/pc式はそのまま5を返す。
  6. call/pc式を待ち受けている継続は、 (lambda (a) (PRINT-AND-NEXT-REPL (+ 1 2 a)))である。 call/pc式が生成する継続contと混同しないようにしよう。
  7. したがって、((lambda (a) (PRINT-AND-NEXT-REPL (+ 1 2 a))) 5)を評価する。
  8. 8を返して次なるread-eval-print-loopへ。

というわけで今度は8を得る。

では、contを保存して後から呼び出してみよう。

;; reset/pcとcall/pcの使用2

(define k #f)  ;; 継続保存用

(+ 1 2 (reset/pc (+ 3 4 (call/pc (lambda (cont) (set! k cont) (cont 5))))))

kにはcont、つまり(lambda (a) (+ 3 4 a))が代入される。 それ以外は最初の使用例と同じなので、15が返る。

では、保存しておいたkを呼び出して確認してみよう。

(k 1) => ((lambda (a) (+ 3 4 a)) 1) => 8
(k 2) => ((lambda (a) (+ 3 4 a)) 2) => 9
(k 5) => ((lambda (a) (+ 3 4 a)) 5) => 12

どうだろう。 継続を理解して、式を待っている継続および生成している継続を整理しておけば、 たいして難しくないんじゃないだろうか。

環境破壊と部分継続

では、継続の時の様に環境をいじってみよう。 継続となんら変わらないので臆することはない。

;; 環境破壊実験

(define x 1)
(define z 3)

(define k #f)  ;; 継続保存用

;; call/pcとreset/pcの使用3
(+ x
   (reset/pc (+  z (call/pc (lambda (cont) (set! k cont) 2)) x))
   z)

まず、継続を整理しておこう。 ここでも正しくは、#<subr +>となっているべきだが端折っている。

  1. reset/pc式を待ち受けている継続は (lambda (a) (PRINT-AND-NEXT-REPL (+ 1 a z)))だ。xは評価済みなので注意。
  2. call/pc式を待ち受けている継続は (lambda (a) (PRINT-AND-NEXT-REPL (+ 1 a z)))だ。xは評価済みなので注意。
  3. call/pc式が自動的に生成する継続は、 (lambda (a) (+ 3 a x))である。zは評価済みなので注意。

では評価を追ってみよう。

  1. (+ x reset/pc式 z)の評価をする。
  2. (+ 1 reset/pc式 z)の状況でreset/pc式を評価しようとする。
  3. (reset/pc (+ z call/pc式 x))の評価を行う。
  4. (+ 3 call/pc式 x)の状況でcall/pc式を評価する。
  5. call/pc式はkに継続contを保存して2を返す。
  6. call/pc式の返りを待ち受けている継続は (lambda (a) (PRINT-AND-NEXT-REPL (+ 1 a z)))なので、 (PRINT-AND-NEXT-REPL (+ 1 2 z))となる。
  7. zが3なので6を返す。

以後、保存した継続k、つまり(lambda (a) (+ 3 a x))を使うと

(k 2) => ((lambda (a) (+ 3 a x)) 2) => 6
(k 3) => ((lambda (a) (+ 3 a x)) 3) => 7

となるのも納得できるだろう。

では、環境を破壊してみよう。

;; 環境破壊
(set! x 10)

この状況で(k 2)を呼ぶとどうなるか考えよう。

(k 2) => ((lambda (a) (+ 3 a x)) 2) => (+ 3 2 10) => 15

正解。
では、zも書き換えてみる。

(set! z 100)

(k 2) => ((lambda (a) (+ 3 a x)) 2) => (+ 3 2 10) => 15

やはりzは評価済みなので結果はさっきと変わらない。 では、今度はcall/pc内でcontを呼んでみよう。

;; 環境破壊実験その2

(define x 1)
(define z 3)

(define k #f)  ;; 継続保存用

;; call/pcとreset/pcの使用4
(+ x
   (reset/pc (+  z (call/pc (lambda (cont) (set! k cont) (cont 2))) x))
   z)

では評価を追ってみよう。

  1. (+ x reset/pc式 z)の評価をする。
  2. (+ 1 reset/pc式 z)の状況でreset/pc式を評価しようとする。
  3. (reset/pc (+ z call/pc式 x))の評価を行う。
  4. (+ 3 call/pc式 x)の状況でcall/pc式を評価する。
  5. call/pc式はkに継続contを保存して(cont 2)を評価する。
  6. contは、(lambda (a) (+ 3 a x))なので ((lambda (a) (+ 3 a x)) 2)を評価して6を得る。
  7. まだ終わらない。この結果6がcall/pc式の値となる。
  8. call/pc式の返りを待ち受けている継続は (lambda (a) (PRINT-AND-NEXT-REPL (+ 1 a z)))なので(+ 1 6 3)となり10を得る。

では、環境を破壊してみよう。

(set! x 10)
(set! z 100)

としておいて、(k 2)を評価するとどうなるだろう。

(k 2) => ((lambda (a) (+ 3 a x)) 2) => 15

実に簡単だ。

では最後にもう少しだけ複雑な例を示そう。 挙動を追ってみて欲しい。

(+ 1 2 (reset/pc (+ 3 4 (call/pc (lambda (cont) (cont (cont (cont 5))))))))

それぞれの継続を確認しておこう。

  1. reset/pc式を待ち受けている継続は (lambda (a) (PRINT-AND-NEXT-REPL (+ 1 2 a)))だ。
  2. call/pc式を待ち受けている継続は (lambda (a) (PRINT-AND-NEXT-REPL (+ 1 2 a)))だ。
  3. call/pc式が自動的に生成する継続は、 (lambda (a) (+ 3 4 a))である。

call/pc式が評価されるところから評価を追うと次のようになる。

  1. (cont 5)は((lambda (a) (+ 3 4 a)) 5)なので12を返す。
  2. この(cont 5)の返り値12を受けて、 (cont 12)を評価すると((lambda (a) (+ 3 4 a)) 12)なので19を返す。
  3. この(cont 12)の返り値19を受けて、 (cont 19)を評価すると((lambda (a) (+ 3 4 a)) 19)なので26を返す。
  4. この値がcall/pc式の返り値なので、 継続(lambda (a) (PRINT-END-NEXT-REPL (+ 1 2 a)))に適用すると、 (+ 1 2 26)を評価した結果29が得られる。

実際にそうなのかデバッグプリントを仕込んで確認してみよう。

;; デバッグプリントを投入
(+ 1 2 (reset/pc (+ 3 4
                    ((lambda (v) (format #t "=>~a~%" v) v)
                     (call/pc (lambda (cont) (cont (cont (cont 5)))))))))

デバッグプリントの仕込み方はすでにcall/ccパズルの説明のところでした通りだ。 call/pcのところから戻ったところに表示付きのidentityを仕掛ければ良い。 これを評価すれば上記の通り、5、12、19が渡ってくるのが見える。 さらに返り値もモニタしてみよう。

;; さらにデバッグプリントを投入
(+ 1 2 (reset/pc #?=(+ 3 4
                       ((lambda (v) (format #t "=>~a~%" v) v)
                        (call/pc (lambda (cont) (cont (cont (cont 5)))))))))

これで、5が渡ってきて12が返り、12が渡ってきて19が返り、 19が渡ってきて26が返ってくるのが見えるようになる。

結構面白い挙動だと思うのだが、理解できただろうか。 call/pcを待ち受けている継続とcall/pcが生成している継続が分離している点と、 reset/pcが内と外の計算を切り離している感触が分ってもらえるまで、 色々いじってもらうのが良いだろう。
ポイントはすでに説明したつもりなので、横着せずにひとつずつ追っていけば 迷うことはないはずだ。

部分継続の使用法

では、部分継続を使うとどんなことが出来るだろう。
あくまで雰囲気を伝えるためのコードであり、あまり正しいものではないが 以下のコードで気持ちだけ伝えようと思う。 実際には是非Kahuaでのプログラミングにチャレンジしてみて欲しい。

;; 出力用サービスプログラム
(define (serv apl)
  (let ((vals (reset/pc (apl))))
    (call-with-output-file "result.txt"
      (lambda (new)
        (write (cdr vals) new)
        (flush new)
        (call-with-output-file "num.txt"
          (lambda (old)
            (write (car vals) old)
            (flush old)
            vals))))))

;; 初期化アプリ
(define (one-zero)
  (cons 1 0))

;; fibアプリ
(define (fib)
  (let ((old (get-value "result.txt"))
        (v (get-value "num.txt")))
    (cons old (+ old v))))

;; 部分継続によるデータ取得の抽象化のつもり
(define (get-value fname)
  (call/pc (lambda (cont)
             (call-with-input-file fname
               (lambda (in) (cont (read in)))))))

何をやっているかは後で説明するとして、ともあれ実行してみよう。 準備として、result.txtとnum.txtというファイル生成しておく。

;; 下準備
(serv one-zero)
;; 繰り返し呼び出してみよう。
(serv fib) => (1 . 1)
(serv fib) => (1 . 2)
(serv fib) => (2 . 3)
(serv fib) => (3 . 5)
(serv fib) => (5 . 8)
(serv fib) => (8 . 13)
(serv fib) => (13 . 21)
(serv fib) => (21 . 34)
(serv fib) => (34 . 55)
(serv fib) => (55 . 89)

相当簡略化したが、Kahuaにおける部分継続の使い方はこんな感じである。 servはKahuaのサーバプログラム、fibやらone-zeroはKahuaのアプリだ。 get-valueはfibアプリで使ってるルーチンだ。

そして、num.txtやらresult.txtはクライアント(ブラウザ)との 一回のリクエスト-レスポンスのやり取りを行うソケットの様なものと思って欲しい。 複数のファイルにレスポンスを返しているのは、 fibに対応したかったからであまり意味はない。 counterアプリ程度にしておけば、より簡単になれたかもしれない。

一回のリクエストは(serv fib)一回の評価に相当すると考えればよい。 fibの中で2回に渡って使われているget-valueは 他の関数となんら違わないように見えるが、 クライアントに入力を要求してデータを受けとる処理を行なっている。 つまり、Kahuaで言えば(get-value ...)により 一回分のレスポンス-リクエスト(レスポンスは入力の要求だ)を行う。 実際には、get-value中のcall-with-input-file式が データ読み込み用のページを作る関数に相当しており、 POSTデータを受け取って処理する部分が最後の行の(read in)に相当する。

result.txtへのデータの書き込みがレスポンスに相当するが、 fibは一回のリクエストに対して、二回のレスポンス-リクエストにより 二つの値を順に取得し、その結果を加算して 最初のリクエストに対するレスポンスを返しているわけだ。

;; fibアプリ(再掲)
(define (fib)
  (let ((old (get-value "result.txt"))
        (v (get-value "num.txt")))
    (cons old (+ old v))))

Kahuaでもこのfibアプリでのget-valueと全く同じ使い方ができ、 これだけで3回のリクエストレスポンスを表現することになる。 とはいえ、重要なのはコード量などではなく、 一回のレスポンス-リクエストをget-valueという関数に抽象化できていることである。 あたかも(read in)をするのと同じ感覚で ネットワークの向こうに居るユーザとの対話が書けるのだ。

これを利用して、現在のログインユーザをget-valueならぬget-userで実装すれば、 Kahuaプログラマは「ここでログインしてもらって...」などと考える必要はない。
現在のユーザの情報が必要になったら、(get-user)を呼ぶだけだ。 どこかにユーザの名前を表示したいという要望があれば、 自然と(name-of (get-user))と書くはずで、考えることはそれで十分なのだ。
get-userのロジック自体は、もしログインしていればそのままユーザオブジェクトが、 ログインしてなければ、ログイン認証を行って ログインが成功したところでユーザオブジェクトを返してくる というコードを書いておけば良い。
どんなページを閲覧中でも、それどころか何かをPOSTした瞬間、 そのPOSTデータが反映される途中においてさえ、 必要になったところでログインを要求するようなアプリが簡単に書けるわけだ。

例えば、閲覧は自由だが書き込みはログインが必要なサイトを作る場合を考える。 ログインが必要なのは何故だろうか? 恐らくその様なサイトでは匿名による投稿を禁止したいからだ。 とすれば、きっと投稿記事にユーザオブジェクトが結びついており、 記事を表示する画面には投稿者の名前なりニックネームが 表示されるようにデザインされるだろう。
POSTリクエストされた時のロジックには

(make <post-data> :poster (get-user))

もしくは、

(set! (poster-of post-data) (get-user))

という風に記事オブジェクトが生成された時か、 その直後にposterスロットにユーザオブジェクトを格納するコードを書くだろう。 この様に書かれたKahuaアプリでは、 ログインしてない状態で書き込みを行おうとsubmitボタンを押した瞬間、 ログイン認証を行い、ログイン成功とともに投稿後の状態に遷移するのだ。

なぜKahuaプログラマが、こんな風に書けることを強く主張したがるのだろうか? アプリの動作とプログラムロジックを考えよう。

クライアントから見ると次のような画面遷移を見ることになる。

  1. 投稿記事入力フォーム(ここで入力してポストする)
  2. ログイン認証画面
  3. 記事閲覧画面(投稿記事もしくは記事一覧など)

ということは、これを素直にアプリで書くとすると

  1. 入力フォームから記事がポストされた時にログインしてなければ、 ポストデータを退避しておきログイン認証させるためのページを返す。
  2. ログイン認証を行い、認証が成功したら、 退避していた情報から記事投稿の処理を再開して記事投稿後のページを生成して返す。

となる。 どうだろう? そもそもリクエストされたものと返しているページが違うので、 どう考えてもロジックは難解になってしまうのが分かるだろう。

  1. 記事が投稿された時にログイン認証画面を表示
  2. アカウントとパスワードが入力された時に記事閲覧画面を表示

という挙動を書くのだから、どう考えてもおかしい。

また、退避していた情報から記事投稿の処理を再開しの部分などは 決して簡単な仕事ではないだろう。 これを投稿した後の処理(継続)を認証成功後に呼び出す ように表現できるのがKahuaなどの継続ベースのフレームワークだ。

  1. 入力フォームから記事がポストされたら記事投稿後のページを生成して返す。

どう考えても、こんなロジックを書くのがずっと自然だ。 ログイン認証は、このロジックにとっては単なるサブルーチンに過ぎなくなるか、 もしくは意識しなくても良くなる。 そもそもログイン認証は記事投稿のロジックにとって本質ではないのだから、 それらしくロジックを組めてしかるべきだ。

PRINT-AND-NEXT-REPL

残念ながらブラックボックスのまま残っている話題がある。
もちろんPRINT-AND-NEXT-REPLについてである。 これは、call-with-input-fileで「どのようにして入力ポートが生成されるか?」 というのと同じように低レイヤの話題だ。 fooの素からfooを生成する仕組みの中でも継続は結構難しいようだ。 私には実装の解説はとてもじゃないができないので、 作りたい人のための継続入門としては なんでも継続 でも読んでもらいたい。


議論

質問

お手元マルチスレッドのサンプルプログラムについて

Tags: 継続, call/cc


Last modified : 2014/05/15 22:26:10 UTC