Проблема с `\+` в пролог-запросах с переменными
Я читаю "Семь языков за семь недель", и я озадачен каким-то вопросом Пролога, на который я не понимаю ответа "нет".
friends.pl файл выглядит так:
likes(wallace, cheese).
likes(grommit, cheese).
likes(wendolene, sheep).
friend(X, Y) :- \+(X = Y), likes(X, Z), likes(Y, Z).
Я могу сделать несколько простых запросов, таких как:
| ?- ['friends'].
compiling /home/marc/btlang-code/code/prolog/friends.pl for byte code...
/home/marc/btlang-code/code/prolog/friends.pl compiled, 12 lines read - 994 bytes written, 8 ms
yes
| ?- friend(wallace,grommit).
yes
| ?- friend(wallace,wendolene).
no
Это все как и ожидалось. Теперь я хочу ввести переменную в запросе. Я хочу сказать, что Пролог предоставит мне список всех друзей Уоллеса. Я ожидаю X = grommit, но я получаю no:
| ?- trace.
The debugger will first creep -- showing everything (trace)
yes
{trace}
| ?- friend(wallace,X).
1 1 Call: friend(wallace,_16) ?
2 2 Call: \+wallace=_16 ?
3 3 Call: wallace=_16 ?
3 3 Exit: wallace=wallace ?
2 2 Fail: \+wallace=_16 ?
1 1 Fail: friend(wallace,_16) ?
no
{trace}
Он даже не пытается объединить X (_16) с grommit, Зачем?
4 ответа
Это определение друга:
friend(X, Y) :- \+(X = Y), likes(X, Z), likes(Y, Z).
Здесь важно то, что вы начинаете с \+(X = Y) который обычно определяется как:
\+ Goal :- Goal,!,fail
Обратите внимание, что это означает, что если цель достигнута, вы обязательно потерпите неудачу. Свободные переменные (те, которые не были назначены) всегда будут объединяться и, следовательно, будут равны, поэтому вы всегда будете терпеть неудачу со свободной переменной. Таким образом, он никогда не будет присваивать значение X или Y, если у него его еще нет.
Вместо
friend(X, Y) :- likes(X, Z), likes(Y, Z), \+(X = Y)
будет вести себя больше, как вы ожидаете.
Проблема здесь в том, что пролог дает вам мощные способы управления потоком программ, но они не очень хорошо вписываются в его более логичный дизайн. Должна быть возможность выразить ограничения типа "отрицание как сбой" таким образом, чтобы эти проблемы не возникали. По этой причине я не большой поклонник пролога.
Относительно комментария Филиппа JF выше:
Должна быть возможность выразить ограничения типа "отрицание как сбой" таким образом, чтобы эти проблемы не возникали.
Это возможно: современное решение таких проблем - это ограничения. В этом случае используйте, например, dif/2, доступный во всех серьезных системах Prolog.
Первая подцель friend/2 является \+(X = Y), Это выполняется при первой попытке найти решение для X = Yзатем отрицая этот результат. Предикат =/2 примерно эквивалентно unify/2то есть он пытается объединить левый операнд с правым операндом. Теперь, когда вы задаете запросы, используя, например, friend(wallace, gromit), два атома wallace а также gromit не объединяйся; но когда в смесь добавляется свободная переменная, она всегда объединяется с любым заданным термином, поэтому X = Y поэтому всегда успешен \+(X = Y) всегда терпит неудачу, и выполнение никогда не проходит эту первую подзадачу.
Другая проблема, связанная с наличием ограничения неравенства, заключается в следующем: невозможно найти привязку для несвязанного X (исключая тривиальный случай объединения его с grommit на данный момент). Пролог находит привязки, пробегая свою базу данных, пытаясь объединить несвязанную переменную. Поэтому likes(grommit, Z) найдет некоторую привязку для Z которые затем могут быть обработаны, потому что есть likes пункты в базе данных. Но нет таких условий для неравенства grommit с чем-то, поэтому Prolog не может производить никаких привязок. При нынешнем положении вещей friend Предикат должен убедиться, что все переменные связаны, прежде чем можно будет проверить неравенство.