質問システムが何をするのか示すため, ボストン付近で急成長するハイテク企業, マイクロシャフト社の人事記録データベース管理にどう使えるかを示そう. 言語は人事情報へのパターン主導アクセスを提供し, 論理的推論をするため, 一般的規則を利用する.
(address (Bitdiddle Ben) (Slumerville (Ridge Road) 10)) (job (Bitdiddle Ben) (computer wizard)) (salary (Bitdiddle Ben) 60000)各表明はリスト(今の場合三つ組)で, 各要素はまたリストになり得る.
働きづめの達人, Benは会社の計算機部門の責任者で, 二人のプログラマと一人の技術者を監督している. 彼らの記録は次の通り:
(address (Hacker Alyssa P) (Cambridge (Mass Ave) 78)) (job (Hacker Alyssa P) (computer programmer)) (salary (Hacker Alyssa P) 40000) (supervisor (Hacker Alyssa P) (Bitdiddle Ben)) (address (Fect Cy D) (Cambridge (Ames Street) 3)) (job (Fect Cy D) (computer programmer)) (salary (Fect Cy D) 35000) (supervisor (Fect Cy D) (Bitdiddle Ben)) (address (Tweakit Lem E) (Boston (Bay State Road) 22)) (job (Tweakit Lem E) (computer technician)) (salary (Tweakit Lem E) 25000) (supervisor (Tweakit Lem E) (Bitdiddle Ben))Alyssaが監督しているプログラマ訓練生がいる:
(address (Reasoner Louis) (Slumerville (Pine Tree Road) 80)) (job (Reasoner Louis) (computer programmer trainee)) (salary (Reasoner Louis) 30000) (supervisor (Reasoner Louis) (Hacker Alyssa P))これらの人々は, 計算機部門で担当[job]記述の第一項のようにcomputerという語で表示してある.
Benは幹部の社員である. 彼の監督者は会社の社長[big wheel]自身である:
(supervisor (Bitdiddle Ben) (Warbucks Oliver)) (address (Warbucks Oliver) (Swellesley (Top Heap Road))) (job (Warbucks Oliver) (administration big wheel)) (salary (Warbucks Oliver) 150000)
Benが監督している計算機部門の他にも, 会社には経理主任とその助手のいる経理部門がある:
(address (Scrooge Eben) (Weston (Shady Lane) 10)) (job (Scrooge Eben) (accounting chief accountant)) (salary (Scrooge Eben) 75000) (supervisor (Scrooge Eben) (Warbucks Oliver)) (address (Cratchet Robert) (Allston (N Harvard Street) 16)) (job (Cratchet Robert) (accounting scrivener)) (salary (Cratchet Robert) 18000) (supervisor (Cratchet Robert) (Scrooge Eben))社長の秘書もいる:
(address (Aull DeWitt) (Slumerville (Onion Square) 5)) (job (Aull DeWitt) (administration secretary)) (salary (Aull DeWitt) 25000) (supervisor (Aull DeWitt) (Warbucks Oliver))
データベースには, ある仕事の人が他のどういう仕事が出来るかの表明もある. 例えば, 計算機の達人は, 計算機プログラマと計算機技術者の仕事が出来る:
(can-do-job (computer wizard) (computer programmer)) (can-do-job (computer wizard) (computer technician))計算機プログラマは, プログラマ訓練生にとって代れる:
(can-do-job (computer programmer)
(computer programmer trainee))
また周知のように
(can-do-job (administration secretary)
(administration big wheel))
;;; Query input: (job ?x (computer programmer))とする. システムは次のように応答する:
;;; Query results: (job (Hacker Alyssa P) (computer programmer)) (job (Fect Cy D) (computer programmer))
質問入力は, われわれがあるパターン(pattern)にマッチしたデータベースの記載事項を探していることを規定している. この例では, パターンは三つの項目からなる事項で, その第一は文字通りの記号job, 第二は何でもよく, 第三は文字通りのリスト (computer programmer)である. マッチするリストの第二項の「何でもよい」は, パターン変数(pattern variable) ?xで指定する. パターン変数の一般形は, 前に疑問符のついた変数の名前と考える記号である. 少し後で, パターン変数が「何でもよい」を表すパターンに単なる?ではなく, 名前を指定するのが有用な理由を見る. システムは指定されたパターンにマッチする, データベース内のすべての事項を示して単純質問に応答する.
パターンは一つを超える変数を持ってよい. 例えば質問
(address ?x ?y)は, すべての社員の住所をリストする.
パターンには変数はなくてもよい. その場合, 質問は単にそのパターンがデータベースの事項として存在するかどうかを決める. 存在すれば一つのマッチがある筈だし, 存在しなければ, マッチはない.
同じパターン変数は, 一つの質問に一回を超えて現れてよい. つまり同じ「何でもよい」が, 各位置に現れるべきことを指定する. 例えば
(supervisor ?x ?x)は, (われわれの例題のデータベースにその表明はないが)自分自身を監督する人をすべて見つける.
質問
(job ?x (computer ?type))は, 担当の事項で, 第三項目が, 第一要素がcomputerである二要素のリストであるものにマッチする:
(job (Bitdiddle Ben) (computer wizard)) (job (Hacker Alyssa P) (computer programmer)) (job (Fect Cy D) (computer programmer)) (job (Tweakit Lem E) (computer technician))このパターンは
(job (Reasoner Louis) (computer programmer trainee))には, この事項の第三項目は三要素のリストであり, パターンの第三項目は二要素であると規定しているので, マッチしない. パターンを変更し, 第三項目が computerで始る, 任意のリストであってよいとしたければ,
(job ?x (computer . ?type))と指定出来る.62 例えば
(computer . ?type)はデータ
(computer programmer trainee)にマッチし, ?typeはリスト(programmer trainee)になる. これはまたデータ
(computer programmer)にもマッチし, ?typeはリスト(programmer)になり, データ
(computer)にもマッチし, ?typeは空リスト()になる.
単純質問に対する質問言語の処理は, 次のように記述出来る:
•
システムは, 質問パターンの変数への, パターンを満足する(satisfy)
すべての代入---つまり, パターン変数がその値で
具体化される(instantiated with)(取り替えられる)と, その結果がデータベースに存在するような, すべての変数の値の組---を見つける.
• システムは, それを満足する変数の代入により, 質問パターンを具体化したすべてを並べて, 質問に応答する.
パターンに変数がない時は, 質問はそのパターンがデータベースに存在するかどうかの決定に変る. 存在すれば, 空の代入, つまり変数に何の値も代入しないものが, そのパターンをデータベースに対して満足させる.
問題 4.55
データベースから, 次の情報を検索する単純質問を示せ:
a. Ben Bitdiddleに監督されている人すべて;
b. 経理部門[accounting division]のすべての人の名前と担当;
c. Slumervilleに住む人すべての名前と住所.
andは次のように, 計算機プログラマすべての住所を見つけるのに使うことが出来る:
(and (job ?person (computer programmer))
(address ?person ?where))
結果の出力は
(and (job (Hacker Alyssa P) (computer programmer))
(address (Hacker Alyssa P) (Cambridge (Mass Ave) 78)))
(and (job (Fect Cy D) (computer programmer))
(address (Fect Cy D) (Cambridge (Ames Street) 3)))
である. 一般に
(and ⟨query1⟩ ⟨query2⟩ ... ⟨queryn⟩)は⟨query1⟩ ... ⟨queryn⟩を同時に満足させるパターン変数の値のすべての組によって満足する.
単純質問と同様に, システムは, 質問を満足するパターン変数へのすべての代入を見つけ, 次に質問のこれらの値による具体化を示すことで, 合成質問を処理する.
(or (supervisor ?x (Bitdiddle Ben))
(supervisor ?x (Hacker Alyssa P)))
は, Ben BitdiddleかAlyssa P. Hackerが監督するすべての従業員を見つける:
(or (supervisor (Hacker Alyssa P) (Bitdiddle Ben))
(supervisor (Hacker Alyssa P) (Hacker Alyssa P)))
(or (supervisor (Fect Cy D) (Bitdiddle Ben))
(supervisor (Fect Cy D) (Hacker Alyssa P)))
(or (supervisor (Tweakit Lem E) (Bitdiddle Ben))
(supervisor (Tweakit Lem E) (Hacker Alyssa P)))
(or (supervisor (Reasoner Louis) (Bitdiddle Ben))
(supervisor (Reasoner Louis) (Hacker Alyssa P)))
一般に(or ⟨query1⟩ ⟨query2⟩ ... ⟨queryn⟩)は, 少なくても⟨query1⟩ ... ⟨queryn⟩の一つを満足するパターン変数の値のすべての組によって満足する.
(and (supervisor ?x (Bitdiddle Ben))
(not (job ?x (computer programmer))))
はBen Bitdiddleが監督し, 計算機プログラマでない人すべてを見つける. 一般に(not ⟨query1⟩)は⟨query1⟩を満足しないパターン変数へのすべての代入で満足する.63
最後の合成形式はlisp-valueという. パターンの最初の要素がlisp-value の時, 次の要素が, 残りの(具体化した)要素を引数として作用させるLisp述語であることを規定する. 一般に
(lisp-value ⟨predicate⟩ ⟨arg1⟩ ... ⟨argn⟩)は, ⟨predicate⟩を具体化された⟨arg1⟩ ... ⟨argn⟩に作用したものが真であるパターン変数への代入で満足する. 例えば給料が30,000ドルより多い人すべてを見つけるには
(and (salary ?person ?amount)
(lisp-value > ?amount 30000))
と書くことが出来る.64
(rule (lives-near ?person-1 ?person-2)
(and (address ?person-1 (?town . ?rest-1))
(address ?person-2 (?town . ?rest-2))
(not (same ?person-1 ?person-2))))
は, 二人が同じ町に住むなら近くに住む[lives-near]と規定する. 最後のnot節は,
規則がすべての人が自分自身と近くに住むということを防止する. same関係は単純な規則:
(rule (same ?x ?x))で定義する.65
次の規則は, 監督者である人を監督する人を, その機関の「大立物[wheel]」であると宣言する.
(rule (wheel ?person)
(and (supervisor ?middle-manager ?person)
(supervisor ?x ?middle-manager)))
規則の一般形は⟨conclusion⟩をパターン, ⟨body⟩を任意の質問として
(rule ⟨conclusion⟩ ⟨body⟩)である.66 規則は大きな(無限大でさえある)表明の集合, つまり規則の本体を満足する変数で, 規則の結論を具体化したもののすべてを表すと考えることが出来る. 単純質問(パターン)を述べた時, 変数への代入は, 具体化したパターンがデータベースに存在するなら, パターンを満足するといった. しかしパターンは, 必ずしも表明として, データベースに陽に存在する必要はない. それは規則が意味する 暗黙の表明でもよい. 例えば,
(lives-near ?x (Bitdiddle Ben))の質問は
(lives-near (Reasoner Louis) (Bitdiddle Ben)) (lives-near (Aull DeWitt) (Bitdiddle Ben))という結果になる. Ben Bitdiddleの近くに住む, 計算機プログラマをすべて見つけるには,
(and (job ?x (computer programmer))
(lives-near ?x (Bitdiddle Ben)))
と聞くことが出来る.
合成手続きの場合のように, 規則は(上のlives-near規則で見たように,) 他の規則の一部として使うことが出来, あるいは再帰的に定義することも出来る. 例えば規則
(rule (outranked-by ?staff-person ?boss)
(or (supervisor ?staff-person ?boss)
(and (supervisor ?staff-person ?middle-manager)
(outranked-by ?middle-manager ?boss))))
は, ある幹部[staff-person]の監督者がボスであるか, あるいは(再帰的に)その幹部の監督者がボスに身分を越されている[outranked-by]なら, その幹部はその機関においてボスに身分を越されているとする.
(meeting accounting (Monday 9am)) (meeting administration (Monday 10am)) (meeting computer (Wednesday 3pm)) (meeting administration (Friday 1pm))上の表明のそれぞれは, 部門全体の会合に対するものである. Benはまた, 全部門にわたる全社規模の会合の事項も追加した. 会社のすべての従業員はこの会合に出席する.
(meeting whole-company (Wednesday 4pm))a. 金曜の朝, Benはその日にあるすべての会合について, データベースに質問したい. 彼はどういう質問を使うべきか.
(rule (meeting-time ?person ?day-and-time)
⟨rule-body⟩)
c. Alyssaは水曜の朝, 仕事場に着き, その日どの会合に出なければならないか考えた. 上の規則を定義したとして, これを見つけるのに彼女はどういう質問をすべきか.
(lives-near ?person (Hacker Alyssa P))を使い, Alyssa P. Hackerは自分の近くに住む人が探せ, その人と車で出勤出来る. 他方彼女は
(lives-near ?person-1 ?person-2)の質問で近くに住む人同士の対すべてを探そうとした時, 彼女は互いに近くに住む人の対のそれぞれが二度ずつリストされることに気づいた; 例えば
(lives-near (Hacker Alyssa P) (Fect Cy D)) (lives-near (Fect Cy D) (Hacker Alyssa P))どうしてこうなったか. 近くに住む人のリストを見つけ, 各対は一度しか現れないようにする方法はあるか. 説明せよ.
これを質問言語で表すには, 「xとyをappendすると zになる」意味と解釈出来る
(append-to-form x y z)関係について, 二つの規則を定義する:
(rule (append-to-form () ?y ?y))
(rule (append-to-form (?u . ?v) ?y (?u . ?z))
(append-to-form ?v ?y ?z))
第一の規則には本体はなく, ?yのどんな値でも, 結論は成立するということを意味する. 第二の規則では
ドット末尾記法をリストのcarとcdrに名前をつけるのに使っていることに注意しよう.
二つの規則があると, 二つのリストのappendを計算する質問を作ることが出来る:
;;; Query input: (append-to-form (a b) (c d) ?z) ;;; Query results: (append-to-form (a b) (c d) (a b c d))更に衝撃的なのは, 同じ規則が「(a b)にappendすると(a b c d)になるリストは何か」という質問をするのに使えることである. それは次のようにする:
;;; Query input: (append-to-form (a b) ?y (a b c d)) ;;; Query results: (append-to-form (a b) (c d) (a b c d))またappendすると(a b c d)になるリストの対のすべてを聞くことも出来る:
;;; Query input: (append-to-form ?x ?y (a b c d)) ;;; Query results: (append-to-form () (a b c d) (a b c d)) (append-to-form (a) (b c d) (a b c d)) (append-to-form (a b) (c d) (a b c d)) (append-to-form (a b c) (d) (a b c d)) (append-to-form (a b c d) () (a b c d))
質問システムは, 上の質問に対し答を推論するのに規則を使うので, いささか賢明さを示すように見える. 実際次の節で見るように, システムは規則を解きほどくのに, 明確に定義したアルゴリズムに従う. 困ったことに, システムは
appendの場合には印象的に働くが, 4.4.3節で見るように, 一般的な方法は更に複雑な場合には破綻する.
問題 4.61
次の規則はリストの中の隣同士の要素を見つけるnext-to関係を実装する.
(rule (?x next-to ?y in (?x ?y . ?u)))
(rule (?x next-to ?y in (?v . ?z))
(?x next-to ?y in ?z))
次の質問に対する応答は何か.
(?x next-to ?y in (1 (2 3) 4)) (?x next-to 1 in (2 1 3 1))
(son Adam Cain) (son Cain Enoch) (son Enoch Irad) (son Irad Mehujael) (son Mehujael Methushael) (son Methushael Lamech) (wife Lamech Ada) (son Ada Jabal) (son Ada Jubal)Cainの孫, Lamechの息子たち, Methushaelの孫たちを見つけるのに質問システムが使えるように, 「SがFの息子であり, かつFがGの息子であるなら, SはGの孫[grandson]である」, 「WがMの妻であり, かつSがWの息子であるなら, SはMの息子である」(聖書の時代には, 現代より遥かに真であると考えられる.)のような規則を形式化せよ. (更に複雑な関係を推論する規則については問題4.69参照)
62
これは問題2.20で述べたドット末尾記法を使う.
63
実際, notのこの記述は, 単純な場合にだけ成り立つ. notの本当の振舞いは,
遥かに複雑である. notの特殊性を, 4.4.2および4.4.3節で調べる.
64
lisp-valueは質問言語に用意していない演算を実行する時だけ使うべきである. 特に等価性(それは質問言語のマッチはそのために設計されたものだから)や, 非等価性(次に示すsame規則で出来るから)
のテストに使ってはならない.
65
二つのものが同じであるというのには, sameはいらないことに注意しよう: それぞれに同じパターン変数を使うだけでよい. ---まず第一に, 効果的には二つのものではなく, 一つのものなのである. 例えばlives-near規則の?townと, 下のwheel規則の?middle-managerを見よう. sameはlives-near規則の?person-1とperson-2のように, 二つのものを別にしたい時に有用である. 質問の二つの場所に, 同じパターン変数を使うと, 両方の場所で同じ値が現れるようになるが, 異ったパターン変数には, 異った値が現れるとは限らない. (異ったパターン変数に代入される値は同じであったり異っていたりする.)
66
sameのように,
本体のない規則も許すことにしよう. そういう規則は, 規則の結論は変数の任意の値で満足されることを意味すると解釈する.