Prolog のプログラムは節(ホーン節)を単位として記述する。 つまり、節が他のプログラミング言語における文に相当する。 そして、節は述語と呼ばれる基本論理式から構成される。 節には、ある述語が無条件で真であることを示す事実節(または 単に事実とも呼ぶ)と、ある述語が真となる条件として他のいくつかの述語が 真でなければならないことを示す規則節(規則)がある。各節の終りには ピリオド「.」を記述する。
事実: 述語.
規則: 述語0 :- 述語1, 述語2, …, 述語n.
ここで、述語1〜nは述語0が真になる条件である。 条件が複数ある場合のコンマ「,」は and (かつ)を意味する。 また、述語は一般的に以下のように記述する。
述語名(引数1, 引数2, …, 引数n)
ここで述語名は英小文字で始める英数字及びアンダースコア「 _」で 付けられた名前である。 引数には数値や名前などの定数の他、変数を記述する。引数は無くても良い。 引数がない場合は述語名のみを記述する(括弧は付けない)。
変数の名前は英大文字またはアンダースコアで始まる英数字で付けられる。 変数名の有効範囲は節である。つまり、同じ変数名でも節が異なれば 違う変数になる。変数は各節のローカル変数ととらえることもできる。 ただし、アンダースコア1文字だけの変数は無名変数とされ、同じ節の 中でもすべて異なる変数として扱われる。なお、Prolog の変数には型がなく、 任意のデータ型の値が入る。
述語名の例: x, y, n, n1, aBC, p987, q_we
変数の例: X, Y, N, N1, Abc, P987, _qwe
無名変数: _
定数にはシンボル(記号、アトム、リテラルとも呼ばれる)、数値、リスト、 構造、文字列がある。
シンボルは述語名と同様の名前で記述される(実際には 述語名もシンボルである)。もし大文字で始めたり、特殊な記号を名前に含めたい 場合にはシングルクォート「'」で囲む。
数値は整数と浮動小数点数(実数)があるが、Prolog では変数に型がない こともあり、計算する際に適宜型変換が行われる。
リストは角括弧「 []」 で囲み、0個以上の要素を並べたものである。要素がないリストのことを空リスト と呼ぶ。なお、リストの要素にはリストを含む任意のデータや変数を記述 することができる。
構造はシンボルの後に丸括弧「()」で囲んだ引数の並びを記述 したものである。引数には任意のデータや変数を記述することができる。 構造は、数値計算の際の関数を表現したり、他の言語における 構造体に相当する使い方がされる。
文字列はダブルクォート「 "」 で囲まれた任意の文字列である。なお、Prolog における文字列は 文字コードを並べたリストとして扱われる。
シンボルの例: foo, bAr, n1, 'Xyz'
数値の例: 0, 1, 100, 3.14, 1.42e10, 3.5e-6
リストの例: [] (空リスト), [a], [1, X, c], [a, [b, c], d]
構造の例: abc(a, b), a1(1, 3), xy(A, [1, 2])
文字列の例: "ABC", "xyz", "12ab"
なお、パーセント記号「%」を書くとそこから行末までが コメントであることを表す(C言語と同様に「/* */」を使うこともできる)。
まずは、簡単なプログラム例をいくつか実行してみて、Prolog処理系の 使い方に慣れてもらう。
まず、以下のプログラム例をエディタで入力して、 ファイル「ex1.pl」に保存する。
parent(taro, hanako). parent(hanako, jiro). parent(taro, saburo). parent(hanako, shiro). parent(saburo, ishiro). parent(shiro, goro).
ここで、「parent(a, b)」は「a は b の親である。」という意味を 記述しているものとする。
次に、「全学計算機システム上のSWI-Prologの使い方」に従って、 SWI-Prologを起動し、プログラムを読み込ませる。
SWI-Prolog起動コマンド: ~sakaguchi.tetsuo.gf/pub/bin/swipl
Prologにプログラムを読み込ませる: [ex1].
Prologに読み込まれたプログラムの確認: listing.
次にPrologに以下のような式(鈎括弧の中)を入力して、答を求めさせる。
結果として、単に「true」と表示された時は、その式が真である こと(成功)を示している。「false」と表示された時は偽であること (失敗)を示す。式に変数が含まれている時は単にtrueと表示するのでは なく、成功する場合にその変数に入る値の候補が表示される。
結果が表示された時に、プロンプト「?-」が出ない時は別の解(値) があるかも 知れないことを意味している。その際、単にエンターキー(リターンキー)を押す と終了するが、セミコロン「;」を押すと別の解を求める。
時間があれば、上記のもの以外の式を試したり、プログラムの行(節)の順序を 入れ替えたり、親子の組み合わせを増やしてみよ。
例題1はPrologに教えた事実をそのまま答えさせているのみであるが、 親子関係を元にすると、例えば祖父母と孫の関係や兄弟(姉妹)関係も わかるはずである。
祖父母と孫というのは親の親、あるいは子供の子供ということになるので、 例えば、taroがsaburoの祖父であることを調べるには、
taroはXの親であり、かつ、Xはsaburoの親である。
「parent(taro, X), parent(X, saburo).」
という式を入力すると答が得られる。
しかしながら、一々このような式を入力するのは面倒なので、祖父母孫 関係を求める規則をプログラムに追加すると簡単になる。規則は以下のように なる。
XはYの親であり、かつ、YはZの親であるならば、XはZの祖父(祖母)である。
「grandparent(X, Z) :- parent(X, Y), parent(Y, Z).」
これにより、式として「grandparent(taro, saburo).」と 入力するだけで上記の式と同じ答が得られる。
上のルールをプログラムに追加し、grandparentの引数に何通りか (変数の場合を含む)指定し、結果を調べてみよ。
兄弟関係を調べるには「同じ親である二人」を条件とすれば良いので、 grandparentの例に習って、兄弟を調べるbrotherを定義 してみよ。同一人物を兄弟とする答があっても良い。
ただし、同一人物は本来兄弟ではないので、同一人物の場合を除外する必要がある。 Prologでは効率良いプログラミングのために使用頻度が高いものや節だけで 定義するのが難しい述語については、処理系に組み込んである。 例えば、同じ値であるかどうかを調べるものとして「=」がある。 例えば、「X = Y」のように書く(大小比較するものなど一部は このように述語名を中置形式で書くことができる)。
不一致を意味するものとしては「\=」がある。例えば、 「A \= B」と書けば、それは A と B が異なる値であれば真となる。 これを用いて上で定義したbrotherを同一人物が出てくることがないように 修正せよ。
例題2では単純に祖父母と孫までを求めていたが、これを発展させると 祖先と子孫の関係を求める規則を定義することができる。例えば曾祖父母と曾孫 については、
ggparent(W, Z) :- parent(W, X), parent(X, Y), parent(Y, Z).
のように定義すれば良いが、このやり方では親子関係を辿る回数の数だけ 別の述語を準備することになる。これをより一般化するために、次のように 祖先を定義してみる。
XがYの親であるならば、XはYの祖先である。
XがYの親であり、かつ、YがZの祖先であるならば、XはZの祖先である。
上の祖先の定義を述語名ancestorとして節を2つ定義し、 Prologのプログラムとして完成させ、祖先を求めてみよ。
うまくいったら、節の順番を入れ替えるとどう変わるか試してみよ。 うまくいかなかったら、何が問題か考えてみる。その際、traceで ancesterをどのように確かめているかを確認してみること。
Prologではデータの集まりや並びを表すために、リストを用いる。 以下の式をPrologに入力してみて、変数にどのような値が入るか 確かめてみよ。
最後の3つの例でわかるように「|」を用いると先頭の(複数の) 要素と残り(の要素のリスト)に分けることができる。 これを利用すると、例えば、次のような節を定義することができる。
first(A, [A| _]).
これは第1引数の値が第2引数のリストの先頭の要素であることを意味する。 第2引数は上の=の場合と同じように尋ねられた式と照合する際に、 先頭と残りの要素のリストに分けられ、かつ第1引数とその先頭の要素が同じ変数 なので、同じ値でないと成功しない。
この節がうまく動くことをいくつかの式で試してから、同様に2番目の要素、 3番目の要素が第1引数になるような節定義を書いてみよ。
さて、このように1番目、2番目、…と定義したものに対して、 もっと一般的な定義ができないか考えてみる。つまり、ある値が リストの要素である際に真となる(成功する)ものである。これ自体は 良く使われるので、既にPrologの処理系に組み込まれている。次の式を 試してみよ。
このmemberは再帰的な定義方法を用いると非常に簡単に定義 できる。以下に日本語での考え方を示す。
・第1引数が第2引数のリストの先頭の要素と同じである。
・第2引数のリストの先頭を除いた残りの要素に第1引数の値が含まれていれば、 第1引数は元のリストの要素に含まれている。
この定義をPrologの節定義として完成させよ。なお、述語名 member は既に使用されているので、my_memberのように違う 述語名とすること。
Prolog では計算式自体はすべて内部で構造として表される。一致を意味する 述語「=」はパターンマッチしか行わないので、例えば
X = 1 + 2
という場合、変数Xには式「1 + 2」のままで値が結び付くため、 「3」とは一致しない。そこで、数値の計算が必要な場合のための「 is」 が準備されている。
X is 1 + 2
のようにisを使うと、Prolog は右辺の式を計算し、その結果を左辺 とパターンマッチする。注意しなければならないのは、右辺に値が未定の変数が あると計算できないので、エラーになる点である。エラーにしないためには、 変数の値が定まっている場合に真になる述語「nonvar」を使ったり、 変数の値が数値に定まっている場合に真になる述語「number」を 組み合わせる。
…, nonvar(X), Y is X + 1, …あるいは
…, number(X), Y is X + 1, …
なお、このようにisはPrologの特徴である逆計算はできない。もし、 逆計算させたいような場合には、古典的に整数を表す構造として s(…) を用いる方法があるが、ここでは略す。
Prologにおけるプログラムの実行は概ね以下のようになる(厳密な 動きについては参考文献など参照のこと)。
ここでバックトラックがあるところがPrologの 特徴である。しかしながら、思わぬところでバックトラックしてしまい意図から 外れた結果になる場合がある。
次のプログラムは1から第1引数までの総和が第2引数と等しいことを示す、 つまり総和を求めるものである。
sumup(1, 1).
sumup(N, X) :- N1 is N - 1, sumup(N1, X1), X is N + X1.
sumup(N, X)は「Xは1 + 2 + … + Nである」と いう意味になる。第1節は1を与えた場合は結果が1になることを、第2節は1より 大きい場合には1だけ引いたもの(N1)の総和を求め、それにNを足したものが 結果になるという定義である。
これで定義したsumupを適当な値を与えて実行すると、正しい結果が 得られるが、一度結果が求まった際に別解を求めるようにバックトラックをさせると、 「Out of local stack」のエラーが生じる。これは、再帰するうちに第1引数が1に なり、第1節とマッチして一旦終るところを、バックトラックさせると第1節との マッチの結果を捨てて、第2節とのマッチをする。 後は1ずつ減らして再帰すると、第1節にはマッチしないので永遠に止まらなく なるからである。
この例に手を加えて、バックトラックさせても問題が 起きないようにしてみよ。 (ヒント: 第2節は第1引数が1より大きい場合のみに適用するべきものである。)
述語「!」はカットと呼ばれる特殊な組み込みの述語である。 これ自体は、必ず成功するが、このカットが成功すると、これ以降に失敗した 述語があった場合、このカットを越えてバックトラックしないようになる。 例えば、
p :- q, !, r.
という節があった時、qが成功し、!が成功し、 rが失敗 した場合、通常なら、qについて別解を求めるべくバックトラックをする はずが、途中に!があるので、そこから左には戻れず、 rは失敗したままとなる(つまり、この節が失敗する)。また、
p :- !.
は事実節(条件が実質的にない)でありながら、カットがあるので、一度 これにマッチすれば、以降にいくつ節があってもバックトラックの際にそちらの節 とマッチを試みることはなくなる。
上のsumupの例をカットを使ってバックトラックしても問題が 起きないように修正せよ。
本来Prologでは「成功」する場合の節定義のみを定義し、定義に書かれていない 場合には「失敗」するという方針でプログラムを書く。しかしながら、明確に 失敗することをプログラムに書きたい場合もある。そのために述語「 fail」 がある。これは引数もないが、必ず失敗する述語である。これとカットを 組み合わせると不一致の述語、つまり「\=」と同様のもの を定義できる。
not_equal(X, X) :- !, fail.
not_equal(_, _).
(必ず成功する「true」という述語もある。)
Prolog では本来述語の引数には述語が来ない、また述語名が定まっているという 「第一階」述語論理に基づいているとされているが、プログラムの都合上、 引数に述語を渡したり、述語そのものを変数に入れると便利なので、そういった 「高階」の機能がある。例えば、述語の成功・失敗を否定する「 not」 がある。例えば、「not(true)」は失敗し、「 not(fail)」 は成功する。 notは実際には以下のように定義可能である
my_not(P) :- P, !, fail.
my_not(_).
計算機のプログラムでは同じ処理を繰返し処理させるというのが通常である。 Prolog ではその原理からループ機能そのものは存在しない。その代わりに 「再帰」を用いるか、「バックトラック」を用いる。 再帰の例はsumupなど で示しているので、ここではバックトラックによる繰返しの簡単な例を 示す。次の例はリストの要素を順に画面に表示するプログラムを再帰を使って 定義したものである。
print_list([]).
print_list([A| R]) :- writeln(A), print_list(R).
なお、「writeln」は引数のデータを画面に表示し、改行する 組み込み述語である(改行のみのnl、改行しないで表示する write もある)。これと同じような働きをするものをバックトラックを使って実現すると
print_list2(L) :- member(A, L), writeln(A), fail.
print_list2(_).
のようになる。これはmemberでリストの要素が Aに入り、 表示したら、failによりバックトラックすると別の要素がまた A に入るということを繰り返す。最後に1つ目の節そのものが失敗するので、 2つ目の節によって必ず成功するようにしておく。
ここまでの説明に基づいて、次のような述語を定義してみよ。なお、 ここでは仮に述語名を「gennum」としておく。
2番目の定義については例えば、次のような式を実行すると、 0から100までを画面に表示することになる。
gennum(N), writeln(N), N > 99.
これを全て事実節で定義するとすれば、
gennum(0).
gennum(1).
gennum(2).
…
と、延々と全ての整数の分だけ事実節を書くことになるが、 これは馬鹿馬鹿しいので、これまでの例にもあった再帰的な定義を用いる。 その場合、0の場合とそれ以外の場合に分けて考えれば良い。
切符を買うと多くの場合4桁の発行番号が印字されている。 頭の体操として、この4桁の数を、4つの1桁の数と見なして、四則演算によって 値が10にするにはどういう式にすれば良いか考えるというものがある。 難しいパズルに挑戦する前に、これの真似事を Prolog にやらせてみよう。
ここでは上の問題そのものではなく、次のようなより簡単な 問題にして考えることにする。
とりあえずヒントを出すと、まず1番目の課題の述語(仮に sum10という 名前にする)について、単純に考えると、
sum10(A, B, C, D) :- 10 is A + B + C + D.
というのが考えられる。しかしながら、これでは必ずA, B, C, Dの値を 与える必要があるので、正解の組み合わせをPrologに求めさせることはできない。 そこで、前の例題である数値生成と組み合わせると、生成した数値と和が10に なるという条件の組み合わせによって正解をPrologに探させることができる。 ただし、再帰による数値生成の単純なプログラムではバックトラックで プログラムがなかなか止まらなくなるので、ここでは事実節を用いる 方法で0から9までの数値を生成するものを定義してそれを用いること。
2番目については同じ数字を使ってはいけないという制約を付与するだけである。
3番目については数値だけでなく演算子も生成し、その結果に基づいて計算 させるか、計算式の種類だけ節定義を書くという方法がある。後者の方が簡単で あるが、組み合わせを事前に人手で書くというのはプログラムとしてはあまり 面白くないので、できれば、前者に挑戦してみて欲しい。4番目はその応用に なる。
この3番目については演算子を生成する述語を準備する手法以外にも 「2つの数を加減乗除した結果を返す、3引数の述語」を定義する方法も 考えられる。同じ引数で呼び出した場合、最初は加算、バックトラックした 次は減算の結果という風に、バックトラックにしたがって違う演算をした 結果を返すものである。
なお、4番目以降、特に5番目は難しいので、必ずしも完成しなくても良い。
by Tetsuo Sakaguchi
更新日時 $Date: 2012/12/11 05:51:15 $ (UTC)