問題4.52-4.54

amb評価器の続き。

4.52

if-fail構造の実装。まずanalyzeに追加。

((if-fail? exp) (analyze-if-fail exp))

次の選択子やらを追加。

(define (if-fail? exp) (tagged-list? exp 'if-fail))
(define (if-fail-first-exp exp) (cadr exp))
(define (if-fail-second-exp exp) (caddr exp))

名前が微妙です。analyze-if-failを作ります。

(define (analyze-if-fail exp)
  (let ((first-proc (analyze (if-fail-first-exp exp)))
        (second-proc (analyze (if-fail-second-exp exp))))
    (lambda (env succeed fail)
      (first-proc env
                  (lambda (value fail2)
                    (succeed value fail2))
                  (lambda ()
                    (second-proc env succeed fail))))))

継続ムズい。

;;; Amb-Eval input:
(if-fail (let ((x (an-element-of '(1 3 5))))
           (require (even? x))
           x)
         'all-odd)
;;; Starting a new problem 
;;; Amb-Eval value:
all-odd

;;; Amb-Eval input:
(if-fail (let ((x (an-element-of '(1 3 5 8))))
            (require (even? x))
            x)
         'all-odd)
;;; Starting a new problem 
;;; Amb-Eval value:
8

;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
all-odd

4.53

うーんたぶん(1 3 5 8)と(20 35 110)の和が素数である組の組み合わせの全部をリストにして返すんじゃないかな。

;;; Amb-Eval input:
(let ((pairs '()))
  (if-fail (let ((p (prime-sum-pair '(1 3 5 8) '(20 35 110))))
             (permanent-set! pairs (cons p pairs))
             (amb))
           pairs))
;;; Starting a new problem 
;;; Amb-Eval value:
((8 35) (3 110) (3 20))

っぽいですね。set!でやると戻っちゃうのでこれはできないですし、便利ですね。

4.54

(define (require? exp) (tagged-list? exp 'require))
(define (require-predicate exp) (cadr exp))

(define (analyze-require exp)
  (let ((pproc (analyze (require-predicate exp))))
    (lambda (env succeed fail)
      (pproc env
             (lambda (pred-value fail2)
               (if (not pred-value)
                   (fail2)
                   (succeed 'ok fail2)))
             fail))))

こんな感じで。

;;; Amb-Eval input:
(an-element-of '(1 2 3 4 5))
;;; Starting a new problem 
;;; Amb-Eval value:
1

;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
2

;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
3

;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
4

;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
5

;;; Amb-Eval input:
try-again
;;; There are no more values of
(an-element-of '(1 2 3 4 5))

;;; Amb-Eval input:
(an-random-element-of '(1 2 3 4 5 6))
;;; Starting a new problem 
;;; Amb-Eval value:
1

;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
5

;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
2

;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
4

;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
3

;;; Amb-Eval input:
try-again
;;; Amb-Eval value:
6

;;; Amb-Eval input:
try-again
;;; There are no more values of
(an-random-element-of '(1 2 3 4 5 6))

動きます。

これでamb評価器が終わりました。次から論理型プログラミングになるみたいです。Prologとか面白いですよね。ちょっとしか触ったことないけど。
短いけど今日はここまで。