К процессу выполнения программы на Прологе

При выполнении логического вывода, если необходимо, происходит конкретизация переменных. Рассмотрим пример.

Программа 113

любит(юрий,музыку).

любит(сергей,спорт).

любит(А,книги):-читатель(А),любопытный(А).

любит(сергей,книги).

любит(сергей,кино).

читатель(юрий).

любопытный(юрий).

?- любит(X,музыку), любит(X,книги).

Двойной запрос в этой программе может быть представлен целевым деревом:

Вначале, просматривая программу сверху вниз. Пролог находит первое предложение, соответствующее первой подцели запроса:

Переменная Х конкретизируется значением «юрий». Начинается согласование 2-й подцели запроса с условием Х=юрий. 1-е и 2-е предложения программы не соответствуют подцели. В 3-ем предложении:

любит(А,книги):-читатель(А), любопытный(А).

аргумент А заголовка есть переменная, поэтому она может соответствоватьX, т.е. получает значение А=юрин; вторые аргументы совпадают. Теперь тело правила образует новое множество целей для согласования. Получаем целевое дерево:

Затем Пролог будет искать факты, соответствующие новым подцелям. Последнее результирующее дерево:

Рассмотрим еще один пример.

Программа 114

любит(оля,чтение).

любит(света,бадминтон).

любит(для,бадминтон).

любит(лена,плавание).

любит(лена,чтение).

?- любит(X,чтение), любит(X,плавание).

Запрос означает: есть ли люди, которым нравится и чтение, и плавание? Сначала Пролог ищет факт, сопоставимый с первой частью вопроса: любит(Х, чтение). Подходит первый же факт программы

любит(оля,чтение).

и переменная Х связывается значением «оля». В то же время Пролог фиксирует в списке фактов указатель, показывающий состояние процедуры поиска. Далее Пролог пытается согласовать вторую часть запроса при условии Х = оля, т.е. ищет с самого начала программы факт «любит(оля, плавание)». Такого факта в программе нет, и поиск заканчивается неуспешно. Тогда Пролог возвращается к первои части запроса: любнт(Х,чтение) , «развязывает» переменную Х и продолжает поиск подходящих фактов, начиная с ранее установленного в списке фактов указателя Подходит факт «любит(лена,чтение)», переменная Х конкретизируется значением «лена», и далее вторая часть вопроса успешно согласуется с фактом «любит(лена, плавание)». Пролог выполнил в данном примере поиск с возвратом.

Графически процесс выполнения программы представляется в виде обхода бинарного дерева - дерева вывода, типа изображенного на рис.3.16. Вершины дерева обозначают вопросы, а ребра показывают возможные пути вывода, причем для каждого ребра характернысвои правила и унифицирующая подстановка значений переменных.

Рис.3.16. Дерево вывода программы на Прологе

Обход дерева начинается с движения от вершины (запроса) по самой левой ветви вниз до конца (abed), при этом запоминаются все точки ветвления (точки возврата). При достижении конца ветви решение будет либо найдено, либо нет. В обоих случаях Пролог продолжает дальнейший поиск решений. Выполняется возврат в последнюю точку ветвления с. При этом конкретные значения, присвоенные переменным при движении вниз на сегменте c-d. отменяются, и движение вниз продолжается по расположенной справа ветви с-е до конца дерева вниз. Затем произойдет возврат в предыдущую точку ветвления b и движение продолжится по ветви bfg, и так до тех пор, пока все дерево вывода не будет пройдено.