Parent) torn, pat)

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

no

Рис. 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