プログラミングGaucheの１９章で継続のお勉強

「リストlisから述語pred?が真になる要素を見つけ、その要素とseedに手続きprocを適用する」
を普通の自己再帰で記述すると以下のようになる。

(define (find-fold pred? proc seed lis)
(cond [(null? lis) seed]
[(pred? (car lis))
(let *1]))

この関数を使って、1から10までのリストから、奇数のみの合算値を求める場合、
以下のような呼び出しとなる。
gosh> (find-fold odd? + 0 '(1 2 3 4 5 6 7 8 9 10))
25

このfind-foldを使って、1から10までのリストから奇数のみのリストを抜き出すとすると、
以下のような呼び出しとなる。
(find-fold odd?
(lambda (elt seed) (print "found: " elt) (cons elt seed))
'()
'(1 2 3 4 5 6 7 8 9 10))

lambdaを関数として定義しておく、
(define (process elt seed)
(print "found: " elt)
(cons elt seed))

ここまでは、普通の再帰呼び出しのfind-foldに、手続きprocessを渡しているので
mapみたいな感じ。

なので、まず計算して、その時点での奇数リストを作りだして、次の自己再帰呼び出しに
find-foldが渡してあげるイメージ。
これがいわゆるCall-Return方式

これを変更して、計算結果のリストが自然に次の自己再帰に渡されていく流れを作る。
これがいわゆる継続渡し方式となる。

継続渡しにする場合は、自己再帰を呼び出す前に、予め計算していたseed2の算出から
次の処理に流れていくようにコードを変更する。
つまり計算結果を受け取る処理を指定するようにする。

(define (find-fold2 pred? proc/cont seed lis)
(cond [(null? lis) seed]
[(pred? (car lis))
(proc/cont (car lis)
seed
(lambda (seed2)
(find-fold2 pred? proc/cont seed2 (cdr lis))))]
[else
(find-fold2 pred? proc/cont seed (cdr lis))]))

処理の流れを変更したので、引数proc/contに渡される関数も変更する。

(define (process/cont elt seed cont)
(print "found: " elt)
(cont (cons elt seed)))

processとは、eltとseedを使って計算した結果を、引数として追加した手続きcontに
渡すようにする。

gosh>(find-fold2 odd? process/cont '() '(1 2 3 4 5 6 7 8 9 10))
found: 1
found: 3
found: 5
found: 7
found: 9
(9 7 5 3 1)

find-fold2に渡されたprocess/contは、(process/cont (car lis) seed lambda式)が渡され、
process/cont内では、最終的に(lambda式 (cons (car lis) seed))が呼ばれることになる。
ここから自己再帰による継続手続きの連鎖が始まる。
しかし、奇数リストを作るというconsは逐次実行されていくことになる。

ここで自己再帰のある時点を計算途中で抜き取り、トップレベルで
処理を続けるか否かコントロールできるようになる。

process/contの代わりに、process/breakという関数を作成し、process/breakが呼び出される度に
グローバル変数に処理途中の計算を束縛する。

(define next #f)
(define (break val) val)
(define (process/break elt seed cont)
(set! next
(lambda ()
(print "found: " elt)
(cont (cons elt seed))))
(break #f))

process/breakは、process/cont内で実装していた処理を、引数無しのlambda式としてnextに束縛し、
(break #f)で単純に#fを返却して終了する。

すると、計算途中のlambda式がnextに保存されたままの状態となる。
ちなみに、process/breakにはcontとして、find-fold2内のlambdaでラップされたfind-fold2の再帰呼び出しを
保持しているので、nextが評価されれば、評価される度に、後続の再帰呼び出しが呼ばれていくことになる。

gosh> (find-fold2 odd? process/break '() '(1 2 3 4 5 6 7 8 9 10))
#f
gosh> (next)
found: 1
#f
gosh> (next)
found: 3
#f
gosh> (next)
found: 5
#f
gosh> (next)
found: 7
#f
gosh> (next)
found: 9
(9 7 5 3 1)
gosh> (next)
found: 9
(9 7 5 3 1)

find-fold2の実装は変わっていないので、find-fold2に渡すproc/contを切り替えるだけで
find-fold2の実行制御を変更することが出来る。

ここで、process/breakは元々のprocessの処理を大幅には変えていないことに着目する。
(print "found: " elt)
(cons elt seed))
をするのが処理の中心で、nextに束縛したり、#fを返すのは外出しに出来る。
そこで、以下のような関数を定義する。

(define (breaker proc)
(lambda (elt seed cont)
(set! next (lambda () (cont (proc elt seed))))
(break #f)))

processを引数にしてbreakerを呼び出せば、process/brakerを同じ処理となる。
これは、２引数eltとseedを受け取る(proc elt seed)の処理の中断と再開を実現する
機能を付加することと同意となる。

gosh>(find-fold2 odd? (breaker process) '() '(1 2 3 4 5 6 7 8 9 10))
#f
gosh> (next)
found: 1
#f
gosh> (next)
found: 3
#f
gosh> (next)
found: 5
#f
gosh> (next)
found: 7
#f
gosh> (next)
found: 9
(9 7 5 3 1)

さらに、find-fold2を実行した結果を引き渡す、処理もfind-fold2に渡してみる。

(define (find-fold/cont pred? proc/cont seed lis cont)
(cond [(null? lis) (cont seed)]
[(pred? (car lis))
(proc/cont (car lis)
seed
(lambda (seed2)
(find-fold/cont pred? proc/cont seed2 (cdr lis) cont)))]
[else
(find-fold/cont pred? proc/cont seed (cdr lis) cont)]))

gosh> (find-fold/cont odd? process/cont '() '(1 2 3 4 5 6 7 8 9 10) print)
found: 1
found: 3
found: 5
found: 7
found: 9
(9 7 5 3 1)
#

やっぱ関数を関数に渡せるって強力だわ。

• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • -

call/ccを使った継続渡し

(define (process/cc elt seed)
(call/cc
(lambda (cont)
(print cont) ; debug
(print "found: " elt)
(cont (cons elt seed)))))

gosh>
(find-fold odd? process/cc '() '(1 2 3 4 5 6 7 8 9 10))
#
found: 1
#
found: 3
#
found: 5
#
found: 7
#
found: 9
(9 7 5 3 1)

うーん、find-foldにprocess/ccを渡した場合、(cont (cons elt seed))の
contには何が入っているのだろうか？
#と表示されているが・・・

breakerによる処理の横取り
(define (breaker/cc proc break)
(lambda (elt seed)
(call/cc
(lambda (cont)
(set! next (lambda () (cont (proc elt seed))))
(break #f)))))

gosh> (call/cc
(lambda (cont0)
(find-fold odd? (breaker/cc process cont0) '() '(1 2 3 4 5 6 7 8 9 10))))
#f
gosh> (next)
found: 1
#f
gosh> (next)
found: 3
#f
gosh> (next)
found: 5
#f
gosh> (next)
found: 7
#f
gosh> (next)
found: 9
(9 7 5 3 1)

うわー、さっぱわかんねぇ。

いや、わかったかも

引き続きSchemeの継続の話。 自前で継続渡し方式でコードを書く場合、
残りの処理は明示的にlambda式を書くことになるので、流れが把握できる。
しかし、call/ccで継続を取り出す場合は、内部的にcall/ccされてるS式が呼び出された瞬間、
そのS式が呼び出された部分の結果を引数にしたlambda式が生成され、それを呼び出すんだと思う。

gosh> (define cc #f)
cc
gosh> (* 3 (call/cc (lambda (k)
(set! cc k)
(+ 1 2))))
9

このような式があった場合、初回は
(* 3 (+ 1 2))で9になり、グローバル変数ccに継続が束縛された段階で
(lambda (x) (* 3 x))みたいな感じになると。

gosh> (cc 10)
30
gosh> (+ 100 (cc 10))
30

gosh> (define *save* ())

*1:seed2 (proc (car lis) seed))) (find-fold pred? proc seed2 (cdr lis)))] [else (find-fold pred? proc seed (cdr lis