Почему этот предикат Пролога работает?

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. равно ([1,2,3], [1,2,1,3]) соответствует первому правилу и вызывает равно ([2,3], [2,1,3]]).
2. равно ([2,3], [2,1,3]]) соответствует второму правилу и вызывает содержит ([2,3], [2,1,3]), содержит ([2,1,3], [2,3]).
3. содержит ([2,3], [2,1,3]) сбоев и равняется возвратам.

И все же это все еще работает. И то же самое делают другие попытки запутать это. Может кто-нибудь, пожалуйста, объясните мне это?

(реализация Пролога: SWI-Prolog Версия 2.7.12)

Answer 1

Пролог использует технику, называемую «возвращение».

Посмотрите на первый шаг, ваш шаг 1.

У Пролога есть два правила, которые он может использовать здесь, если он использует правило, которое вы выбрали в своем объяснении, он всегда будет неудачным. Но как только он потерпит неудачу, Пролог вернется и попробует альтернативное правило:

равно ([1,2,3], [1,2,1,3]): - содержит ([1,2,3], [1,2,1,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