Пролог: «вырезать» в запросе против правил/фактов

Выполняя упражнение 10.4 на learnprolognow, может кто-нибудь объяснить мне или помогите мне представить, почему для ?- p(X),p(Y) мы получаем:
X=1,Y=1; X=1,Y=2; X=2, Y=1; X=2, Y=1. И не только X=1, Y=1; X=1, Y=2.

Я думаю, что неправильно понимаю, как происходит разрез, когда он находится в наборе правил, а не в запросе, потому что я думаю, что могу визуализировать его для ?- p(X),!,p(Y)., где он на самом деле ведет себя так, как я думал, будет последний...

Изменить: с веб-сайта

% database
p(1).
p(2):-!.
p(3).

% Queries
p(X). % returns: X=1; X=2.
p(X),p(Y). % returns: X=1,Y=1; X=1, Y=1; X=2, Y=2. (?)
p(X),!,p(Y). % returns X=1, Y=1; X=1, Y=2.

prolog prolog-cut
person user452306    schedule 05.01.2018    source источник
comment
Прочитайте это: en.wikibooks.org/wiki/Prolog/Cuts_and_Negation   -  person damianodamiano    schedule 05.01.2018
comment
Спасибо, я уже посмотрел на это, но мне не хватает, почему для p(X),p(Y) он откатывается, чтобы изменить значение X?   -  person user452306    schedule 05.01.2018
comment
p(X), p(Y) возвращается к p(X), потому что так работает Пролог. Разрез между ними, p(X), !, p(Y), предотвращает возврат к p(X). Другими словами, как только p(X), p(Y) завершится успешно, Пролог отступит и попытается найти другое Y, которое также приведет к успеху. Как только эти варианты исчерпаны, он возвращается назад, чтобы найти другой X, чтобы позволить p(X) добиться успеха, а затем снова переходит к p(Y) (начиная с p/1 фактов).   -  person lurker    schedule 05.01.2018
comment
Значит, урезание в правилах не предотвращает откат запроса?   -  person user452306    schedule 05.01.2018
comment
Да, это так. Вы видите X = 3 или Y = 3 в любом из ваших решений? Вы не из-за p(2) :- !.. Пролог никогда не доходит до проверки p(3)..   -  person lurker    schedule 05.01.2018

Ответы (1)


arrow_upward
1
arrow_downward

Чтобы понять эту проблему, вы можете представить дерево с X в качестве первого уровня и Y в качестве второго уровня (в прологе используется разрешение sld, которое хорошо описывается деревом). Рассмотрим эту проблему:

p(1).
p(2):-!.
p(3).

sol(X,Y):-
    p(X),
    p(Y).

Я добавил предикат solve/2, чтобы сделать его более понятным. Запустите запрос:

?- solve(X,Y).

Прежде всего, вы должны выбрать значение для X. Пролог использует поиск в глубину сверху вниз, слева направо. Таким образом, он оценивает p(x): p(1) успешно (потому что это первое предложение, если вы напишете p(2) выше p(1), p(2) будет успешным) и, таким образом, X = 1. Затем оценивает p(Y): p(1) успешно, и поэтому у вас есть первое решение:

X = Y, Y = 1.

Если вы нажмете больше, то пролог сделает возврат (вы можете представить это как шаг вверх по дереву) и попробует другое значение для p(Y). В этом случае p(2) выполняется успешно, предикат истинен, и вы получаете:

X = 1, Y = 2.

Теперь, если вы нажмете дальше, из-за того, что в теле p(2) есть разрез (!) (общее правило в прологе имеет форму head :- body), пролог не будет углубляться, а p(3) будет проигнорирован. Так что решения p(Y) больше нет. Итак, есть еще один возврат, и на этот раз для p(X), p(2) успешно и X = 2, а для p(Y), p(1) успешно, и вы получаете:

X = 2, Y = 1.

Если вы нажмете на больше, вы получите:

X = Y, Y = 2.

Теперь, из-за того, что после p(2) есть вырез, больше нет доступных решений как для X, так и для Y (! вырезает все, что ниже p(2)).

Если вы удалите разрез, вы получите все возможные решения:

X = Y, Y = 1
X = 1,
Y = 2
X = 1,
Y = 3
X = 2,
Y = 1
X = Y, Y = 2
X = 2,
Y = 3
X = 3,
Y = 1
X = 3,
Y = 2
X = Y, Y = 3

Имейте в виду, что порядок предложений важен. Если вы пишете

p(2).
p(1):-!.
p(3).

Ты получаешь

X = Y, Y = 2
X = 2,
Y = 1
X = 1,
Y = 2
X = Y, Y = 1

Вы можете проверить это поведение с помощью трассировщика. В SWI или SWISH вы можете написать ?- trace, solve(X,Y).

Если у вас возникла такая ситуация:

p(1).
p(2).
p(3).

sol(X,Y):-
    p(X),
    !,
    p(Y).

prolog проверит все возможные значения для Y и только одно значение для X, потому что разрез останавливает исследование дерева (в идеале у вас есть 3 ветви для X (1,2,3) и 3 для Y (1,2,3) , ! вырезает 2 и 3 из X), и вы получаете:

X = Y, Y = 1
X = 1,
Y = 2
X = 1,
Y = 3

Извините за длинный пост, надеюсь на ясность.

person damianodamiano    schedule 05.01.2018
comment
Спасибо, но почему это: Итак, происходит еще один возврат, и на этот раз для p(X),(...)? Разве сокращение не должно остановить все отступления? Или он останавливается только до определенного уровня? - person user452306; 05.01.2018
comment
Разрез, да, останавливает откат. В этом случае вы тестируете p(1), а затем p(2) как для X, так и для Y. В этом случае ! останавливает поиск с возвратом только для предиката p/1, а не весь поиск с возвратом. - person damianodamiano; 05.01.2018
comment
В этом есть смысл! Спасибо большое :) - person user452306; 05.01.2018