SICP 読書ノート#66 - 4.4.2-4.4.3 質問システムはどう働くか〜論理プログラミングは数学的論理か (pp.270-278)

一気に流し読みしましたが、説明ばかりでいまいち頭に入ってこない。

気になる記述を適当にメモ書き。

質問システム

pattern matchingとunificationを中心に構成される

パターンマッチング

pattern matcherはあるデータが指定されたパターン(例：(job ?x ?y))に適合するかをテストするプログラム
pattern matcherはパターン、データ、およびパターン変数の束縛を規定するframeを取る
- Scheme処理系のenvironmentのframeと同じような感じ？
frameはstreamを使って構成される
- なぜstream？単純なqueueではだめ？

合成質問

パターン変数(例：?x)の束縛は、前の質問から順に行われる (たぶん)

ユニフィケーション

パターン変数が複数ある場合に推論的に束縛させていくプログラム？
データベースから規則を読み出してパターンマッチを行う (こともある？)

規則の作用

ユニフィケーションの具体例。こんな感じで合ってる？

(1) (lives-near ?x (Hacker Alyssa P)を規則のlives-nearにマッチさせる。結果は以下の通り

(and (address ?x (?town . ?rest-1))
     (address (Hacker Alyssa P) (?town . ?rest-2))
     (not (same ?x (Hacker Alyssa P))))

(2) データベースから(address ?x (?town . ?rest-1)にマッチするパターンが読み出され、残りテスト、

    (address (Hacker Alyssa P) (?town . ?rest-2))
     (not (same ?x (Hacker Alyssa P)))

で真となるかのフィルタリングが行われる

(3) 真となった場合、出力ストリームに追加される

無限ループ

パターン変数の束縛が収束しない場合に発生する

notに関する問題

(not P)は「Pが真ではない」にあらず
「Pがデータベースの知識からは推論できない」が正しい

問題 4.64

?middle-managerが未束縛のままoutranked-byの再帰呼び出しを行うため、上手く動作しない。

問題 4.65

wheelの規則の実装を見ればわかるが、

(rule (wheel ?person)
      (and (supervisor ?middle-manager ?person)
           (supervisor ?x ?middle-manager)))

社長であるOliverには直属のmiddle managerが4人もいるので、4回ヒットし出力される。

問題 4.66

query systemをhackしてaccumulation-funcitonを追加する必要があると思うが、まだquery systemの実装を見ていないのでパス。(§4.4.4で見る模様)

問題 4.67

これもquery systemの実装を見ていないのでパス

問題 4.68

append-to-fromを使ってreverseの規則を追加する。

まずは問題2.18のreverseをappendを使って実装し直す。

(define (reverse lst)
  (if (null? lst)
      lst
      (append (reverse (cdr lst)) (list (car lst)))))

これを公理的定義で表すと、

(reverse (?z . ())) => (?z)
(reverse ?v) => ?y かつ (append ?y (?u)) => ?x であるならば、 (reverse (?u . ?v)) => ?x

よってreverseの規則は以下の通り。

(assert! (rule (reverse (?z . ())  (?z))))

(assert! (rule (reverse (?u . ?v) ?x)
               (and (reverse ?v ?y)
                    (append-to-from ?y (?u) ?x))))

テスト。

;;; Query input:
(reverse (1) ?x)

;;; Query results:
(reverse (1) (1))

;;; Query input:
(reverse (1 2) ?x)

;;; Query results:
(reverse (1 2) (2 1))

;;; Query input:
(reverse (1 2 3) ?x)

;;; Query results:
(reverse (1 2 3) (3 2 1))

;;; Query input:
(reverse ?x (3 2 1)) ;;=> 返ってこない

問題 4.69

問題4.63のデータと規則に加えて、

(assert! (rule ((great . ?relation) ?x ?y)
               (and (son ?x ?m)
                    (?relation ?m ?y))))

(assert! (rule ((grandson) ?g ?ggs)
               (grandson-of ?g ?ggs)))

とすると、

;;; Query input:
((great grandson) ?x ?y)

;;; Query results:
((great grandson) Irad Lamech)
((great grandson) Enoch Methushael)
((great grandson) Cain Mehujael)
((great grandson) Adam Irad)

次は「§4.4.4 質問システムの実装」から。

@uents blog

Code wins arguments.