Не могу понять, почему пролог зацикливается

Из книги Братко " Программирование пролога для искусственного интеллекта" (4-е издание) у нас есть следующий код, который не работает:

anc4(X,Z):-
    anc4(X,Y),
    parent(Y,Z).
anc4(X,Z):-
    parent(X,Z).

В книге на странице 55, рисунок 2.15, показано, что parent(Y,Z) продолжает вызываться, пока стеку не хватит памяти.

Что я не понимаю, так это то, что пролог сначала делает рекурсивный вызов anc4(X,Y), а не родительский (Y,Z). Почему пролог не идет снова и снова на первую строку, anc4(X,Y), а точнее идет на вторую строчку?

Можете ли вы уточнить, почему линия parent(Y,Z) продолжает называться?

Спасибо.

Источник

2 ответа

Решение

Происхождение вашей "проблемы" (т. Е. Порядка целей) глубоко укоренено в основе языка.

Пролог основан на простой и эффективной стратегии обратного отслеживания, реализации разрешения SLD и оставленных рекурсивных предложений, таких как anc4/2вызвать бесконечную рекурсию. Действительно, оператор запятой (,)/2 обозначает

оценивать правильное выражение, только если левое выражение выполнено

Таким образом, порядок целей в предложении на самом деле является неотъемлемой частью программы.

Для вашего конкретного случая,

... , parent(Y,Z).

не может быть вызван, если

anc4(X,Y),

не держит

Аналогом порядка целей является порядок пунктов.

То есть вся программа имеет другую семантику после обмена предложениями:

anc4(X,Z):-
    parent(X,Z).
anc4(X,Z):-
    anc4(X,Y),
    parent(Y,Z).

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

Источник

Пролог не может обрабатывать левую рекурсию по умолчанию без механизма табуляции. Только некоторые системы Prolog поддерживают табулирование, и обычно вам нужно явно объявить, какие предикаты представлены в таблице.

Если вы используете, например, XSB, YAP или SWI-Prolog, попробуйте добавить следующую директиву поверх вашего исходного файла, содержащего определение для anc4/2 сказуемое:

:- table(anc4/2).

и повторите ваши запросы. Механизм табулирования определяет, когда запрос вызывает вариант (*), и приостанавливает выполнение этой ветви до тех пор, пока не будет найден ответ на запрос, и пробует альтернативную ветку (предоставленную в вашем случае вторым предложением). Если это произойдет, выполнение возобновляется с этим ответом.

(*) Вариант здесь означает, что два условия равны при переименовании переменной.

Источник
Другие вопросы по тегам