私は Prolog でプログラミングする方法を学んでおり、自然数とその和を定義する次のプログラムを見つけました。
sum( succ( X ), Y, succ( Z )) :- sum( X, Y, Z ).
sum( 0, X, X ).
?- sum( succ( succ(0)), succ( succ( succ(0))), Answer ).
Answer = succ( succ( succ( succ( succ(0)))))
（ここにあります）
問題は、このプログラムの実行フローに苦労していることです。実を言うと、私はそれが何をするのかわかりません。Prolog はどのようにして Answer の値を割り出すことができますか? Prolog が Answer の値を見つけるためにたどる手順は何ですか?
前もって感謝します。
Prolog の「評価」は、指定されたクエリをプログラムのルールのheadに一致させ、一致する置換の下で、一致するルールのbodyに進むことによって進みます。ルールが選択されると、一意性のために、その変数の名前が一様に変更されます。
(1) sum( succ( X ), Y, succ( Z )) :- sum( X, Y, Z ).
（2）合計（0、X、X）。
?- sum( succ( succ(0)), succ( succ( succ(0))), 答え ).
(1) -> sum( succ( X1 ), Y1 , succ( Z1 )) :- sum( X1, Y1, Z1 ).
%% X1 = succ(0), Y1 = succ( succ( succ(0))), succ(Z1) = 答え. %%
-? sum( X1, Y1, Z1 ) .
-? sum( succ( 0 ), Y1, Z1 ).
(1) -> sum( succ( X2 ), Y2, succ( Z2 )) :- sum( X2, Y2, Z2 ) .
%% X2 = 0、Y2 = Y1、成功 (Z2) = Z1。%%
-? 合計 ( X2、Y2、Z2 )。
-? 合計（0、Y2、Z2）。
(2) -> sum( 0, X3, X3 ). ％％ 終わり。%%
%% X3 = Y2、X3 = Z2。%%
ここから、Answer = succ(Z1) = succ( succ(Z2)) = succ( succ(X3)) = succ( succ( Y2)) = succ( succ (Y1)) = succ( succ( succ( succ( succ(0))))).
既存の述語を理解するとき、または新しい述語を設計するときに、Prolog がどのように動作するかを理解するのに役立ちます。次のようなクエリを作成すると、次のようになります。
sum( succ(succ(0)), succ(succ(succ(0))), Answer ).
sum(_, _, _)Prolog は、一致するファクトとルール( )を探し、一致sum/3する最初のものを選択します。適用される規則は次のとおりです。
(1) sum( succ(X), Y, succ(Z) ) :- sum( X, Y, Z ).
(2) sum( 0, X, X ).
クエリを見ると、明らかにルール 1 のパターンと一致しています。Prolog では、変数は任意の種類の用語にインスタンス化でき、同じ名前の変数は統合 (同じ値にインスタンス化) されることに注意してください。Prolog がルール #1 の「ヘッド」をクエリと統合する場合、次のように変数を統合することでこれを行います。
X = succ(0)
Y = succ(succ(succ(0)))
(A) Answer = succ(Z)
まだバインドされていない (具体的な値が割り当てられていない)にもかかわらず、Answerには値があることに注意してください。ここで、クエリになるルールに従います。これはクエリになります。succ(Z)Zsum(X, Y, Z)
sum( succ(0), succ(succ(succ(0))), Z )
| | |
X Y Z
これは の新しいクエリであるため、Prolog は再び先頭から開始されますsum/3。最初と同じように、ルール #1 と次の統合が一致します。
X = 0
Y = succ(succ(succ(0)))
(B) Z = succ(Z')
の head で使用されているものとは異なるため、上記を使用しZ'て の他の変数と区別しています。これは、C で として宣言された関数があり、どこかから別のローカル変数でそれを呼び出す場合、その名前は 2 つの異なる場所で使用され、2 つの異なる変数を表すようなものです)。Zsum(succ(0), succ(succ(succ(0))), Z)Zsum(..., succ(Z))int f(x) { return 2*x; }xx
次に、次の再帰クエリをたどることができます。これは次のようにsum(X, Y, Z')なります。
sum( 0, succ(succ(succ(0))), Z' )
| | |
X Y Z'
この再帰クエリは、最初の引数 が一致しないため、ルール 1 に0一致しませんsucc(X)。ただし、ルール #2 に一致します。
0 = 0
X = succ(succ(succ(0)))
(C) X = Z'
今X = succ(succ(succ(0)))そうZ' = succ(succ(succ(0)))です。このルールにはクエリが含まれていないため、最終的にクエリ元に戻ります。これを上記の (B) に戻すと、次のようになります。
Z = succ(Z') = succ(succ(succ(succ(0))))
これを (A) に戻します。
Answer = succ(Z) = succ(succ(succ(succ(succ(0)))))
そして、あなたはそれを持っています。trace@CapelliC が言及した機能を使用すると、これらの連続するステップが Prolog インタープリターで発生するのを確認し、変数のインスタンス化をたどることができます。
このような単純なプログラムの場合、trace/0 が最適です。leash /1 (初心者にはまったく明らかではない) を使用すると、デバッガー インターフェイスを制御できます。
21 ?- leash(-all),trace.
true.
[trace] 22 ?- sum( succ( succ(0)), succ( succ( succ(0))), Answer ).
Call: (6) sum(succ(succ(0)), succ(succ(succ(0))), _G710)
Call: (7) sum(succ(0), succ(succ(succ(0))), _G789)
Call: (8) sum(0, succ(succ(succ(0))), _G791)
Exit: (8) sum(0, succ(succ(succ(0))), succ(succ(succ(0))))
Exit: (7) sum(succ(0), succ(succ(succ(0))), succ(succ(succ(succ(0)))))
Exit: (6) sum(succ(succ(0)), succ(succ(succ(0))), succ(succ(succ(succ(succ(0))))))
Answer = succ(succ(succ(succ(succ(0))))).
あなたのプログラムが最初の引数で限定再帰検索を行い、それを最初の節 (6,7 とマークされた呼び出し) または 2 番目の節 (8 とマークされた呼び出し) のいずれかと統合していることがわかります。