(wat-aro)

無職から有職者にランクアップしました

SICP 問題 4.62

;; last-pairに該当するルールを作る
(rule (last-pair (?x) (?x)))

(rule (last-pair? (?x . ?y) ?z)
      (last-pair? ?y ?z))

;; 質問
(last-pair (3) (?x))
;; ひとつ目の質問にマッチして
;; ?x=3となるので
(last-pair (3) (3))
;; と出力されるはず.


;; 質問
(last-pair (1 2 3) ?x)
;; まずふたつ目の質問にマッチする.
;; ?y=1, ?z=(2 3).二行目で(last-pair (2 3) ?x)となる.
;; 次にまた二つ目の質問にマッチ.
;; ?y=2,?z=(3).二行目で(last-pair (3) ?x)
;; ひとつ目の質問にマッチ.(last-pair (3) (3))
(last-pair (1 2 3) (3))

;; 質問
(last-pair (2 ?x) (3))
;; まず二つ目の質問にマッチする.
;; ?y=2, ?z=?x, ?x=3.
;; 2行目で(last-pair ?x (3))となる.
;; 実装がわからないのでここから想像.
;; まずひとつ目の質問を評価機は試す.
;; すると(last-pair (3) (3))になる.
;; 次に二つ目の質問を試す.
;; すると(last-pair (?x . ?y) (3))かつ(last-pair ?y (3))
;; なのでどの組み合わせを試しても成り立つ.
;; ここで無限ループになる.
;; 仮にすべての組み合わせを試して,それに対して
;; 二行目の質問もさらにすべての組み合わせに対して成り立つ.