Prolog Language
データの推論
サーチ…
備考
データ構造と呼ばれる新しいセクションが生まれました。そこでは、特定の構造の説明+いくつかの簡単な作成例が提供されています。内容を簡潔かつ整理したものにするために、データ操作に関する文書は含まれていてはなりません。
したがって、このセクションは、Prologのデータに関する推論の一般化を目的として、「データについての推論」に改名されました。これには、「トップダウン推論」から「リストのトラバーサル」など、さまざまなトピックが含まれます。その広範な一般化のために、明確なサブセクションを作成する必要があります!
再帰
Prologには繰り返しはありませんが、すべての反復は再帰を使用して書き換えられます。述語に自身を参照するゴールが含まれている場合、再帰が表示されます。このような述語をPrologに書くとき、標準の再帰パターンは常に少なくとも2つの部分を持っています:
ベース(再帰的ではない)句 :通常、ベースケースのルールは、解決しようとしている問題の最小可能な例を表します。メンバーのないリスト、またはただ1つのメンバーです。ツリー構造を扱っている場合、空のツリー、またはその中にただ1つのノードを持つツリーなどを扱うかもしれません。再帰的なプロセスの基底を非再帰的に記述します。
再帰的(継続的)句 :自己への呼び出し、継続的な再帰を含む必要なロジックをすべて含みます。
一例として、よく知られた述語append/3
を定義する。宣言的に見ると、リストL3
がリストL1
およびL2
を追加した結果であるときに、 append(L1,L2,L3)
が追加されます。述語の宣言的意味を理解しようとするとき、述語が保持する解を記述しようとする。ここでの難しさは、述語が提示すべき手続き的振る舞いを念頭に置いて、段階的に繰り返される詳細を避けることにあります。
% Base case
append([],L,L).
% Recursive clause
append([X|L1],L2,[X|L3]) :- append(L1,L2,L3).
基底の場合、宣言的に "空のリストに追加されたLはすべてL"であることに注意してください。これはLが空でないこと、またはリストでもないことに注意してください(Prologのすべてが条件になります)。
?- append(X,some_term(a,b),Z).
X = [],
Z = some_term(a, b).
再帰的なルールを説明するために、Prologは左から右へルールを実行しますが、頭を1秒間省略し、最初にボディを見ます。右から左へルールを読みます:
append([X|L1],L2,[X|L3]):- append(L1,L2,L3).
ここで、ボディが保持しているとしappend(L1,L2,L3)
。「 append(L1,L2,L3)
がappend(L1,L2,L3)
ていると仮定するとappend(L1,L2,L3)
append([X|L1],L2,[X|L3]) :-append(L1,L2,L3).
それで頭もそうです: "それではappend([X|L1],L2,[X|L3])
普通の英語でこれは単に次のように翻訳されます:
L3がL1とL2の連結であるとすると、[Xの後にL3が続く]は、[XにL1が続く]とL2の連結でもあります。
実際の例では:
[1,2,3]を[1]と[2,3]の連結とすると、[a、1,2,3]は[a、1]と[2,3]の連結でもあります。 "
次にいくつかのクエリを見てみましょう:
特定のシナリオのテストケースを提供するのではなく、 最も一般的なクエリを使用して述語を最初にテストすることは、常に良い考えです。それを考えてみましょう:Prologの統一のために、テストデータを提供する必要はありません。
?- append(L1,L2,L3).
L1 = [],
L2 = L3 ; % Answer #1
L1 = [_G1162],
L3 = [_G1162|L2] ; % Answer #2
L1 = [_G1162, _G1168],
L3 = [_G1162, _G1168|L2] ; % Answer #3
L1 = [_G1162, _G1168, _G1174],
L3 = [_G1162, _G1168, _G1174|L2] ; % Answer #4
...
より良い概観を得るために、自由変数_G1162
ような表記法をアルファベットの文字に置き換えてみましょう:
?- append(L1,L2,L3).
L1 = [],
L2 = L3 ; % Answer #1
L1 = [_A],
L3 = [_A|L2] ; % Answer #2
L1 = [_A, _B],
L3 = [_A, _B|L2] ; % Answer #3
L1 = [_A, _B, _C],
L3 = [_A, _B, _C|L2] ; % Answer #4
...
最初の答えでは、基本ケースはパターンマッチングされ、PrologはL1
を空のリストにインスタンス化し、 L3
が空のリストとL2の連結であることを証明する統一されたL2
とL3
を作成しました。
答え#2では、時系列のバックトラッキングにより、再帰的な節が始まり、PrologはL2
と連結されたL1
の頭部のある要素がそのリストの頭部に同じ要素を持つL3
であることを証明しようとします。そうするために、新しい自由変数_A
はL1の頭で統一され、L3は[_A|L2]
あることが証明されています。
新しい再帰呼び出しが行われ、 L1 = [_A]
。もう一度、プロローグはL1
の頭部に配置されたいくつかの要素がL2
で連結されていることを、頭部に同じ要素を持つL3
であることを証明しようとします。 _A
は既にルールの完全に一致するL1
の頭であることに注意してください。ここで、再帰によってPrologは新しい自由変数の前に_A
を置き、 L1 = [_A,_B]
とL3 = [_A,_B|L2]
明らかに再帰パターンが繰り返されていることがわかります。たとえば、再帰の100番目のステップの結果は次のようになります。
L1 = [X1,X2,..,X99],
L3 = [X1,X2,..,X99|L2]
注:良いプロローグコードの典型的なものである、の再帰的な定義としてappend/3
リストが他の二つのリストの連結であるかどうかを検証する可能性を私たちだけではなくを提供し、それはまた、完全にとの論理的な関係を満たす、すべての可能な答えを生成し 、または部分的にインスタンス化されたリスト。
リストへのアクセス
メンバー
member/2
は署名member(?Elem, ?List)
持ち、 Elem
がList
メンバであればtrue
を示す。この述部は、リスト内の変数にアクセスするために使用できます。リスト内の変数には、バック・トラッキングによってさまざまな解が取り出されます。
クエリ例:
?- member(X, [1,2,3]).
X = 1 ;
X = 2 ;
X = 3.
?- member(X,[Y]).
X = Y.
?- member(X,Y).
Y = [X|_G969] ;
Y = [_G968, X|_G972] ;
Y = [_G968, _G971, X|_G975] ;
Y = [_G968, _G971, _G974, X|_G978]
...
パターンマッチング
アクセスする必要のある指標が小さい場合、パターンマッチングは良い解決策になります。例:
third([_,_,X|_], X).
fourth([_,_,_,X|_], X).