Next: 8.6 Resetの実現
Up: 8 Continuation（継続）
Previous: 8.4 Catch としての使い方の例
Call/ccを用いると，自動バックトラックが可能になります．
ここで，ランダムに整数を生成し，その生成されたものを
フィルタリングすることによって所望のデータを計算する
という手続きを考えます．
フィルタリングは，生成されたものが所望のものかどうかを
判断する述語を与えて行うことができます．もし，その述語が
成り立たなければ，新しいデータを生成しなおさなければなりません．
そのように，データの生成をし直す処理がバックトラック処理
になります．
まず，２つの引数をとりそのどちらかをランダムに選んで返すという
ことを考えます．
<cl> (scheme-interpreter)
==> (define backtrack-points nil)
BACKTRACK-POINTS
==> (define (choose-first f g)
(call/cc
(lambda (k)
(set! backtrack-points
(cons (lambda () (k (g)))
backtrack-points))
(f))))
CHOOSE-FIRST
==> (define (random-choice f g)
(if (= 1 (random 2))
(choose-first f g)
(choose-first g f)))
RANDOM-CHOICE
==> (define (integer)
(random-choice
(lambda () 1)
(lambda () (+ 1 (integer)))))
INTEGER
choose-firstは，二つの手続きを引数とし，第二引数の手続きを
backtrack-pointsに追加し，第一引数の手続きを実行します．
random-choiceは，２つの手続きを引数とし，乱数にしたがって，その
どちらかをchoose-firstします．
integerは，１を返す手続きと，integerを呼び出してそれに１加えるという
手続きをrandom-choiceします．
==> (define (fail)
(let ((last-choice (car backtrack-points)))
(set! backtrack-points
(cdr backtrack-points))
(last-choice)))
FAIL
==> (define (even)
(let ((n (integer)))
(if (even? n) n (fail))))
EVEN
次に，偶数だけを返す手続きevenを考えます．
それは，integerで整数を生成して，その生成された
結果が偶数ならばそれを返し，そうでなければ，fail手続きを
実行して，バックトラックします．
failは，呼ばれるごとに，backtrack-pointsに貯えられている手続きを
1つ取り出して実行します．
繰り返しevenを呼び出して実行すると，
==> (define (iter f n)
(write (f)) (newline)
(if (> n 0)
(iter f (- n 1))))
ITER
==> (even)
2
==> (iter even 8)
14
4
4
2
6
2
2
2
8
NIL
という具合になります．
generated through LaTeX2HTML. M.Inaba 平成18年5月6日