nakayama-blog

Ex. 4.77

実際には、not は and 中でしか使われない。

(not B) とか (A or (not B)) なんていうのは、not がフィルターである限り無意味だからだ。

これを意味ある query にしたければ、(ALL and (not B)) とか (A or (ALL and (not B))) とするしかない。結局、not は and と組みで使うしかない。なので、この辺の対応は運用にまかせることとする。

ということで、not を遅延させるというのは、and すなわち conjoin の中で not の処理を後回しにするだけでよい。

こんな感じにする。

(and (not A)
     B
     C)

これを

(and B
     C
     (not A))

という風に処理する。

and が入れ子になった場合

(and A
     (and (not B)
          C
          D)
     E
     F)

これの not の遅延のさせ方は2つある。

①
(and A
     (and C
          D)
     E
     F
     (not B))
②
(and A
     (and C
          D
          (not B))
     E
     F)

フィルター not をなるべく遅延させるという意味では①がいいのだが、問題文の指示どおり、処理を速くするために②のほう採用する。このほうがコーディングも簡単。

ということで

(define (conjoin conjuncts frame-stream)
  (let ((ccc (reorder-conjuncts conjuncts)))
    (if (empty-conjunction? ccc)
	frame-stream
	(conjoin (rest-conjuncts ccc)
		 (qeval (first-conjunct ccc)
			frame-stream)))))

(define (reorder-conjuncts conjuncts)
  (let ((a '())
	(b '()))
    (define (grouping ccc)
      (if (not (empty-conjunction? ccc))
	  (let ((first (first-conjunct ccc)))
	    (if (eq? (type first) 'not)
	      (set! b (append b (cons first '())))
	      (set! a (append a (cons first '()))))
	    (grouping (rest-conjuncts ccc)))))
    (grouping conjuncts)
    (append a b)))

こんな感じ。まったく面白みのないソース。単に conjuncts の順番を入れ替えてから実行するようにしただけ。

一応動く。

;;; Query input:
(and (not (same Adam ?x)) (son ?x ?y))
;;; Query results:
(and (not (same Adam Ada)) (son Ada Jubal))
(and (not (same Adam Ada)) (son Ada Jabal))
(and (not (same Adam Methushael)) (son Methushael Lamech))
(and (not (same Adam Mehujael)) (son Mehujael Methushael))
(and (not (same Adam Irad)) (son Irad Mehujael))
(and (not (same Adam Enoch)) (son Enoch Irad))
(and (not (same Adam Cain)) (son Cain Enoch))
(and (not (same Adam Lamech)) (son Lamech Jubal))
(and (not (same Adam Lamech)) (son Lamech Jabal))

lisp-valueのほうも同じように and のなかで後ろ回しにすればよいと思われる。(ry

複雑な query や変な rule と絡めた場合はまったく考えていないけど、もういいです。