Parent) torn, pat)

parent! torn, Y) predecessor^ Y, pat)

Рис. 1.8. Первый этап выполнения Рис. 1.9. Продолжение схемы выполнения программы. программы; цель, показанная ввер- показанной на рис. 1.8 ху, является истинной, если истинно цгль. пакошннаяяиизу

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

(bob, pat)

Для достижения данной цели снова используется правило prl. Следует отметить, что это (второе) применение того же правила не имеет ничего общего с его предыдущим применением. Поэтому система Prolog использует в правиле новый набор переменных при каждом его применении. Чтобы продемонстрировать это, переименуем переменные в правиле prl для этого этапа применения правила следующим образом:

predecessor! X¹, Z'):-

parent; X', Z'),

Голова данного правила должна соответствовать текущей цели predecessor [ bob, pat], поэтому:

х- = bob, z ■ = pat

Текущая цель заменяется следующей: parent (boh, pat)

Данная цель достигается сразу же, поскольку она представлена в программе в виде факта. На этом завершается формирование схемы выполнения, которая представлена в графическом виде на рис. 1.10.

Графическая схема выполнения программы (см. рис. 1.10) имеет форму дерева. Узлы дерева соответствуют целям или спискам целей, которые должны быть достигнуты. Дуги между узлами соответствуют этапам применения (альтернативных) предложений программы, на которых цели одного узла преобразуются в цели другого узла. Верхняя цель достигается после того, как будет найден путь от корневого узла (верхней цели) к лист-узлу, обозначенному как "yes". Лист носит метку "yes", если он представляет собой простой факт. Процесс выполнения программ Prolog состоит в поиске путей, оканчивающихся такими простыми фактами. В ходе поиска система Prolog может войти в одну из ветвей, не позволяющих достичь успеха. При обнаружении того, что ветвь не позволяет достичь цели, система Prolog автоматически возвращается к предыдущему узлу и пытается использовать в этом узле альтернативное предложение.

Глава 1. Введение в Prolog

predecessor! torn, pat)

no правилу ргТ

по правилу рг2

parent! torn, pat)

parent) torn, Y) predecessor! Y, pat)

Y = bob