(and (job ?x (computer programmer))
(supervisor ?x ?y))
または
(and (supervisor ?x ?y)
(job ?x (computer programmer)))
のどちらかを使って質問を形成する.
会社にプログラマより多くの監督者がいれば(通常の場合), データベースはandの第一の節で作られた中間結果(フレーム)のそれぞれに対して走査しなければならないので, 第二のより第一の式を用いる方がよい.
論理型プログラミングの目的は, 計算問題を二つの問題:「何を」計算すべきかと, これを「いかに」計算すべきかに分解する技法をプログラマに提供することである. それを実現するには, 計算しようと思うことを記述するには強過ぎるが, 制御可能な手続き的解釈には弱い数理論理の陳述の部分集合を選ぶ. その意図は, 一方では論理型プログラム言語で規定したプログラムは, 計算機で実行可能な効率よいプログラムであるべきだということである. (「いかに」計算するかの)制御は, 言語の評価の順序を利用することで実現される. われわれは節の順序と各節のサブゴールの順序を, 計算が実効的かつ効率的と思われる順序で行われるよう配置することが出来る必要がある. また同時に, (「何を」計算するかの)計算の結果を, 論理の規則の単純な結果として見ることが出来る必要がある.
われわれの質問言語は, 数理論理の, 手続き的に解釈出来る部分集合と見ることが出来る. 表明は単なる事実(原始的命題)を表す. 規則は, 規則の本体が成り立つ場合には, 規則の結論も成り立つという包含を表す. 規則は, 規則の結論を実現させるには, 規則の本体を実現させよという, 自然な手続き解釈を持つ. 従って, 規則は計算を規定する. しかし規則はまた数理論理の陳述と見られるから, 同じ結果は, 完全に数理的論理の範囲で作業して得られると仮定し, 論理型プログラムが実現させた「推論」を正当化出来る.76
(assert! (married Minnie Mickey))を含む, 有名な結婚のデータベースを設定していると考えよう. いま
(married Mickey ?who)と聞けば, システムはAがBと結婚していれば, BはAと結婚しているということを知らないので, 応答は得られない. そこで規則
(assert! (rule (married ?x ?y)
(married ?y ?x)))
を表明し, もう一度(married Mickey ?who)と質問する. 困ったことに, これはシステムを次のように無限ループへ追い込む:
(and (supervisor ?x ?y)
(not (job ?x (computer programmer))))
(and (not (job ?x (computer programmer)))
(supervisor ?x ?y))
二つの質問は同じ結果は生じない. 第一の質問は(supervisor ?x ?y)にマッチするデータベースの事項をすべて見つけることで始り, 次に結果のフレームを, ?xの値が(job ?x (computer programmer))を満足するものを除去してフィルタする. 第二の質問は, 入力のフレームから(job ?x (computer programmer))を満足するものを除去するフィルタリングで始る. 入力フレームは空なので, データベースに(job ?x (computer programmer))を満足するパターンが存在しないかチェックする. 一般にこの形の事項が存在するので, not節は空フレームをフィルタし, フレームの空ストリームを返す. 従って合成質問全体では, 空ストリームを返す.
問題はわれわれのnotの実装が, 変数の値に対し, フィルタとして働くようになっていることである. notが, 変数のあるものが, (上の例の?xのように)未束縛のまま残っているフレームに対して処理されるなら, システムは期待していない結果を生じる. 同様な問題は lisp-valueを使う時にも起きる. ---Lispの述語は, 引数のあるものが未束縛だと働けない. 問題4.77参照.
質問言語のnotが数理論理のnotから異るもっと重大な点がある. 論理では「not P」の陳述はPが真でないと解釈する. しかし質問システムでは, 「not P」はデータベースの知識からは推論出来ないという意味である. 例えば4.4.1節の人事のデータベースがあると, システムはBen
Bitdiddleは野球マニアではない, 外では雨が降っていない, 2 + 2は4ではない, のようなすべてのnot文をいそいそと推論する.78
つまり論理型プログラムのnotは, 必要な情報はすべてデータベースに含まれているという, いわゆる
閉世界仮説(closed
world assumption)を反映している.79
問題 4.64
Louis Reasonerは誤ってoutranked-by規則(4.4.1節)をデータベースから消去してしまった. 彼はこれに気がつくと急いでそれを再入力した. 困ったことに規則を少し変更して
(rule (outranked-by ?staff-person ?boss)
(or (supervisor ?staff-person ?boss)
(and (outranked-by ?middle-manager ?boss)
(supervisor ?staff-person ?middle-manager))))
のように入力した. Louisがこの情報をシステムに入力した後, DeWitt
Aullが来てBen Bitdiddleが身分を越されているのは誰か知ろうとした. 彼は質問(outranked-by (Bitdiddle Ben) ?who)を出した. 答を返した後, システムは無限ループに入った. なぜか説明せよ.
(wheel ?who)驚いたことにシステムは
;;; Query results: (wheel (Warbucks Oliver)) (wheel (Bitdiddle Ben)) (wheel (Warbucks Oliver)) (wheel (Warbucks Oliver)) (wheel (Warbucks Oliver))と応答した. Warbucks Oliverはなぜ四回も出力されたか.
(sum ?amount
(and (job ?x (computer programmer))
(salary ?x ?amount)))
で出来ればよい. 一般にBenのシステムは, accumulation-functionを
sum, averageまたはmaximumのようなものであり得るとして
(accumulation-function ⟨variable⟩
⟨query pattern⟩)
の形の式を許す. Benはこれを実装するのは何でもないと考え, 単に質問パターンをqevalに送り込んだ. これはフレームのストリームを作り出す. 次に彼はストリームの各フレームから指示された変数の値を取り出すマップ関数にこのストリームを渡し, 結果の値のストリームをアキュムレートする関数に渡す. Benが実装を完了し, 使ってみようとした時, 問題4.65のwheel質問の結果に悩みながらCyが近寄ってきた. CyがBenにシステムの応答を見せると,
Benは「あぁ, 駄目だ. この単純なアキュムレーション方法は働かない」とうめいた.
Benには何が分ったか. 彼が状況を打開するのに使える方法を概説せよ.
問題 4.67
本文と問題4.64で示したような単純なループが避けられるように, 質問システムにループ検出器を組み込む方法を考案せよ. 一般的な考え方は, システムは現在の推論の鎖のある種の歴史を保持し, すでに作業した質問の処理を始めないようにするものである. この歴史にどのような情報(パターンやフレーム)を入れるべきか. またどうチェックしたらよいか述べよ. (4.4.4節で, 質問システムの実装の細部を学んでから, システムを修正して, ループ検出器を組み込むとよい.)
問題 4.68
問題2.18の与えられたリストと同じ要素を逆順に含むリストを返すreverse演算を実装する規則を定義せよ. (ヒント: append-to-formを使う.) その規則は(reverse (1 2 3) ?x)と(reverse ?x (1 2 3))
の両方に答えられるか.
問題 4.69
問題4.63のデータベースとそこで形式化した規則から始めて, 孫の関係に「great[孫の子]」を追加する規則を考案せよ. これによりシステムはIradはAdamの孫の子[great-grandson]である, JabalとJubalはAdamの孫の子の子の子の子の子[great-great-great-great-great-grandson]であると推論出来る.
(ヒント: 例えばIradについての事実を((great grandson) Adam Irad)のように表そう. リストの最後が語grandsonで終るかどうかを見る規則を書く. ?relをgrandsonで終るリストとし, 関係((great . ?rel) ?x ?y)を導く規則を表すのにこれを使え.) 出来た規則を((great grandson) ?g ?ggs)や(?relationship Adam Irad)のような質問でチェックせよ.
75
推論の特定の方法が正当であるというのは, わかり切ったことではない. 真の前提から出発すれば, 真である結論のみが導かれることを証明しなければならない. 規則の作用で表現される推論の方法は, Aが真で, AならBが真なら, Bが真と結論出来る
三段論法(modus ponens)というよく知られた論法である.
76
論理的プログラムが実現した「推論」という時, 計算が終了することを仮定していることに同意してこの文を限定する必要がある. 困ったことに, この限定された文も, notやlisp-valueを使っているため, 質問言語のわれわれの実装では正しくない. (またPrologのプログラムや, 現在の他の論理型プログラム言語でも正しくない.) 次に述べるように, 質問言語のnotの実装は, 数理論理のnotとは首尾一貫してはいず, lisp-valueはそれ以上の複雑さをもたらす. われわれは言語からnotとlisp-valueを除き, プログラムを単純質問とandとorだけを使って書くことに同意して, 数理論理と首尾一貫した言語を実装することは出来る. しかしこれでは, 言語の表現能力を著しく低下させる. 論理型プログラム研究の主要な関心事の一つは, 基盤の表現能力を犠牲にせず, 数理論理ともっと首尾一貫性を実現する方法を探すことである.
77
これは論理の問題ではなく, われわれの解釈系の用意した論理の手続き的解釈の一つである. ここではループに落ち込まないように解釈系を書くことは出来る. 例えば表明や規則から導かれる証明のすべてを,
深さ優先でなく, 幅優先で数え上げることが出来る.
しかしこういうシステムは, プログラムでの推論の順を利用することを困難にする. こういう問題への技巧的な制御を組み込む試みの一つは,
deKleer他1977に記述がある. こういう重大な制御の問題を防ぐ技法のもう一つは, 特定の種類のループ検出器のような(問題4.67)特別な知識を組み込むことである. しかしシステムを, 推論実行中に無限ループに落ち込むのから防ぐ, 信頼出来る一般的な方法はあり得ない. 適当に選んだ関数fについて, 「P(x)が真なことを示すには, P(f(x))が真なことを示せ」という形の悪魔の規則を想像せよ.
78
質問(not (baseball-fan (Bitdiddle Ben)))を考える. システムは(baseball-fan (Bitdiddle Ben))はデータベースにはないことに気がつく.
そこで空フレームはパターンを満足せず, 初期のフレームのストリームからフィルタで除去されない. そこで質問の結果は空フレームであり, 入力質問を具体化するのに使われ, (not (baseball-fan (Bitdiddle Ben)))を生じる.
79
このnotの扱いの議論と正当化は
Clark(1978)の論文にある.