Prolog Programming

Prolog で扱う事実とは？

私たちが使う文章には主語と述語があります。たとえば「太郎はコーヒーが好きである」という文では、主語は「太郎」で、述語は「好き」となりますね。Prolog は述語を中心に物事の関係を表します。「好き」は「太郎」と「コーヒー」の関係を表しています。この関係を Prolog で表現すると次のようになります。

like(taro, coffee).

Prolog の場合、最後に必ずピリオド ( . ) をつけます。忘れないように注意してください。ほかにも考えてみましょう。

太郎はココアが好き => like(taro, cocoa).
花子は紅茶が好き => like(hanako, tea).

このように、関係を示す言葉をいちばん前に持ってきて表現する方法を「述語表記」といいます。後ろに続く言葉を引数といいます。すなわち、Prolog では以下の形式で事実を表現します。

述語(引数, ..., 引数). 

それでは、実際に今までの例をプログラムしてみましょう。ファイル like.pl に like(taro, coffee). だけを書いて保存します。Prolog の場合、ソースファイルの拡張子は .pl が標準です。

対話モード (REPL) でプログラムを読み込むには、述語 consult(filename). を使うか、リストの表記法 [filename]. を使います。リストはあとで詳しく説明します。ファイル名 filename を指定するとき、拡張子 .pl は付けないでください。

?- [like].
true.

これでファイル like.pl を読み込み、「太郎はコーヒーが好きである」という事実が定義されました。true は成功したことを表すデータです。逆に、失敗したことを表すデータが false です。昔のバージョンでは、true と false のかわりに YSE と NO が表示されました。

なお、SWI-Prolog は端末からプログラムを入力することもできます。consult や [ ] などプログラムを読み込む述語に user を指定します。user は標準入出力を指定する特別なファイル名です。

?- [user].
|: like(taro, coffee).
|: ^D
true.

?-

プログラムの入力を終了するときは CTRL-D を押してください。

それでは、太郎がコーヒーを好きか、たずねてみましょう。質問する場合は、その関係をそのまま入力します。

?- like(taro, coffee).
true.

まあ、これは当たり前ですね。では、花子は紅茶が好きか、たずねてみましょう。

?- like(hanako, tea).
false.

これは「花子は紅茶が好きである」という事実がないので、Prolog は違うといってきたのです。それでは、like(hanako, tea). と like(taro, cocoa). を like.pl に定義して、like.pl を再度読み込んでください。そして質問してみましょう。

?- like(hanako, tea).
true.

?- like(taro, cocoa).
true.

?-

今度は、そうだよといってきました。

ところで、ある事実に対して true と false しかたずねることができないのであれば、面白くありませんね。事実が増えてくると、たとえば、太郎が好きなものは何か？ とか、コーヒーを好きな人は誰か？、といった質問をしたいと思うでしょう。もちろん、Prolog はそのような質問を受け付けることができます。そのために「変数」というマジックを使います。Prolog の変数は他のプログラミング言語の変数とは少々変わっています。

Prolog の変数はちょっとヘン？

Prolog の標準であるエジンバラ Prolog に準拠してる処理系では、半角英大文字から始まる名前を変数として扱います。SWI-Prolog もそうです。

【変数の例】 X Y Z Prolog Lisp Abc
【名前の例】 x y z prolog lisp abc

使い方は、何を当てはめてもよい場合に変数を用いて表します。たとえば、先ほどの質問の場合、「太郎は何が好きか」の「何が」を変数で表すのです。この質問は次のようになります。

like(taro, X).

変数は X 以外でもかまいません。それでは、たずねてみましょう。Prolog には今まで入力した事実が定義されているものとします。

?- like(taro, X).
X = coffee

他の処理系では X = coffee -> のように、-> が表示されることがあります。これは別の解を調べるか、Prolog がたずねていることを示す記号です。SWI-Prolog の場合、この記号は表示されませんが、ここでセミコロン (;) を入力すると、Prolog は別解を探します。それでは別解があるか調べてみましょう。

