"ПРОГРАММИРОВАНИЕ НА ЯЗЫКЕ ПРОЛОГ" - читать интересную книгу автора (Клоксин У, Меллиш К)

1.4. Конъюнкции

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

нравится(мэри,пища).

нравится(мэри,вино).

нравится(джон,вино).

нравится(джон,мэри).

Мы хотим узнать, нравятся ли Джон и Мэри друг другу. Для этого мы спрашиваем: «Нравится ли Джон Мэри и нравится ли Мэри Джон?». Связка и выражает тот факт, что нас интересует конъюнкция двух указанных целей – мы хотим последовательно согласовать с базой данных обе цели. Мы выражаем это в вопросе, записывая обе цели через запятую:

?- нравится(джон,мэри),нравится(мэри,джон).

Запятая читается как «и» и используется для разделения произвольного числа различных целей, которые должны быть согласованы с базой данных для того, чтобы ответить положительно на вопрос. Если задана последовательность целей (разделенных запятыми), то Пролог пытается согласовать каждую цель по очереди, просматривая базу данных в поисках сопоставимых фактов. Чтобы согласовать с базой данных последовательность целей, необходимо согласовать все отдельные цели. Что должен напечатать Пролог в ответ на приведенный выше вопрос? Ответ будет нет. Действительно, так как имеет место факт, что Джону нравится Мэри, то первая цель согласуется с базой данных. Однако вторая цель не согласуется с базой данных, так как в ней отсутствует факт нравится(мэри,джон). Учитывая, что мы хотели знать, нравятся ли они оба друг другу, окончательным ответом на вопрос является нет.

Сочетая возможности конъюнкции и использования переменных, можно строить достаточно содержательные вопросы. Теперь, когда мы знаем, что нельзя выяснить, нравятся ли Джон и Мэри друг другу, мы спрашиваем: «Существует ли что-нибудь такое, что нравится обоим - Джону и Мэри?». Этот вопрос также содержит две цели:

• Существует ли такой объект X, который нравится Мэри.

• Нравится ли Джону найденное значение X.

В Прологе два указанных целевых утверждения следует объединить, используя конъюнкцию, как показано ниже:

?- нравится(мэри,Х), нравится(джон,X).

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

Важно помнить, что каждая цель имеет свой собственный маркер для указания места в базе данных, где найдены соответствующие им факты. Если, однако, вторая цель не согласуется с базой данных, то Пролог попытается найти новое соответствие для предыдущей цели (в данном случае для первой цели). Помните, что Пролог полностью просматривает базу данных для каждой из целей. Если случится так, что некоторый факт в базе данных можно сопоставить с заданной целью, то Пролог отметит это место в базе данных на случай, если впоследствии он будет вынужден снова искать для этой цели другое соответствие. И когда возникнет необходимость найти для цели другое соответствие, Пролог начнет поиск не с начала базы данных, а с места, отмеченного маркером, соответствующим этой цели. Наш предыдущий вопрос: «Существует ли что-нибудь, что нравится и Мэри и Джону?» иллюстрирует пример такого поиска с возвратом («бектрекинга»). Пролог выполняет следующую последовательность действий:

1. База данных просматривается в попытке согласовать первую цель. Так как второй аргумент (X) неконкретизирован, то ему может соответствовать все что угодно. Первый факт, сопоставимый с целью, в приведенной выше базе данных есть нравится(мэри, пища). С этого момента каждому появлению переменной X в вопросе соответствует значение пища. Пролог отмечает в базе данных то место, где был обнаружен соответствующий факт, так что при необходимости найти другой способ согласования цели с фактами он может вернуться в эту точку и продолжить поиск. Более того, следует помнить, что переменная X была конкретизирована в этой точке и Пролог может «забыть» найденное для X значение в случае необходимости найти новое соответствие в фактах для рассматриваемой цели.

2. Теперь в базе данных ищется факт нравится(джон,пища), так как следующая цель – это нравится (джон,X), а переменная X теперь имеет значение пища. Как можно видеть, база данных такого факта не содержит, так что эта цель с базой данных не согласуется. В этой ситуации мы должны попытаться найти новое соответствие в фактах для предыдущей цели. Поэтому Пролог предпринимает попытку найти новое соответствие для нравится(мэри,X), при этом поиск в базе данных начинается с отмеченного маркером места. Но сначала необходимо «расконкретизировать» переменную X так, чтобы X опять могла быть сопоставлена с любым объектом.

3. Отмеченным маркером местом является факт нравится(мэри, пища). Поэтому Пролог начинает поиск со следующего непосредственно за ним факта. Так как мы еще не достигли конца базы данных, то мы не исчерпали всех объектов, которые нравятся Мэри. Следующим сопоставимым фактом является нравится(мэри, вино). Теперь переменная X принимает значение вино, и Пролог отмечает это место на случай, если потребуется найти новое соответствие для того, что нравится Мэри.

