この Prolog 述語はなぜ機能するのでしょうか?

Question

次のコードがあります。このコードはリストに対して動作しますが、これらのリストはセットを表すため、[1,1,2,2,3,3] と [1,2,3] は同等である必要があることに注意してください。

%contains(L1, L2), returns true if L1 contains L2
contains(_, []).
contains(L1, [Head|Tail]) :- member(Head, L1), contains(L1, Tail).
%equals(L1, L2), returns true if L1 is equal to L2
equals([X|L1],[X|L2]) :- equals(L1, L2).
equals(L1, L2) :- contains(L1, L2), contains(L2, L1).

考え方としては、equals([1,2,3],[1,2,1,3]) は true を返す必要があるということです。ただし、上記の定義に基づいて、私が期待することは次のとおりです。

1. equals([1,2,3],[1,2,1,3]) は最初のルールに一致し、equals([2,3],[2,1,3]]) を呼び出します。
2. Equals（[2,3]、[2,1,3]]）は2番目のルールと一致し、Invokes contains（[2,3]、[2,1,3]）が含まれます（[2,1,3]、 [2,3]）。
3. contains([2,3], [2,1,3]) は失敗し、等しい場合は No を返します。

それでもまだ機能します。そして、それを混乱させようとする他の試みも同様です。誰か説明してくれませんか？

(プロローグの実装:SWI-Prolog バージョン 2.7.12)

Answer 1

プロローグは "バックトラッキング" と呼ばれる技術を使用しています。

最初のステップ、あなたのステップ1を見てみましょう。

Prologはそれはそれはあなたがあなたの説明で選択したルールを使用している場合、それは常に失敗します、ここで使用できる2つのルールがあります。それが失敗した後しかし、プロローグはバックトラックと代替ルールをしようとします：

（[1,2,3]、[1,2,1,3]）に等しい： - （[1,2,1,3]、[1,2,3]）が含まれ、1 - [（含まれてい、2,1,3]、[1,2,3]）

が繰り返し誤った答えを見つけた後バックトラックすることにより、最終的にはプロローグが真の解決策を見つけたので、それは答えが真であることを知ってます。

真の答えを見つけることなく、ルールを適用するあらゆる可能な方法を試してみましたならば、答えは偽でなければならない場合ます。

このプロローグの非常に基本的な部分です。私はあなたがはるかにそれを理解せずにこれを得た驚いています。

Answer 2

あなたのコードは非常に奇妙である、しかし、私はあなたがテストの目的でトレース述語を使用することをお勧めすることができます。ここでは例があります：

4 ?- trace([equals,contains]).
%         equals/2: [call, redo, exit, fail]
%         contains/2: [call, redo, exit, fail]
true.

[debug] 5 ?- equals([1,2,3],[1,2,1,3]).
 T Call: (7) equals([1, 2, 3], [1, 2, 1, 3])
 T Call: (8) equals([2, 3], [2, 1, 3])
 T Call: (9) equals([3], [1, 3])
 T Call: (10) contains([3], [1, 3])
 T Fail: (10) contains([3], [1, 3])
 T Fail: (9) equals([3], [1, 3])
 T Redo: (8) equals([2, 3], [2, 1, 3])
 T Call: (9) contains([2, 3], [2, 1, 3])
 T Call: (10) contains([2, 3], [1, 3])
 T Fail: (10) contains([2, 3], [1, 3])
 T Fail: (9) contains([2, 3], [2, 1, 3])
 T Fail: (8) equals([2, 3], [2, 1, 3])
 T Redo: (7) equals([1, 2, 3], [1, 2, 1, 3])
 T Call: (8) contains([1, 2, 3], [1, 2, 1, 3])
 T Call: (9) contains([1, 2, 3], [2, 1, 3])
 T Call: (10) contains([1, 2, 3], [1, 3])
 T Call: (11) contains([1, 2, 3], [3])
 T Call: (12) contains([1, 2, 3], [])
 T Exit: (12) contains([1, 2, 3], [])
 T Exit: (11) contains([1, 2, 3], [3])
 T Exit: (10) contains([1, 2, 3], [1, 3])
 T Exit: (9) contains([1, 2, 3], [2, 1, 3])
 T Exit: (8) contains([1, 2, 3], [1, 2, 1, 3])
 T Call: (8) contains([1, 2, 1, 3], [1, 2, 3])
 T Call: (9) contains([1, 2, 1, 3], [2, 3])
 T Call: (10) contains([1, 2, 1, 3], [3])
 T Call: (11) contains([1, 2, 1, 3], [])
 T Exit: (11) contains([1, 2, 1, 3], [])
 T Exit: (10) contains([1, 2, 1, 3], [3])
 T Exit: (9) contains([1, 2, 1, 3], [2, 3])
 T Exit: (8) contains([1, 2, 1, 3], [1, 2, 3])
 T Exit: (7) equals([1, 2, 3], [1, 2, 1, 3])
true