X = coffee ;
X = cocoa.

?-

; を入力すると Prolog は別の解を探索し、今度は cocoa を見つけました。coffee と cocoa 以外の解は無いので、ここで探索を終了します。

変数は複数使うことができます。like(X, Y) と質問すれば、「好き」という関係を持つすべての事実を求めることができます。ただし、述語の部分を変数にすることはできません。

?- like(X, Y).
X = taro,
Y = coffee ;
X = taro,
Y = cocoa ;
X = hanako,
Y = tea.

?-

別解を求めない場合は、リターンキーを入力します。すると、入力待ちの状態 (トップレベル) に戻ります。

?- like(X, Y).
X = taro
Y = coffee

?-

今までの例でわかるように、Prolog の変数は一般的なプログラミング言語の変数とは違った働きをします。Ｃ言語や Java などの変数は値を記憶する入れ物であり、その中に格納されるデータの種類は決まっています。

ところが、Prolog の変数はそれだけでは何が入るのか決まっていません。Prolog は質問に答える場合、質問と一致する事実がないか調べます。このことを「パターンマッチング (pattern matching)」といいます。このパターンマッチングによって変数の値が決まるのです。

パターンマッチングの動作を追いかけてみましょう。質問 like(X, Y). と、事実 like(taro, coffee). について考えます。最初、変数 X, Y ともに値は定まっていません。このような変数を「自由変数」といいます。まず X と taro を調べます。Prolog の場合、自由変数はどんなデータにでもパターンマッチングは成功します。そして、変数にはそのデータが代入されます。

この場合、X に taro という値がセットされます。その次に Y と coffee を調べます。Y も自由変数なのでパターンマッチングは成功します。このとき、Y に coffee という値がセットされます。残りの項目がないので、like(X, Y). と like(taro, coffee). のパターンマッチングは成功です。Prolog は変数 X と Y の値を出力します。

それでは質問を変えて like(X, X). としたらどうでしょう。最初の X は同じですね。その次の X と coffee は一致するのでしょうか。X には taro がセットされています。Prolog は変数に値がセットされている場合、その値を使ってパターンマッチングを行います。この場合、taro と coffee を比較します。同じ値ではないのでパターンマッチングは失敗となります。Prolog は false と出力します。

別解を求める場合は、値がセットされた変数を自由変数に戻します。そして次に定義されている事実とパターンマッチングを行います。この動作を「バックトラック (backtracking)」といい、Prolog の大きな特徴になっています。Prolog の基本的な動作は、「パターンマッチングとバックトラックを組み合わせたもの」といえるでしょう。

Prolog のプログラムとは？

●規則

Prolog は複数の事実を用いて一つの事実を表すことができます。これを「規則 (rule)」といいます。一般に、規則は次のような形をとります。

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

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

先頭の head を「頭部」といい、残りの goal をまとめて「体部」といいます。頭部と体部は :- で区切ります。また、各々の goal を「ゴール」といいます。そして、事実、規則および質問のことを「節 (clause)」と呼びます。規則の中で頭部しかない特別なものが事実である、と考えてもいいでしょう。

簡単な例を示します。SWI-Prolog を起動して、次に示すファイル fly.pl を読み込んでください。

リスト : fly.pl

fly(X) :- airplane(X).
airplane(jet_plane).
airplane(helicopter).

最初の節は、「飛行機は空を飛ぶ」という規則を表しています。次の 2 つの節は、「ジェット機は飛行機である」と「ヘリコプターは飛行機である」という事実を表しています。このことから、「ジェット機は空を飛ぶ」という結論を導くことができます。では、Prolog に質問してみましょう。

?- fly(jet_plane).
true.

それでは、太郎君が空を飛べるか、質問してみましょう。

?- fly(taro).
false.

太郎君は空を飛べません。ところで、空を飛べるのは飛行機だけではありません。スーパーマンも空を飛べます。実は、太郎君はなんとスーパーマンだったのです。次のように fly.pl を修正して再度読み込んでください。

