可能であれば、誰かにこの手順を説明してもらいたいです (「learn prolog now」という本から)。2 つの数字を取り、それらを加算します。
add(0,Y,Y).
add(s(X),Y,s(Z)) :- add(X,Y,Z).
原則として理解していますが、いくつか問題があります。クエリを発行するとしましょう
?- add(s(s(0)), s(0), R).
結果は次のとおりです。
R = s(s(s(0))).
ステップ 1 はルール 2 との一致です。ここで、X は s(0) になり、Y は s(0) のままです。ただし、Z (本によると) は s(_G648)、またはその中にインスタンス化されていない変数を持つ s() になります。どうしてこれなの？
最後のステップで、最初のルールが一致し、再帰が終了します。ここで、Y の内容は、どういうわけか、Z のインスタンス化されていない部分になってしまいます! 非常に紛らわしいので、わかりやすい英語の説明が必要です。
最初の施設:
s(X)後継者として定義しましたX最初に、私がより直感的に見つけた後継者を伴う加算の別の定義を見てみましょう。
add(0,Y,Y).
add(s(A),B,C) :- add(A,s(B),C).
これは基本的に同じことを行いますが、再帰の方が見やすいです:
私たちは尋ねます
add(s(s(0)),s(0),R).
今、最初のステップのプロローグは、それが同等であると言います
add(s(0),s(s(0)),R)
なぜならadd(s(A),B,C) :- add(A,s(B),C)、質問 A = s(0) と B=s(0) を見ると、しかし、これはまだ終了しないので、A=0 と B=s(s(0)) でその等価性を再適用する必要があるため、次のようになります。
add(0,s(s(s(0))),R)
つまり、add(0,Y,Y).これが意味することを考えると
R = s(s(s(0)))
add の定義は基本的に同じですが、2 つの再帰があります。
最初に最初の引数を 0 まで実行するため、add(0,Y,Y) になります。
add(s(s(0)),s(0),R)
X=s(0)、Y = s(0)、s(Z) = R、Z = _G001 の場合
add(s(0),s(0),_G001)
X = 0、Y=s(0) および s(s(Z)) = s(G_001) = R および Z = _G002 の場合
add(0,s(0),_G002)
これで、定義 add(0,Y,Y) から _G002 が s(0) であることがわかりますが、その手順をさかのぼってトレースする必要があるため、_G001 は s(_G002) であり、R は s(_G001) であり、s(s(_G002) です。 ) は s(s(s(0))) です。
つまり、定義 add(0,Y,Y) にたどり着くには、最初の再帰でプロローグに内部変数を導入する必要があり、そこから R が 2 番目の再帰で評価されます。
Prolog プログラムの意味を理解したい場合は、最初に関係が何を記述しているかに集中することができます。次に、その終端特性を理解したいと思うかもしれません。
あなたの質問が示唆するように、具体的な実行の非常に詳細に入る場合、すぐに詳細の多様性に夢中になります。結局、Prolog には2 つの異なるインターレース制御フロー (AND 制御と OR 制御) があり、それに加えて、パラメーターの受け渡し、代入、比較、方程式の解法を含む統合があります。
簡単に言うと、コンピューターは膨大な数の推論に対して具体的なクエリを簡単に実行しますが、画面いっぱいに推論すると疲れてしまいます。その点ではコンピュータに勝てません。幸いなことに、プログラムを理解するためのより良い方法があります。
意味については、まずルールを見てください。それは読みます：
add(s(X),Y,s(Z)) :- add(X,Y,Z).
間に見え:-ますか？矢を象徴するものです。矢印が右から左を指すのは少し珍しいです。非公式の書き方では、むしろ左から右に書きます。これを次のように読みます。
提供された場合
add(X,Y,Z)は true であり、その後もadd(s(X),Y,s(Z))true です。
add(X,Y,Z)したがって、 「X+Y=Z」という意味はすでにあると仮定します。すると、「(X+1)+Y=(Z+1)」も成り立つことがわかります。
その後、その終端特性を理解したいと思うかもしれません。これを非常に簡単に説明しましょう: それを理解するには、ルールを確認するだけで十分です: 2 番目の引数は、さらに引き渡されるだけです。したがって: 2 番目の引数は終了に影響しません。そして、1 番目と 3 番目の引数はどちらも同じように見えます。したがって、どちらも同じように終了に影響を与えます! 実際、1 番目または 3 番目の引数のいずれかが と統合されない場合、 add/3 は終了しs(_)ます。
次のように、failure-sliceとタグ付けされた他の回答で詳細を確認してください。
しかし今、あなたの質問に答えるために、add(s(s(0)), s(0), R). 私は最初の引数だけを見ています: はい! これで終了します。それでおしまい。
問題を 3 つの部分に分けてみましょう。変数のインスタンス化に関する問題と、その例のバリエーションで使用するアキュムレータ パターンです。
add(0,Y,Y).
add(s(X),Y,Z):-add(X,s(Y),Z).
そして、置換の構成を使用する例についてのコメント。
Prolog がどのルール (つまり、ホーン節) が一致する (そのヘッドが統合する) かを確認するために適用するのは、特に、変数がある場合、X とファンター、つまり f(Y ）これらの2つの用語は統一されています（発生チェックについては小さな部分があります...チェックしますが、atmは気にしません）したがって、1つを別の用語に変換できる置換があります。
2 番目のルールが呼び出されると、実際に R は s(Z) に統合されます。Prolog がインスタンス化されていない新しい変数に与える内部表現に怯える必要はありません。コードを表すのは単なる変数名 ('_' で始まるため) です (Prolog には、常に新しく生成された変数を表現する方法が必要であり、 _G648、_G649、_G650 など)。Prolog プロシージャを呼び出す場合、インスタンス化されていないパラメータ (この場合は R) は、プロシージャの実行が完了すると、プロシージャの結果を格納するために使用されます。何かにインスタンス化されます (常に統合によって)。ある時点で var がある場合、つまり K が s(H) (または必要に応じて s(_G567)) にインスタンス化されている場合、
アキュムレータ パターンは関数型プログラミングから取られたものであり、要するに変数、アキュムレータ(私の場合は Y 自体) を持つ方法であり、いくつかのプロシージャ コール間で部分的な計算を実行する負担があります。このパターンは再帰に依存しており、おおよそ次の形式になります。
最後に、あなたの例に関して、それは別のパターンに従います。置換の構成は、アキュムレータと統合によるインスタンス化について考えた方がよく理解できると思います。
スタック トレースは次のとおりです。
add(s(s(s(0))),s(0),S1). ^ S1=s(S2)=s(s(s(s(0))))
add( s(s(0)) ,s(0),S2). | S2=s(S3)=s(s(s(0)))
add( s(0) ,s(0),S3). | S3=s(S4)=s(s(0))
add( 0 ,s(0),S4). | S4=s(0)
add( 0 ,s(0),s(0)). ______|