SICP 読み (216) 4.3.2 非決定性プログラムの例

今日の成果は若干微妙。ふらふら状態でアバレ回ってる感満点ッス。

問題 4.44

以下の手続きをでっち上げてみた。

(define (require p) (if (not p) (amb)))
(define (distinct? items)
 (let ((last (tailend items)))
   (cond ((null? (cdr items)) true)
         ((eq? last (car items)) false)
         (else
          (distinct? (cdr items))))))

(define (tailend seq)
 (define (tailend-iter seq ret)
   (if (null? seq)
       ret
       (tailend-iter (cdr seq) (car seq))))
 (tailend-iter seq '()))

(define (safe? k seq)
 (let ((last (tailend seq)))
   (define (safe-iter p k seq)
     (cond ((= (- k p) 0) true)
           ((= (abs (- (car seq) last)) (- k p)) false)
           ((= (car seq) last) false)
           (else
            (safe-iter (+ p 1) k (cdr seq)))))
   (safe-iter 1 k seq)))

(define (enumerate-seq n)
 (define (enum-seq-iter seq)
   (if (> seq n)
       '()
       (cons seq
             (enum-seq-iter (+ seq 1)))))
 (enumerate-seq 1))

(define (n-queens board-size)
 (define (n-queens-iter n ret)
   (cond ((> n board-size) ret)
         (else
          (let ((l (append ret (apply amb (enumerate-seq board-size)))))
            (require (distinct? l))
            (require (safe? n l))
            (n-queens-iter (+ n 1) l)))))
 (n-queens-iter 1 '()))

きちんと動作する保障が全く無いまま、評価器の primitive-procedures に

       (list 'apply apply)
       (list 'append append)

というナニを追加して評価。

*** ERROR: Unbound variable amb

と言われる。そりゃ外側な gosh は amb なんて知らんわな。大体無理矢理 apply ってあり得んじゃん、と言いつつ apply を syntax にする事を思いつく。反則気味ですが、評価器に入れてしまえ。(ってか完全に反則

と言いつつ以下の手続きを ch4-ambeval.scm に追加。

(define (apply? exp)
 (tagged-list? exp 'apply))
(define (apply-proc exp) (cadr exp))
(define (apply-arg exp) (caddr exp))
(define (analyze-apply exp)
 (analyze (append (list (apply-proc exp)) (apply-arg exp))))

そして以下を analyze に追加

((apply? exp) (analyze-apply exp))

動きません。色々確認した所、apply-arg がきちんと評価されていない模様。その後も色々試していたのですが、評価器の仕様をきちんと理解しないと話にならない事に気がつきました。4.3 節終了後に再度戻って検討してみたいと思います。

その後

構文解析な方面に進んでいるんですが、既にヒッカカッております。もう少しきちんと読まないと駄目だな。で、その中で amb が入れ子になっている手続きがあるんですが、全然さっぱりイメージできず。これは机上でトレイスきちんとやれ、という挑戦ッスか??
とほほ。