リスト : fly.swi の修正

fly(X) :- airplane(X).
fly(X) :- superman(X).   /* 追加 */

airplane(jet_plane).
airplane(helicopter).
superman(taro).          /* 追加 */

Prolog のコメントは、% から改行まで (1 行コメント) と、/* から */ まで (複数行コメント) の二種類があります。それでは太郎君が飛べるか、再び質問してみます。

?- fly(taro).
true.

太郎君は空を飛ぶことができました。変数を使うと、空を飛ぶものすべてを求めることができます。

?- fly(Y).
Y = jet_plane ;
Y = helicopter ;
Y = taro.

?-

このように、Prolog は定義された事実と規則から答えを見つけてくれます。これは Prolog がプログラムを実行するときに、「バックトラック (backtracking)」を行っているからです。

たとえば、簡単な例として迷路を考えてみましょう。ある地点 A で道が左右に分かれているとします。ここで左の道を選んで先へ進むと、行き止まりになってしまいました。この場合は A 地点まで戻って右の道へ進まないといけませんね。つまり、失敗したら「後戻り」して別の道を選ぶ、という試行錯誤をゴールに行き着くまで繰り返すわけです。Prolog の場合も、このような試行錯誤をしながら答えを探しているのです。

●Prolog の動作

それでは、このプログラムを例にして Prolog の動作を具体的に説明します。簡単なプログラムですが、実行過程はけっこう複雑です。最初に、図 1 を見てください。

Prolog は質問とマッチングする規則または事実を探します。規則は頭部とマッチングするものを選択します。この場合、fly(X) とマッチングし、規則 fly(X) :- airplane(X). を選択します。

2 つの変数 Y と X がパターンマッチングに成功するのは、不思議に思われるかもしれません。Y と X は変数ですが、お互いにまだ値が定まっていない自由変数です。Prologでは、自由変数同士のパターンマッチング ^[*2] は成功するのです。これは他の言語とは違う Prolog の大きな特徴です。これにより変数 Y と X が関連付けられます。

次に体部 airplane(X) を実行します。図 2 を見てください。

同じように airplane(X) とマッチングする規則または事実を選択します。この場合、事実 airplane(jet_plane) とマッチングし、変数 X の値は jet_plane となります。

事実ですから他に実行するゴールはありません。体部の実行を続けますが、airplane(X) は最後のゴールなので、規則 fly(X) :- airplane(X). は成功します。

この規則を呼び出したのは質問 fly(Y) です。呼び出した規則が成功したので、質問の答えが見つかりました。Y は X とマッチングしているので、Y = jet_plane となります。

次は、別解の探索を説明しましょう。図 3 を見てください。

Prolog では、別解を探索することを「再試行」といいます。Prolog は実行した節の順番を覚えていて、最後に実行した節から探索を再開します。この場合は、規則 fly(X) :- airplane(X). のゴール airplane(X) です。再度 airplane(X) とマッチングする節を探索します。このとき、変数は自由変数に戻されること、すでにマッチングした事実 airplane(jet_plane). は探索の対象から外されることに注意してください。

今度は airplane(helicopter). とマッチングしました。X の値は helicopter になります。最後のゴール airplane(X) が成功したので、今度も規則 fly(X) :- airplane(X) は成功です。Y = helicopter という結果になります。

また再試行しましょう。 図 4 を見てください。

1 回目の再試行と同様に airplane(X) を実行しますが、これ以上事実は定義されていません。したがって、airplane(X) は失敗します。ゴールが失敗した場合、一つ前のゴールに後戻り (バックトラック) します。すべてのゴールが失敗したら、その規則は失敗となります。この場合、後戻りするゴールがないので、規則 fly(X) :- airplane(X). は失敗します。

規則が失敗した場合、その規則を呼び出した節に後戻りします。この場合は質問 fly(Y) に戻り、fly(Y) とマッチングする別の節を探します。すると、規則 fly(X) :- superman(X). が見つかります。今度はこの規則を実行します。同じようにゴールを実行して、taro という答えが見つかります。

