Лучшее понимание пролога

Я пытаюсь понять Пролог и то, как он использует алгоритм разрешения. У меня есть этот пример, который я нашел:

hates(1, 2).
hates(2, 3).
hates(3, 4).
jealous(A, B) :- jealous(A, C), jealous(C,B).
jealous(A,B) :- hates(A,B).

Но когда я пытаюсь сказать, что jealous(1,4), оно продолжает переполняться и никогда не дает истинного результата, что странно, как будто 1 ненавидит 2, 2 ненавидит 3 и 3 ненавидит 4, тогда 1 также должен ненавидеть 4.

Но я попытался изменить его, чтобы он был таким:

hates(1, 2).
hates(2, 3).
hates(3, 4).
jealous(A,B) :- hates(A,B).
jealous(A, B) :- jealous(A, C), jealous(C,B).

И тогда это работает, когда я говорю jealous(1,4).


prolog transitive-closure failure-slice
person Gringo    schedule 08.04.2021    source источник

Ответы (2)


arrow_upward
6
arrow_downward

И тогда это работает, когда я говорю jealous(1,4)

Нет, это не так. Ну или типа того. Просто введите ПРОБЕЛ, чтобы увидеть, что он снова зацикливается. А как насчет jealous(4,1), который зацикливается сразу?

Чтобы понять это, достаточно взглянуть на очень маленькую часть вашей программы, а именно на эту:

jealous(A,B) :- false, hates(A,B).
jealous(A, B) :- jealous(A, C), false, jealous(C,B).

Обратите внимание на переменную B, которая никогда не используется в видимой части. Таким образом, это не может иметь никакого влияния на прекращение. И обратите внимание на A, который только что вручили первому голу. Таким образом, оба аргумента не имеют значения в этой программе. Таким образом, эта программа завершается никогда. Он может найти решение тут и там, но он никогда не остановится, если его попросят найти их все.

Этот крошечный фрагмент называется failure-slice и если он не завершается, то завершается и вся ваша программа! То есть вообще нет необходимости читать ваше определение hates/21.

Если вы хотите освоить выполнение Пролога, вам необходимо освоить понятие среза сбоя. Ибо опытные программисты делают это более или менее интуитивно. Таким образом, они не читают всю программу, а просто просматривают соответствующие части. Прелесть Пролога в том, что между таким фрагментом и программой в целом существует действительно причинно-следственная связь.

Чтобы решить эту проблему, вам нужно что-то изменить в той части, которая была выделена срезом отказа. Вот одно из таких возможных изменений:

jealous(A,B) :- hates(A,B).
jealous(A, B) :- hates(A, C), jealous(C,B).

Но как только у вас есть циклы в hates/2, это больше не работает. Затем рассмотрите closure/3:

jealous(A, B) :-
   closure(hates, A, B).

Другой способ — использовать таблицы. Но имейте в виду, табличное решение решает эту проблему, но больше не будет работать в контексте ограничений (с которыми вы рано или поздно столкнетесь).

1) при условии, что у вас чисто монотонная программа.

person false    schedule 08.04.2021

arrow_upward
4
arrow_downward

Если вы используете SWI-Prolog или XSB Prolog, вы можете попробовать добавить это:

:- table jealous/2.

и это должно работать (я не пробовал, но вот похожий пример: https://www.swi-prolog.org/pldoc/man?section=table-non-termination).

Ваша проблема заключается в стратегии выполнения Prolog по умолчанию, которая сначала идет в глубину слева направо. Вы можете избежать этого, изменив последнее предложение на:

jealous(A, B) :- hates(A, C), jealous(C,B).

(похожих примеров много в учебниках по Прологу)

person Peter Ludemann    schedule 08.04.2021