SICP 読書ノート#63 - 4.3.3 amb評価器の実装 (pp.254-261)
この節ではamb評価器の内部に迫ります。
個人的には自前でambオペレータを作った際に、継続やバックトラックと散々戯れたので、ここはさらっと読み流します。
amb評価器で重要そうなのは、やはりamb式の評価ですよね。
(define (analyze-amb exp) (let ((cprocs (map analyze (amb-choices exp)))) (lambda (env succeed fail) (define (try-next choices) (if (null? choices) (fail) ((car choices) env succeed (lambda () (try-next (cdr choices)))))) (try-next cprocs))))
- まず、ambの選択肢を評価し、実行手続きに変換する
- 次に、
- 選択肢がなければ
(fail)
させる (→バックトラックが発生) - 選択肢が残っていれば、残りの選択肢を
fail
側に継続渡しして最初の実行手続きを実行させる
- 選択肢がなければ
- ような実行手続きを返す
amb評価器は継続渡しスタイルで非決定性決算を実装しているだけで、本質的にはcall-ccを使った自前のaambオペレータと変わらないと思います。
(define *alternatives* '()) (define (choose choices) (if (null? choices) (try-again) (call/cc (lambda (cc) (define try-next (lambda () (cc (choose (cdr choices))))) (set! *alternatives* (cons try-next *alternatives*)) (force (car choices)))))) ;; ... (define (amb . choices) (choose choices))
というわけで、理解したということにして先へ進みます。
SICPで全部の問題解いている人、ほんとすごいよなぁ (遠い目...)
次は「§4.4 論理型プログラミング」から。