next up previous
Next: 8.6 Resetの実現 Up: 8 Continuation(継続) Previous: 8.4 Catch としての使い方の例

8.5 Call/CCによる自動バックトラック

Call/ccを用いると,自動バックトラックが可能になります. ここで,ランダムに整数を生成し,その生成されたものを フィルタリングすることによって所望のデータを計算する という手続きを考えます. フィルタリングは,生成されたものが所望のものかどうかを 判断する述語を与えて行うことができます.もし,その述語が 成り立たなければ,新しいデータを生成しなおさなければなりません. そのように,データの生成をし直す処理がバックトラック処理 になります. まず,2つの引数をとりそのどちらかをランダムに選んで返すという ことを考えます.

<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は,2つの手続きを引数とし,乱数にしたがって,その どちらかをchoose-firstします. integerは,1を返す手続きと,integerを呼び出してそれに1加えるという 手続きを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日