またまた再試行しましょう。図 5 を見てください。

今までと同じように superman(X) の別解を探索しますが、マッチングする節は見つかりません。したがって、規則 fly(X) :- superman(X). は失敗します。そして、質問 fly(Y) に後戻りしますが、もはやマッチングする節はありません。したがって fly(Y) は失敗します。fly(Y) は質問でしたから、探索を終了してトップレベルに戻ります。

このように、簡単なプログラムですが Prolog の動作は複雑です。とりあえずバックトラックのことを考えずに、Prolog が答えを見つけてくれる、と理解してもらってもかまいません。実際、バックトラックのことを考えなくても、Prolog でプログラムを作ることができます。

まあ、そこが Prolog の面白いところなんですが、複雑なプログラムになると、どうしてもバックトラックのことを考えなければならない場合も出てきます。そのときになったら、また詳しく説明することにしましょう。

簡単な例題 : 家系図

もう少し具体的な例として、次のような家系図を考えてみましょう。

この家系図を男性、女性、父親、母親の関係を表す述語で定義します。

リスト : 家系図の定義

/* 男性 */
male(taro).
male(ichiro).
male(jiro).
male(saburo).
/* 女性 */
female(hanako).
female(tomoko).
female(sachiko).
female(youko).
/* 父親 */
father_of(taro, ichiro).
father_of(taro, jiro).
father_of(taro, tomoko).
father_of(ichiro, saburo).
father_of(ichiro, youko).
/* 母親 */
mother_of(hanako, ichiro).
mother_of(hanako, jiro).
mother_of(hanako, tomoko).
mother_of(sachiko, saburo).
mother_of(sachiko, youko).

Prolog で述語 p(a, b) を記述した場合、a は b の p なのか、それとも a の p が b なのか、はっきりしないことがあります。たとえば、father(taro, ichiro). の場合、太郎は一郎の父親なのか、それとも太郎の父親が一郎なのか、はっきりわからないのです。

英語では前者を taro is father of ichiro と書きますので、Prolog でも father_of(taro, ichiro) と _of をつけて表すことが多いようです。後者の場合はそのままです。今回の例題はこの表記法に従っています。

それでは、定義した事実を使って規則を作ってみましょう。まず「両親 (parents_of)」という規則を定義します。両親は、父親か母親という事実を満たせばいいですね。このような場合、Prolog では次のように定義します。

リスト : 両親 (parents_of) の定義

parents_of(X, Y) :- father_of(X, Y).
parents_of(X, Y) :- mother_of(X, Y).

「両親は父親である」と「両親は母親である」という規則を定義するだけです。このようなプログラムでも、Prolog では最初の節が失敗したら次の節が選択されるので、「両親は父親または母親である」という条件を満たしています。

他のプログラム言語では、「または」という条件は「論理和 (or)」を使って表現するのが一般的ですが、Prolog では規則を並べることで実現できます。逆に、「かつ」という条件は、他のプログラミング言語では「論理積 (and)」を使いますが、Prolog では前に説明したようにゴールを並べることで実現できます。このように、Prolog は事実および規則を宣言することでプログラミングを行います。もちろん、一般的な or にあたる制御構造も備えていますのでご安心を。

それでは実行してみましょう。一郎の両親は誰か質問します。

?- parents_of(X, ichiro).
X = taro ;
X = hanako.

?-

正解は太郎と花子です。うまく動作していますね。それでは、この述語を使って「息子 (son_of)」という規則を定義しましょう。X が Y の息子であるならば、Y は X の両親でかつ X は男性のはずです。Prolog では次のように定義します。

リスト : 息子 (son_of) の定義

son_of(X, Y) :- parents_of(Y, X), male(X).

「かつ」は規則でゴールを順番に並べれば実現できましたね。まず parents_of(Y, X) を満たす関係を求めます。そのあと male(X) で X が男性であることを確かめます。male(X) で失敗しても、parents_of(Y, X) に後戻りして次の候補を探すので大丈夫です。

