Share
Embed
Transcript
10 slides
-
3 サザ◦さん %事実 親子(ふね,サザエ). 親子(ふね,カツオ). 親子(ふね,ワカメ). 親子(サザエ,タラオ). %規則 兄弟(X,Y) :
親子(Z,X), 親子(Z,Y), X\==Y. %ここまでをファイルに記述し、Prolog処理系にロードする %質問 ? 親子(ふね,X). X = サザエ ; X = カツオ ; X = ワカメ ? 兄弟(カツオ,ワカメ). yes. ? 兄弟(タラオ,ワカメ). no. -
4 地図を塗り分ける different(red,green). different(red,blue). different(green,red). different(green,blue). different(blue,red). different(blue,green). coloring(Hyogo,Kyoto,Shiga,Nara,Osaka,Wakayama) :
different(Hyogo,Kyoto), …… , different(Osaka,Wakayama). ? coloring(Hyogo,Kyoto,Shiga,Nara,Osaka,Wakayama). Hyogo = red Kyoto = green Shiga = red Nara = red Osaka = blue Wakayama = green ; Hyogo = red Kyoto = green Shiga = blue Nara = red Osaka = blue Wakayama = green (...以下省略) -
5 append %リストを連結 append([], Xs, Xs). append([X | Ls], Ys,
[X | Zs]) : append(Ls, Ys, Zs). %質問 ? append([1,2],[3,4,5],X). X = [1,2,3,4,5] yes. ? append([1,2],X,[1,2,3,4,5]). X = [3,4,5] yes. ? append(X,Y,[a,b,c]). X = NIL Y = [a,b,c] ; X = [a] Y = [b,c] ; X = [a,b] Y = [c] ; X = [a,b,c] Y = NIL -
6 Prologの動作 • 合致する節がなければ失敗 • 合致する節があり、その副目標もすべて成功すれ ば、成功 • 節の意味 –
A :- B, C, D. • 「B かつ C かつ D が真なら A は真」(命題として見る) • 「サブルーチンAは文B, C, Dを逐次実行」(手続き的な見方) • Prologの実行は深さ優先探索と見ることもできる -
7 単一化(ユニフィケーション) • Prologの変数 – Prologの変数ははじめ未束縛(アンバウンド) – 一度代入されると値は変えられない • 『合致する』というのは項同士の単一化(ユニフィケーショ
ン)で調べる – 単一化は2つの項を等しくしようとする操作 – 未束縛変数と値の単一化は、変数への代入 – 未束縛変数同士の単一化は、2つの変数を同一視 – 親子(ふね, サザエ) と 親子(ふね, X)を単一化 • Xにサザエが代入される(Xは未束縛だとする) – 親子(ふね, サザエ) と 親子(波平, サザエ)の単一化 • 失敗する • 双方向性 – appendの例では、3つの引数うちどれを変数にしてもうごいた -
8 バックトラック • Prologの大きな特徴 • もし目標が失敗したら – いったん巻き戻して、別の候補を探しに行く – それまでの変数への代入はなかったことにされる
• 非決定性 – 解が複数 – バックトラックのおかげで、親子(ふね,X) は3つの解を持 つ -
9 Warren's Abstract Machine (WAM) • Prologプログラムを効率よく動かすために考えられたアーキテクチャ switchonterm L2,L1,L5,FAIL L1:
switchonconstant {[] L3} → L2: trymeelse L5 L3: getconstant [],A1 getvalue X2,A3 proceed L4: trustme L5: getlist A1 unifyvariable X4 unifyvariable X1 getlist A3 unifyvalue X4 unifyvariable X3 execute append/3 %append( % [], % Xs, Xs %). %append( % [ % X | % Ls], Ys, % [ % X | % Zs]) : %append(Ls, Ys, Zs). append/3をWAMの命令列にコンパイルした結果 -
10 参考文献 • Prolog(Wikipedia) – https://ja.wikipedia.org/wiki/Prolog • Prologを使ってみる – http://www.takeoka.org/~take/ailabo/prolog/prolog-prol
ogue.html • 7つの言語 7つの世界(Bruce.A.Tate, オーム社) • wambook – http://wambook.sourceforge.net/ • AN ABSTRACT PROLOG INSTRUCTION SET(和訳) – http://www.takeoka.org/~take/ailabo/prolog/wam/wam.h tml