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 論理型プログラミング」から。

---

※「SICP読書ノート」の目次はこちら