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

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

0 голосов
/ 07 сентября 2018

Из книги Братко, Программирование пролога для искусственного интеллекта (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 ]

0 голосов
/ 07 сентября 2018

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

Пролог основан на простой и эффективной стратегии обратного отслеживания, для реализации разрешения 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).

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

0 голосов
/ 07 сентября 2018

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

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

:- table(anc4/2).

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

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

...