4. Как и ранее, Пролог пытается теперь согласовать с фактами вторую цель в вопросе, осуществляя поиск в базе данных факта нравится(джон,вино). Пролог не пытается при этом использовать механизм поиска нового соответствия для этой цели. Это новая цель, которую он выбирает, продвигаясь, как и раньше, слева направо по списку целей в исходном вопросе, поэтому он должен начать поиск с начала базы данных. Когда после недолгого поиска будет найден сопоставимый факт, Пролог выдает надлежащее сообщение. Как только вторая цель согласована, Пролог отмечает соответствующий ей факт в базе данных на случай, если вдруг потребуется найти для нее новое соответствие. Для каждой цели, которую Пролог пытается согласовать, в базе данных имеется свой маркер, указывающий факт, поставленный в соответствие этой цели.

5. Теперь обе цели согласованы. Переменная X обозначает имя вино. Маркер первого целевого утверждения отмечает в базе данных факт нравится(мэри,вино), а маркер второго целевого утверждения отмечает факт нравится(джон,вино).

Как и в случае других запросов, как только Пролог находит ответ, он прекращает поиск и ожидает дальнейших указаний.

Если ввести ;, то Пролог продолжит поиск объектов, которые нравятся одновременно Джону и Мэри. Теперь мы знаем, что все последующие попытки поиска новых ответов на вопрос с двумя целями начинаются с мест, отмеченных маркерами, которые оставили эти цели на предыдущем этапе.

Подводя итог, можно представить конъюнкцию целей в вопросе как список целей, упорядоченных слева направо и разделенных запятыми. Каждая цель может иметь соседа слева и соседа справа. Ясно, что цели, занимающие в списке крайнее левое и крайнее правое положения, не будут иметь соседей соответственно слева и справа. Обрабатывая конъюнкцию целей, Пролог пытается по очереди согласовать с базой данных каждую цель, просматривая вопрос слева направо. Если обнаруживается факт, сопоставимый с целью, то Пролог оставляет в этом месте базы данных маркер, связанный с целью. Это можно наглядно представить с помощью стрелки, ведущей от цели к некоторому месту в базе данных, где находится соответствующий факт. Кроме того, некоторые ранее неконкретизированные переменные могут при этом быть конкретизированы, как это имело место выше на шаге 1. Если некоторая переменная конкретизируется, то конкретизируются и все вхождения этой переменной в вопрос. Далее Пролог пытается удовлетворить правого соседа этой цели, начиная поиск с вершины базы данных (наполнение базы данных в Прологе осуществляется сверху вниз, так что вершина – это факт, внесенный в базу данных первым). Как и любая другая цель, для которой найдено соответствие, она оставляет после себя в базе данных маркер (проводит еще одну стрелку от этой новой цели к соответствующему ей факту), на случай если впоследствии возникнет необходимость найти для цели другое соответствие. Каждый раз, когда целевое утверждение не выполняется (нельзя найти сопоставимого факта), Пролог возвращается и пытается найти новое соответствие для соседа слева данной цели, начиная поиск с места, отмеченного соответствующим ему маркером. Кроме того, Пролог должен сначала расконкретизировать все переменные, которые были конкретизированы при достижении этой цели. Другими словами, когда Пролог ищет новое соответствие для цели, он должен «уничтожить» старое значение этих переменных. Если для цели, к рассмотрению которой был возврат справа, нельзя найти новое соответствие, то Пролог перейдет еще левее, постепенно приближаясь к левой границе конъюнкции. Если не удается найти новое соответствие для крайней слева цели, которая уже не имеет соседа слева, то в этом случае считается несогласуемой с базой данных вся конъюнкция целей в вопросе к Прологу. Такое поведение, когда Пролог неоднократно пытается согласовать (и вновь согласовать) цели, входящие в вопрос-конъюнкцию, называется поиском с возвратом (бектрекингом). В следующей главе дается краткое описание механизма возврата, а в гл. 4 проводится более полное и детальное рассмотрение этого процесса.

Разбирая примеры, полезно записывать под каждой переменной, входящей в целевое утверждение, значение (имя объекта), которое было присвоено этой переменной при установлении согласованности цели с базой данных. Следует также изображать стрелки, идущие от цели к соответствующему ей маркеру в базе данных. На рис. 1.1 приведен пример такой иллюстрации на бумаге работы Пролога, состоящий из четырех «мгновенных снимков» процесса поиска в приведенном выше примере. На каждом снимке показаны полная база данных и вопрос, а также пронумерованная последовательность комментариев. На рисунке цели, для которых найдены соответствия, заключены в прямоугольник.

На протяжении всей книги мы постараемся показать, где в рассматриваемых примерах имеет место возврат и какую роль он играет в решении задачи. Значение механизма возврата при поиске настолько велико, что ему полностью посвящена гл. 4.

Упражнение 1.1. Продолжить разбор рассмотренного выше примера с помощью карандаша и бумаги, предположив, что вы ввели точку с запятой;, инициируя возврат для того, чтобы определить, существует ли еще что-нибудь, что нравится одновременно Джону и Мэри.

Рис. 1.1.