SICP演習問題4.61, 4.62

なんとかquery評価器を実装した．
そのままの実装では動かないので，注意．
変更点は

1. (define false #f) (define true #t)を追加
2. self-evaluating? に ((boolean? exp) #t) を追加
3. (define extend-in-underlying-scheme extend)を追加して，もともとのextendを残す
4. (define user-initial-environment (interaction environment))

参考:http://www29.atwiki.jp/sicpstudygroup/?cmd=word&word=4.4&type=normal&page=naga%3A4-55%2F4-79

この問題は，その前のappendの例をよーく理解してから解いたほうがいいです．
そうしないと，4.68(reverse)の問題がまったくわからない。

exercise 4.61

(load "./evaluator-with-query.scm")
(query-driver-loop)

;; rule1: 前に隣合わせがある場合
(assert! (rule (?x next-to ?y in (?x ?y . ?u))))
;;rule2:  後ろに隣りあわせがある場合
(assert! (rule (?x next-to ?y in (?v . ?z))
               (?x next-to ?y in ?z)))

;;; Query input:
(?x next-to ?y in (1 (2 3) 4))
;;; Query results:
((2 3) next-to 4 in (1 (2 3) 4)) ;rule2
(1 next-to (2 3) in (1 (2 3) 4)) ;rule1

;;; Query input:
(?x next-to 1 in (2 1 3 1))
;;; Query results:
(3 next-to 1 in (2 1 3 1)) ;rule2
(2 next-to 1 in (2 1 3 1)) ;rule1

exercise4.62

;; exercise4.62
;; 手続きでのlast-pair
(define (last-pair lis)
  (if (null? (cdr lis))
      lis
      (last-pair (cdr lis))))

;; 規則でのlast-pair
; rule1
; 任意のリストについて, carがxで, cdrが空リストならリストxを返す
; rule2
; 任意のx, y, zについて, yがlast-pair zであるなら,
; (cons x y)のlast-pairがzになる

(assert! (rule (last-pair (?x . ()) (?x))))  ;rule1
(assert! (rule (last-pair (?x . ?y) ?z)      ;rule2
               (last-pair ?y ?z)))

;;; Query input:
(last-pair (3) ?x)
;;; Query results:
(last-pair (3) (3))

;;; Query input:
(last-pair (1 2 3) ?x)
;;; Query results:
(last-pair (1 2 3) (3))

;;; Query input:
(last-pair (2 ?x) (3))
;;; Query results:
(last-pair (2 3) (3))

;;; Query input:
(last-pair ?x (3))
;; 無限ループ
;; xが(x . y)に分割できないため