Программирование на языке пролог
Шрифт:
Предположим, что в ответ на первое найденное Прологом соответствие ( Х=цветы) мы предлагаем системе продолжить поиск (введя
Что произойдет, если, имея те же факты, что и ранее, мы зададим вопрос:
?- нравится(Х,мэри).
В этом вопросе спрашивается: «Существует ли объект, которому нравится Мэри?».Теперь вы сами можете понять, что в примере объектами, которые нравятся Мэри, являются джони поль. Опять, если бы мы хотели увидеть все варианты, мы должны были бы вводить; после каждого ответа, выдаваемого Прологом:
?- нравится(Х, мэри). наш вопрос
Х=джон; первый ответ. Мы вводим
Х=поль; второй ответ. Вновь вводим
нет больше ответов нет.
1.4. Конъюнкции
Предположим, что мы хотим получать ответы на вопросы о более сложных отношениях, таких как: «Нравятся ли Джон и Мэри друг другу?».Один из способов сделать это – узнать сначала, нравится ли Джону Мэри, и если Пролог ответит да, то спросить, нравится ли Мэри Джон. Таким образом, эта задача состоит из двух «целевых утверждений» (или целей), которые Пролог должен согласовать. Ввиду того что подобная комбинация часто используется при программировании на Прологе, для нее имеется специальное обозначение. Предположим, мы имеем следующую базу данных:
нравится(мэри,пища).
нравится(мэри,вино).
нравится(джон,вино).
нравится(джон,мэри).
Мы хотим узнать, нравятся ли Джон и Мэри друг другу. Для этого мы спрашиваем: «Нравится ли Джон Мэрии нравится ли Мэри Джон?».Связка ивыражает тот факт, что нас интересует конъюнкция двух указанных целей – мы хотим последовательно согласовать с базой данных обе цели. Мы выражаем это в вопросе, записывая обе цели через запятую:
?- нравится(джон,мэри),нравится(мэри,джон).
Запятая читается как «и» и используется для разделения произвольного числа различных целей, которые должны быть согласованы с базой данных для того, чтобы ответить положительно на вопрос. Если задана последовательность целей (разделенных запятыми), то Пролог пытается согласовать каждую цель по очереди, просматривая базу данных в поисках сопоставимых фактов. Чтобы согласовать с базой данных последовательность целей, необходимо согласовать все отдельные цели. Что должен напечатать Пролог в ответ на приведенный выше вопрос? Ответ будет нет. Действительно, так как имеет место факт, что Джону нравится Мэри, то первая цель согласуется с базой данных. Однако вторая цель не согласуется с базой данных, так как в ней отсутствует факт нравится(мэри,джон). Учитывая, что мы хотели знать, нравятся ли они обадруг другу, окончательным ответом на вопрос является нет.
Сочетая возможности конъюнкции и использования переменных, можно строить достаточно содержательные вопросы. Теперь, когда мы знаем, что нельзя выяснить, нравятся ли Джон и Мэри друг другу, мы спрашиваем: «Существует ли что-нибудь такое, что нравится обоим– Джону и Мэри?».Этот вопрос также содержит две цели:
• Существует ли такой объект X, который нравится Мэри.
• Нравится ли Джону найденное значение X.
В Прологе два указанных целевых утверждения следует объединить, используя конъюнкцию, как показано ниже:
?- нравится(мэри,Х), нравится(джон,X).
Пролог отвечает на вопрос, пытаясь подобрать соответствие для первой цели. Если в базе данных есть факт, соответствующий целевому высказыванию, то Пролог отметит найденное место и попытается согласовать вторую цель. Если и она достигнута, то Пролог также отмечает в базе данных соответствующее ей место, и таким образом находится решение, удовлетворяющее обеим целям.
Важно помнить, что каждая цель имеет свой собственный маркер для указания места в базе данных, гденайдены соответствующие им факты. Если, однако, вторая цель не согласуется с базой данных, то Пролог попытается найти новое соответствие для предыдущей цели (в данном случае для первой цели). Помните, что Пролог полностью просматривает базу данных для каждой из целей. Если случится так, что некоторый факт в базе данных можно сопоставить с заданной целью, то Пролог отметит это место в базе данных на случай, если впоследствии он будет вынужден снова искать для этой цели другое соответствие. И когда возникнет необходимость найти для цели другое соответствие, Пролог начнет поиск не с начала базы данных, а с места, отмеченного маркером, соответствующим этой цели. Наш предыдущий вопрос: «Существует ли что-нибудь, что нравится и Мэри и Джону?»иллюстрирует пример такого поиска с возвратом («бектрекинга»). Пролог выполняет следующую последовательность действий:
1. База данных просматривается в попытке согласовать первую цель. Так как второй аргумент (X)неконкретизирован, то ему может соответствовать все что угодно. Первый факт, сопоставимый с целью, в приведенной выше базе данных есть нравится(мэри, пища).С этого момента каждомупоявлению переменной Xв вопросе соответствует значение пища.Пролог отмечает в базе данных то место, где был обнаружен соответствующий факт, так что при необходимости найти другой способ согласования цели с фактами он может вернуться в эту точку и продолжить поиск. Более того, следует помнить, что переменная Xбыла конкретизирована в этой точке и Пролог может «забыть» найденное для Xзначение в случае необходимости найти новое соответствие в фактах для рассматриваемой цели.
2. Теперь в базе данных ищется факт нравится(джон,пища),так как следующая цель – это нравится (джон,X), а переменная Xтеперь имеет значение пища.Как можно видеть, база данных такого факта не содержит, так что эта цель с базой данных не согласуется. В этой ситуации мы должны попытаться найти новое соответствие в фактах для предыдущей цели. Поэтому Пролог предпринимает попытку найти новое соответствие для нравится(мэри,X), при этом поиск в базе данных начинается с отмеченного маркером места. Но сначала необходимо «расконкретизировать» переменную Xтак, чтобы Xопять могла быть сопоставлена с любым объектом.