Prologプログラミング: データベース


記号

Prologでは, 記号は英小文字(a, b, ..., z)の後に, 英字(下線も英字に含める)または数字を0文字以上続けた名前で表される.
        a  coffee  n_Tamura  may2
英字の大文字と小文字は区別される. いくつかのPrologシステムでは漢字も使用できる. SICStus Prologでは,シングル・クォーテーションでくくる.
        'コーヒー'  '田村'

変数

Prologでは, 変数は英大文字(A, B, ..., Z, 下線も英大文字に含める)の後に, 英字または数字を0文字以上続けた名前で表される.
        A  Coffee  MAY2  _1

リスト

Prologでは,リストは要素をコンマで区切って並べたものを 角カッコでくくって表す.たとえば
        [jan, 31, 1957, thu]
        [pi, 3.14]
であり,一般的には
        [要素1, 要素2, ..., 要素n]
と書く. 要素の個数はリストの長さと呼ばれる. 長さ0のリスト(空リスト) [] は記号 nil で表すこともできる.

要素が,またリストであってもよい.

述語

Prolog では述語 (predicate) と呼ばれるものを 定義することによってプログラムを作り上げていく.

述語は,データの間の関係やデータの持つ性質を表す. たとえば太郎 (記号 taro で表す) と次郎 (記号 jiro で表す)の間で, 太郎が次郎の父親であるという関係が存在するとする. この関係は「父親である」という関係を表す述語 father を 使って以下のように表現できる.


    father(taro, jiro)
すなわち, father(F, C) により 「 F が C の父親である」という関係を表現している. taro と jiro は引数と呼ばれる.

同様に,「男である」という性質を表す述語 male を用いると, 太郎が男であるということは次のように表現できる.


    male(taro)
一般的には,

    述語(引数1, 引数2, ..., 引数n)
と書くことで引数の間の関係(あるいは性質)を表す.
練習問題1
太郎を表すのに taro ではなく, 大文字を使って Taro としたほうがわかりやすいと思うが, なぜそうしないだろうか.

事実

Prolog では述語 (あるいは関係といってもいい) は, 事実 (fact) または規則 (rule) によって定義される. ここでは,事実による定義について説明する (規則については後述).

上で述べた,太郎が次郎の父親であるという関係を正しい事として 定義するには,以下の行を Prolog プログラム中に記述する (最後にピリオドがあることに注意!).


    father(taro, jiro).
これは事実 (fact) と呼ばれる.

同様に,太郎が男であるという事実は,プログラム中で


    male(taro).
と記述する.

Prolog を使ってみる (その1)

Prologシステムを立ち上げると, プロンプト(入力促進記号)として | ?- が表示される.

    | ?- 
以下では,次の8つの事実からなるプログラムを例にとる.

    father(naoyuki, hyogo).
    father(saburo, naoyuki).
    father(saburo, shinji).
    father(yoshihisa, hisako).
    mother(hisako, hyogo).
    mother(yoko, naoyuki).
    mother(yoko, shinji).
    mother(nobuko, hisako).
ここで,述語 father は「第 1 引数が第 2 引数の父親である」という関係を表し, 述語 mother は「第 1 引数が第 2 引数の母親である」という関係を表す. また,このプログラムは family.pl という名前のファイルに 書かれているものとする.

Prolog プログラムをファイルから読み込むには, [ファイル名]. と入れる. family.pl というファイルからプログラムを読み込むには 次のようにする.


    | ?- [family].
    yes
    | ?- 
プログラムが正しく読み込まれた時は yes と表示される.

読み込まれたプログラムを表示させるには, listing. と入力する. fatherとmotherの順序は,処理系によっては逆に表示されることもある.


    | ?- listing.
    father(naoyuki,hyogo).
    father(saburo,naoyuki).
    father(saburo,shinji).
    father(yoshihisa,hisako).
    mother(hisako,hyogo).
    mother(yoko,naoyuki).
    mother(yoko,shinji).
    mother(nobuko,hisako).
    yes
系図を描くと以下の通り.

    saburo === yoko    yoshihisa === nobuko
            |                     |
      +-----+-------+             |
      |             |             |
    shinji        naoyuki ===== hisako
                            |
                          hyogo

単純な質問

Prolog では,質問 (問合せ,query) により, 関係が成立するかどうかを調べることができる. たとえば, naoyuki が hyogo の父親であるかどうかを調べるには, ?- father(naoyuki, hyogo). という質問を入力する. 関係が成立すれば yes と表示され, 成立しなければ no と表示される (より正確には,成立することがいえなければ).

    | ?- father(naoyuki, hyogo).
    yes
    | ?- father(saburo, hyogo).
    no