それでは実行してみましょう。

?- son_of(X, hanako).
X = ichiro ;
X = jiro ;
false.

?-

花子の息子は一郎と次郎である、と答えが出ました。

ここで、male(X) を female(X) に変更すると、「娘 (daughter_of)」の関係を表すことができます。

リスト : 娘 (daughter_of) の定義

daughter_of(X, Y) :- parents_of(Y, X), female(X).

最後に、「祖父 (grandfather_of)」の関係を求める規則を定義しましょう。これは今までと違ってちょっと面倒です。X の祖父 Y を求めるには、まず X の両親を求め、さらにその父親を求めます。母方と父方の両方に祖父がいますから、父親の父親を求めるのでは母方の祖父がわかりません。このような場合、X と Y 以外の変数を使うとうまくいきます。プログラムは次のようになります。

リスト : 祖父 (grandfather_of) の定義

grandfather_of(X, Y) :- parents_of(Z, Y), father_of(X, Z).

parents_of(Z, Y) で、変数 Z には Y の父親か母親がセットされています。そして、father_of(X, Z) で Z の父親を探せばいいわけです。変数を使うことで実行結果を保持し、それを次のゴールへ渡すことができるのです。

それでは実行してみましょう。

?- grandfather_of(X, saburo).
X = taro ;
false.

?- grandfather_of(X, Y).
X = taro,
Y = saburo ;
X = taro,
Y = youko ;
false.

?-

祖父と同じように、「祖母 (grandmother_of)」の関係も定義できますのでやってみて下さい。

算術演算

SWI-Prolog で扱うことのできる数値は次の 3 種類です。

• 整数 (integer)
  整数の大きさに制限はありません (多倍長整数)
• 有理数 (rational)
  n と m を整数とすると、n / m の有理数は nrm または rdiv(n, m) と表します
• 浮動小数点数 (float)
  絶対値で 2.2250738585072014e-308 から 1.7976931348623157e+308

浮動小数点数はＣ言語の double に相当します。

四則演算は一般のプログラミング言語と同じく、演算子 +, *, -, / が用意されています。なお、整数同士の除算 / の結果は浮動小数点数になります。商を求める場合は演算子 // を、剰余を求める場合は演算子 mod を使ってください。そして、演算結果を変数にセットするには is を使います。簡単な例を示しましょう。

?- X is 1 + 2 + 3.
X = 6.

?-

Prolog の場合、パターンマッチングにより変数に値がセットされました。is の場合も同じです。左辺の数式を計算し、それを右辺の変数とマッチングを行います。次の例を見てください。

?- X is 1 + 2, X is 3 + 4.
false.

?-

最初の計算で、変数 X の値は 3 になりました。次に 3 + 4 を計算し、その値 7 と X をマッチングします。この場合、X の値は 3 なのでマッチングは失敗します。このように Prolog の is は、一般のプログラミング言語の代入とは働きが違います。また、数値演算関連の述語は、再試行すると失敗することにも注意して下さい。

今度は、「X の 2 乗は Y である」という述語を定義します。プログラムは次のようになります。

リスト : 2 乗を求める

square(X, Y) :- Y is X * X.

square は、X * X の計算結果を Y とマッチングさせるだけです。それでは、実際に実行してみましょう。

?- square(2, Y).
Y = 4.

?- square(2, 4).
true.

?- square(X, 4).
=> エラー

最初の例は、2 乗の計算結果が Y にセットされます。square は述語ですから、2 つの引数に数値を与えると、2 乗の関係であれば成功し、そうでなければ失敗します。では、最後の例のように X を求めることはできるのでしょうか。この場合は、X が自由変数で算術演算が実行できないため、エラーとなります。

家系図で示したプログラム、たとえば grandfather_of(X, Y) では、X から Y を求める、逆に Y から X を求める、そして X と Y の関係をすべて求めることができました。このように、ひとつの述語で複数の使い方ができるのが、他のプログラミング言語にはない Prolog の面白い特徴です。ですが、数値演算の場合、自由変数が含まれていると演算不能になるため、このような使い方はできません。ご注意ください。

