Document

Prolog演習
PowerPointのアニメーション機能を利用すると分かりやすい
と思います．
2002年に北陸先端科学技術大学院大学の講義
（知識処理方法論A）で使用したものを公開用に
少し手直ししたもの．
中田豊久 ([email protected])
2002/06/12
1
データ (変数と定数）（１）
データは定数と変数がある．

定数は，a, a0, coffeeなどの小文字も英字（数字以
外）で始まる．
変数は，X,_a,_のように大文字の英字，または，
_(下線)で始まる．



変数は，箱のようなもの．プログラムの実行中
に中に入るものが変化する．中は次のどれか
である．
1.
2.
3.
2002/06/12
何も入っていない
定数が入っている
変数が入っている
2
データ（変数と定数）（２）

変数の有効範囲は，節に限られる．
grandchild(X,Z):- parent(Z,Y), parent(Y,X).
ancestor(X,Y):- parent(X,Y).
(ancestor(Y,X):- parent(Y,X).は，上と同じ)


定数は，固定された値．プログラムの実行中に
値を変えることはない．定数には，文字と数値が
ある．
定数の有効範囲は，プログラム全体である．
2002/06/12
3
grandchild 述語 (成功例)
parent(‘波平’,‘サザエ’).
parent(‘波平’,‘カツオ’).
parent(‘波平’,‘ワカメ’).
parent(‘舟’,‘サザエ’).
parent(‘舟’,‘カツオ’).
parent(‘舟’,‘ワカメ’).
parent(‘サザエ’,‘タラオ’).
parent(‘マスオ’,‘タラオ’).
grandchild(X,‘波平’).
GC=X, GF=‘波平’
X=‘タラオ’
parent(‘波平’,FA),parent(FA,X).
FA=‘サザエ’FA=‘サザエ’
FA=‘サザエ’
parent(‘波平’,‘サザエ’).
grandchild(GC,GF):parent(GF,FA),parent(FA,GC).
| ?- grandchild(X,’波平‘).
X = ‘タラオ’
X=‘タラオ’
parent(‘サザエ’,X).
X=‘タラオ’X=‘タラオ’
parent(‘サザエ’,‘タラオ’).
ユニフィケーション
2002/06/12
4
grandchild 述語 (失敗例)
parent(‘波平’,‘サザエ’).
parent(‘波平’,‘カツオ’).
parent(‘波平’,‘ワカメ’).
parent(‘舟’,‘サザエ’).
parent(‘舟’,‘カツオ’).
parent(‘舟’,‘ワカメ’).
parent(‘サザエ’,‘タラオ’).
parent(‘マスオ’,‘タラオ’).
grandchild(X,‘マスオ’).
GF=‘マスオ’
新しい解を探す
失敗GC=X,
parent(‘マスオ’,FA),parent(FA,X).
FA=‘タラオ’ FA=‘タラオ’
新しい解を探す
parent(‘マスオ’,‘タラオ’).
grandchild(GC,GF):parent(GF,FA),parent(FA,GC).
| ?- grandchild(X,’マスオ‘).
no
2002/06/12
FA=‘タラオ’
失敗
parent(‘タラオ’,X).
バックトラック
5
Prologプログラムを作るための2
つの視点（１）

宣言的な視点



例えば，親子関係を事実としてした状態で，祖
父／孫関係を作りたい時．
祖父／孫関係を，親子関係で説明することを
考える．
祖父／孫関係は，親子の親子関係で説明で
きる、という事実をルールとして記述する．
grandchild(GC,GF) :parent(GF,FA),parent(FA,GC)
2002/06/12
6
Prologプログラムを作るための2
つの視点（２）

手続き的な視点



2002/06/12
宣言的な視点で，望むプログラムが出来れば
問題ない．
しかし，通常，うまく動作しなかったり，処理時
間に問題が発生したりする．
その場合，先に示したようにProlog内部の動
作を把握してプログラムの修正，改良をする
必要が発生する．その時に，手続き的な視点
が必要になる．
7
ancestor述語
parent(‘波平’,‘サザエ’).
parent(‘波平’,‘カツオ’).
parent(‘波平’,‘ワカメ’).
parent(‘舟’,‘サザエ’).
parent(‘舟’,‘カツオ’).
parent(‘舟’,‘ワカメ’).
parent(‘サザエ’,‘タラオ’).
parent(‘マスオ’,‘タラオ’).
ancestor(X,Z):-parent(X,Z).
ancestor(X,Z):-parent(X,Y),
ancestor(Y,Z).
| ?- ancestor(X,’タラオ‘).
X = ‘サザエ’ ? ;
X = ‘マスオ’ ? ;
X = ‘波平’ ?
2002/06/12
ancestor(X,’タラオ‘).
parent(X,’タラオ‘).
[X=X,Z=‘タラオ’]
parent(‘サザエ’,‘タラオ’).
[X=‘サザエ’]
parent(‘マスオ’,‘タラオ’).
[X=‘マスオ‘]
parent(X,Y),ancestor(Y,’タラオ‘).
[X=X,Z=‘タラ
オ’]
parent(‘波平’,‘サザエ’),ancestor(‘サザエ’,‘タ
ラオ’). [X=‘波平’,Y=‘サザエ’]
parent(‘波平’,‘サザエ’),
オ’).
parent(‘サザエ’,‘タラ
[X=‘サザエ’,Z=‘タラオ’]
8
プログラムの構成

fact(事実)とruleで構成される．
%----- fact ---------------------------------------------------parent(‘波平’,‘サザエ’).
%波平はサザエの親である
parent(‘舟’,‘サザエ’).
%舟はサザエの親である
%----- rule ---------------------------------------------------%XがZの親の場合，XはZの先祖である．
ancestor(X,Z):- parent(X,Z).
%XがYの親で，かつ，YがZの先祖の場合，XはZの先祖である．
ancestor(X,Z):- parent(X,Y), ancestor(Y,Z).
2002/06/12
9
リスト


[1,a,b,coffee,X] のように定数，変数の集まりをリストと
呼ぶ．
リストの要素にリストを持つことも出来る．


また，要素なしのリストもある．


[1,a,[10,c]]
[]
“|” 文字でリストの先頭とそれ以外を分離(結合)できる
(ユニフィケーション)．



2002/06/12
[X|Y] = [1,2,3] (X=1, Y=[2,3])
[X|Y] = [1]
(X=1, Y=[]).
[X|Y] = []
no
10
member述語 (成功例)
member(X,[X|_]).
member(X,[_|Y]):- member(X,Y).
| ?- member(a, [x,y,a]).
yes
member(a, [x,y,a]).
X=a ? member(a,[a,....]) -> fail
member(a,[y,a]). [X=a,Y=[y,a]]
X=a ? member(a,[a,..]) ->fail
member(a,[a]). [X=a,Y=[a]]
X=a ? member(a,[a,..]) -> true!
2002/06/12
11
member述語 (失敗例)
member(X,[X|_]).
member(X,[_|Y]):- member(X,Y).
| ?- member(a, [x,y]).
no
member(a, [x,y]).
X=a ? member(a,[a,....]) -> fail
member(a,[y]). [X=a,Y=[y]]
X=a ? member(a,[a,..]) ->fail
member(a,[]). [X=a,Y=[]]
X=a ? member(a,[a,..]) -> fail
[_|Y] = [] -> fail
2002/06/12
12
ユニフィケーション

X=Y,Y=1.


parent(X)=parent(taro).


X=a, Y=[b,c,d].
X=[1].


no
[X|Y] = [a,b,c,d].


X=taro.
parent(X)=grandchild(taro).


X=1,Y=1.
X=[1].
[X] = [1].

2002/06/12
X=1.
13
バックトラック


一度ユニフィケーションした変数に対して，別の
解を探すこと．
Prologシステムは，与えられた述語すべてが満
足する解を，ユニフィケーション，バックトラックを
繰り返して探す．


最終的な解が得られるまでは，Prologシステムは，自
動的にバックトラックを発生させる．
1つ解が得られたときに，別の解を探索するため
に ; (セミコロン)を入力して，手動でバックトラッ
クを発生させることも出来る．
2002/06/12
14
論理和,条件分岐

grandchild(GC,GF) :- parent(GF,FA) , parent(FA,GC).


parent(PA,C) :- father(PA,C) ; mother(PA,C).



GFの子供がFAであり，かつ，FAの子供がGCの場合,GCはGFの
孫である．（論理積）
PAがCの父親，または，PAがCの母親の場合，PAはCの親である．
parent(PA,C):-father(PA,C).
parent(PA,C):-mother(PA,C). と同じ
man(X) -> father(X,Y) ; mother(X,Y).

2002/06/12
man(X)が成功すれば，father(X,Y)を調査する．失敗すれば，
mother(X,Y)を調査する．
15
再帰構造

自分の定義に自分自身を使用することを
再帰構造という．


member(X,[_|Y]):- member(X,Y).
再帰構造を利用したプログラムの作成は，通常，
最終状態（最初の状態）と，n番目とn+1番目の
関係を記述した述語を作成する．


2002/06/12
最終状態 member(X,[X|_]).
n,n+1番目の関係
member(X,[_|Y]):- member(X,Y).
16
否定

Prologの否定は，論理的否定ではなく，失
敗としての否定である．

~parent(‘波平’,‘タラオ’). (論理的否定）


¥+ parent(‘波平’,‘タラオ’). (Prologの否
定)

2002/06/12
波平は，タラオの親ではない，という事実
波平は，タラオの親である，という事実はない
17
unmarried_man述語
unmarried_man(X):\+ married(X), man(X).
man(bill).
married(joe).
| ?- unmarried_man(bill).
yes
| ?- unmarried_man(taro).
no
unmarried_man(bill).
\+ married(bill), man(bill) [X=bill]
\+ fail, true -> true !
unmarried_man(taro).
\+ married(taro), man(taro) [X=taro]
\+ fail, fail -> fail
2002/06/12
18
停止性
停止しないプログラム

married(X,Y):- married(Y,X).


停止させるには，
1.
2.
2002/06/12
Controlキーを押しながらCキーを押す．
Prolog interruptionと表示されたら，a
キーを押して，リターンキーを押す．
19
算術演算 (特殊なユニフィケーション)

X = 2+3.


X is 2+3.


X=5.
X = 2+3, Y is X.


X=2+3.
X=2+3, Y=5.
X = 2+3, Y = X.

2002/06/12
X=2+3, Y=2+3.
20
バックトラックの制御（１）
child(taro).
adult(jiro).
members(jiro).
fee(X,1000):child(X),members(X).
fee(X,2000):adult(X),members(X).
fee(taro,X).
| ?- fee(taro,X).
no
fee(taro,1000). [X=taro]
child(taro),members(taro).
true,false. -> fail !
fee(taro,2000). [X=taro]
adult(taro),members(taro).
taroが，会員じゃないことが
分かっているので，この部分は，
無駄な処理である．
2002/06/12
false,members(taro). -> fail !
21
バックトラックの制御（２）
fee(taro,X).
child(taro).
adult(jiro).
members(jiro).
fee(X,1000):child(X),!,members(X).
fee(X,2000):adult(X),!,members(X).
| ?- fee(taro,X).
no
| ?- fee(bill,X).
no
fee(taro,1000). [X=taro]
child(taro),!,members(taro).
true,!,false. -> fail
fee(bill,X).
fee(bill,1000). [X=bill]
child(bill),!,members(bill).
false,!,member(bill). -> fail
fee(bill,2000). [X=bill]
adult(bill),!,members(bill).
2002/06/12
false,!,member(bill). -> fail
22
バックトラックの制御（３）

C :- a,b.
C :- d,e.


C :- !,a,b.
C :- d,e.


a,bが成り立たなければ，d,eは調査せずに失敗する．
C :- a,!,b.
C :- d,e.


a,bが成り立たなければ，d,eを調査する．
aが成り立たなければ，d,eを調査するが，bが成り立たなければ，
d,eは調査しない．
C :- a,b,!.
C :- d,e.

2002/06/12
a,bが成り立たなければ，d,eを調査する．しかし一度a,bが成り立
てば，d,eを調査することはしない．
23
おわり
2002/06/12
24

Download Report