У Клоксин - ПРОГРАММИРОВАНИЕ НА ЯЗЫКЕ ПРОЛОГ
Подводя итог, можно представить конъюнкцию целей в вопросе как список целей, упорядоченных слева направо и разделенных запятыми. Каждая цель может иметь соседа слева и соседа справа. Ясно, что цели, занимающие в списке крайнее левое и крайнее правое положения, не будут иметь соседей соответственно слева и справа. Обрабатывая конъюнкцию целей, Пролог пытается по очереди согласовать с базой данных каждую цель, просматривая вопрос слева направо. Если обнаруживается факт, сопоставимый с целью, то Пролог оставляет в этом месте базы данных маркер, связанный с целью. Это можно наглядно представить с помощью стрелки, ведущей от цели к некоторому месту в базе данных, где находится соответствующий факт. Кроме того, некоторые ранее неконкретизированные переменные могут при этом быть конкретизированы, как это имело место выше на шаге 1. Если некоторая переменная конкретизируется, то конкретизируются и все вхождения этой переменной в вопрос. Далее Пролог пытается удовлетворить правого соседа этой цели, начиная поиск с вершины базы данных (наполнение базы данных в Прологе осуществляется сверху вниз, так что вершина – это факт, внесенный в базу данных первым). Как и любая другая цель, для которой найдено соответствие, она оставляет после себя в базе данных маркер (проводит еще одну стрелку от этой новой цели к соответствующему ей факту), на случай если впоследствии возникнет необходимость найти для цели другое соответствие. Каждый раз, когда целевое утверждение не выполняется (нельзя найти сопоставимого факта), Пролог возвращается и пытается найти новое соответствие для соседа слева данной цели, начиная поиск с места, отмеченного соответствующим ему маркером. Кроме того, Пролог должен сначала расконкретизировать все переменные, которые были конкретизированы при достижении этой цели. Другими словами, когда Пролог ищет новое соответствие для цели, он должен «уничтожить» старое значение этих переменных. Если для цели, к рассмотрению которой был возврат справа, нельзя найти новое соответствие, то Пролог перейдет еще левее, постепенно приближаясь к левой границе конъюнкции. Если не удается найти новое соответствие для крайней слева цели, которая уже не имеет соседа слева, то в этом случае считается несогласуемой с базой данных вся конъюнкция целей в вопросе к Прологу. Такое поведение, когда Пролог неоднократно пытается согласовать (и вновь согласовать) цели, входящие в вопрос-конъюнкцию, называется поиском с возвратом (бектрекингом). В следующей главе дается краткое описание механизма возврата, а в гл. 4 проводится более полное и детальное рассмотрение этого процесса.
Разбирая примеры, полезно записывать под каждой переменной, входящей в целевое утверждение, значение (имя объекта), которое было присвоено этой переменной при установлении согласованности цели с базой данных. Следует также изображать стрелки, идущие от цели к соответствующему ей маркеру в базе данных. На рис. 1.1 приведен пример такой иллюстрации на бумаге работы Пролога, состоящий из четырех «мгновенных снимков» процесса поиска в приведенном выше примере. На каждом снимке показаны полная база данных и вопрос, а также пронумерованная последовательность комментариев. На рисунке цели, для которых найдены соответствия, заключены в прямоугольник.
На протяжении всей книги мы постараемся показать, где в рассматриваемых примерах имеет место возврат и какую роль он играет в решении задачи. Значение механизма возврата при поиске настолько велико, что ему полностью посвящена гл. 4.
Упражнение 1.1. Продолжить разбор рассмотренного выше примера с помощью карандаша и бумаги, предположив, что вы ввели точку с запятой;, инициируя возврат для того, чтобы определить, существует ли еще что-нибудь, что нравится одновременно Джону и Мэри.
Рис. 1.1.
1.5. Правила
Предположим, мы хотим сформулировать утверждение, что Джону нравятся все люди. Один из способов сделать это заключается в записи для каждого человека, упоминаемого в базе данных, отдельного факта:
нравится(джон,альфред).
нравится(джон,бертран).
нравится(джон,чарлз).
нравится(джон,дейвид).
* * *
Это было бы очень утомительным, особенно если в нашей программе на Прологе упоминается несколько сот человек. Другой способ выразить факт, что Джону нравятся все люди, - это сказать Джону нравится любой объект при условии, что этот объект является человеком. Здесь этот факт представлен в форме правила для определения того, что нравится Джону, а не прямого перечисления всех людей, которые ему нравятся. В ситуации, когда Джону мог бы нравиться любой человек, представление утверждения в виде правила является значительно более компактным, чем список фактов.
В Прологе правила используются в том случае, когда необходимо сказать, что некоторый факт зависит от группы других фактов. В естественном языке для выражения правила мы можем использовать слово если. Например:
• Я пользуюсь зонтом, если идет дождь.
• Джон покупает вино, если оно дешевле, чем пиво.
Правила используются также для выражения определений, например:
X является птицей, если:
X является живым существом и X имеет перья.
или
X является сестрой Y, если:
X является женщино и X и Y имеют одних и тех же родителей.
В последних примерах мы использовали переменные X и Y. Важно помнить, что каждое вхождение переменной в правило обозначает один и тот же объект. Иначе мы разрушили бы саму суть определения. Например, используя приведенное выше определение птицы, мы не смогли бы показать, что Фред является птицей на основании того, что Фидо – это живое существо, а Мэри имеет перья. Этот принцип согласованной интерпретации переменных справедлив также и для правил в Прологе.
Правило – это некоторое общее утверждение об объектах и об отношениях между ними. Например, мы можем сказать, что Фред является птицей, если Фред является живым существом и Фред имеет перья, мы можем также сказать, что Бертрам является птицей, если Бертрам является живым существом и Бертрам имеет перья. Таким образом, мы допускаем, что при каждом новом использовании правила переменная обозначает новый, отличный от прежнего объект. Конечно, в рамках конкретного использования правила переменные интерпретируются согласованно, как на это указывалось выше.
Рассмотрим несколько примеров, начав с правила, содержащего одну переменную и конъюнкцию:
Джону нравится любой, кому нравится вино, или,
другими словами,
Джону нравится что-то, если чему-то нравится вино,
или, используя переменные,
Джону нравится X, если X нравится вино.
В Прологе правило состоит из заголовка и тела правила. Заголовок и тело соединяются с помощью символа :-, который состоит из двоеточия : и тире -. Символ ':-' читается если.
Предыдущий пример записывается на Прологе следующим образом:
нравится(джон,X):- нравится(Х,вино).
Отметим, что правила также заканчиваются точкой. Заголовком этого правила является нравится(джон,Х). Заголовок правила описывает факт, для определения которого предназначено это правило. Тело правила, в данном случае нравится(Х,вино), описывает конъюнкцию целей, которые должны быть последовательно согласованы с базой данных, для того чтобы заголовок правила был истинным. Например, мы можем сделать Джона более разборчивым в выборе тех, кто ему нравится, просто добавив к телу правила еще несколько целевых утверждений, разделив их запятыми:
нравится(джон,X):- нравится(Х,вино), нравится(X,пища).
или, другими словами, Джону нравится любой, кому нравятся вино и пища. Или, предположим, что Джону нравится любая женщина, которой нравится вино:
нравится(джон,Х):- женщина(Х), нравится(Х,вино).
Всякий раз, когда мы имеем дело с правилом в Прологе, необходимо отмечать все вхождения переменных. В последнем примере переменная X использована три раза. Всякий раз, как переменная X конкретизируется некоторым объектом (ей присваивается значение), все вхождения X в пределах области действия этой переменной становятся конкретизированными. При каждом употреблении правила область действия переменной X – это все правило, начиная с заголовка и до точки '.' в конце этого правила. Так, если в приведенном выше правиле переменная X оказалась конкретизированной, принимая значение мэри, то Пролог попытается согласовать с базой данных целевые утверждения женщина(мэри) и нравится(мэри,вино).