数値の大小を比較する場合は、次の述語を使います。

これらの述語は数式 (Expr) を計算して、その結果が条件を満たしていれば成功します。

ところで、Prolog 処理系によっては、演算子 is の右辺で「算術関数 (arithmetic functions)」を呼び出すことができます。SWI-Prolog の場合、sqrt(), log(), sin(), cos(), tan() など、他のプログラミング言語でいう数学関数が多数用意されています。詳細は SWI-Prolog のリファレンス Arithmetic Functions をご覧ください。

簡単な使用例を示します。

?- X is abs(10).
X = 10.

?- X is abs(-10).
X = 10.

?- X is max(1, 2).
X = 2.

?- X is min(1, 2).
X = 1.

?- X is sqrt(2).
X = 1.4142135623730951.

?- X is log(1).
X = 0.0.

?- X is pi.
X = 3.141592653589793.

?- X is sin(0).
X = 0.0.

?- X is sin(pi/2).
X = 1.0.

?- X is sin(pi).
X = 1.2246467991473532e-16.

?- X is cos(0).
X = 1.0.

?- X is cos(pi/2).
X = 6.123233995736766e-17.

?- X is cos(pi).
X = -1.0.

●問題

次に示す述語を定義してください。

1. 引数 X に 1 を加える add1(X, A)
2. 引数 X から 1 を引く sub1(X, A)
3. 引数 X を三乗する cubic(X, A)
4. 引数 X を 1/2 にする half(X, A)
5. 二つの引数 X, Y の平均値をとる medium(X, Y, A)
6. 二つの引数 X, Y の二乗の平均値をとる square_medium(X, Y, A)
7. 引数 X が 0 か判定する is_zero(X)
8. 引数 X が正か判定する is_positive(X)
9. 引数 X が負か判定する is_negative(X)
10. 引数 X の符号 (-1, 0, 1) を返す sign(X, A)
11. 引数 X が偶数か判定する is_even(X)
12. 引数 X が奇数か判定する is_odd(X)

●解答

?- [user].
|: add1(X, A) :- A is X + 1.
|: sub1(X, A) :- A is X - 1.
|: cubic(X, A) :- A is X * X * X.
|: half(X, A) :- A is X / 2.
|: medium(X, Y, A) :- Z is X + Y, half(Z, A).
|: square_medium(X, Y, A) :- X2 is X * X, Y2 is Y * Y, medium(X2, Y2, A).
|: ^D
true.

?- add1(10, A).
A = 11.

?- sub1(10, A).
A = 9.

?- cubic(3, A).
A = 27.

?- half(2, A).
A = 1.

?- half(3, A).
A = 1.5.

?- medium(1, 2, A).
A = 1.5.

?- square_medium(1, 2, A).
A = 2.5.

?- [user].
|: is_zero(X) :- X =:= 0.
|: is_positive(X) :- X > 0.
|: is_negative(X) :- X < 0.
|: sign(X, 0) :- is_zero(X).
|: sign(X, 1) :- is_positive(X).
|: sign(X, -1) :- is_negative(X).
|: is_even(X) :- X mod 2 =:= 0.
|: is_odd(X) :- X mod 2 =:= 1.
|: ^D
true.

?- is_zero(0).
true.

?- is_zero(0.0).
true.

?- is_zero(1.0).
false.

?- is_positive(0).
false.

?- is_positive(-1).
false.

?- is_positive(1).
true.

?- is_negative(0).
false.

?- is_negative(-1).
true.

?- is_negative(1).
false.

?- sign(0, A).
A = 0 ;
false.

?- sign(10, A).
A = 1 ;
false.

?- sign(-10, A).
A = -1.

?- is_even(10).
true.

?- is_even(11).
false.

?- is_odd(10).
false.

?- is_odd(11).
true.