yes が表示されることを成功, no が表示されることを失敗と呼ぶことがある.

知りたい箇所を変数にして質問することもできる. たとえば,誰が hyogo の父親であるかを調べるには, ?- father(F, hyogo). という質問を行う. Prolog システムは,質問の関係が成立するような変数の値を答える. 変数にどのような値を代入しても成立しない場合は no と答える.


    | ?- father(F, hyogo).
    F = naoyuki ? 
    yes
    | ?- father(F, saburo).
    no
各質問ごとで変数は独立である. したがって,上の例での 1 つめの質問 ?- father(F, hyogo). の変数 F と, 2 つめの質問 ?- father(F, saburo). の変数 F とは 異なる変数である.

逆の質問,すなわち誰が naoyuki の子供であるかを知るには 第 2 引数を変数にすれば良い.


    | ?- father(naoyuki, C).
    C = hyogo ? 
    yes
変数を含んだ質問では,複数の答えが存在する場合がある. たとえば, saburo の子供は naoyuki と shinji の 2 人がいるから ?- father(saburo, C). の答えは 2 種類存在するはずである. Prolog ではこのような場合,プログラム中での記述の順序にしたがって 答えが表示される. したがって,この例では C=naoyuki がまず示され, ユーザからの入力待ちになる.

    | ?- father(saburo, C).
    C = naoyuki ? 
ここで,セミコロン (;) を入れてリターンキーを押すと, Prolog システムは次の答えを求め,表示する.

    | ?- father(saburo, C).
    C = naoyuki ? ;
    C = shinji ? 
さらに,セミコロン,リターンと入力すると, Prolog システムは次の答えを求めようとするが,存在しないので no と表示する.

    | ?- father(saburo, C).
    C = naoyuki ? ;
    C = shinji ? ;
    no
セミコロン,リターンの代わりに,単にリターンを入力した場合は, システムは次の答えを求めないで, yes と表示する. 実はこれまでの例, ?- father(F, hyogo). などでも 答えの表示に対してリターンを入力していた.

すべてを変数にした質問も可能である. たとえば, ?- father(F, C). という質問をすると, 変数が 1 つの場合と同様に, 質問の関係が成立するような変数の値が表示される.


    | ?- father(F, C).
    F = naoyuki,
    C = hyogo ? 
この場合も,答えの表示される順序はプログラムでの記述の順序に従う. また,セミコロン,リターンにより次の答えが表示されるのも同じである.

    | ?- father(F, C).
    F = naoyuki,
    C = hyogo ? ;
    F = saburo,
    C = naoyuki ? 
練習問題2
hyogo に子供がいて yoko という名前だとしよう ( naoyuki の母親の yoko とは別人). どの様な事実を付け加えればよいか.
練習問題3
このプログラムに常識とは矛盾する事実,たとえば father(hyogo, hyogo). を付け加えることはできるだろうか (常識では,自分が自分の父親にはなれない).

複雑な質問

Prolog では,単純な質問を組み合わせた複雑な質問をすることもできる.

たとえば,誰が hyogo の父方の祖父かという質問を考えてみる. hyogo の父を変数 F で, hyogo の父方の祖父を変数 G で表したとすると, hyogo と F との関係は father(F, hyogo) で, F と G との関係は father(G, F) で表される. そして,求める答えはその 2 つの関係が両方とも成立する場合である. これを Prolog では, 2 つの関係をコンマ (,) でつないだ 次のような質問で表現する.


    | ?- father(F, hyogo), father(G, F).
    F = naoyuki,
    G = saburo ? 
コンマは論理における「かつ」 (連言,and) を意味している. もちろん, 2 つの関係の順序を入れ換えても同じ意味である.

    | ?- father(G, F), father(F, hyogo).
    F = naoyuki,
    G = saburo ? 
Prolog システムは,コンマを含んだ質問を左の述語から順に調べていく. たとえば, ?- father(F, hyogo), father(G, F). の質問では, まず father(F, hyogo) の答えを求める. 答えは F=naoyuki である. 次に,その答えのもとで father(G, F), すなわち father(G, naoyuki) の答えを求める. 答えは G=saburo となり,質問全体の答えは F=naoyuki, G=saburo となる.

質問 ?- father(G, F), father(F, hyogo). の場合も左から順に処理される. まず father(G, F) の最初の答え G=naoyuki, F=hyogo が求められる. 次に father(F, hyogo), すなわち father(hyogo, hyogo) の関係を調べるが, 成立しないで失敗する. このような場合, Prolog は後戻り (バックトラック) して, 別の答えを探す. すなわち,後戻りして father(G, F) の次の答えを求めにいき, G=saburo, F=naoyuki を得る. 続いて father(F, hyogo),すなわち father(naoyuki, hyogo) を調べる. こんどは成功し,質問全体の答えは F=naoyuki, G=saburo となる.

