АЛГОРИТМ ВЫПОЛНЕНИЯ ПРОГРАММ НА ПРОЛОГЕ
Факты и правила программы на Прологе являются описанием отношений и связей между объектами некоторой предметной области, т.е. записью условия некой логической задачи, которую предстоит решить. Описанные отношения и связи рассматриваются статически. Такой подход к программе называется декларативным. Порядок следования фактов, правил и подцелей в правилах не влияет на декларативный смысл программы.
Вместе с тем, программу можно рассматривать с точки зрения последовательности сопоставлений, конкретизации переменных и резолютивных выводов, происходящих при ее выполнении. Такой подход называется процедурным. Процедурный смысл программы обязательно должен учитываться при программировании на Прологе. Так, факт можно рассматривать как полностью определенную процедуру, для выполнения которой больше ничего не нужно. Правило
А:-В1,В2,...,Вn.
можно рассматривать как определение процедуры А, утверждающее, что для ее выполнения надо определить Bl, B2, ... , Вn. Процедуры Bl, B2, ... , Вn должны выполняться в определенном порядке - слева направо. Если выполнение очередной процедуры завершается успешно, то происходит переход к следующей процедуре. Если же по какой-либо причине очередная процедура выполняется неуспешно, то происходит переход к следующему варианту описания этой процедуры, и порядок поиска такого варианта в Прологе задан - сверху вниз. Поиск подходящих для согласования фактов и правил в базе знаний происходит последовательно сверху-вниз, и если подходящих фактов не найдено - ответ отрицательный. Эта стратегия согласования называется «сверху-вниз» и «замкнутый мир».
Рассмотрим процесс выполнения программы более подробно на примере.
Программа 112
а : - b, с, d.
b : - е, f.
с. d. е. f.
? - а.
Выполнение программы начинается с применения метода резолюций к целевому и одному из предложений программы для получения их резольвенты. Подходящее предложение программы подбирается перебором сверху-вниз так, чтобы сопоставление его заголовка с целевым предложением было успешным.
В результате резолюции получается новое целевое предложение и метод резолюции применяется к нему и к другому предложению программы. Процесс продолжается до тех пор, пока не будут согласованы с фактами все возникшие при резолюции подцели, табл. 3.6.
Таблица 3.6
К процессу выполнения программы на Прологе
|
Номер шага резолюции |
Целевое предложение |
Исходное предложение |
Резольвента |
|
|
1 |
?-а. |
a:-b,c,d. |
?-b,c,d. |
|
|
2 |
?-b,c,d. |
b:-c,f. |
?-e,f,c,d. |
|
|
3 |
?-е,f,с,d |
e. ?-f,c,d. |
||
|
4 |
?-f,c,d. |
f. ?-c.d. |
||
|
5 |
?-c,d. |
c. ?-d. |
||
|
6 |
?-d. |
d. Пустая |
Программа 113
любит(юрий,музыку).
любит(сергей,спорт).
любит(А,книги):-читатель(А),любопытный(А).
любит(сергей,книги).
любит(сергей,кино).
читатель(юрий).
любопытный(юрий).
?- любит(X,музыку), любит(X,книги).
Двойной запрос в этой программе может быть представлен целевым деревом:
Вначале, просматривая программу сверху вниз. Пролог находит первое предложение, соответствующее первой подцели запроса:
Переменная Х конкретизируется значением «юрий». Начинается согласование 2-й подцели запроса с условием Х=юрий. 1-е и 2-е предложения программы не соответствуют подцели. В 3-ем предложении:
любит(А,книги):-читатель(А), любопытный(А).
аргумент А заголовка есть переменная, поэтому она может соответствовать X, т.е. получает значение А=юрин; вторые аргументы совпадают. Теперь тело правила образует новое множество целей для согласования. Получаем целевое дерево:
Затем Пролог будет искать факты, соответствующие новым подцелям. Последнее результирующее дерево:
Рассмотрим еще один пример.
Программа 114
любит(оля,чтение).
любит(света,бадминтон).
любит(для,бадминтон).
любит(лена,плавание).
любит(лена,чтение).
?- любит(X,чтение), любит(X,плавание).
Запрос означает: есть ли люди, которым нравится и чтение, и плавание? Сначала Пролог ищет факт, сопоставимый с первой частью вопроса: любит(Х, чтение). Подходит первый же факт программы
любит(оля,чтение).
и переменная Х связывается значением «оля». В то же время Пролог фиксирует в списке фактов указатель, показывающий состояние процедуры поиска. Далее Пролог пытается согласовать вторую часть запроса при условии Х = оля, т.е. ищет с самого начала программы факт «любит(оля, плавание)». Такого факта в программе нет, и поиск заканчивается неуспешно. Тогда Пролог возвращается к первои части запроса: любнт(Х,чтение) , «развязывает» переменную Х и продолжает поиск подходящих фактов, начиная с ранее установленного в списке фактов указателя Подходит факт «любит(лена,чтение)», переменная Х конкретизируется значением «лена», и далее вторая часть вопроса успешно согласуется с фактом «любит(лена, плавание)». Пролог выполнил в данном примере поиск с возвратом.
Графически процесс выполнения программы представляется в виде обхода бинарного дерева - дерева вывода, типа изображенного на рис.3.16. Вершины дерева обозначают вопросы, а ребра показывают возможные пути вывода, причем для каждого ребра характерны свои правила и унифицирующая подстановка значений переменных.
Рис.3.16. Дерево вывода программы на Прологе
Обход дерева начинается с движения от вершины (запроса) по самой левой ветви вниз до конца (abed), при этом запоминаются все точки ветвления (точки возврата). При достижении конца ветви решение будет либо найдено, либо нет. В обоих случаях Пролог продолжает дальнейший поиск решений. Выполняется возврат в последнюю точку ветвления с. При этом конкретные значения, присвоенные переменным при движении вниз на сегменте c-d. отменяются, и движение вниз продолжается по расположенной справа ветви с-е до конца дерева вниз. Затем произойдет возврат в предыдущую точку ветвления b и движение продолжится по ветви bfg, и так до тех пор, пока все дерево вывода не будет пройдено.
