Prolog入門(2)

Prologの構文

項 (Term)

定数 (constant)

(例) 1, 2, 0, -5.23, 1.23E-6

アトム

小文字で始まる文字列です。大文字で始まるアトムを使いたいときは ' (シングルクォート)で囲みます。 (例) a, b, apple, 'United States'

変数 (variable)

「大文字」または「_」で始まる文字列。一つの規則に一度しか現れない変数は名前をつける必要がないので、「名前なし変数」として _ で表します。_は同じ規則の中でも、全て別物とみなされます。

複合項 (compound term)

「名前(引数1,引数2, ...) の」形式を持つ項で、ファンクタ(functor)と呼びます。アトムが名前となっています。引数の数をアリティ(arity)と言います。「名前」と「アリティ」がファンクタを特徴づけています。

(例) point(X,Y,Z) これは名前が'point'、アリティが3のファンクタです。

単一化

「変数の値を何かと同一視することで、項同士が等しくなるようにする操作」を「単一化」と呼びます。

「単一化する」ことを「ユニファイする (unify)」と言い、「単一化」のことを「ユニフィケーション (unification)」と言います。変数が定数とユニファイすることを、「インスタンシェート(instantiate, 具体化)」と言います。

演算

X is Y

右辺Yの値を評価して左辺Xに代入します。したがって、Xは未定義変数でなくてはいけません。

Yの部分の式に使える演算子は以下のものがあります。

加算	減算	乗算	除算	余り
+	-	*	/	mod

(注意) Prologの'='はユニフィケーションですから、 X = 1 + 2 と書かれても変数X が +(1,2) というファンクタを指すようになるだけです。 1+2という式の結果を計算させるためには X is 1 + 2 と書く必要があります。

その他の算術演算子

X > Y	XはYより大きい
X < Y	XはYより小さい
X >= Y	XはYより大きいか等しい
X <= Y	XはYより小さいか等しい
X =:= Y	XとYは等しい
X =\= Y	XとYは等しくない

これらの演算子は両辺を評価してから、比較します。次の式の違いに注意しましょう。

?- 1 + 2 =:= 2 + 1 
yes
?- 1 + 2 = 2 + 1 
no

前者は、両辺の式をまず評価して 3 という数値同士を比較することになり、成功します。後者は、「左辺の +(1,2) というファンクタと右辺の +(2,1) というファンクタをユニフィケーションできますか？」というわけで、失敗となります。

2個以上のデータはペアを複数個使うことで表現できます。ペアのヘッド部にデータを記憶し、テイル部に次のペアを記憶すればよいのです。それ以上データが存在しないことを表す '[]' という特別のデータも導入することにしましょう。

省略規則

[X | []] の形式の場合 "| []" は省略し、[X] と表現できます。

  例    [saburo | []]  → [saburo]

[X | [Y | Z]] の形式の場合 "|[ ... ]" は省略でき、[X, Y | Z] と表現できます

  例    [jiro | [saburo | []]] → [jiro ,saburo | []] → [jiro, saburo]

実は、ペアを表しているのは、名前が'.'、アリティが2のファンクタです。本来は[taro,jiro]は '.'(taro, '.'(jiro, [])) という構造を持っています。しかし、リストは非常に便利でよく利用する構造なので、人間にとってわかりやすいように [X|Y] のような形式で表現しています。

次の質問はそれぞれ成功するでしょうか？リスト構造をよく考えて答えて下さい。

?- [X|Y] = [taro | jiro].
?- [X|Y] = [taro | []].
?- [X|Y] = [taro].
?- [X|Y] = [taro, jiro, saburo].
?- [X,Y] = [taro, jiro, saburo].
?- [X,Y,Z] = [taro, jiro, saburo].
?- [X|Y] = [[a,b],c].
?- [X,Y] = [[a,b],c].
?- [X|Y] = [[a | [b | [c|d]]]]
?- [X] = [a, [b | []]].

リストを扱う述語

リストLの最初の要素Xを取り出す述語 first(L,X), 「先頭の次」の要素Xを取り出す述語 second(L,X) を定義してみましょう。

first.pl

first([X|_],X).
second([_,X|_],X).

File→Consultで first.plを読み込んでから
?- first([a,b,c,d],X).  
X = a  
yes
?- second([a,b,c,d],X).  
X = b  
yes

0から数える(すなわち「最初」の要素は0番目、「その次」の要素は 1番目と数える)ことにして、n番目の要素XをリストL取り出す述語 nth(L,X)は次のようになります。

nth.pl

nth(0,[X|_],X).
nth(N,[_|T],X) :- N > 0, N1 is N-1, nth(N1,T,X).

File→Consultで nth.plを読み込んでから
?- nth(0, [a,b,c,d], X).  
X = a  
yes
?- nth(2,[a,b,c,d],X).  
X = c  
yes

与えられたリストの中の最大値を求めるプログラムは次のようになります。

maxlist.pl

maxlist([X],X).
maxlist([H|T],X) :- maxlist(T,Y), X is max(H,Y).

File→Consultでmaxlist.plを読み込んでから
?- maxlist([9,8,1,2,7,13,6,5],A).  
A = 13 
yes

二つのリストをつないで一つのリストを生成するプログラムは次のようになります。 append(X,Y,Z) において、ZはリストXとYをつないだリストとなります。

append.pl

append([],X,X).
append([H|T],X,[H|Y]) :- append(T,X,Y).

File→Consultで append.plを読み込んでから
?- append([a,b],[c,d,e],X).  
X = [a,b,c,d,e] 
yes

課題B1

次の述語を定義しなさい。ファイル名は list.pl としましょう。ただし、まず、今日のプリントに出て来た first/2, second/2, nth/2, maxlist/2,append/3 を list.plに定義してからにして下さい。

述語	説明
third(L,E)	EはリストLの先頭の次の次の要素
count(L,N)	NはリストLの要素の個数
sum(L,S)	SはリストLの要素の和
member(E,L)	EはリストLの要素に含まれる
index(E,L,N)	EはリストLの何番目の要素か
minlist(L,A)	AはリストLの中の最小の要素

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

[注意] 必ずしも全部できなくても構いません。ただし、提出するのは、正しく動くものだけにして下さい。

オプション課題B2

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

述語	説明
reverse(X,Y)	XはリストYの要素を逆順にしたリスト
dellist(E,L,A)	リストAリストLから(最初に現れる)要素Eを取り除いたもの
mysort(L,S)	SはリストLの要素を大きい順に並べたリスト