f(a) の木表現 g(X,f(a)) の木表現 f g | / \ a X f | a
プログラムやゴール中で上のような記法を使った場合, Prolog 処理系が自動的に標準的な記法に変換します. Prolog 内部では標準的な記法に従って,項を記憶しています. 標準的な記法は, write_canonical という組込述語で表示できます.
| ?- write_canonical(a+b). +(a,b) | ?- write_canonical(1+2+3*4*5). +(+(1,2),*(*(3,4),5))write 述語などで,項を出力する場合は, 逆に内部表現から前置記法,挿入記法,後置記法の形に変換して表示します. カッコも必要な部分だけに付けられます.
| ?- write(+(a,b)). a+b | ?- write((1*2)+(3*4)). 1*2+3*4Prolog のパターンマッチ (単一化, unification) の動作を理解するには, 項の内部表現がどうなっているのかを理解しておく必要があります. たとえば 1+2*3 は X+Y とはマッチしますが, X*Y とはマッチしません. また 1+2+3 と X+Y をマッチさせると X は 1+2, Y は 3 となります.
| ?- 1+2*3 = X+Y. X = 1, Y = 2*3 ? | ?- 1+2*3 = X*Y. no | ?- 1+2+3 = X+Y. X = 1+2, Y = 3 ? | ?- write_canonical(1+2+3). +(+(1,2),3) | ?- 1+2*3 = 1+(2*3). yes | ?- 1+2*3 = (1+2)*3. no | ?- 1+2+3 = (1+2)+3. yes | ?- 1+2+3 = 1+(2+3). noX+Y, 1+2+3 の木表現を下に示します.
X+Y の木表現 1+2+3 の木表現 + + / \ / \ X Y + 3 / \ 1 2
write_siki(X) :- atomic(X), write(X). write_siki(X+Y) :- write(X), write(' と '), write(Y), write(' との和').1つ目の規則は,与えられた式 X が数またはアトム(すなわち atomic )ならば, X をそのまま表示せよ,という意味です. 2つ目の規則は,与えられた式が X+Y という形ならば, 「X と Y との和」と表示せよ,という意味です.
このプログラムを実行すると下のように数式を日本語で表示します.
| ?- write_siki(1+2). 1 と 2 との和しかし数式の部分にまた数式が含まれている場合には, 部分の式はそのまま表示されてしまいます.
| ?- write_siki(1+2+3). 1+2 と 3 との和1+2 の部分も日本語で表示するためには, 以下のように再帰的にプログラミングする必要があります. また X*Y の場合についても規則を付け加えています.
write_siki(X) :- atomic(X), write(X). write_siki(X+Y) :- write_siki(X), write(' と '), write_siki(Y), write(' との和'). write_siki(X*Y) :- write_siki(X), write(' と '), write_siki(Y), write(' との積').実行して見ると,次のような結果になります.
| ?- write_siki(1+2+3). 1 と 2 との和 と 3 との和 | ?- write_siki(1*2+3*4). 1 と 2 との積 と 3 と 4 との積 との和
d(x, 1). d(Y, 0) :- atomic(Y), Y \== x. d(Y+Z, DY+DZ) :- d(Y, DY), d(Z, DZ). d(Y^N, N*Y^N1*DY) :- integer(N), N1 is N-1, d(Y, DY).それぞれ以下のような規則を表します.
| ?- d(x^3+x+a, DY). DY = 3*x^2*1+1+0 ?上のプログラムの 3 行目の規則は, 次のように書いたほうが最初はわかりやすいかもしれません.
d(Y+Z, W) :- /* Y+Z の微分 W を求めるには */ d(Y, DY), /* Y の微分 DY を求めて */ d(Z, DZ), /* Z の微分 DZ を求めて */ W = DY+DZ. /* W を DY+DZ とすればよい */ところが Prolog では,等式は両辺の項が等しいという関係を表しています. したがって,上の例では W = DY+DZ とあるので, W を単純に DY+DZ で 置き換えてかまいません. 置き換えた結果が最初のプログラムなわけです.
では,最初のプログラムがどのように実行されるかを調べてみましょう. 次のようなゴールを入れたとします.
| ?- d(x+a, W).
| ?- DY=1, DZ=0, W=DY+DZ. DY = 1, DZ = 0, W = 1+0 ? | ?- W=DY+DZ, DY=1, DZ=0. DY = 1, DZ = 0, W = 1+0 ?先に DY=1, DZ=0 としてから W=DY+DZ としても, 先に W=DY+DZ としても全く同じ結果になります. これは Prolog の = は,代入ではなく, 両辺が等しいという関係を表しているということを意味します.
このように Prolog では, 計算過程をプログラミングする (手続き的プログラミング) のではなく, 関係をプログラミング (宣言的プログラミング) すれば良いのです. 関係を満たす解は,処理系が自動的に探してくれます.
ただし Prolog は常に万能ではありません. たとえば is を使った計算ではうまくいきません. これは is の計算に方向性があるからです.
| ?- DY=1, DZ=0, W is DY+DZ. DY = 1, DZ = 0, W = 1 ? | ?- W is DY+DZ, DY=1, DZ=0. {INSTANTIATION ERROR: in expression}数値の計算に対しても宣言的プログラミングを可能にする 処理系も存在しています(制約論理型プログラミング言語).
ある命題論理式が充足可能であるのは, 論理式中の各命題変数に t か f をうまく割り当てると その論理式の真理値を t にできる時です. たとえば A /\ B という論理式は, A に t を, B にも t を割り当てれば t になりますから充足可能です. A /\ (-A) という論理式は, A に t を割り当てても f を割り当てても t になりませんから充足不可能です.
まず, NOT を含まない場合について考えてみましょう. 以下のプログラムは,引数に与えられた論理式が t になる場合を探します.
canbe_t(t) :- !. canbe_t(A /\ B) :- canbe_t(A), canbe_t(B). canbe_t(A \/ B) :- canbe_t(A); canbe_t(B).最初の行は命題変数の場合です. 命題変数が充足可能であるためにはその真理値が t でなければなりません. またカット(!)が実行されるので, 命題変数に対しては他の規則は利用されません (このWeb文書の中には,カットについての説明はまだ含まれていません. 参考書,たとえばBratko著「Prologへの入門」の5章など,を読んでください). 2 行目は A かつ B の場合です. A と B の両方が t になる場合を探します. 3 行目は A または B の場合です. A または B の少なくともどちらか一方が t になる場合を探します. セミコロン ; は,または を表します. 以下のように 2 行に分けてもまったく同じことになります.
canbe_t(A \/ B) :- canbe_t(A). canbe_t(A \/ B) :- canbe_t(B).NOT が入ってくると真理値が f になる場合を探す必要が出てきます. そのための述語 canbe_f の定義を付け加えます. プログラムの全体は以下のようになります.
canbe_t(t) :- !. canbe_t(A /\ B) :- canbe_t(A), canbe_t(B). canbe_t(A \/ B) :- canbe_t(A); canbe_t(B). canbe_t(-A) :- canbe_f(A). canbe_f(f) :- !. canbe_f(A /\ B) :- canbe_f(A); canbe_f(B). canbe_f(A \/ B) :- canbe_f(A), canbe_f(B). canbe_f(-A) :- canbe_t(A).以下に利用例を示します. 結果が no となった場合は,充足不可能 (常に f ) ということです. したがってその否定の論理式が恒真 (トートロジー) であることがわかります.
| ?- canbe_t(A /\ (-B)). A = t, B = f ? | ?- canbe_t(A /\ (B \/ (-A)) /\ (-B)). no
canbe_t((A -> B)) :- ??? ここに何を書いたら良いか ??? canbe_f((A -> B)) :- ??? ここに何を書いたら良いか ???