SICP 読書ノート#58 - 4.3 非決定性計算 - 継続とは何か (pp.245)
「§4.3 Schemeの変形---非決定性計算」に入りました。
最初はテキストの内容の全貌が掴めず、サンプルコードをロードしてambを叩きまくっていたのですが、だんだん何がわからないかが頭の中で整理できてきました。
→ambの振る舞いがどういうことなのかわからない
→非決定性計算が何なのかがわからない
→継続が何なのかがわからない
おそらく、継続に関する説明がないままにambを使った例題が続いた後に、ambの実装で唐突に継続が出てくるところがわかりにくい原因だと思います。さらに、Schemeでは継続を作り出すcall/cc (call-with-current-continuation) があるのに、この章では登場しません。
そこで、まずは「継続」とは何かから学びました。
継続とは何か
$.ajax({ url: "ajax.html", }).done(function(data){ alert('success!!'); }).fail(function(data){ alert('error!!!'); });
のように、通信に成功した場合はdone()、失敗した場合はfail()といったコールバックが呼び出されると思います。
このように、◯◯の後は□□、といった処理のリレー渡しのような実装スタイルを「継続渡しスタイル」といいます。なお、SICP本文のamb評価器も成功/失敗処理を継続渡しスタイルで実装しています。
- 作者: ポールグレアム,野田開,Paul Graham
- 出版社/メーカー: オーム社
- 発売日: 2007/03
- メディア: 単行本
- 購入: 10人 クリック: 146回
- この商品を含むブログ (128件) を見る
ただし、SchemeやLispでいうところの「継続」はプラスαがあります。
On Lispでは次のように書かれています。
継続とは、動作中に凍結したプログラムだ。すなわち計算処理の状態を含んだ一つの関数的オブジェクトだ。保存された計算処理は、それが中断された時点から再開する。プログラムの状態を保存し、後に再開できる能力は、ある種の問題解決に素晴しい威力を発揮する。
この計算処理を保存し再開する能力を、汎用的に与えてくれる仕組みがcall/ccです。
call/cc入門
文章ではうまく説明できないので、コードを動かしながら解説します。書いていると自分の理解も深まりますしね。
他のScheme処理系と同様、Racketでもcall/ccは最初から使えるので前準備は不要です。
まずはcall/ccを呼んでみます。
racket@> (+ 1 (call/cc (lambda (cc) 2)) 3) => 6
この(call/cc (lambda (cc) 2))のcc(current continuation)がまさに継続で、この瞬間の計算処理の状態を含むオブジェクトとなります。ここではccは特に使わず、call/ccで単に2を返すので、普通に(+ 1 2 3) => 6となります。
次にccをfrozenというグローバル変数に束縛させます。
racket@> (define frozen false) racket@> (+ 1 (call/cc (lambda (cc) (set! frozen cc) 2)) 3) => 6
frozenを叩いてみると、#<continuation>と返ってきます。ccは継続オブジェクトということが分かります。
racket@> frozen => #<continuation>
frozenに引数を作用させます。
racket@> (frozen 10) => 14 racket@> (+ 100 (frozen 10)) => 14 racket@> (+ (frozen 10) 100) => 14
この例から分かるように、frozenを作用させた時の振る舞いは、
(lambda (x) (+ 1 x 3))のような処理が実行される- コンテキストはcall/ccの実行時へジャンプ。作用元へは戻ってこない
となります。On Lispの「継続とは、動作中に凍結したプログラムだ。すなわち計算処理の状態を含んだ一つの関数的オブジェクトだ」の説明通り、ccには処理だけでなくスタックの状態を全て保持され、ccを呼び出すときにそのスタックの状態から処理を再開するように振る舞うことがわかります。
さらに(lambda (x) (+ 1 x 3))のような処理について、もう少し検証してみます。
racket@> (frozen false) +: contract violation expected: number? given: #f argument position: 2nd other arguments...: 1 3 ;; => 引数は2番目ということが分かる racket@> (frozen 10 20 30) result arity mismatch; expected number of values not received expected: 1 received: 3 values...: 10 20 30 ;; => 引数は1つしかとれない
このことから、(lambda (x) (+ 1 x 3))のような処理という言い方で間違いないかと思います。
今度は、変数の加算処理で実験してみます。
racket@> (define a 1) racket@> (define b 3) racket@> (+ a (call/cc (lambda (cc) (set! frozen cc) 2)) b) => 6 racket@> (frozen 10) => 14 racket@> (set! a 100) racket@> (set! b 200) racket@> (frozen 10) => 211
最後の結果は310ではなく211でした。call/ccが呼び出された時の計算処理状態では、aはすでに評価されています。よって、frozenの実行時には(lambda (x) (+ 1 x b))のような処理が実行されることとなり、結果は211となります。
次に、call/ccの中でccを実行してみます。
racket@> (set! frozen false) racket@> (+ 1 (call/cc (lambda (cc) (set! frozen cc) (cc 10) 2)) 3) => 14 racket@> frozen => #f
ccは
(lambda (x) (+ 1 x 3))のような処理のため、(cc 10) => 14となる。また、そこで処理を抜け出すため14がそのまま返る(cc 10)の実行は、(set! frozen cc)より前のためfrozenは#fのまま
となります。
レキシカルクロージャはどうでしょうか。
racket@> (define accumlator false) racket@> (let ((x 0)) (call/cc (lambda (cc) (set! accumlator cc))) (set! x (+ x 1)) x) => 1 racket@> (accumlator) => 2 racket@> (accumlator) => 3 racket@> (accumlator 100) ;; この場合の引数は無視される => 4
継続においてもレキシカルクロージャはもちろん有効です。
深さ優先探索の例
On Lispの例をそのまま引用。carをleft-branch、cdrをright-branchとする木について考えます。
(define t1 '(a (b (d h) (c e (f i) g))))
この木を深さ優先で探索するプログラムはcarを優先させればよいので、以下のように実装できます。
(define (dft tree) (cond ((null? tree) 'done) ((not (pair? tree)) (display (format "~A " tree))) (else (dft (car tree)) (dft (cdr tree)))))
実行結果は以下の通り。
racket@> (dft t1) => a b d h c e f i g 'done
次にnodeにヒットすると結果を出力して探索を停止、restartで探索を再開するようなプログラムを、call/ccを使って実装し直します。
(define *saved* '()) (define (dft-node tree) (cond ((null? tree) (restart)) ((not (pair? tree)) tree) (else (call/cc (lambda (cc) (set! *saved* (cons (lambda () (cc (dft-node (cdr tree)))) *saved*)) (dft-node (car tree))))))) (define (restart) (if (null? *saved*) 'done (let ((cont (car *saved*))) (set! *saved* (cdr *saved*)) (cont))))
これを実行すると以下のようになります。left-branchの探索を進める際に、right-branchの探索を*saved*にpushし、やがてnodeにぶつかると探索を停止します。(restart)を実行するとright-branchの探索が再開される。
racket@> (dft-node t1) => 'a racket@> (restart) => 'b racket@> (restart) => 'c ;; ... racket@> (restart) => 'done
nodeの出力とrestartを続けて呼ぶことで、dftと同じく全ノードを深さ優先探索するプログラムとなります。
racket@> (define (dft2 tree) (set! *saved* '()) (let ((node (dft-node tree))) (cond ((eq? node 'done) 'done) (else (display (format "~A " node)) (restart))))) racket@> (dft2 t1) => a b d h c e f i g 'done
ただしこの例だと、わざわざcall/ccを使わなくてもdft-nodeを実装できてしまうけど… :-P
racket@> (define (dft-node2 tree) (cond ((null? tree) (restart)) ((not (pair? tree)) tree) (else (begin (set! *saved* (cons (lambda () (dft-node2 (cdr tree))) *saved*)) (dft-node2 (car tree)))))) racket@> (dft-node2 t1) => 'a racket@> (restart) => 'b racket@> (restart) => 'c ;; ...
長くなったのでここまで。
次回はcall/ccを使ってambオペレータを実装します。
