<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))))) INTEGERchoose-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という具合になります.