Prolog入門

Prologとは

Prologプログラム

Prologのプログラムは次の3つの要素から成る。

事実

「taro likes hanako (太郎は花子を好きである)」という文を考えると、 主語が「taro」、目的語が「hanako」、述語が「likes」となります。 これは「taro」という事物と「hanako」という事物の関係(前者が後者を likesである)を表現しています。

Prologでは、この述語に注目して、事物の関係を表します。

  like(taro, hanako).

次の点に注意して下さい。

事実は必ずしも関係だけを表すものではなく、事物の性質を表すものでも 構いません。たとえば「りんごは赤い」という事実は次のように表現できます。

  red(apple).

Prologでは事実の集まりを「データベース (database)」と呼びます。

質問

いくつかの事実があるとき、質問をすることができます。 質問は ?- という記号を前につけて表します。

?- likes(taro,hanako).   ←入力
yes                    ←Prologの回答

Prologは質問に適合する事実があれば "yes" と回答し、なければ "no" と 回答します。 つまり Prolog における "no" は「知らない」ということです。

変数

もし taro が好むものを調べようとするとき「taroは音楽が好きか?」とか 「taroはゲームが好きか?」などと繰り返し質問をして yes-no を答えさせる のは面倒です。このような時は、知りたい事物を「変数」にして与えます。

?- likes(taro, X).   ← 入力
X = hanako           ← Prologが変数の値を表示する
yes                  ← Prologの回答

Prologは「大文字で始まる名前」は変数(variable)です。 変数は「値が決まっているか」か「決まっていないか」のどちらかで、 Prologはすべての事実を探索してこの変数が表す事物を見つけます。 ただし、「事物」は変数にできますが「述部」は変数にできない ことに注意が必要です。

つぎのようなデータベースがある場合の質問を考えてみましょう。

likes(taro, flowers).
likes(taro, hanako).
likes(jiro, hanako).
?- likes(taro,X).
 X = flower   ←エンター(リターン)を入力する
 yes
?- likes(taro,X).
 X = flower ;  ← 第一の解を表示する。セミコロンを入力すると、
 X = hanako ;    ← 第二の解を表示する。さらにセミコロンを入力すると
 no            ←これ以上、解は存在しない。

Prologが解を見つけて表示しているときに ; を入力することによって、 Prologに別の解を再探索させることができます。 別の解を見つけるために後戻りすることをバックトラック(backtrack)と 言います。

連言

AND を表す関係を記述したいときには、コンマで区切って並べて記述します。 たとえば「taroとhanakoがお互いに好きか?」という質問を表したければ 次のように書くことができます。

?- likes(taro,hanako), likes(hanako,taro).

また、「taroとhanakoとjiroがすべて好きなものは何か?」は次のように 表現できます。

?- likes(taro,X), likes(hanako,X), likes(jiro,X).

次のようなデータベースがあったときに、どのように動作するかを 考えましょう。

likes(taro, wine).
likes(taro, beer).
likes(mary, book).
likes(mary, beer).
likes(jiro, beer).
?- likes(taro,X), likes(mary,X), likes(jiro, X).
  X = beer    ← Prologが見つけた解

まずlikes(taro,X)を探して X=wine となります。 そのXで likes(mary,X) を満たそうと likes(mary,wine)を探しますが、 存在しないので「後戻り(backtrack,バックトラック)」をして別の解を探します。 するとlikes(taro,beer)から X= beerが見つかるのでそのXでlikes(mary,X) を満たそうとします。これは成功するので、 さらにlikes(jiro,X)を満たそうと likes(jiro,beer)を探しにいきます。 最終的に X=beer は連言をすべて満たしますので解となります。

規則

「ある事実が、他のいくつかの事実に依存する」ことを表すために 「規則」を使います。

「johnはwineが好きな女性を好きだ」という事実は、次のような規則で 表現できることでしょう。

likes(john, X) :- likes(X, wine), female(X).

さらに「johnは車と飛行機が好きな女性を好きだ」という事実もあれば、 次のような規則を追加します。

likes(john, X) :- likes(X, car), likes(X, airplane), female(X).

このようにORの関係の事実や規則は並べて書くことができます。


Prolog言語

Prologの規則は一般に次のような形式で表します。

  head :- goal1, goal2, ..., goalN.

これは、「goal1からgoalN までのすべての 規則が成り立てば規則headは成り立つ」ということを表しています。 つまり 「goal1 AND goal2 AND ... AND goalN ならば head である」という意味です。

headをヘッド部(head)、goalの部分をボディ部(body)といいます。 ボディ部にはゴールが記述されます。ゴールは複数書かれても構いません。 「ゴール部が無い、すなわち前提条件がない規則が事実である」と みなすこともできます。

Prologでは、ヘッド部が一致するものは上から順に探索します。 またボディ部に書かれたゴールは左から右へという順序で探索されます。

実は次のような形の記録をホーン・クローズ (Horn Clause、ホーン節)と 言います。Prologの規則はホーンクローズの形式で記述されています。
    P(X,Y,...) ← P1, P2, ..., Pn
  [意味]
    P(X,y,...)が真であるためにはP1 かつ P2 かつ ... Pn が真でなければならない。

    P1 かつ P2 かつ ... Pn が真ならば P(X,y,...)は真である。

課題A1

漫画「サザエさん」の登場人物に関する以下のデータベースを 作りなさい。ファイル名はsazae.plとしましょう。

ただし、「XとYが等しくない」という命題は「X \== Y」と表すことに 注意しましょう。

表現すべき人物: namihei, fune, sazae, katsuo, wakame, masuo, tara

述語説明
事実
child(C,P)CはPの子ども
male(X)Xは男性
female(X)Xは女性
規則
father(F,C)FはCの父親
mother(M,C)MはCの母親
grandfather(G,X)GはXの祖父
sibling(X,Y)XはYの兄弟または姉妹
uncle(U,X)UはXのおじ
aunt(A,X)AはXのおば
nephew(N,X)NはXの甥
sazae.pl
male(namihei).
female(fune).
female(sazae).
...
child(sazae,namihei).
child(katsuo,namihei).
...
father(F,C) :- child(C,F), male(F).
...

〆切までに 課題提出WEB の「2年ゼミ課題A」の自分のグループ名のところから sazae.pl を提出して下さい。 コメントに「A1」といれること。

提出した後は、必ず上記のWEBを再度参照して、正しく 提出されていることを確認しておいて下さい。

(注)バックトラックさせたとき、同じ答えが2度出力されることがありますが、 今はそれで構いません。

オプション課題A2

時間が余れば他の関係についても定義を sazae.pl に追加してみて下さい。 もしも完成したら、上記と同じ提出先にコメント欄を「A2」として 提出して下さい。

例:
    sister(X,Y)     XはYの姉妹である
    brother(X,Y)    XはYの兄弟である
    cousin(X,Y)     XはYのいとこである
    ancestor(X,Y)   XはYの祖先(親の親の...)である

オプション課題A3

時間が余れば「ちびまるこちゃん」における登場人物の関係を maruko.pl に定義してみて下さい。 もし完成したら、上記と同じ提出先にコメント欄を「A3」として 提出して下さい。