練習問題4
hyogo の母方の祖父を求めるにはどの様な質問をすれば良いか.
練習問題5
?- father(F, naoyuki), father(F, C). は 何を質問していると考えられるだろうか.
練習問題6
質問 ?- father(F, naoyuki), father(F, C). は どのように処理されるか.

規則

前にも触れたように, Prolog では事実だけでなく 規則 (rule) と呼ばれるものによって新たな述語(すなわち関係)を 定義することができる.

たとえば,「 P が C の親である」という関係を parent(P, C) で表し, この述語を既存の father と mother という述語で定義することを考える. これらの述語間の関係を考えると, まず father(P, C) ならば parent(P, C) である. これは Prolog では以下の規則として表現される.


    parent(P, C) :- father(P, C).
ここで, :- は「ならば」を意味する. ただし :- の右側が条件で左側が結論である. すなわち P :- Q. により「 Q ならば P 」を意味する. さらに, mother(P, C) ならば parent(P, C) も正しい.

    parent(P, C) :- mother(P, C).
父親と母親だけが親であるから, 述語 parent は以上の 2 つの規則で定義できる.

「ならば」の条件がもっと複雑であってもよい. たとえば「祖父である」という関係を述語 grandfather で表し, この述語を既存の father と mother という述語で定義することを考える. 父親の父親は祖父であり,母親の父親も祖父であるから, 述語 grandfather は次のような 2 つの規則で定義できる.


    grandfather(GF, C) :- father(F, C), father(GF, F).
    grandfather(GF, C) :- mother(M, C), father(GF, M).
あるいは, parent と father を使って次の規則 1 つで定義することもできる.

    grandfather(GF, C) :- parent(P, C), father(GF, P).
練習問題7
「 GM が C の祖母である」を表す述語 grandmother(GM, C) を定義せよ.
練習問題8
「 C が P の子供である」を表す述語 child(C, P) を定義せよ.
練習問題9
「 C が G の孫である」を表す述語 grandchild(C, G) を定義せよ.
練習問題10
「 X が Y の兄弟姉妹である」を表す述語 sibling(X, Y) を定義せよ.
練習問題11
「 X が Y の兄弟である」を表す述語 brother(X, Y) を定義せよ.

Prolog を使ってみる (その2)

以下の行を family.pl に付け加えたとする.

    parent(P, C) :- father(P, C).
    parent(P, C) :- mother(P, C).
    grandfather(GF, C) :- parent(P, C), father(GF, P).
付け加えたプログラムを読み込むには,再度 [family] と入力すれば良い.

    | ?- [family].

規則によって定義された述語に対しても,事実の場合と同様に質問を することができる.


    | ?- parent(P, hisako).
    P = yoshihisa ? ;
    P = nobuko ? ;
    no
    | ?- grandfather(GF, hyogo).
    GF = saburo ? 
規則の場合も事実の場合と同様に, プログラム中で記述した規則の順序にしたがって答えが表示される. 上の例では, 「父親は親である」にあたる規則がプログラム中で先に現れているから, hisako の親として父親の yoshihisa が先に表示されている.

ここでさらに「男である」を意味する述語 male と, 「女である」を意味する述語 female の事実を付け加える.


    male(hyogo).
    male(naoyuki).
    male(shinji).
    male(saburo).
    male(yoshihisa).
    female(hisako).
    female(yoko).
    female(nobuko).
練習問題12
「 S が P の息子である」を表す述語 son(S, P) を定義せよ.
練習問題13
「 U が C のおじである」を表す述語 uncle(U, C) を定義せよ.

再帰的定義

Prolog では再帰的定義が可能である. たとえば,「先祖である」という関係は 次のように再帰的に定義される.

    ancestor(A, C) :- parent(A, C).
    ancestor(A, C) :- parent(P, C), ancestor(A, P).
1 行目の規則は「親は先祖である」を意味し, 2 行目の規則は「親の先祖は先祖である」を意味する.

hyogo の先祖は次のようにして求められる.


    | ?- ancestor(A, hyogo).
    A = naoyuki ? ;
    A = hisako ? ;
    A = saburo ? ;
    A = yoko ? ;
    A = yoshihisa ? ;
    A = nobuko ? ;
    no
練習問題14
「 D が P の子孫である」を表す述語 descendant(D, P) を定義せよ.

最初に戻る 次へ