Интерес к Прологу впервые возник у меня под влиянием Дональда Мики. Я благодарен также Лоренсу Берду, Фернандо Перейра и Дэвиду Г. Уоррену, входившим в свое время в эдинбургскую группу разработчиков Пролога, за их советы по составлению программ и многочисленные дискуссии. Чрезвычайно полезными были замечания и предложения, высказанные Эндрью Макгеттриком и Патриком Уинстоном. Среди прочитавших рукопись книги и сделавших ценные замечания были также Игорь Кононенко, Таня Маярон, Игорь Мозетик, Тимоти Ниблетт и Фрэнк Зердин. Мне бы хотелось также поблагодарить Дебру Майсон-Этерингтон и Саймона Пламтри из издательства Эддисон-Уэсли за труд, вложенный в издание этой книги. И наконец, эта книга не могла бы появиться на свет без стимулирующего влияния творческой деятельности всего международного сообщества специалистов по логическому программированию.
Иван Братко Институт Тьюринга, Глазго Январь 1986
Часть 1
Язык Пролог
Глава 1
Общий обзор языка Пролог
В этой главе на примере конкретной программы рассматриваются основные механизмы Пролога. Несмотря на то, что материал излагается в основном неформально, здесь вводятся многие важные понятия.
1.1. Пример программы: родственные отношения
Пролог — это язык программирования, предназначенный для обработки символьной нечисловой информации. Особенно хорошо он приспособлен для решения задач, в которых фигурируют объекты и отношения между ними. На рис. 1.1 представлен пример — родственные отношения. Тот факт, что Том является родителем Боба, можно записать на Прологе так:
родитель( том, боб).
Здесь мы выбрали родитель в качестве имени отношения, том и боб — в качестве аргументов этого отношения. По причинам, которые станут понятны позднее, мы записываем такие имена, как том, начиная со строчной буквы. Все дерево родственных отношений рис. 1.1 описывается следующей пролог-программой:
родитель( пам, боб).
родитель( том, боб).
родитель( том, лиз).
родитель( боб, энн).
родитель( боб, пат).
родитель( пам, джим).
Рис. 1.1. Дерево родственных отношений.
Эта программа содержит шесть предложений. Каждое предложение объявляет об одном факте наличия отношения родитель.
После ввода такой программы в пролог-систему последней можно будет задавать вопросы, касающиеся отношения родитель. Например, является ли Боб родителем Пат? Этот вопрос можно передать пролог-системе, набрав на клавиатуре терминала:
?- родитель( боб, пат).
Найдя этот факт в программе, система ответит
yes (да)
Другим вопросом мог бы быть такой:
?- родитель( лиз, пат).
Система ответит
no (нет),
поскольку в программе ничего не говорится о том, является ли Лиз родителем Пат. Программа ответит "нет" и на вопрос
?- родитель( том, бен).
потому, что имя Бен в программе даже не упоминается.
Можно задавать и более интересные вопросы. Например:"Кто является родителем Лиз?"
?- родитель( X, лиз).
На этот раз система ответит не просто "да" или "нет". Она скажет нам, каким должно быть значение X (ранее неизвестное), чтобы вышеприведенное утверждение было истинным. Поэтому мы получим ответ:
X = том
Вопрос "Кто дети Боба?" можно передать пролог-системе в такой форме:
?- родитель( боб, X).
В этом случае возможно несколько ответов. Сначала система сообщит первое решение:
X = энн
Возможно, мы захотим увидеть и другие решения. О нашем желании мы можем сообщить системе (во многих реализациях для этого надо набрать точку с запятой), и она найдет другой ответ:
X = пат
Если мы потребуем дальнейших решений, система ответит "нет", поскольку все решения исчерпаны.
Нашей программе можно задавать и более общие вопросы: "Кто чей родитель?" Приведем другую формулировку этого вопроса:
Найти X и Y такие, что X — родитель Y.
На Прологе это записывается так:
?- родитель( X, Y).
Система будет по очереди находить все пары вида "родитель-ребенок". По мере того, как мы будем требовать от системы новых решений, они будут выводиться на экран одно за другим до тех пор, пока все они не будут найдены. Ответы выводятся следующим образом:
X = пам
Y = боб;
X = том
Y = боб;
X = том
Y = лиз;
...
Мы можем остановить поток решений, набрав, например, точку вместо точки с запятой (выбор конкретного символа зависит от реализации).
Нашей программе можно задавать и еще более сложные вопросы, скажем, кто является родителем родителя Джима? Поскольку в нашей программе прямо не сказано, что представляет собой отношение родительродителя, такой вопрос следует задавать в два этапа, как это показано на рис. 1.2.
(1) Кто родитель Джима? Предположим, что это некоторый Y.
(2) Кто родитель Y? Предположим, что это некоторый X.
Такой составной вопрос на Прологе записывается в виде последовательности двух простых вопросов:
?- родитель( Y, джим), родитель( X, Y).
Ответ будет:
X = боб
Y = пат
Рис. 1.2. Отношение родительродителя, выраженное через композицию двух отношений родитель.
Наш составной вопрос можно интерпретировать и так: "Найти X и Y, удовлетворяющие следующим двум требованиям":
родитель( Y, джим) и родитель( X, Y)
Если мы поменяем порядок этих двух требований, то логический смысл останется прежним:
родитель( X, Y) и родитель( Y, джим)
Этот вопрос можно задать нашей пролог-системе и в такой форме:
?- родитель( X, Y), родитель( Y, джим).
При этом результат будет тем же. Таким же образом можно спросить: "Кто внуки Тома?"
?- родитель( том, X), родитель( X, Y).
Система ответит так:
X = боб
Y = энн;
X = боб
Y = пат
Следующим вопросом мог бы быть такой: "Есть ли у Энн и Пат общий родитель?" Его тоже можно выразить в два этапа:
(1) Какой X является родителем Энн?
(2) Является ли (тот же) X родителем Пат?
Соответствующий запрос к пролог-системе будет тогда выглядеть так:
?- родитель( X, энн), родитель( X, пат).
Ответ:
X = боб
Наша программа-пример помогла проиллюстрировать некоторые важные моменты:
• На Прологе легко определить отношение, подобное отношению родитель, указав n-ку объектов, для которых это отношение выполняется.
• Пользователь может легко задавать пролог-системе вопросы, касающиеся отношений, определенных в программе.
• Пролог-программа состоит из предложений. Каждое предложение заканчивается точкой.
• Аргументы отношения могут быть (среди прочего): конкретными объектами, или константами (такими, как том и энн), или абстрактными объектами, такими, как X и Y. Объекты первого типа называются атомами. Объекты второго типа — переменными.
• Вопросы к системе состоят из одного или более целевых утверждений (или кратко целей). Последовательность целей, такая как
родитель( X, энн), родитель( X, пат)
означает конъюнкцию этих целевых утверждений:
X — родитель Энн и
X — родитель Пат.
Пролог-система рассматривает вопросы как цели, к достижению которых нужно стремиться.
• Ответ на вопрос может оказаться или положительным или отрицательным в зависимости от того, может ли быть соответствующая цель достигнута или нет. В случае положительного ответа мы говорим, что соответствующая цель достижима и успешна. В противном случае цель недостижима, имеет неуспех или терпит неудачу.
• Если на вопрос существует несколько ответов, пролог-система найдет столько из них, сколько пожелает пользователь.
Упражнения
1.1. Считая, что отношение родитель определено так же, как и раньше в данном разделе (см. рис. 1.1), найдите, какими будут ответы пролог-системы на следующие вопросы:
(a) ?- родитель( джим, X).
(b) ?- родитель( X, джим).
(c) ?- родитель( пам,X), родитель( X, пат).
