предок( X, Z) :-
родитель( X, Y),
предок( Y, Z).
Как и раньше, переменным X и Z приписываются значения:
X = том, Z = пат
В этот момент переменной Y еще не приписано никакого значения. Верхняя цель предок( том, пат) заменяется двумя целями:
родитель( том, Y),
предок( Y, пат)
Этот шаг вычислений показан на рис. 1.10, который представляет развитие ситуации, изображенной на рис. 1.9.
Рис. 1.10. Продолжение процесса вычислений, показанного на рис. 1.9.
Имея теперь перед собой две цели, система пытается достичь их в том порядке, каком они записаны. Достичь первой из них легко, поскольку она соответствует факту из программы. Процесс установления соответствия — сопоставление (унификация) вызывает приписывание переменной Y значения боб. Тем самым достигается первая цель, а оставшаяся превращается в
предок( боб, пат)
Для достижения этой цели вновь применяется правило пр1. Заметим, — что это (второе) применение правила никак не связано с его первым применением. Поэтому система использует новое множество переменных правила всякий раз, как оно применяется. Чтобы указать это, мы переименуем переменные правила пр1 для нового его применения следующим образом:
предок( X', Z') :-
родитель( X', Z').
Голова этого правила должна соответствовать нашей текущей цели предок( боб, пат). Поэтому
X' = боб, Z' = пат
Текущая цель заменяется на
родитель( боб, пат)
Такая цель немедленно достигается, поскольку встречается в программе в качестве факта. Этот шаг завершает вычисление, что графически показано на рис. 1.11.
Рис. 1.11. Все шаги достижения цели предок( том, пат). Правая ветвь демонстрирует, что цель достижима.
Графическое представление шагов вычисления на рис. 1.11 имеет форму дерева. Вершины дерева соответствуют целям или спискам целей, которые требуется достичь. Дуги между вершинами соответствуют применению (альтернативных) предложений программы, которые преобразуют цель, соответствующую одной вершине, в цель, соответствующую другой вершине. Корневая (верхняя) цель достигается тогда, когда находится путь от корня дерева (верхней вершины) к его листу, помеченному меткой "да". Лист помечается меткой "да", если он представляет собой простой факт. Выполнение пролог-программы состоит в поиске таких путей. В процессе такого поиска система может входить и в ветви, приводящие к неуспеху. В тот момент, когда она обнаруживает, что ветвь не приводит к успеху, происходит автоматический возврат к предыдущей вершине, и далее следует попытка применить к ней альтернативное предложение.
Упражнение
1.7. Постарайтесь понять, как пролог-система, используя программу, приведенную на рис. 1.8, выводит ответы на указанные ниже вопросы. Попытайтесь нарисовать соответствующие диаграммы вывода по типу тех, что изображены на рис.1.9–1.11. Будут ли встречаться возвраты при выводе ответов на какие-либо из этих вопросов?
(a) ?- родитель( пам, боб).
(b) ?- мать( пам, боб).
(с) ?- родительродителя( пам, энн).
(d) ?- родительродителя( боб, джим).
1.5. Декларативный и процедурный смысл программ
До сих пор во всех наших примерах всегда можно было понять результаты работы программы, точно не зная, как система в действительности их нашла. Поэтому стоит различать два уровня смысла программы на Прологе, а именно:
• декларативный смысл и
• процедурный смысл.
Декларативный смысл касается только отношений, определенных в программе. Таким образом, декларативный смысл определяет, что должно быть результатом работы программы. С другой стороны, процедурный смысл определяет еще и как этот результат был получен, т.е. как отношения реально обрабатываются пролог-системой.
Способность пролог-системы прорабатывать многие процедурные детали самостоятельно считается одним из специфических преимуществ Пролога. Это свойство побуждает программиста рассматривать декларативный смысл программы относительно независимо от ее процедурного смысла. Поскольку результаты работы программы в принципе определяются ее декларативным смыслом, последнего (Опять же в принципе) достаточно для написания программ. Этот факт имеет практическое значение, поскольку декларативные аспекты программы являются, обычно, более легкими для понимания, нежели процедурные детали. Чтобы извлечь из этого обстоятельства наибольшую пользу, программисту следует сосредоточиться главным образом на декларативном смысле и по возможности не отвлекаться на детали процесса вычислений. Последние следует в возможно большей мере предоставить самой пролог-системе.
Такой декларативный подход и в самом деле часто делает программирование на Прологе более легким, чем на таких типичных процедурно-ориентированных языках, как Паскаль. К сожалению, однако, декларативного подхода не всегда оказывается, достаточно. Далее станет ясно, что, особенно в больших программах, программист не может полностью игнорировать процедурные аспекты по соображениям эффективности вычислений. Тем не менее следует поощрять декларативный стиль мышления при написании пролог-программ, а процедурные аспекты игнорировать в тех пределах, которые устанавливаются практическими ограничениями.
Резюме
• Программирование на Прологе состоит в определении отношений и в постановке вопросов, касающихся этих отношений.
• Программа состоит из предложений. Предложения бывают трех типов: факты, правила и вопросы.
• Отношение может определяться фактами, перечисляющими n-ки объектов, для которых это отношение выполняется, или же оно может определяться правилами.
• Процедура — это множество предложений об одном и том же отношении.
• Вопросы напоминают запросы к некоторой базе данных. Ответ системы на вопрос представляет собой множество объектов, которые удовлетворяют запросу.
• Процесс, в результате которого пролог-система устанавливает, удовлетворяет ли объект запросу, часто довольно сложен и включает в себя логический вывод, исследование различных вариантов и, возможно, возвраты. Все это делается автоматически самой пролог-системой и по большей части скрыто от пользователя.
• Различают два типа смысла пролог-программ: декларативный и процедурный. Декларативный подход предпочтительнее с точки зрения программирования. Тем не менее, программист должен часто учитывать также и процедурные детали.
• В данной главе были введены следующие понятия:
предложение, факт, правило, вопрос
голова предложения, тело предложения
рекурсивное правило
рекурсивное определение
процедура
атом, переменная
конкретизация переменной
цель
цель достижима, цель успешна
цель недостижима,
цель имеет неуспех, цель терпит неудачу
возврат
декларативный смысл, процедурный смысл.
Литература
Различные реализации Пролога используют разные синтаксические соглашения. В данной книге мы применяем так называемый Эдинбургский синтаксис (его называют также синтаксисом DEC-10, поскольку он принят в известной реализации Пролога для машины DEC-10; см. Pereira и др. 1978), он используется во многих популярных пролог-системах, таких как Quintus Prolog, Poplog, CProlog, Arity/Prolog, Prolog-2 и т.д.
Bowen D. L. (1981). DECsystem-10 Prolog User's Manual. University of Edinburgh: Department of Artificial Intelligence.
Mellish С. and Hardy S. (1984). Integrating Prolog in the POPLOG environment. Implementations of Prolog (J. A. Campbell, ed.). Ellis Horwood.
Pereira F. (1982). C-Prolog User's Manual. University of Edinburgh: Department of Computer-Aided Architectural Design.
Pereira L. M., Pereira F., Warren D. H. D. (1978). User's Guide to DECsystem-10 Prolog. University of Edinburgh: Department of Artificial Intelligence.
Quintus Prolog User's Guide and Reference Manual. Palo Alto: Quintus Computer System Inc. (1985).
The Arity/Prolog Programming Language. Concord, Massachusetts: Arity Corporation (1986).
Глава 2
Синтаксис и семантика Пролог-программ
В данной главе дается систематическое изложение синтаксиса и семантики основных понятий Пролога, а также вводятся структурные объекты данных. Рассматриваются следующие темы:
• простые объекты данных (атомы, числа, переменные)
• структурные объекты
• сопоставление как основная операция над объектами
• декларативная (или непроцедурная) семантика программ
