Prolog入門

Prologとは

Prologは「事物(Object)」と事物間の「関係(relation)」に関する問題を解くために使われるプログラミング言語。
プログラムを「宣言的に」表現できる。他の言語では「手続き的に」表現している。
自然言語解析や、理解、推論などの人工知能の分野で有効。
PROgramming in LOGics が名前の由来
一階述語論理に基づいている。
1970年頃、フランスの Alain Colmerauer (アラン・コルメロエ)によって開発された。(自然言語の解析をするQ-Systemが基となった。)

Prologプログラム

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

事実: 事物とその関係についていくつかの事実を宣言すること。
規則: 事物とその関係についての規則を定義すること。
質問: 事物とその関係について質問すること。

事実

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

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

  like(taro, hanako).

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

すべての関係と事物の名前は小文字で始まる。

  例:    likes,  taro,  hanako

まず最初に関係の名前が置かれ、次に括弧で囲まれた中にコンマで区切って事物を書く。

  例:  likes(taro, hanako).
        likes ← 関係を表す  (２引数を持つことのできる述語です)
        hanako, taro ← 事物を表す
事実の最後には '.' (ピリオド)が置かれる。

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

  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 :- goal₁, goal₂, ..., goal_N.

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

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

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

実は次のような形の記録をホーン・クローズ (Horn Clause、ホーン節)と言います。Prologの規則はホーンクローズの形式で記述されています。

    P(X,Y,...) ← P₁, P₂, ..., P_n
  [意味]
    P(X,y,...)が真であるためにはP₁ かつ P₂ かつ ... P_n が真でなければならない。

    P₁ かつ P₂ かつ ... P_n が真ならば 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 の「２年ゼミ課題A」の自分のグループ名のところから sazae.pl を提出して下さい。コメントに「A1」といれること。

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

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

オプション課題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」として提出して下さい。