Prolog演習 PowerPointのアニメーション機能を利用すると分かりやすいと思います．

Presentation on theme: "Prolog演習 PowerPointのアニメーション機能を利用すると分かりやすいと思います．"— Presentation transcript:

1 Prolog演習 PowerPointのアニメーション機能を利用すると分かりやすいと思います．
2002年に北陸先端科学技術大学院大学の講義（知識処理方法論A）で使用したものを公開用に少し手直ししたもの． 中田豊久 2002/06/12

2 データ (変数と定数） （１） データは定数と変数がある．
データ (変数と定数）　（１） データは定数と変数がある． 定数は，a, a0, coffeeなどの小文字も英字（数字以外）で始まる． 変数は，X,_a,_のように大文字の英字，または，_(下線)で始まる． 変数は，箱のようなもの．プログラムの実行中に中に入るものが変化する．中は次のどれかである． 何も入っていない 定数が入っている 変数が入っている 2002/06/12

3 データ （変数と定数） （２） 変数の有効範囲は，節に限られる．
データ　（変数と定数）　（２） 変数の有効範囲は，節に限られる． grandchild(X,Z):- parent(Z,Y), parent(Y,X). ancestor(X,Y):- parent(X,Y). (ancestor(Y,X):- parent(Y,X).は，上と同じ) 定数は，固定された値．プログラムの実行中に値を変えることはない．定数には，文字と数値がある． 定数の有効範囲は，プログラム全体である． 2002/06/12

4 grandchild 述語 (成功例) GC=X, GF=‘波平’ FA=‘サザエ’ | ?- grandchild(X,’波平‘).
parent(‘波平’,‘サザエ’). parent(‘波平’,‘カツオ’). parent(‘波平’,‘ワカメ’). parent(‘舟’,‘サザエ’). parent(‘舟’,‘カツオ’). parent(‘舟’,‘ワカメ’). parent(‘サザエ’,‘タラオ’). parent(‘マスオ’,‘タラオ’). grandchild(GC,GF):- parent(GF,FA),parent(FA,GC). GC=X, GF=‘波平’ X=‘タラオ’ ユニフィケーション parent(‘波平’,FA),parent(FA,X). FA=‘サザエ’ FA=‘サザエ’ FA=‘サザエ’ X=‘タラオ’ parent(‘波平’,‘サザエ’). parent(‘サザエ’,X). | ?- grandchild(X,’波平‘). X = ‘タラオ’ X=‘タラオ’ X=‘タラオ’ parent(‘サザエ’,‘タラオ’). 2002/06/12

5 grandchild 述語 (失敗例) GC=X, GF=‘マスオ’ 新しい解を探す 新しい解を探す FA=‘タラオ’
grandchild(X,‘マスオ’). parent(‘波平’,‘サザエ’). parent(‘波平’,‘カツオ’). parent(‘波平’,‘ワカメ’). parent(‘舟’,‘サザエ’). parent(‘舟’,‘カツオ’). parent(‘舟’,‘ワカメ’). parent(‘サザエ’,‘タラオ’). parent(‘マスオ’,‘タラオ’). grandchild(GC,GF):- parent(GF,FA),parent(FA,GC). 失敗 新しい解を探す GC=X, GF=‘マスオ’ バックトラック parent(‘マスオ’,FA),parent(FA,X). 新しい解を探す FA=‘タラオ’ FA=‘タラオ’ FA=‘タラオ’ 失敗 parent(‘マスオ’,‘タラオ’). parent(‘タラオ’,X). | ?- grandchild(X,’マスオ‘). no 2002/06/12

6 Prologプログラムを作るための2つの視点 （１）
宣言的な視点 例えば，親子関係を事実としてした状態で，祖父／孫関係を作りたい時． 祖父／孫関係を，親子関係で説明することを考える． 祖父／孫関係は，親子の親子関係で説明できる、という事実をルールとして記述する． grandchild(GC,GF) :- parent(GF,FA),parent(FA,GC) 2002/06/12

7 Prologプログラムを作るための2つの視点 （２）
手続き的な視点 宣言的な視点で，望むプログラムが出来れば問題ない． しかし，通常，うまく動作しなかったり，処理時間に問題が発生したりする． その場合，先に示したようにProlog内部の動作を把握してプログラムの修正，改良をする必要が発生する．その時に，手続き的な視点が必要になる． 2002/06/12

8 ancestor述語 ancestor(X,’タラオ‘). parent(X,’タラオ‘). [X=X,Z=‘タラオ’]
ancestor(X,Z):-parent(X,Z). ancestor(X,Z):-parent(X,Y), ancestor(Y,Z). parent(X,’タラオ‘). [X=X,Z=‘タラオ’] parent(‘サザエ’,‘タラオ’). [X=‘サザエ’] parent(‘マスオ’,‘タラオ’). [X=‘マスオ‘] parent(X,Y),ancestor(Y,’タラオ‘). [X=X,Z=‘タラオ’] parent(‘波平’,‘サザエ’),ancestor(‘サザエ’,‘タラオ’). [X=‘波平’,Y=‘サザエ’] | ?- ancestor(X,’タラオ‘). X = ‘サザエ’ ? ; X = ‘マスオ’ ? ; X = ‘波平’ ? parent(‘波平’,‘サザエ’), parent(‘サザエ’,‘タラオ’). [X=‘サザエ’,Z=‘タラオ’] 2002/06/12

9 プログラムの構成 fact(事実)とruleで構成される．
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

10 リスト [1,a,b,coffee,X] のように定数，変数の集まりをリストと呼ぶ． リストの要素にリストを持つことも出来る．
[1,a,[10,c]] また，要素なしのリストもある． [] “|” 文字でリストの先頭とそれ以外を分離(結合)できる(ユニフィケーション)． [X|Y] = [1,2,3] (X=1, Y=[2,3]) [X|Y] = [1] (X=1, Y=[]). [X|Y] = [] no 2002/06/12

11 member述語 (成功例) member(a, [x,y,a]). X=a ? member(a,[a,....]) -> fail
member(X,[X|_]). member(X,[_|Y]):- member(X,Y). member(a, [x,y,a]). X=a ? member(a,[a,....]) -> fail member(a,[y,a]). [X=a,Y=[y,a]] | ?- member(a, [x,y,a]). yes X=a ? member(a,[a,..]) ->fail member(a,[a]). [X=a,Y=[a]] X=a ? member(a,[a,..]) -> true! 2002/06/12

12 member述語 (失敗例) member(a, [x,y]). X=a ? member(a,[a,....]) -> fail
member(X,[X|_]). member(X,[_|Y]):- member(X,Y). member(a, [x,y]). X=a ? member(a,[a,....]) -> fail member(a,[y]). [X=a,Y=[y]] | ?- member(a, [x,y]). no X=a ? member(a,[a,..]) ->fail member(a,[]). [X=a,Y=[]] X=a ? member(a,[a,..]) -> fail [_|Y] = [] -> fail 2002/06/12

13 ユニフィケーション X=Y,Y=1. parent(X)=parent(taro). parent(X)=grandchild(taro).
X=taro. parent(X)=grandchild(taro). no [X|Y] = [a,b,c,d]. X=a, Y=[b,c,d]. X=[1]. [X] = [1]. X=1. 2002/06/12

14 バックトラック 一度ユニフィケーションした変数に対して，別の解を探すこと．
Prologシステムは，与えられた述語すべてが満足する解を，ユニフィケーション，バックトラックを繰り返して探す． 最終的な解が得られるまでは，Prologシステムは，自動的にバックトラックを発生させる． 1つ解が得られたときに，別の解を探索するために ; (セミコロン)を入力して，手動でバックトラックを発生させることも出来る． 2002/06/12

15 論理和,条件分岐 grandchild(GC,GF) :- parent(GF,FA) , parent(FA,GC).
GFの子供がFAであり，かつ，FAの子供がGCの場合,GCはGFの孫である．　（論理積） parent(PA,C) :- father(PA,C) ; mother(PA,C). 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). man(X)が成功すれば，father(X,Y)を調査する．失敗すれば，mother(X,Y)を調査する． 2002/06/12

16 再帰構造 自分の定義に自分自身を使用することを再帰構造という．
member(X,[_|Y]):- member(X,Y). 再帰構造を利用したプログラムの作成は，通常，最終状態（最初の状態）と，n番目とn+1番目の関係を記述した述語を作成する． 最終状態　member(X,[X|_]). n,n+1番目の関係　　　　　 member(X,[_|Y]):- member(X,Y). 2002/06/12

17 否定 Prologの否定は，論理的否定ではなく，失敗としての否定である． ~parent(‘波平’,‘タラオ’). (論理的否定）
波平は，タラオの親ではない，という事実 \+ parent(‘波平’,‘タラオ’). (Prologの否定) 波平は，タラオの親である，という事実はない 2002/06/12

18 unmarried_man述語 unmarried_man(bill).
unmarried_man(X):- \+ married(X), man(X). man(bill). married(joe). unmarried_man(bill). \+ married(bill), man(bill) [X=bill] \+ fail, true -> true ! | ?- unmarried_man(bill). yes | ?- unmarried_man(taro). no unmarried_man(taro). \+ married(taro), man(taro) [X=taro] \+ fail, fail -> fail 2002/06/12

19 停止性 停止しないプログラム 停止させるには， married(X,Y):- married(Y,X).
Controlキーを押しながらCキーを押す． Prolog interruptionと表示されたら，aキーを押して，リターンキーを押す． 2002/06/12

20 算術演算 (特殊なユニフィケーション) X = 2+3. X is 2+3. X = 2+3, Y is X.
X = 2+3, Y = X. X=2+3, Y=2+3. 2002/06/12

21 バックトラックの制御 （１） fee(taro,X). fee(taro,1000). [X=taro]
バックトラックの制御　（１） 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,1000). [X=taro] fee(taro,2000). [X=taro] child(taro),members(taro). true,false. -> fail ! | ?- fee(taro,X). no taroが，会員じゃないことが 分かっているので，この部分は， 無駄な処理である． adult(taro),members(taro). false,members(taro). -> fail ! 2002/06/12

22 バックトラックの制御 （２） fee(taro,X). fee(taro,1000). [X=taro]
バックトラックの制御　（２） 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,1000). [X=taro] child(taro),!,members(taro). true,!,false. -> fail fee(bill,X). | ?- fee(taro,X). no | ?- fee(bill,X). fee(bill,1000). [X=bill] fee(bill,2000). [X=bill] child(bill),!,members(bill). false,!,member(bill). -> fail adult(bill),!,members(bill). false,!,member(bill). -> fail 2002/06/12

23 バックトラックの制御 （３） C :- a,b. C :- d,e. 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は調査せずに失敗する． C :- a,!,b. 　　　 　　　　C :- d,e. aが成り立たなければ，d,eを調査するが，bが成り立たなければ，d,eは調査しない． C :- a,b,!. 　　 　　　　C :- d,e. a,bが成り立たなければ，d,eを調査する．しかし一度a,bが成り立てば，d,eを調査することはしない． 2002/06/12

24 おわり 2002/06/12