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

Пролог применяется в тех случаях, когда необходимо использовать ЭВМ для решения задачи, которая может быть выражена в терминах объектов и отношений между ними. Например, когда мы говорим: «Джон имеет книгу», мы объявляем, что между одним объектом «Джон» и другим объектом «книга» имеет место отношение обладания. Более того, это отношение имеет определенный порядок: Джон имеет книгу, но книга не имеет Джона! Когда мы задаем вопрос: «Имеет ли Джон книгу?», то нас интересует правильность именно отношения.

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

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

Программирование на языке Пролог состоит из следующих этапов:

• объявления некоторых фактов об объектах и отношениях между ними,

• определения некоторых правил об объектах и отношениях между ними и

• формулировки вопросов об объектах и отношениях между ними.

Например, предположим, что мы записали на Прологе наше правило о сестрах. Мы могли бы сделать запрос о том, являются ли Мэри и Джейн сестрами. Пролог просмотрел бы все, что ему известно о Мэри и Джейн, и выдал бы ответ да или нет в зависимости от того, что ему известно. Таким образом, можно рассматривать Пролог как некоторое хранилище фактов и правил, используемых для поиска ответов на вопросы. Программирование на Прологе заключается в том, чтобы описать все эти факты и правила. Пролог-система позволяет использовать ЭВМ как хранилище фактов и правил и предоставляет механизм, позволяющий делать выводы, переходя от одних фактов к другим.

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

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

Начнем обсуждение с фактов об объектах. Предположим, мы хотим сообщить Прологу[1]факт: «Джону нравится Мэри». Этот факт включает в себя два объекта, обозначенных именами «Мэри» и «Джон», и отношение, обозначенное словом «нравится». В языке Пролог используется стандартная форма записи фактов:

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

?- имеет(мэри, книга).

Если мы интерпретируем мэри как человека по имени Мэри, а книга - это какая-то конкретная книга, то смысл вопроса в следующем: «Имеет ли Мэри (данную конкретную) книгу?» или «Имеет ли место факт, что Мэри имеет данную книгу?». Мы не спрашиваем, имеет ли она все книги или книги вообще.

Обращение к Прологу с вопросом инициирует процедуру поиска в базе данных, ранее введенной в систему. Пролог ищет факты, сопоставимые с фактом о вопросе. Два факта сопоставимы (или соответствуют один другому), если их предикаты одинаковы (побуквенное совпадение) и их соответствующие аргументы попарно совпадают. Если Пролог находит факт, сопоставимый с вопросом, то он отвечает да^[3]. Если в базе данных такого факта не существует, то Пролог отвечает нет. Ответ, выдаваемый Прологом, выводится на дисплей терминала непосредственно под запросом. Пусть имеется следующая база данных:

Если вы хотите узнать, что нравится Джону, то было бы утомительно спрашивать «Нравятся ли Джону книги?», «Нравится ли Джону Мэри?» и так далее, получая каждый раз ответ да или нет. Более разумно обратиться к Пролог-системе с просьбой назвать что-нибудь, что нравится Джону. Такой вопрос можно сформулировать следующим образом««Нравится ли Джону X?». Задавая вопрос, мы не знаем, для обозначения какого объекта использована литера X. Нам хотелось бы, чтобы Пролог перечислил все имеющиеся возможности для обозначения какого объекта использована литера X. В Прологе можно не только присваивать имена конкретным объектам, но и использовать имена, подобные X, для обозначения объектов, которые должны быть определены Пролог-системой. Имена такого типа называются переменными. Переменная в Прологе может иметь либо не иметь конкретное значение. Переменная конкретизирована, если имеется объект, который обозначает эта переменная. Переменная не конкретизирована, если еще не известно, что именно она обозначает. В Прологе используется соглашение, позволяющее отличать переменные от имен конкретных объектов – каждое имя, начинающееся с прописной буквы, рассматривается как переменная.

При поиске ответа на вопрос Пролог организует просмотр всех фактов в базе данных, чтобы обнаружить объект, который эта переменная могла бы обозначать. Так, когда мы спрашиваем «Нравится ли Джону X?», Пролог просматривает все известные ему факты для обнаружения тех вещей, которые нравятся Джону.

Такая переменная, как X, сама по себе не является именем какого-то конкретного объекта, но она может быть использована для обозначения объектов, которым мы не можем дать имя. Например, мы не можем чему-то, что нравится Джону, дать имя как объекту, поэтому для выражения подобных вопросов вместо вопросов вида

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

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

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

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

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

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

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

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

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

• Существует ли такой объект 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.

Предположим, мы хотим сформулировать утверждение, что Джону нравятся все люди. Один из способов сделать это заключается в записи для каждого человека, упоминаемого в базе данных, отдельного факта:

К этому моменту мы уже обсудили большинство основных черт языка Пролог. В частности, мы рассмотрели:

• объявление фактов об объектах;

• задание вопросов относительно известных фактов;

• роль переменных и их области действия;

• конъюнкцию как способ описания и-условий;

• представление отношений в виде правил;

• общую схему поиска с механизмом возврата.

С этим небольшим набором элементарных конструкций можно уже писать полезные программы для работы с простыми базами данных. Скорее всего, наиболее правильно так и поступить, работая над упражнениями, приведенными ниже.

Чтобы понять, как пользоваться этой книгой, вам следует прочитать предисловие, если вы не сделали это до сих пор. Кроме того, когда вы начнете писать программы для имеющейся в вашем распоряжении системы программирования на Прологе, вам следует обратиться к соответствующему приложению, чтобы узнать, как организуется взаимодействие с системой. Вы также найдете несколько практических советов в гл. 8.

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

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

Упражнение 1.3. В основу этого упражнения положено одно из упражнений из книги Kowalski R. Logic for Problem Solving, North Holland, 1979. Предположим, что кем-то уже написаны на Прологе утверждения, определяющие следующие отношения:

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

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

В Прологе имеются два типа литер: печатаемые литеры и непечатаемые литеры. Печатаемые литеры обладают визуальным образом, появляющимся на терминале при выводе. Непечатаемые литеры такого образа не имеют, но при выводе они вызывают выполнение некоторых действий. Этими действиями могут быть пропуск пустого места («печать» пробела), переход на новую строку, подача звукового сигнала. Ниже приведены все печатаемые литеры, которые можно использовать в Пролог-программах.

ABCDEFGHIJKLMNOPQRSTUVWXYZ

abedefghijklmnopqrstuvwxyz

0123456789

!"#$%&'()=–~^|\{}[] _`@ +;*:‹›,.?/

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

Литеры на самом деле интерпретируются как небольшие целые числа – из диапазона от 0 до 127. Каждой литере поставлено в соответствие некоторое целое число, называемое ее ASCII-кодом. Аббревиатура ASCII расшифровывается следующим образом: American Standard Code for Information Interchange (Американский стандартный код для обмена информацией)[6]. Этот код широко используется на вычислительных машинах и в языках программирования во всем мире. Таблицу кодов ASCII можно найти почти в любом руководстве по работе на ЭВМ. Коды букв упорядочены в алфавитном порядке, так что выяснение порядка следования литер в алфавите сводится к сравнению их кодов с помощью операторов отношений, описываемых ниже в данной главе. Коды всех печатаемых литер больше 32.

Хотя польза кода ASCII в данный момент может быть для читателя и не очевидной, мы вновь вернемся к этому вопросу в разд. 3.2. и 3.5.

Иногда удобно записывать некоторые функторы как операторы. Это особая форма синтаксиса, облегчающая чтение соответствующих структур. Например, арифметические операции обычно записываются как операторы. В арифметическом выражении x+y*z знаки сложения и умножения являются операторами. Если же данное арифметическое выражение записать в обычном для структур виде, то оно будет выглядеть следующим образом: +(x,*(y,z)). Однако в некоторых случаях операторная форма записи удобнее потому, что мы со школьных лет привыкли использовать ее в арифметических выражениях. Кроме того, структурная форма требует заключения аргументов функтора в круглые скобки, что иногда обременительно.

Важно отметить, что операторы не вызывают выполнения каких-либо арифметических операций. Так, в Прологе 3+4 и 7 означают разные объекты. Терм 3+4 - другой способ записи терма +(3,4), который является структурой. Позже будет описан способ интерпретации структур как арифметических выражений и вычисления их в соответствии с правилами арифметики.

Для начала необходимо знать, как читать арифметические выражения, содержащие операторы. Это требует знания трех свойств каждого оператора: его позиции, его приоритета и его ассоциативности. В данном разделе будут описаны правила использования операторов Пролога с учетом этих свойств, но пока без излишних подробностей. В Пролог-программе можно определить много различных видов операторов, но мы будем иметь дело только с хорошо знакомыми атомами +, -, * и /.

Синтаксис терма, содержащего операторы, частично зависит от их позиций. Операторы, подобные знакам сложения (+), вычитания (-), умножения (*) и деления (/), записываются между своими аргументами и называются поэтому инфиксными операторами. Можно также помещать операторы перед их аргументами. Так, в выражении -х+у минус перед х обозначает арифметическую операцию изменения знака. Операторы, записываемые перед своими аргументами, называются префиксными операторами. Наконец, некоторые операторы могут помещаться после своего аргумента. Например, оператор вычисления факториала, употребляемый математиками, помещается после числа, для которого необходимо вычислить факториал. В математических обозначениях факториал х записывается как x!_t где восклицательный знак обозначает операцию вычисления факториала. Операторы, записанные после своих аргументов, называются постфиксными операторами. Таким образом, позиция оператора указывает его место по отношению к своим аргументам. Все операторы, рассматриваемые в следующем разделе, являются инфиксными.

Теперь рассмотрим приоритет операторов. Когда нам необходимо проинтерпретировать терм х+y*z как арифметическое выражение, мы знаем, что для того, чтобы получить правильное значение, нужно сначала перемножить у и z, а затем прибавить х. Этими знаниями мы обязаны школе, где нас научили, что умножения и деления выполняются до сложений и вычитаний; исключениями являются случаи, когда порядок операций задается скобками. С другой стороны, структурная форма +(x,*(y,z)) явно показывает порядок выполнения операций, поскольку структура с функтором * является аргументом структуры с функтором +. Для того чтобы ЭВМ правильно произвела соответствующие вычисления, необходимо сначала выполнить умножение – тогда в структуре с + будут известны значения аргументов. Таким образом, для использования операторов необходимы правила, указывающие порядок выполнения операций. Именно этой цели служит приоритет.

Приоритет оператора определяет, какая операция выполняется первой. В Прологе каждый оператор связан со своим классом приоритета. Класс приоритета представляет собой целое число, величина которого зависит от конкретной версии Пролога. Однако в любой версии оператор с большим приоритетом имеет класс приоритета, более близкий к 1. Если классы приоритетов принимают значения из диапазона от 1 до 255, то оператор с первым классом приоритета выполняется первым, до выполнения операторов, принадлежащих (например) к классу 129. В Прологе операторы умножения и деления принадлежат к более высокому классу приоритетов, чем сложение и вычитание, поэтому терм а-b/с эквивалентен терму -(a,/(b,c)). Точное соответствие между операторами и классами приоритетов в данный момент не существенно, однако желательно запомнить относительный порядок выполнения операций.

Наконец, рассмотрим свойство ассоциативности операторов. Необходимость знания этого свойства становится очевидной, когда нам требуется определить порядок выполнения операторов с одинаковым приоритетом. Например, какому выражению эквивалентно выражение «8/2/2» – «(8/2)/2» или «8/(2/2)»? В первом случае при интерпретации выражения было бы получено значение 2, во втором 8. Для того чтобы иметь возможность разделить эти два случая, необходимо знать, является ли данный оператор левоассоциативным или правоассоциативным. Левоассоциативный оператор должен иметь слева операции одинакового или низшего приоритета, а справа – операции низшего приоритета. Например, все арифметические операции (сложить, вычесть, умножить и поделить) являются левоассоциативными. Это означает, что выражения, подобные «8/4/4», интерпретируются как «(8/4)/4», а выражение «5+8/2/2» эквивалентно «5+((8/2)/2)».

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

Напомним, что структура, образованная арифметическими операторами, подобна любой другой структуре. На самом деле никакие арифметические действия не выполняются до тех пор, пока не встретится предикат 'is' (есть), описанный в разд. 2.5.

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

ЭВМ часто используют для выполнения действий над числами. С помощью арифметических операций можно сравнивать числа и проводить вычисления. В данном разделе будут приведены примеры такого использования арифметических операций.

Рассмотрим сначала сравнение чисел. Для двух заданных чисел всегда можно сказать, равно ли одно число другому, меньше ли одно число другого, больше ли одно число другого. Пролог предоставляет некоторые «встроенные» предикаты, позволяющие

сравнивать числа. Для этого могут использоваться обсуждавшиеся в разд. 2.4 предикаты '='и '\='. Их аргументами могут быть конкретизированные переменные, значениями которых являются целые числа, а также целые числа, записанные в виде констант. Существует еще несколько предикатов, позволяющих сравнивать числа. Перечислим здесь все эти предикаты, отметив предварительно, что каждый из них можно использовать в форме инфиксного оператора.

X = Y X и Y представляют одно и то же число

X \= Y X и Y представляют разные числа

X ‹ Y X меньше Y

X › Y X больше Y

X =‹ Y X меньше или равно Y

X ›= Y X больше или равно Y

Отметим, что символ «меньше или равно» записывается не так, как во многих других языках программирования (обычно ‹=). Это сделано в Прологе для того, чтобы программист мог использовать похожий на стрелку атом ‹= для своих собственных нужд.

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

Оксфордский толковый словарь английского языка определяет слово «рекурсия» следующим образом:

РЕКУРСИЯ. [Теперь употребляется редко, устаревшее.] Обратное движение, возвращение.

Это определение загадочно и, по-видимому, устаревшее. В настоящее время рекурсия является очень популярным и мощным средством в области нечислового программирования. Она используется в двух случаях: для описания структур, имеющих другие структуры в качестве компонент, и для описания программ, выполнению которых предшествует выполнение их собственной копии. Иногда начинающие программисты относятся к рекурсии с подозрением, не понимая, как это можно определить некоторое отношение через само себя? В Прологе рекурсия – это нормальный и естественный способ представления структур данных и программ. Мы надеемся, что тема этой главы – рекурсия – обретает ясность удобным и ненавязчивым образом.

Чтобы легче было понять сложную структуру, ее обычно представляют в виде дерева, в котором каждому функтору соответствует вершина, а компонентам соответствуют ветви дерева. Каждая ветвь может указывать на другую структуру, так что мы можем иметь структуры внутри структур. Обычно принято изображать дерево таким образом, чтобы корень дерева находился вверху, а ветви были направлены вниз, как это показано на рис. 3.1. Заметим, что два последних дерева имеют одинаковую форму, хотя корни и листья деревьев различны. Прежде чем читать дальше, вы должны быть уверены в том, что можете представить в виде дерева каждую из структур, с которыми вы уже сталкивались в предыдущих главах.

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

Рис. 3.1.

Если мы возьмем наше предложение («Джону нравится Мэри») и вставим слова из этого предложения в качестве аргументов функторов существительное и глагол в структуру предложения, то мы получим (см. рис. 3.3):

предложение(существительное(джон), глагольная_группа(глагол(нравится), существительное(мэри)))

Этот пример показывает, как можно использовать структуры в языке Пролог для представления синтаксиса очень простых предложений. В общем случае если мы знаем, какой частью речи является каждое слово в предложении, то можно записать структуру на Прологе, которая в явном виде описывает отношения между различными словами в предложении. Эта задача сама по себе представляет интересную тему исследования, и далее мы еще вернемся к вопросу о том, как, используя Пролог, заставить ЭВМ «понимать» некоторые простые предложения.

Деревья могут также применяться для графического описания переменных внутри структуры, в частности показывая, как сцеплены переменные, имеющие одинаковые имена (см. рис. 3.4).

 Рис. 3.2.

Рис. 3.3.

Рис. 3.4.

Список - довольно широко используемая структура данных в области числового программирования. Список -это упорядоченная последовательность элементов, которая может иметь произвольную длину. Признак упорядоченный указывает на то, что порядок элементов в последовательности является существенным. Элементами списка могут быть любые термы – константы, переменные, структуры, которые включают, конечно, и другие списки. Указанные свойства очень полезны в ситуации, когда мы не в состоянии заранее предсказать, насколько большим должен быть список и какую информацию он будет содержать. Более того, списки позволяют представить практически любой тип структуры, который может потребоваться при символьных вычислениях. Списки широко используются для представления деревьев синтаксического разбора, грамматик, карт городов, программ для ЭВМ и математических объектов, таких как графы, формулы и функции. Существует язык программирования – Лисп, в котором единственными доступными структурами данных являются константа и список. Однако в Прологе список – это просто один из частных видов структуры.

Списки могут быть представлены как специального вида дерево. Список – это любой пустой список, не содержащий ни одного элемента, либо структура, имеющая две компоненты: голову и хвост списка. Конец списка обычно представляют как хвост, который является пустым списком. Пустой список записывают как [] – открывающая квадратная скобка, за которой следует закрывающая квадратная скобка. Голова и хвост списка являются компонентами функтора, обозначаемого точкой '.'. Так, список, состоящий из одного элемента 'а' есть .(а, []), а его представление в виде дерева имеет вид

Аналогично список, состоящий из атомов a, b и с, мог бы быть записан как .(а,.(b,.(с,[]))), что изображается следующим образом:

Иногда функтор точка ('.') определяется как оператор, так что допустимо для Пролога два последних списка записать как а.[] и а.(b.(с.[]))). Второй список можно было бы записать просто как а.b.с.[], так как функтор точка – правоассоциативный оператор. Списки являются упорядоченными последовательностями элементов, так что список а.b отличается от списка b.а.

Некоторые любят записывать древовидные диаграммы списков в виде дерева, «растущего» слева направо, ветви которого направлены вниз. Приведенный выше список, представленный диаграммой в виде такой «виноградной лозы» выглядит так:

В этой диаграмме компонента функтора '.', соответствующая голове списка, «свисает» вниз, а компонента, соответствующая хвосту списка, «растет» вправо. Конец списка четко выделен тем, что последняя компонента – хвост списка – является пустым списком. Главное преимущество использования диаграммы для представления списка заключается в том, что она может быть записана справа налево на листе бумаги.

«Виноградная» диаграмма может оказаться удобной для записи списков на бумаге, когда нам необходимо видеть структуру списка, но в программах на Прологе для записи списков такие диаграммы не используются. Так как запись сложных списков с помощью функтора '.' часто оказывается неудобной, то в Прологе предусмотрена другая синтаксическая форма, которая может быть использована для записи списков в программе. Это так называемая скобочная форма записи списка. Она представляет собой заключенную в квадратные скобки последовательность элементов списка, разделенных запятыми. Например, упоминавшиеся выше списки могут быть записаны в скобочной форме в виде [а] и [а, b, с]. Списки могут содержать другие списки или переменные. Например, в Прологе допустимы следующие списки:

[]

[конкретный, человек, [любит, ловить, рыбу]]

[а, V1, b, [X, Y]]

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

Чтобы продемонстрировать структуру списков, содержащих в качестве элементов другие списки, приведем «виноградную» диаграмму для последнего из рассмотренных списков:

Из приведенной диаграммы ясно видно, что каждый ее горизонтальный уровень является списком, состоящим из некоторого числа элементов. Верхний уровень на приведенной диаграмме представляет список, содержащий четыре элемента, один из которых сам является списком. Второй уровень, содержащий два элемента, представляет четвертый элемент списка верхнего уровня. Работа со списками основана на расщеплении их наголову и хвост списка. Голова списка – это первый аргумент функтора '.', который используется для конструирования списка. Хвост списка – это второй аргумент функтора '.'. В случае когда для записи списка используется скобочная форма записи, головой списка является первый его элемент. Хвост списка представляет список, состоящий из всех элементов исходного списка, за исключением первого его элемента. Следующие примеры демонстрируют расщепление списков на голову и хвост:

Заметим, что пустой список не имеет ни головы, ни хвоста. В последнем примере оператор ± используется как функтор для структур +(Х, Y) и +(х,у).

Так как операция расщепления списка на голову и хвост очень широко используется, то в Прологе введена специальная форма для представления списка с головой X и хвостом Y. Это записывается как [X|Y], где для разделения X и Y используется вертикальная черта. При конкретизации структуры подобного вида X сопоставляется с головой списка, a Y – с хвостом списка, как это показано в следующем примере:

Предположим, что имеется некоторый список, в котором X обозначает его голову, a Y – хвост списка. Напомним, что такой список мы можем записать так: [X|Y]. Этот список мог бы содержать, например, клички тех лошадей потомков жеребца Coriander, которые все выиграли скачки в Великобритании в 1927 году:

[curragh_tip, music_star, park_mill, portland]

Теперь предположим, что мы хотим определить, содержится ли некоторая кличка в указанном списке. В Прологе это можно сделать, определив, совпадает ли данная кличка с головой списка.

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

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

Рассмотрим программу на Прологе, которая в ответ на введенное с терминала предложение (на английском языке) печатает другое предложение, представляющее преобразованное исходное предложение. Эта программа для «ответов» программисту могла бы поддерживать следующий диалог:

Вы: you are a computer (Вы - ЭВМ)

Пролог: i am not a computer (Я – не ЭВМ)

Вы: do you speak french (Вы говорите по-французски?)

Пролог: no i speak german (Нет, я говорю по-немецки)

Хотя этот диалог может показаться натянутой, но все же осмысленной беседой, очень легко написать программу, выполняющую свою «часть» диалога. Для этого достаточно просто последовательно выполнять следующие действия:

1. Ввести предложение, набранное пользователем на терминале.

2. Заменить каждое вхождение слова you на слово i.

3. Аналогичным образом заменить are на am not.

4. Заменить french на german.

5. Заменить do на nо.

Если применить данную схему преобразования к надлежащим образом подобранным предложениям, подобным использованным в приведенном выше диалоге, то получим осмысленные преобразованные предложения. Однако эта схема применима не ко всем предложениям. Например;

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

Рассмотрим предикат, который мы назовем меньше. Если предикат меньше(Х, Y) используется в качестве целевого утверждения, то он истинен (т. е. согласуется с базой данных), если X и Y обозначают атомы и X по алфавиту предшествует Y. Так, предикат меньше(арбуз, букварь) истинен, а меньше(ветер,автомобиль) ложен. Точно так же должен быть ложен и предикат меньше(картина,картина). Сравнивая два слова, мы сравниваем их последовательно, буква за буквой и при сравнении каждой буквы определяем, какое из следующих условий имеет место:

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

2. Очередная литера в первом слове предшествует в алфавите соответствующей литере во втором слове. Например, меньше (слово,слон). Буква 'в' в слове слово предшествует в алфавите букве 'н' в слове слон. В этом случае предикат меньше истинен.

3. Литера в первом слове совпадает с соответствующей литерой во втором слове. В этом случае следует использовать предикат меньше для сравнения оставшихся литер в обоих словах. Например, если дано меньше(облако,одеяло), то, так как оба аргумента начинаются с буквы 'о', необходимо взять в качестве следующей цели меньше(блако,деяло).

4. Одновременно достигнут конец первого и второго слов, как, например, в случае меньше(яблоко,яблоко). При возникновении такого условия предикат меньше должен быть ложным, так как оба слова являются одинаковыми.

5. Обработаны все литеры второго слова, но еще остались литеры в первом слове, как, например, в случае меньше(алфавитный,алфавит). В такой ситуации предикат меньше должен быть ложным.

После того как сформулированы перечисленные выше условия, задача перевода их на Пролог является довольно простой. Будем представлять слова в виде списков литер (целых чисел из некоторого диапазона). Для этого необходим способ преобразования атома в список литер. Эту функцию выполняет встроенный предикат Пролога name(имя). Целевое утверждение name(X, Y) согласуется с базой данных, когда атом, являющийся значением X, состоит из литер, коды которых образуют список, являющийся значением Y (используются коды ASCII). Отсылаем читателя к гл. 2, если он забыл, что такое коды ASCII. Если один из аргументов не определен, то Пролог предпримет попытку конкретизировать его, создавая соответствующую структуру. Поэтому можно использовать предикат name для преобразования слова в список литер. Например, зная, что код ASCII для 'а' есть 97, код для 'l' – 108 и код для 'p' – 112, можно задавать следующие вопросы:

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

Давайте подытожим всю информацию, которую мы почерпнули в гл. 1 и 2 о том, что может произойти с целевым утверждением (целью).

1. Может иметь место попытка доказать согласованность целевого утверждения с базой данных. В процессе доказательства база данных просматривается, начиная с ее вершины. При этом возможны две ситуации:

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

(б) В базе данных нет факта (или заголовка правила), сопоставимого с целевым утверждением. В этом случае мы говорим, что попытка доказать согласованность целевого утверждения потерпела неудачу (цель не согласуется с базой данных). Тогда будет предпринята попытка (см. п.2) вновь доказать согласованность целевого утверждения, указанного в прямоугольнике, расположенном выше стрелки. Если исходное целевое утверждение входит в конъюнкцию, то это будет целевое утверждение, расположенное в программе непосредственно слева от рассматривавшегося целевого утверждения.

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

В этой главе процесс возврата будет рассмотрен более подробно. Кроме того, будет рассмотрен специальный механизм – «отсечение», который может быть использован в программах на Прологе. Отсечение позволяет указывать, какие из ранее сделанных выборов альтернатив не следует более пересматривать.

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

отец(мэри, джордж).

отец(джон, джордж).

отец(сью,гарри).

отец(джордж,эдуард).

в которых отец(X, Y) обозначает, что Y является отцом X. Вопрос

?- отец(X,Y).

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

X = мэри, Y = джордж;

X = джон, Y = джордж;

X = сью, Y = гарри;

X = джордж, Y = эдуард.

Пролог найдет эти ответы, просматривая базу данных в поисках фактов и правил с предикатом отец и печатая их в том порядке, в каком они представлены в базе данных. При этом Пролог не проявляет особого «интеллекта» – он ничего не помнит о предыдущих ответах. Так, если мы обратимся с вопросом

?- отец(_,X).

(для каких X верно то, что X является отцом), то мы получим

Х=джордж;

Х=джордж;

Х=гарри;

Х=эдуард.

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

Повторный просмотр выполняется точно таким же способом, если выбор среди альтернатив происходит на более глубоком уровне обработки. Например, для определения отношения «одним из детей X является Y» могло бы быть использовано правило

ребенок(Х,Y):- отец(Y,X).

Тогда вопрос

?- ребенок(Х,Y).

дал бы

X = джордж, Y = мэри;

X = джордж, Y=джон;

X = гарри, Y = сью;

X = эдуард, Y = джордж.

Так как отец(Y, X) имеет четыре решения, то столько же решений имеет и ребенок(Х, Y). Более того, решения порождаются в том же самом порядке. Единственное, что отличает эти решения, - это различный порядок аргументов в соответствии с определением для предиката ребенок. Аналогично, если мы определили

отец(X):- отец(_,X).

(отец (X) обозначает, что X является чьим-либо отцом), то на вопрос

?- отец(X).

были бы получены ответы:

X = джордж;

X = джордж;

X = гарри;

X = эдуард.

Если мы перемешаем факты и правила, то выбор альтернатив вновь будет производиться в соответствии с порядком, в котором представлены факты и правила. Так, мы могли бы определить:

человек(адам).

человек(X):- мать(X,Y).

человек(ева).

мать(каин,ева).

мать(авель,ева).

мать(иавал,ада).

мать(тувалкаин,цилла).

(адам - человек; объект является человеком, если он имеет мать; ева – человек. Перечисленные люди имеют указанных матерей). В этом случае если бы мы сделали запрос

?- человек (X).

то ответом было бы:

X = адам;

X = каин;

X = авель;

X = иавал;

X = тувалкаин;

X = ева.

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

возможная_пара(X, Y):- парень(Х), девушка(Y).

парень(джон).

парень(мармадук).

парень(бертрам).

парень(чарлз).

девушка(гризелда).

девушка(эрминтруда).

девушка(брунхильда).

В программе определено, что X и Y образуют возможную пару, если X является парнем, a Y — девушкой. Теперь давайте посмотрим, какие возможные пары имеются:

?- возможная_пара(X, Y).

X = джон, Y = гризелда;

X = джон, Y = эрминтруда;

X = джон, Y = брунхильда;

X = мармадук, Y = гризелда;

X = мармадук, Y = эрминтруда;

X = мармадук, Y = брунхильда;

X = бертрам, Y = гризелда;

X = бертрам, Y = эрминтруда;

X = бертрам, Y = брунхильда;

X = чарлз, Y = гризелда;

X = чарлз, Y = эрминтруда;

X = чарлз, Y = брунхильда.

Вы должны быть уверены, что понимаете, почему Пролог породил решения в таком порядке. Прежде всего он ищет сопоставление для цели парень(X) и находит, что первым парнем является джон. Затем он находит сопоставление для цели девушка(Y), выбирая гризелда в качестве первой девушки. В этом месте мы запрашиваем новое решение, вводя ';'. Пролог поэтому считает, что последнее доказательство согласованности цели потерпело неудачу, и делает попытку вновь доказать согласованность последней из рассматривавшихся целей. Этой целью является утверждение девушка, встретившееся при доказательстве согласованности целевого утверждения возможная_пара. Обнаруживается альтернативный вариант эрминтруда, и, следовательно, следующим решением является пара джон и эрминтруда. Аналогично порождается пара джон и брунхильда в качестве третьего решения. При следующей попытке доказать согласованность целевого утверждения девушка(Y) Пролог обнаружит, что маркер, соответствующий этому целевому утверждению, находится в конце базы данных и, следовательно, попытка найти новое сопоставление для этого целевого утверждения терпит неудачу. Тогда делается попытка вновь доказать согласованность целевого утверждения парень(Х), маркер которого был установлен на первый факт предиката парень, и, следовательно, следующим найденным решением, соответствующим второму парню, является мармадук. Теперь, когда для этого целевого утверждения найдено новое решение, Пролог определяет, что следует делать далее – он должен найти сопоставление для цели девушка(Y), осуществляя поиск решения с самого начала базы данных. Так что он выбирает гризелда в качестве первой девушки. Следующие три решения содержат мармадук и имена трех девушек. Очередная попытка найти альтернативное решение для цели девушка заканчивается неудачей. Поэтому ищется другой парень, а поиск среди девушек производится с начала базы данных. Аналогичным образом происходит выполнение программы и далее.

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

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

Рассмотрим следующее определение целого числа (здесь под «целым» числом понимается целое положительное число). Целевое утверждение целое_число(N) согласуется с базой данных, если переменная N конкретизирована и ее значением является целое число. Если переменная N неконкретизирована в момент рассмотрения целевого утверждения, то попытка найти соответствие для утверждения целое_число (N) приведет к тому, что будет выбрано целое число, которое будет присвоено N в качестве значения.

/* 1 */ целое_число(0).

/* 2 */ целое_число (X):- целое_число (Y),X is Y+1)

Если мы зададим вопрос

?- целое_число (X).

то получим в качестве возможных ответов все целые числа в порядке возрастания (0, 1, 2, 3,…), по одному числу каждый раз. Всякий раз, когда инициируется возврат (возможно, в результате ввода точки с запятой ';'), для предиката целое_число находится новое сопоставление, в результате чего его аргументу присваивается очередное целое число. Таким образом, это короткое определение порождает бесконечное число решений. Почему? На рис. 4.1, 4.2, 4.3 показана последовательность событий, приводящая к порождению трех первых решений. На каждом этапе самый нижний указатель (1) на рисунке указывает место, где впоследствии будет выбрано иное решение. Первоначально для ответа на вопрос имеется выбор между фактом 1 и правилом 2. Если выбирается факт 1, то ничего более выбирать не придется, и мы получаем X = 0. В противном случае выбирается правило 2 и ищется соответствие для цели, порождаемой этим правилом. Если выбирается факт 1, то завершается доказательство целевого утверждения с ответом X=1; в противном случае используется правило 2 и снова ищется соответствие для появившейся подцели. И так далее. На каждом этапе первое что делает Пролог – это выбирает факт 1. Только при выполнении возврата он изменяет последний сделанный им выбор. Каждый раз, когда он это делает, он возвращается к тому месту, где в последний раз выбирал факт 1, и выбирает вместо него правило 2. При этом выборе появляется новая подцель. Факт 1 представляет первую возможность для сопоставления с этой подцелью.

Рис. 4.1.

Рис. 4.2.

Рис. 4.3.

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

принадлежит(X,[X |_]).

принадлежит(X,[_ |Y]):- принадлежит(X,Y).

порождает альтернативные решения. Если мы задаем вопрос

?- принадлежит(а,X).

(обратите внимание, что X в вопросе является неконкретизированной переменной), то последовательные значения переменной X будут представлять частично конкретизированные списки, в которых а является первым, вторым, третьим и так далее элементом списка. Убедитесь, что вы понимаете, почему так получается. Другим следствием возврата, допускаемого при выполнении предиката принадлежит, является то, что вопрос

?- принадлежит(а,[а,b,r,а,с,а,d,а,b,r,а]).

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

Этот раздел посвящен специальному механизму, используемому в программах на Прологе и называемому «отсечением»[8]. Отсечение позволяет указать, какие из сделанных ранее выборов не следует пересматривать при возврате по цепочке согласованных целевых утверждений. Существуют две причины, побуждающие включать в программу такие указания:

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

• Программа может занимать меньше места в памяти ЭВМ, так как отсутствие необходимости запоминать точки возврата для последующего анализа позволяет более экономно использовать память.

В некоторых случаях включение отсечения в программу может означать переход от программы, которая не будет работать, к программе, которая будет работать.

Синтаксически использование в правиле отсечения выглядит как вхождение целевого утверждения с предикатом '!', не имеющим аргументов. Как целевое утверждение этот предикат всегда согласуется с базой данных и не может быть вновь согласован. Однако он имеет побочный эффект, который изменяет процесс последующего возврата. Эффект заключается в том, что маркеры некоторых целей становятся недоступными, так что для этих целей нельзя найти новые сопоставления. Рассмотрим, как это происходит на примере. Предположим, что вы заведуете библиотекой и имеете базу данных на Прологе, содержащую информацию о наличии книг, о том, кто и какие книги взял и когда книги должны быть возвращены. Один из вопросов, который мог бы вас интересовать,- это какие виды услуг, предоставляемых библиотекой, доступны каждому из читателей. Некоторые услуги, которые мы могли бы назвать основными, должны быть доступны любому читателю. Они включают пользование каталогом и справочным бюро. С другой стороны, дополнительные услуги, такие как пользование абонементом или получение книг из других библиотек, хотелось бы предоставлять читателю выборочно. Одно из правил могло бы состоять в том, что если читатель не возвратил в указанный срок книгу, то дополнительные виды услуг ему недоступны до тех пор, пока он не вернет книгу. Здесь приведена часть программы, которая использует это правило:

услуги(Читатель,Вид_услуг):-

 книга_не_возвращена(Читатель,Книга),!,основные_услуги (Вид_услуг).

услуги(Читатель,Вид_услуг):-общие_услуги(Вид_услуг).

основные_услуги(пользование_каталогом).

основные_услуги(получение_справок).

дополнительные_услуги (абонемент).

дополнительные_услуги(межбиблиотечный_абонемент).

общие_услуги(X):-основные_услуги(X).

общие_услуги(X):-дополнительные_услуги(X).

книга_не_возвращена('С. Уотзер',книга10089),

книга_не_возвращена('А. Джонс', книга29907).

. . .

читатель('А.Джонс'). читатель('В.Метеск').

Зачем понадобилось использовать отсечение в этой программе и какой эффект оно оказывает? Предположим, что вы хотите просмотреть список всех читателей и определить, какие услуги им доступны. В этом случае вам надо обратиться к Прологу со следующим вопросом:

?- читатель(X), услуги(X,Y).

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

Мы можем представить ситуацию, возникшую непосредственно перед выполнением отсечения, в виде диаграммы, приведенной на рис. 4.4. Когда в программе встречается отсечение, то оно «отсекает» путь, представляющий цепочку выполненных доказательств таким образом, что следующая цель соединяется непосредственно с исходной (см. рис. 4.5). Результат действия отсечения в правиле для предиката услуги (утверждение 1) заключается в том, что все цели, выбранные с момента, когда было выбрано это правило, запоминаются в системе как неизменяемые при обратном просмотре.

Путь, представляющий цепочку найденных доказательств, при этом изменяется так, что исключаются все маркеры, соответствующие целям, расположенным между услуги и отсечением включительно. Таким образом, если впоследствии произойдет возврат на точку! (отсечение), то попытка согласовать цель услуги немедленно потерпит неудачу. Система не будет рассматривать альтернативные решения для целевого утверждения книга_не_возвращена ('А. Джонс', Книга), и это совершенно разумно, так как мы интересуемся лишь тем, числится ли за читателем хотя бы одна не возвращенная в срок книга, а не тем, каковы все книги, числящиеся за ним. Утверждение 2 в предикате услуги тоже рассматриваться системой не будет, так как при возврате обходится и выбор правила, в котором встречается отсечение. Такое поведение системы в рассматриваемой ситуации тоже является разумным, так как мы не хотим порождать решения, указывающие на то, что А. Джонсу доступны все услуги.

Рис. 4.4.

Рис. 4.5.

Действие отсечения в этом примере можно резюмировать следующим образом:

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

В этом примере использование отсечения привело к «сокращению» всех решений, принятых после выбора целевого утверждения услуги. Оно называется родительским целевым утверждением для отсечения, так как именно это целевое утверждение привело к использованию правила, содержащего отсечение. На наших диаграммах родительским целевым утверждением всегда является целевое утверждение, соответствующее наименьшему прямоугольнику, содержащему прямоугольник с '!'. Формальное определение эффекта, производимого отсечением, формулируется следующим образом:

Если отсечение встречается в качестве целевого утверждения, то после этого система лишается возможности изменять решения, принятые ею с момента вызова родительского целевого утверждения. Все альтернативы принятым решениям отбрасываются. Следовательно, попытка вновь доказать согласованность с базой данных любого целевого утверждения между родительским целевым утверждением и ! (отсечением) закончится неудачей.

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

foo:- а, b, с,!, d, e, f

Пролог без каких-либо ограничений может выполнять возврат среди целей a, b и с до тех пор, пока доказательство согласованности целевого утверждения с с базой данных не приведет к тому, что Пролог «перешагнет» через «забор»! и приступит к доказательству согласованности целевого утверждения d. Далее возврат может осуществляться между целевыми утверждениями d, e и f, при этом, возможно, неоднократно будет достигаться согласованность всей конъюнкции целиком. Однако если произойдет неудача при доказательстве согласованности целевого утверждения d, что вызовет «перешагивание через забор» справа налево, то никаких попыток вновь доказать согласованность целевого утверждения с делаться не будет; доказательство согласованности конъюнкции целей в целом, а следовательно, и цели foo потерпит неудачу.

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

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

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

В этом разделе мы представим программу, которая вводит предложение с терминала и преобразует его в список атомов языка Пролог. В программе определяется предикат ввести, имеющий один аргумент. Программа должна уметь определять, где заканчивается одно вводимое слово и начинается следующее. Поэтому предположим, что слово состоит из нескольких букв, цифр или специальных литер. Буквы и цифры уже были представлены в разд. 2.1. Мы будем рассматривать одиночную кавычку ''' и дефис '-' как специальные литеры. Литеры

, ; : ? ! .

будут рассматриваться как отдельные слова. Все другие литеры являются разделителями между словами. Предложение считается законченным, когда встречается одно из слов '.', '!' или '?'. Прописные буквы автоматически преобразуются в строчные, так что одно и то же слово всегда превращается в один и тот же атом. В результате такого определения программа будет поддерживать диалог с пользователем, подобный следующему:

?- ввести(S).

The man, who is very rich, saw John's watch.

S = [the,man,',',who,is,very,rich,',',saw,'John's',watch,'.']

В действительности мы вставили в представление предложения дополнительные одинарные кавычки, чтобы выделить некоторые атомы.

Программа использует предикат get0 для ввода литер с терминала. Затруднение, связанное с предикатом get0, состоит в том, что если литера прочитана с терминала этим предикатом, то она «ушла навсегда» и никакое другое целевое утверждение get0 или попытка вновь доказать целевое утверждение get0 не позволит получить доступ к этой литере вновь. Поэтому следует избегать возврата за точку использования get0, если мы хотим избежать «потери» литеры, которую он читает. Например, следующая программа, которая должна вводить литеры и печатать их снова, заменяя литеры а на b (код литеры 97 на код 98), не будет работать:

Причина, по которой операторы рассматриваются в главе, посвященной вводу-выводу, состоит в том, что операторы предоставляют некоторые синтаксические удобства при чтении и записи термов. Никаких других причин для введения операторов нет. Для начала коротко напомним сказанное в разд. 2.3, а затем расскажем о том, как объявляются операторы.

Синтаксис языка разрешает использование операторов, обладающих следующими тремя свойствами: позицией, приоритетом и ассоциативностью. По занимаемой позиции операторы могут быть инфиксными, постфиксными или префиксными (оператор, имеющий два аргумента, может располагаться между аргументами; оператор с одним аргументом может находиться либо после аргумента, либо перед ним). Приоритет оператора – это некоторое целое число, диапазон изменения которого зависит от конкретной реализации Пролога. Предположим, что оно находится в диапазоне от 1 до 255. Приоритет используется для того, чтобы придать однозначную интерпретацию выражениям в тех случаях, когда синтаксис термов не задан явно с помощью скобок. Ассоциативность необходима для придания однозначной интерпретации выражениям, в которых имеются два оператора с одинаковыми приоритетами. Оператору в языке Пролог соответствует специальный атом, который специфицирует позицию и ассоциативность оператора. Для инфиксных операторов возможны следующие спецификации:

xfx xfy yfx yfy

Чтобы понять смысл этих спецификаций, их полезно рассматривать как «образцы» возможного использования операторов. В приведенных образцах буква f представляет оператор, а х и у – аргументы. Таким образом, во всех приведенных выше образцах оператор должен находиться между двумя аргументами, т. е. он является инфиксным оператором. В соответствии с этим соглашением

fx fy

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

xf yf

представляют возможные спецификации для постфиксных операторов. Может вызвать недоумение использование двух букв для обозначения аргументов. Использование букв х и у в той или иной позиции позволяет выразить информацию об ассоциативности оператора. В предположении, что выражение не содержит скобок, буква у указывает, что соответствующий ей аргумент может содержать операторы с приоритетом, равным приоритету данного оператора или с более низким приоритетом. Напротив, буква х указывает, что каждый оператор в соответствующем ей аргументе должен иметь строго более низкий приоритет по сравнению с приоритетом данного оператора. Рассмотрим, что это значит для оператора +, объявленного как yfx. Если имеется выражение

а + b + с

то для него возможны две следующие интерпретации:

(а + b) + с      а + (b + с)

Вторая интерпретация исключается, так как при этом аргумент, стоящий после первого вхождения +, содержит оператор с тем же самым приоритетом (второй оператор +). Это противоречит тому, что в спецификации оператора + после f стоит х.

Оператор, имеющий спецификацию yfx, является левоассоциативным. Аналогично оператор со спецификацией xfy является правоассоциативным. Если мы знаем необходимую ассоциативность объявляемого инфиксного оператора, то это значит, что однозначно определяется соответствующая оператору спецификация.

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

not not a

допустима синтаксически, если оператор not объявлен как fy, и недопустима в случае, когда он объявлен как fx.

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

В этой главе будут описаны некоторые встроенные предикаты, которые может обеспечивать Пролог-система. Что имеется в виду, когда мы говорим, что предикат является встроенным? Это значит, что определение этого предиката уже имеется в Пролог-системе и нет необходимости иметь собственное его описание. Встроенные предикаты предоставляют возможности, которые нельзя реализовать с помощью описаний на чистом Прологе. Они также могут предоставлять удобные средства, избавляя программиста от необходимости самому определять эти предикаты. В действительности мы уже встречались с некоторыми встроенными предикатами – это предикаты для ввода и вывода, обсуждавшиеся в гл. 5. Оператор «отсечения» тоже можно рассматривать как встроенный предикат.

Предикаты для ввода-вывода показывают, что встроенные предикаты могут иметь «побочные эффекты». Это значит, что при доказательстве согласованности целевого утверждения, содержащего такой предикат, помимо конкретизации аргументов предиката могут возникнуть дополнительные изменения. Это, естественно, не может случиться с предикатами, определенными на чистом Прологе. Другой важный факт, касающийся встроенных предикатов, состоит в том, что они могут быть определены только для аргументов конкретного вида. Например, рассмотрим предикат '‹' определенный таким образом, что Х‹Y выполняется, если число X меньше, чем число Y. Подобное отношение не может быть определено в Прологе без помощи посторонних средств, использующих некоторые знания о числах. Таким образом, ‹ – это встроенный предикат, а его определение использует некоторые операции вычислительной машины, на которой реализована Пролог-система, для определения относительной величины чисел (представленных в виде двоичного кода или каким-либо иным способом).

Что произойдет, если мы используем в качестве целевого утверждения предикат X‹Y, где X является атомом или даже более того, если как X, так и Y неконкретизированы? Определение предиката, данное на машинном языке, окажется просто неприменимым. Поэтому мы должны оговорить, что предикат X‹Y может быть использован в качестве целевого утверждения, если на момент, когда делается попытка выполнить его, обе переменные X и Y имеют в качестве значений числа. Что произойдет в случае, когда это условие не выполняется, зависит от конкретной реализации Пролог-системы. Возможно, доказательство согласованности такого целевого утверждения просто закончится неудачей. А может быть, будет напечатано сообщение об ошибке и система выполнит ряд действий, соответствующих этой ситуации (подобных прекращению попыток ответить на текущий вопрос).

Когда вы пишете программу на Прологе, вам следует сообщить системе, какие утверждения нужно использовать, и затем задавать относительно них вопросы. Возможно, вы захотите вводить утверждения с терминала или захотите указать Пролог-системе приготовленный вами заранее файл, откуда следует брать утверждения. В действительности обе эти операции с точки зрения Пролога одинаковы, так как терминал рассматривается как файл, имеющий имя user. Имеются два основных встроенных предиката для ввода новых утверждений: consult и reconsult. Кроме того, в языке существует удобная форма записи на случай, когда вы захотите ввести утверждения сразу из нескольких файлов,- так называемая списковая форма записи. Для тех, кому это интересно, укажем, что в разд. 7.13 приведены простые определения на Прологе предикатов consult и reconsult.

Встроенный предикат consult предназначен для использования в тех ситуациях, когда вы хотите добавить утверждения из некоторого файла /или вводимые с терминала) к утверждениям, уже имеющимся в базе данных. Аргумент предиката должен быть атомом, указывающим имя файла, из которого должны браться утверждения. Какие литеры составляют допустимое имя файла, естественно, зависит от конкретной, используемой вами ЭВМ. Ниже приведены примеры возможной записи целевого утверждения с предикатом consult на различных ЭВМ:

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

Это целевое утверждение всегда согласуется с базой данных. В действительности этот предикат не является необходимым, так как утверждения в базе данных и цели могут быть переупорядочены или перегруппированы так, чтобы избежать использования предиката true. Однако для удобства он входит в состав встроенных предикатов.

Это целевое утверждение никогда не согласуется с базой данных. Имеются две ситуации, когда этот предикат оказывается полезным. Одна из них – это использование комбинации !- fail, которая уже была описана в разд. 4.3. Конъюнкция целевых утверждений

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

Целевое утверждение var(X) согласуется с базой данных, если на текущий момент X является неконкретизированной переменной. Таким образом, возможен следующий диалог:

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

• Создавать структуру, представляющую утверждения в базе данных.

• Добавлять к базе данных утверждение, представленное заданной структурой.

• Удалять из базы данных утверждение, представленное заданной структурой.

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

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

Обычно когда мы хотим задать в программе на Прологе операции со структурой определенного вида, то мы делаем это, «упоминая» некоторым образом подобную структуру. Это значит, что если предикат используется для обработки множества структур различного вида, передаваемых ему в качестве аргумента, то обычно мы обеспечиваем отдельное утверждение для каждого класса структур. Хорошим примером такого подхода является программа для символьного дифференцирования, которая будет рассмотрена в разд. 7.1. В этой программе используются отдельные утверждения для функторов +, -, * и так далее. Мы знаем заранее, какие структуры могут появиться, и обеспечиваем утверждения для каждой из них.

В некоторых программах мы не можем предвидеть заранее все возможные структуры. Это имеет место, например, при написании программы «красивой печати», которая могла бы печатать произвольные структуры языка Пролог, размещая их в нескольких строках и используя отступы. (См. разд. 5.1, где представлена такая программа для печати списков.) Так, например, возможно, мы захотели бы напечатать терм

книга(629,автор(бронте, эмили),вх)

следующим образом:

книга

 629

 автор

  бронте

  эмили

 вх

Важным моментом является то, что мы хотим, чтобы эта программа работала правильно, какую бы структуру мы ей ни задали. Понятно, что одна из возможностей сделать это – обеспечить отдельное утверждение для каждого функтора, какой только можно представить. Но это работа, которую мы никогда не завершим, потому что существует бесконечно много различных функторов! Написать подобную программу можно, используя встроенные предикаты для работы со структурами произвольного вида. Здесь мы опишем некоторые из них – это предикаты functor, arg и '=..'. Мы опишем также предикат name, выполняющий операции над атомами.

Предикат functor определен таким образом, что functor(T,F,N) означает, что Т – это структура с функтором F, имеющим N аргументов. Этот предикат можно использовать двумя основными способами, В первом случае аргумент Т уже имеет значение. Целевое утверждение считается несогласованным с базой данных, если Т не является ни атомом, ни структурой. Если Т – это атом или структура, то F сопоставляется с функтором этой структуры, а N присваивается значение, равное числу аргументов функтора. Заметим, что в данном контексте считается, что атом – это структура с числом аргументов 0. Ниже приведено несколько примеров целевых утверждений с предикатом functor:

В Прологе есть два встроенных предиката, изменяющих нормальную последовательность событий, происходящих в процессе возврата. Предикат «!» устраняет возможности для повторного согласования целевых утверждений, а предикат repeat создает новые альтернативы там, где их не было ранее.

Символ отсечения ('!') можно рассматривать как встроенный предикат, который лишает Пролог-систему возможности изменить некоторые из решений, принятых ею ранее. Более подробное описание отсечения смотрите в гл. 4.

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

В правилах и вопросах вида X:-Y или ?-Y терм, появляющийся на месте Y, может состоять из единственного целевого утверждения либо представлять конъюнкцию целевых утверждений или их дизъюнкцию. Более того, можно употреблять в качестве целевых утверждений переменные и успешно доказывать согласованность целевого утверждения, когда целевое утверждение в действительности не согласуется, используя для этого предикат not. Предикаты, представленные в этом разделе, позволяют реализовать эти сложные способы выражения целевых утверждений.

Функтор ',' (запятая) определяет конъюнкцию целевых утверждений. Этот функтор был введен в гл. 1. Если X и Y – целевые утверждения, то целевое утверждение X, Y согласуется с базой данных, если согласуется X и Y. Если X согласуется и затем Y не согласуется, то делается попытка найти новое доказательство согласованности для X. Если X не согласуется, то не согласуется и конъюнкция в целом. Это и составляет суть механизма возврата. Функтор Y является встроенным и определен как левоассоциативный инфиксный оператор, так что X, Y, Z эквивалентно (X,Y),Z.

Функтор ';' определяет дизъюнкцию (означающую или) целевых утверждений. Если X и Y – целевые утверждения, то целевое утверждение X; Y согласуется с базой данных, если согласуется X или Y. Если X не согласуется, то делается попытка доказать согласованность Y. Если и Y не согласуется, то не согласуется и дизъюнкция в целом. Мы можем использовать функтор ';' для того, чтобы выразить альтернативы в пределах одного утверждения. Например, будем считать, что некоторый объект является человеком, если этот объект – либо Адам либо Ева или если у объекта есть мать. Мы можем выразить это в одном правиле следующим образом:

В этом разделе коротко рассматриваются различные встроенные предикаты, используемые для проверки равенства элементов и позволяющие делать их равными.

Когда Пролог встречает целевое утверждение X=Y, то он пытается сделать X и Y равными, сопоставляя их друг с другом. Если сопоставление возможно, то целевое утверждение считается согласованным (а X и Y, возможно, становятся более конкретизированными). В противном случае целевое утверждение считается несогласованным. Более полное обсуждение этого предиката приведено в разд. 2.4. Предикат равно определен таким образом, как если бы имел место факт

X = X.

Убедитесь, что вы понимаете, как это определение работает.

Предикат '\=' является противоположным по отношению к предикату '=' с точки зрения согласованности с базой данных. Это значит, что X\=Y согласовано, если X=Y не согласовано, и наоборот. Если целевое утверждение X\ = Y согласовано (X и Y не могут быть сопоставлены друг с другом), то не произойдет никаких изменений в конкретизации X и Y. Если бы '\=' не был встроенным предикатом, то мы могли бы определить его на Прологе следующим образом:

Предикаты для ввода и вывода литер и термов обсуждались в гл. 5. Здесь мы резюмируем наши знания о каждом из этих предикатов.

Это целевое утверждение согласуется с базой данных, если X может быть сопоставлена с очередной литерой в текущем входном потоке данных. Цель get0 выполняется лишь один раз (его нельзя согласовать повторно). Операция перехода к очередной литере не переделывается при возврате, так как не существует способа поместить литеру обратно в текущий входной поток данных.

Это целевое утверждение согласуется с базой данных, если переменная X может быть сопоставлена с очередной печатаемой (неуправляющей) литерой в текущем входном потоке данных. Печатаемые литеры имеют код ASCII, превышающий 32. Все управляющие литеры пропускаются. Предикат get выполняется только один раз (он не может быть согласован вновь). Результат get не устраняется при возврате, так как нет способа поместить литеру обратно в текущий входной поток данных.

Этот предикат читает и пропускает литеры в текущем входном потоке данных до тех пор, пока не встретится литера, сопоставимая с X. Предикат skip выполняется только один раз.

Этот предикат читает очередной терм из текущего входного потока данных и сопоставляет его с X. Предикат read выполняется только один раз. Вводимый терм должен заканчиваться точкой '.' которая не становится частью этого терма. После точки должна следовать по крайней мере одна управляющая литера. Точка удаляется из текущего входного потока данных.

Этот предикат записывает целое число X в виде литеры (кодом которой и является X) в текущий выходной поток данных. Предикат put выполняется только один раз. Если X неконкретизирован, то фиксируется ошибка.

Записывает в текущий выходной поток данных последовательность управляющих литер, вызывающую переход на «новую строку». В случае вывода на дисплей все литеры, выводимые после nl, будут размещены на следующей строке страницы; nl выполняется только один раз.

Записывает X «пробелов» в текущий выходной поток данных. Если X неконкретизирован, то фиксируется ошибка, tab выполняется только один раз.

Этот предикат записывает терм X в текущий выходной поток данных, write выполняется только один раз. Каждая неконкретизированная переменная, входящая в X, записывается как уникальное имя, начинающееся с подчеркивания ('_'), за которым следует уникальное число, как, например, '_239'. Переменные, сцепленные в пределах одного аргумента предиката write, при печати будут иметь одинаковые имена. Предикат write учитывает при печати термов имеющиеся объявления операторов. Так, например, инфиксный оператор будет напечатан между своими аргументами.

Предикат display работает в точности таким же способом, что и write, за тем исключением, что он игнорирует все объявления операторов. Предикат display печатает любую структуру, начиная с ее функтора, за которым в круглых скобках печатается список аргументов.

Этот предикат объявляет оператор, имеющий приоритет X, позицию и ассоциативность Y и имя Z. Спецификация позиции и ассоциативности выбирается из числа следующих атомов:

fx fy xf yf xfx xfy yfx yfy

Если объявление оператора корректно, то op считается согласованным. Более подробно этот предикат описан в разд. 5.5.

Предикаты для изменения текущего входного и текущего выходного потоков данных были введены в гл. 5. Здесь мы резюмируем наши знания о каждом из этих предикатов.

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

Это целевое утверждение согласуется с базой данных, если имя текущего входного потока данных (файла) сопоставимо с X, и не согласуется в противном случае.

Этот предикат закрывает текущий входной поток данных (файл) и определяет, что текущим входным потоком данных становится клавиатура терминала (user).

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

Это целевое утверждение согласуется с базой данных, если X сопоставимо с именем текущего выходного потока данных, иначе оно не согласуется.

Этот предикат закрывает текущий выходной поток данных (файл) и записывает маркер конца файла в соответствующий файл. Текущим выходным потоком данных становится дисплей терминала (user).

Арифметические возможности языка Пролог первоначально обсуждались в разд. 2.5. Здесь мы подытожим наши знания об использовании предиката 'is' и о том, какие имеются функторы для формирований арифметических выражений.

Y должен быть конкретизирован структурой, которую можно интерпретировать как арифметическое выражение (см. разд. 2.4). Сначала вычисляется выражение, которым конкретизирован Y, и получается целое число, называемое результатом. Результат сопоставляется с X, и is считается согласованным или несогласованным в зависимости от исхода сопоставления. Ниже описываются функторы, которые могут быть использованы для построения структуры, расположенной справа от предиката is.

Оператор сложения. При вычислении, инициированном предикатом is, результатом является арифметическая сумма его аргументов. Аргументы должны быть конкретизированы структурами, которые можно вычислить и получить в качестве результатов целые числа.

Оператор вычитания. При вычислении, инициированном предикатом is, результатом является арифметическая разность его аргументов. Аргументы должны быть конкретизированы структурами, которые можно вычислить и получить в качестве результатов целые числа.

Оператор умножения. При вычислении, инициированном предикатом is, его результатом является арифметическое произведение его аргументов. Аргументы должны быть конкретизированы структурами, которые можно вычислить и получить в качестве результатов целые числа.

Оператор целочисленного деления. При вычислении, инициированном предикатом is, его результатом является целая часть частного от деления его аргументов. Аргументы должны быть конкретизированы структурами, которые можно вычислить и получить в качестве результатов целые числа.

Остаток от деления целых чисел (сравнение по модулю). При вычислении, инициированном предикатом is, его результатом является целочисленный остаток, получаемый при делении X на Y. Аргументы должны быть конкретизированы структурами, которые можно вычислить и получить в качестве результатов целые числа.

Конкретные реализации Пролога могут включать и некоторые другие арифметические операции, такие, как возведение в степень. Примеры, приведенные в этой книге, используют лишь операции, перечисленные здесь.

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

Предикат проверки на равенство, описанный в разд. 6.8, считается согласованным и в случае, когда его аргументами являются равные целые числа.

Предикат проверки на несовпадение из разд. 6.8 также применим для целых чисел. Он выполняется, когда его аргументами являются различные числа.

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

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

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

Предикат меньше или равно выполняется, когда левый аргумент меньше или равен правому аргументу. Оба аргумента должны быть конкретизированы. Заметим, что этот предикат записан как '=‹' а не '‹=' так что символ '‹=' является свободным и может быть использован в качестве оператора, который выглядит как стрелка.

В этом разделе описаны встроенные предикаты, которые позволяют наблюдать за выполнением вашей программы. Здесь мы лишь опишем эти встроенные предикаты, а более подробное обсуждение отладки и трассировки программ содержится в гл. 8.

Эффект выполнения предиката trace заключается в установлении режима полной трассировки. Это значит, что после выполнения trace вы получите возможность наблюдать за каждым из четырех основных типов событий[9], которые происходят с каждым порождаемым вашей программой целевым утверждением.

Эффект выполнения предиката notrace заключается в отмене режима полной трассировки. Однако сохраняется трассировка, вызываемая наличием контрольных точек (предикат spy).

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

• Атом. В этом случае контрольная точка устанавливается на все предикаты с именем, соответствующим атому, независимо от того, сколько аргументов они имеют. Так, если бы мы имели утверждения для сорт, имеющие как два, так и три аргумента, то целевое утверждение spy сорт вызвало бы установку контрольных точек на оба множества утверждений.

• Структура вида Имя/Размерность, где Имя - это атом, а Размерность - целое число. Эта запись определяет предикат с функтором Имя, число аргументов которого равно Размерность. Так spy сорт/2 вызвало бы установку контрольных точек на целевые утверждения предиката сорт с двумя аргументами.

• Список. В этом случае список должен заканчиваться пустым списком '[]', а каждый элемент списка сам должен быть допустимым аргументом для предиката spy. Пролог установит контрольные точки во всех местах, указанных в списке. Так spy[copт/2, присоединить/3] вызвал бы установку контрольных точек на предикат сорт с двумя аргументами и на предикат присоединить с тремя аргументами.

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

Целевое утверждение nodebug вызывает устранение всех контрольных точек, установленных на текущий момент.

Подобно spy, nospy является префиксным оператором. Предикат nospy является более селективным, чем nodebug, так как вы можете точно указать, какие контрольные точки должны быть удалены. Это достигается путем указания аргумента, задаваемого в точности в такой же форме, как и для предиката spy. Так, целевое утверждение nospy[обр/2, присоединить/3] приведет к тому, что будут удалены все контрольные точки с предиката обр с двумя аргументами и с присоединить с тремя аргументами.

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

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

Предположим, что мы хотим установить отношения между элементами информации с тем, чтобы использовать их, когда потребуется. Например, толковый словарь ставит в соответствие слову его определение, а словарь иностранного языка ставит в соответствие слову на одном языке слово на другом языке. Мы уже познакомились с одним способом составления словаря: с помощью задания фактов. Если нам нужно составить таблицу выигрышей на скачках, проводившихся на Британских островах в течение 1938 г., то мы можем просто определить факты вида выигрыши(Х, Y), где X - кличка лошади, a Y – количество гиней (денежных единиц), выигранных этой лошадью. Следующая база данных может рассматриваться как часть этой таблицы:

Выигрыши(abaris,582).

Выигрыши(careful,17).

Выигрыши(jingling_silvee,300).

Bыигрыши(majola,356).

Если мы хотим узнать, какую сумму выиграла лошадь по кличке maloja, нам нужно просто правильно построить вопрос и Пролог даст нам ответ:

?- Bыигрыши(maloja, X).

X=356

Напомним, что Пролог просматривает базу данных сверху вниз. Это значит, что если база данных нашего словаря упорядочена в алфавитном порядке, как в приведенном выше примере, то на поиск суммы выигрыша для ablaze Пролог затратит меньше времени, чем на поиск суммы выигрыша для zoltan. Однако хотя Пролог способен просмотреть свою базу данных гораздо быстрее, чем вы сможете просмотреть напечатанную таблицу, неразумно просматривать таблицу с начала до конца, если известно, что данные искомой лошади расположены в самом конце. Точно так же, хотя в Прологе имеются специальные средства быстрого просмотра базы данных, он не всегда проходит так быстро, как хотелось бы. В зависимости от размеров таблицы и от того, сколько информации хранится о каждой лошади, Прологу может потребоваться на просмотр таблицы неприемлемо большое время.

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

Рис. 7.1.

Упорядоченное дерево состоит из некоторого числа структур, называемых узлами, причем каждому входу словаря соответствует один узел. Каждый узел содержит четыре компоненты. Сюда входят два связанных с узлом элемента данных, как в предикате выигрыши в вышеприведенном примере. Один из этих элементов называется ключом, его имя определяет место в словаре (кличка лошади в нашем примере). Другой элемент используется для хранения какой-либо другой информации о данном объекте (сумма выигрыша в нашем примере). Кроме того, каждый узел содержит ссылку (наподобие ссылки на хвост списка) на узел со значением ключа, которое лексикографически (по алфавиту) меньше, чем имя, являющееся ключом данного узла, а также еще одну ссылку на узел со значением ключа лексикографически большим, чем имя, являющееся ключом данного узла. Будем использовать структуру, которую обозначим как в(Л,В,М, Б) (в - сокращение от «выигрыши»), где Л – кличка лошади (атом), используемая в качестве ключа, В – сумма выигрыша в гинеях (целое), М – структура, соответствующая лошади, кличка которой меньше, чем та, что хранится в Л, а Б – структура, соответствующая лошади, кличка которой больше, чем значение в Л. Когда для М и Б нет соответствующих структур, мы не будем их конкретизировать. Для небольшого множества лошадей указанная структура, будучи записанной в виде дерева, могла бы иметь вид, как представлено на рис. 7.1.

Если записать ее на Прологе в ступенчатом виде, учитывая ширину страницы, то она могла бы выглядеть так:

в(massinga,858,

  в(braermar,385,

    в(adela,588,_,_),

    _),

   в(panorama,158,

     в(nettleweed,579,_,_),

     _).

).

Теперь, располагая такой структурой, мы хотим «просмотреть» ее по кличкам лошадей, чтобы узнать их выигрыши в течение 1938 г. Как и раньше, структура должна иметь формат в(Л,В,М, Б). Условие окончания поиска состоит в том, что кличка искомой лошади должна совпасть с Л. В этом случае поиск удачен и не требуется пробовать другие варианты. В противном случае мы должны использовать предикат меньше, определенный в гл. 3, чтобы определить, какую из «ветвей» дерева, М или Б, нужно рекурсивно просмотреть. Мы используем эти принципы при определении предиката искать, причем искать(Л,Т, Г) означает, что лошадь Л, если она найдена в таблице Т (которая организована в виде структуры формата в), выиграла Г гиней:

искать (Л, в(Л,Г,_,),Г):- !.

искать Л, в(Л1,_,До,_),Г):-меньше(Л,Л1),искать(Л,До,Г).

искать(Л, в(Л1,_,_,После),Г):- not (меньше(Л,Л1)), искать(Л,После,Г).

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

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

?- искать(ruby_vintage,S,X).

имеет следующую интерпретацию: построить структуру в, в которой кличке ruby_vintage поставлен в соответствие выигрыш X, и присвоить ее в качестве значения переменной S. Таким образом, искать осуществляет вставку новых компонент в частично заданную структуру. Поэтому многократно обратившись к искать, можно построить словарь. Например, вопрос

?- искать(abaris,X,582), искать(maloja,X,356).

привел бы к тому, что значение переменной X стало упорядоченным деревом из двух вхождений.

Понять то, каким образом искать одновременно выполняет и создание и выборку компонент, можно на основе тех знаний о Прологе, которыми вы уже располагаете; мы настоятельно рекомендуем разобраться в этом самостоятельно. Подсказка: если искать(Л,Т, Г) используется в конъюнкции целей, то «изменения» в структуре Т сохраняются только в области определения Т.

Упражнение 7.1. Поэкспериментируйте с предикатом искать, чтобы установить, какие различия будут в словаре, если элементы в него вставлять каждый раз в разном порядке. Например, как будет выглядеть дерево словаря, если вставлять его элементы в таком порядке: massinga, braemar nettleweed, panorama? А если в таком порядке: adela, braemar, nettleweed, massinga?

Стоит темная грозовая ночь. Когда вы ехали по пустынной сельской дороге, ваша машина сломалась и вы оказались перед входом сказочного дворца. Вы подошли к двери, обнаружили, что она открыта, и стали искать телефон. Как нужно осматривать дворец, чтобы не заблудиться и быть уверенным, что вы осмотрели каждую комнату? И каков кратчайший путь к телефону? Именно для таких крайних обстоятельств и разработаны методы поиска в лабиринте.

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

Этот метод нуждается в некоторых уточнениях, но мы сделаем их позднее, при обсуждении проблем поиска на графе. А сначала давайте запишем по порядку наши шаги, чтобы знать, какие задачи предстоит решать:

1. Подойти к двери какой-либо комнаты. Если номер комнаты есть в нашем списке, то перейти к шагу 1.

2. Если в поле зрения нет ни одной комнаты, то «вернуться назад» через ту комнату, через которую мы прошли сюда, и посмотреть, нет ли возле нее каких-либо других комнат.

3. Иначе дописать номер комнаты к нашему списку.

4. Поискать телефон в этой комнате.

5. Если телефона нет, то перейти к шагу 1. Иначе мы останавливаемся, и наш список содержит путь, который мы прошли, чтобы попасть в нужную комнату.

Будем считать, что номера комнат являются константами (безразлично целыми числами или атомами). Сначала мы можем решить, как просматривать номера комнат, записанные на листке бумаги. Для этого можно использовать предикат принадлежит, определенный в разд. 3.3, полагая, что содержимое листка бумаги представлено в виде списка. Теперь мы можем продвинуться в решении задачи поиска в лабиринте. Рассмотрим небольшой пример, где задан план дома, комнаты которого помечены буквами (см. рис. 7.2). Заметим, что просветы в стенах обозначают двери и что комната а – это просто представление пространства вне дома. Имеются двери, ведущие из а в b, из с в d, из f в е, и так далее. Сведения о том, где имеются двери, могут быть представлены в виде фактов Пролога:

д(а,b).

д(b,е).

д(b,с).

д(d,c).

д(c,d).

д(e,f).

д(g,e).

Рис. 7.2.

Заметим, что информация о наличии дверей не избыточна. Например, мы сказали, что имеется дверь, ведущая из комнаты g в комнату е, но не сказали, что имеется дверь, ведущая из комнаты е в комнату g, т. е. мы не зафиксировали утверждение д(e,g). Чтобы обойти эту проблему представления двухсторонних дверей, мы могли бы повторно записать д-факт для каждой двери с перестановкой аргументов. Или мы могли бы устроить программу таким образом, чтобы она понимала, что каждая дверь фактически может рассматриваться как двухсторонняя. Этот вариант мы и выбрали в нижеследующей программе.

Чтобы перейти из одной комнаты в другую, мы должны распознать один из следующих случаев:

• мы находимся в той комнате, которая нам нужна, или

• мы должны войти в дверь и распознать эти случаи снова (рекурсивно).

Рассмотрим целевое утверждение переход(X,Y,T), которое доказуемо (согласуется с базой данных), если можно перейти из комнаты X в комнату Y. Третий аргумент Т – это наш листок бумаги, который мы носим с собой и на котором записан перечень номеров комнат, в которых мы побывали до сего момента.

Граничное условие перехода из комнаты X в комнату Y состоит в том, что, возможно, мы уже находимся в комнате Y (т. е., возможно, X есть Y). Это условие представлено в виде утверждения:

переход(Х,Х,Т).

В противном случае мы выбираем некоторую смежную комнату, назовем ее Z, и смотрим, были ли мы в ней раньше. Если нет, то «переходим» из Z в Y, дописывая Z в наш список. Все это выражается в виде следующего утверждения:

переход(Х, Y,T,):- Д(Х,Z),not(принадлежит(Z,Т)), переход(Z,Y,[Z|T]).

Словами это может быть выражено так: для того чтобы «перейти» из X в Y, не проходя через комнаты из списка Т, надо найти дверь из X куда-либо (т. е. в Z), убедиться, что Z еще не занесена в список Т, и «перейти» из Z в Y, используя список Т с дописанной в него Z.

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

Наша программа рассматривает каждую дверь как одностороннюю. Если мы считаем, что наличие двери из комнаты а в комнату b – это то же самое, что наличие двери из комнаты b в комнату а, то, как отмечалось выше, мы должны указать это явно. Кроме повторного задания д-фактов с перестановкой аргументов, имеются два способа задать эту информацию в самой программе. Самый очевидный способ – это добавить еще одно правило, получая в итоге:

переход(Х,X,T).

переход(X,Y,T):- д(X,Z), not(принадлежит(Z,Т)),переход(Z,Y[Z|T]). переход(Х,Y,T):- д(Z,Х), not(принадлежит(Z,Т)),пeреход(Z,Y,[Z|T]).

Или, используя предикат ';' (обозначающий дизъюнкцию), можно записать:

переход(Х,Х,Т).

переход(Х,Y,T):- (д(Х,Z); д(Z,Х)), not(принадлежит (Z,T)),пepexод(Z,Y,[Z|T]).

Теперь о том, как найти телефон. Рассмотрим целевое утверждение есть_телефон(X), которое согласуется с базой данных, если в комнате X есть телефон. Если мы хотим сказать, что в комнате g есть телефон, то мы просто записываем в нашу базу данных факт есть_телефон(g). Предположим, мы начали поиск с комнаты а. Один из способов узнать дорогу к телефону – это задать вопрос:

?- переход(а,Х,[]), есть_телефон(X).

Это – вопрос типа «создать и проверить», который находит достижимые комнаты и затем проверяет наличие в них телефона. Другой способ – это найти сопоставление сначала для предиката есть_телефон(Х), а затем попробовать перейти из комнаты а в X:

?- есть_телефон(Х), переход(а,Х,[]).

Последний метод более эффективен, однако он подразумевает что мы «знаем», где телефон, еще до того, как начали поиск.

Начальная установка третьего аргумента пустым списком означает, что мы начинаем поиск, имея чистый лист бумаги. Изменяя эту начальную установку, можно получить разные варианты поиска. Вопрос «найти телефону не заходя в комнаты d и f» можно выразить на Прологе так:

?- есть_телефон(X), переход (a,X,[d,f]).

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

Упражнение 7.2. Допишите вышеприведенную программу так, чтобы она печатала такие сообщения, как «входим в комнату X» и «телефон найден в комнате Y», подставляя в них соответствующие номера комнат.

Упражнение 7.3. Может ли эта программа находить альтернативные пути? Если да, то где нужно «отсечь», чтобы избежать нахождения более чем одного пути?

Упражнение 7.4. Чем определяется порядок, в котором просматриваются комнаты?

Ханойские башни - это игра, в которой используются три штыря и набор дисков. Все диски различаются диаметром и нанизываются на штыри через отверстие в центре каждого диска. Первоначально все диски находятся на левом штыре. Цель игры состоит в том, чтобы переместить все диски на центральный штырь. Правый штырь можно использовать как «запасной» для временного размещения дисков. При каждом перемещении диска с одного штыря на другой должны соблюдаться два ограничения: перемещать можно только самый верхний диск на штыре, и, кроме того, нельзя ставить диск на другой диск меньшего размера.

Многим из тех людей, которые играют в эту игру, практически никогда не удается обнаружить весьма простую стратегию, позволяющую успешно играть в Ханойские башни с тремя штырями и N дисками. Чтобы не утомлять вас поисками решения этой задачи, мы откроем его:

• Граничное условие выполняется в случае, когда на исходном (левом) штыре нет дисков.

• Переместить N-1 дисков с исходного штыря на запасной (правый) штырь, используя итоговый штырь как запасной; отметим, что это перемещение осуществляется рекурсивно.

• Переместить один диск с исходного штыря на итоговый штырь. В этом месте наша программа будет выдавать сообщение об этом перемещении.

• Наконец, переместить N-1 дисков с запасного на итоговый, используя исходный штырь в качестве запасного.

Пролог-программа, реализующая данную стратегию, определяется следующим образом. Определяется предикат ханой с одним аргументом, такой, что xaной(N) означает выдачу сообщений о последовательности перемещений, когда на исходном штыре находится N дисков. Из двух утверждений предиката переместить один задает граничное условие, которое сформулировано выше, а второй – реализует рекурсивные случаи. Предикат переместить имеет четыре аргумента. Первый аргумент – это число дисков, которые нужно переместить. Три другие представляют исходный, итоговый и запасной штыри для перемещения дисков. Предикат сообщить использует предикат write для печати названий штырей, участвующих в перемещении диска.

В главе 3 мы рассматривали программу, выдающую на печать список деталей, необходимых при сборке некоторого узла на основе справочника комплектующих деталей. В данном разделе мы усовершенствуем эту программу, будем учитывать количество деталей путем суммирования числа требуемых деталей по мере перехода от узлов к их составляющим. Кроме того, усовершенствованная программа правильно обрабатывает повторения; процедура собрать устраняет повторения при суммировании для каждой из требуемых деталей перед тем, как ответ выдается на печать.

Организация базы данных справочника сходна с тем, что описано в гл. 3. Сборочный узел представлен в виде списка структур вида чис(X, Y), где X – это имя некоторой детали (простой детали или узла), a Y – необходимое количество таких деталей. Ниже перечислены все предикаты измененной программы с указанием их назначения:

Деталиузла(А): выдает на печать список всех простых деталей, требующихся для сборки узла А, и количество каждой детали.

Деталиузлов(N,X,P): P - это список структур чис(Дет, Кол), где Дет - это название детали, а Кол - это количество таких деталей, требующихся для сборки каждого из экземпляров узлов X. N - целое, а X – атом, представляющий название некоторой детали.

Деталировка(N,S,Р): Р - это, как и выше, список структур чис, требующихся для сборки всех узлов, представленных элементами списка S; N задает число экземпляров списка S, N – целое; S – список структур чис.

Собрать(Р, А): Р и А – списки структур чис. А – это список, составленный из тех же элементов, что и Р, но без повторений одной и той же детали. Причем количество каждой детали, указанное в списке А, совпадает с суммой всех повторений этой детали в списке Р. Предикат собрать мы используем для того, чтобы собрать несколько описей наборов одинаковых деталей в одну опись. Например, 3 винта, 4 шайбы и 4 винта собираются вместе, давая 7 винтов и 4 шайбы.

Дособрать(Х,М, L,O,N) : L и О - это списки структур, чис, О – это список всех элементов списка L, в состав которых не входит деталь X; X – это атом, задающий название некоторой детали; N – это общее количество X в списке L, сложенное с М; М – это целое число, которое используется для суммирования количеств X в L и передается как аргумент в каждом вызове дособрать. При выходе из рекурсии, который обеспечивается выполнением граничного условия, М возвращается как N.

Вывдеталейузла(Р): Р – это список структур чис, который выдается на печать по одной структуре на строке вывода. Цель put(9) выводит литеру с кодом ASCII=9, что соответствует горизонтальной табуляции. С предикатом присоединить мы уже неоднократно встречались ранее.

Полностью Пролог-программа выглядит так:

В этом разделе мы рассмотрим некоторые основные предикаты, полезные при работе со списками. Поскольку Пролог позволяет работать с произвольными структурами данных, списки не могут играть в нем той незаменимой роли, какая им отводится в других языках программирования, таких, как Лисп и Поп-2. Однако независимо от того, будут или не будут использоваться списки в ваших программах, всегда важно представлять себе, как работают предикаты, определения которых рассматриваются в данном разделе, поскольку они основаны на принципах, которые применимы при работе с любыми структурами данных.

Нахождение последнего элемента списка: Цель последний(X, L) согласуется с базой данных, если элемент X является последним элементом списка L. Граничное условие выполняется, когда список L содержит только один элемент. Это условие проверяется первым правилом. Второе правило задает общий рекурсивный случай:

Множество - одна из наиболее важных структур данных, используемых как в математике, так и в программировании. Множество – это набор элементов, напоминающий список, но отличающийся тем, что вопрос о том, сколько раз и в каком месте что-либо входит в множество в качестве его элемента, не имеет смысла. Так, множество (1, 2, 3) – это то же самое множество, что и (1, 2, 3, 1), поскольку значение имеет только сам факт, принадлежит данный элемент множеству или нет. Элементами множеств могут также быть другие множества. Самой фундаментальной операцией над множествами является определение того, принадлежит некоторый элемент данному множеству или нет.

Не должно вызывать удивления, что множества удобно представлять в виде списков. Список может содержать произвольные элементы, включая другие списки, и над списками можно определить предикат принадлежности. Однако условимся, что когда мы представляем множество в виде списка, такой список содержит только по одному элементу на каждый объект, принадлежащий множеству. При работе со списками без повторяющихся элементов упрощаются некоторые операции, такие, как удаление элементов. Итак, нам предстоит иметь дело только со списками без повторяющихся элементов. Предикаты, рассматриваемые ниже, соблюдают это свойство и опираются на него.

Над множествами обычно определяется следующий набор операций (мы будем применять и общепринятые математические обозначения для тех читателей, кто к ним привык):

Принадлежность множеству: X∈Y

X принадлежит некоторому множеству Y, если X является одним из элементов Y.

Пример: а∈{с,а,t}.

Включение: X⊂Y

Множество Y включает в себя множество X, если каждый элемент множества X является также элементом Y. Множество Y может содержать некоторые элементы, которых нет в X.

Пример: {x,r,u}⊂{p,q,r,f,t,u,v,w,x,y,z}.

Пересечение: X∩Y

Пересечением множеств X и Y является множество, содержащее те элементы, которые одновременно принадлежат X и Y.

Пример: {r,a,p,i,d} ∩ {p,i,c,t,u,r,e} = {r,i,p}.

Объединение: X ∪ Y

Объединением множеств X и Y является множество, содержащее все элементы, принадлежащие X или Y или одновременно им обоим.

Пример: {a,b,c} ∪ {с,d,е} = {a,b,c,d,e}.

Это – основные операции, которые обычно используются при работе с множествами. Теперь мы можем приступить к написанию Пролог-программ, реализующих каждую из них. Первая основная операция 'принадлежность' реализуется тем же самым предикатом принадлежит, с которым мы уже встречались несколько раз. Однако в нашем определении принадлежит в граничном случае нет символа «отсечения», поэтому мы можем создавать последовательные элементы списка, используя возвратный ход:

Иногда полезно упорядочить список элементов в соответствии с заданным порядком их следования. Если элементами списка являются целые числа, то для того чтобы определить соблюден ли порядок следования, можно использовать предикат '‹'. Список (1, 2, 3) упорядочен, поскольку любая пара соседних целых чисел этого списка удовлетворяет предикату '‹'. Если элементами списка являются атомы, то мы можем воспользоваться предикатом меньше, о чем уже говорилось в гл. 3. Список [alpha,beta,gamma] упорядочен в алфавитном порядке, поскольку каждая пара соседних атомов этого списка удовлетворяет предикату меньше.

Специалисты по информатике разработали много методов сортировки списков, когда задан некоторый предикат, который говорит нам о том, находятся ли соседние элементы списка в требуемом порядке следования. Мы рассмотрим Пролог-программы для четырех таких методов: наивная сортировка, сортировка включением (вставками), сортировка методом пузырька и быстрая сортировка. В каждой программе используется предикат упорядочено, который может быть определен через '‹' меньше или любой другой предикат по вашему усмотрению, в зависимости от того, какого рода структуры вы сортируете. При этом предполагается, что целевое утверждение упорядочено(Х, Y) доказуемо, если объекты X и Y удовлетворяют требуемому порядку следования, т. е. если X в некотором смысле меньше чем Y.

Один из способов сортировки чисел в порядке возрастания состоит в следующем: вначале создается некоторая перестановка чисел, затем проверяется расположен ли полученный список в порядке возрастания. Если это не так, то создается новая перестановка чисел. Этот метод известен под названием наивная сортировка:

Во всех программах, которые рассматривались до сих пор, база данных использовалась лишь для хранения фактов и правил, с помощью которых определяются предикаты. Можно использовать базу данных и для хранения обычных структур, т. е. таких, которые порождаются при выполнении программы. До сих пор для передачи таких структур от одного предиката к другому мы применяли механизм аргументов. Однако существуют доводы в пользу хранения этой информации в базе данных. Иногда некоторый элемент информации может потребоваться во многих частях программы. Передача его через механизм аргументов может привести к появлению одного – двух дополнительных аргументов у большинства предикатов. Другим доводом является возможность сохранения информации при возвратном ходе. В этом разделе мы рассмотрим три предиката, которые позволяют хранить в базе данных структуры, время жизни которых превышает то, что может быть обеспечено с помощью переменных. Вот эти три предиката: random, вырабатывающий при каждом вызове псевдослучайное целое, найтивсе, порождающий список всех структур, обеспечивающих истинность данного предиката, и генатом, порождающий атомы с различающимися именами.

Цель random(R, N) конкретизирует N целым числом, случайно выбранным в диапазоне от 1 до R. Метод выбора случайного числа основан на конгруэнтном методе с использованием начального числа («затравки») инициализируемого произвольным целым числом. Каждый раз, когда требуется случайное число, ответ вычисляется на основе существующего начального значения, и при этом порождается новое начальное число, которое сохраняется до тех пор, пока вновь не потребуется вычислить случайное число. Для хранения начального числа между вызовами random мы используем базу данных. После того как начальное число использовано, мы убираем (с помощью retract) из базы данных старую информацию о начальном числе, вычисляем его новое значение, и засылаем в базу данных новую информацию (с помощью asserta). Исходное начальное значение – это просто факт в базе данных, с функтором seed имеющим одну компоненту – целое значение начального числа.

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

Проще всего описать граф в базе данных с помощью фактов, представляющих дуги между узлами графа. На рис, 7.3 приведен пример графа и его представления с помощью фактов. Чтобы пройти от узла g к узлу а, мы можем пойти по пути g, d, e, а или по одному из многих других возможных путей. Если мы представляем ориентированный граф, то предикат а следует понимать так, что а(Х, Y) означает, что существует дуга из X в Y, но из этого не следует существование дуги из Y в X. В данном разделе мы будем иметь дело только с неориентированными графами, у которых все дуги двунаправленные. Это допущение совпадает с тем, которое мы делаем в разд. 7.2 при поиске в лабиринте.

Простейшая программа поиска по графу, представленному так, как указано выше, выглядит следующим образом:

Простое число – это целое положительное число, которое делится нацело только на 1 и на само себя. Например, число 5 – простое, а число 15 – нет, поскольку оно делится на 3. Один из методов построения простых чисел называется «решетом Эратосфена». Этот метод, «отсеивающий» простые числа, не превышающие N, работает следующим образом:

1. Поместить все числа от 2 до N в решето.

2. Выбрать и удалить из решета наименьшее число.

3. Включить это число в список простых.

4. Просеять через решето (удалить) все числа, кратные этому числу.

5. Если решето не пусто, то повторить шаги 2-5.

Чтобы перевести эти правила на Пролог, мы определим предикат целые для получения списка целых чисел, предикат отсеять для проверки каждого элемента решета и предикат удалить для создания нового содержимого решета путем удаления из старого всех чисел, кратных выбранному числу. Это новое содержимое опять передается предикату отсеять. Предикат простые - это предикат самого верхнего уровня, такой что простые(N, L) конкретизирует L списком простых чисел, заключенных в диапазоне от 1 до N включительно.

простые(Предел,Рs):- целые(2,Предел,Is),отсеять(Is,Рs).

целые (Min,Max,[Min|Oct]):-Min=‹Max,!, М is Min+1,целые(М,Мах,Ост).

целые(_,_,[]).

отсеять([],[]).

отсеять([I|Is],[I|Ps]):-удалить(I,Is,Нов),отсеять(Нов,Рs).

удалить(Р,[],[]).

удалить (P,[I|Is],[I|Nis]):-not(0 is I mod Р),!,удалить(Р,Is,Nis).

удалить (P,[I|Is],Nis):-0 is I mod Р,!,удалить(Р,Is,Nis).

Продолжая эту арифметическую тему, рассмотрим Пролог-программу, реализующую рекурсивную формулировку алгоритма Евклида для нахождения наибольшего общего делителя (НОД) и наименьшего общего кратного (НОК) двух чисел. Целевое утверждение нод(I,J,K) доказуемо, если K является наибольшим общим делителем чисел I и J. Целевое утверждение нок(I,J,K) доказуемо, если K является наименьшим общим кратным чисел I и J:

нод(I,0,I).

нод(I,J,K):- R is I mod J, нод(J,R,K).

нок(I,J,K):- нод(I,J,R), K is (I*J)/R.

Заметим, что из-за особенностей способа вычисления остатка эти предикаты не являются «обратимыми». Это означает, что для того чтобы они работали, необходимо заблаговременно конкретизировать переменные I и J.

Упражнение 7.10. Если числа X, Y и Z таковы, что квадрат Z равен сумме квадратов X и Y (т. е. если Z²=X²+Y²), то про такие числа говорят, что они образуют Пифагорову тройку. Напишите программу, порождающую Пифагоровы тройки. Определите предикат pythag такой что, задав вопрос

?- pythag(X,Y,Z).

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

Символьным дифференцированием в математике называется операция преобразования одного арифметического выражения в другое арифметическое выражение, которое называется производной. Пусть U обозначает арифметическое выражение, которое может содержать переменную х. Производная от U по х записывается в виде dU/dx и определяется рекурсивно с помощью некоторых правил преобразования, применяемых к U. Вначале следуют два граничных условия. Стрелка означает «преобразуется в»; U и V обозначают выражения, а с – константу:

dc/dx → 0

dx/dx → 1

d(-U)/dx → -(dU/dx)

d(U+V)/dx → dU/dx+dV/dx

d(U-V)/dx → dU/dx-dV/dx

d(cU)/dx → c(dU/dx)

d(UV)/dx → U(dV/dx) + V(dU/dx)

d(U/V)dx → d(UV^-1)/dx

d(U^c)/dx → cU^c-l(dU/dx)

d(lnU)/dx → U^-1(dU/dx)

Этот набор правил легко написать на Прологе, поскольку мы можем представить арифметические выражения как структуры и использовать знаки операций как функторы этих структур. Кроме того, сопоставление целевого утверждения с заголовком правила мы можем использовать как сопоставление образцов. Рассмотрим цель d(E,X, F), которая считается согласованной, когда производная выражения E по константе^[12] X есть выражение F. Помимо знаков операций +, -, *, /, которые имеют встроенные определения, нам нужно определить операцию ^, такую, что X^Y означаете x^y, а также одноместную операцию ~, такую что ~Х означает «минус X». Эти определения операций введены исключительно для того, чтобы облегчить распознавание синтаксиса выражений. Например, после того как d определен, можно было бы задать следующие вопросы:

Если некоторая структура покомпонентно копируется с целью образования новой структуры, то мы говорим, что одна структура отображается в другую. Обычно при копировании каждая компонента слегка изменяется подобно тому, как в гл. 3 мы изменяли одно предложение, превращая его в другое. В том примере нам иногда нужно было скопировать какое-то слово в точности в том виде, в каком оно встретилось в исходном предложении, а иногда при копировании нам нужно было изменить слово. Для этого мы использовали следующую программу, которая отображает первый аргумент предиката преобразовать во второй его аргумент:

преобразовать([],[]).

преобразовать([А|В],[С|D]):- заменить(А,С),преобразовать(В,D).

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

отобспис((_,[],[]).

отобспис((P,[X|L],[Y|M]):- Q =..[P,X,Y],call(Q),отобспис(Р,L,М).

Об этом определении следует сказать несколько слов. Во-первых, определение содержит граничное условие (первое утверждение) и общий рекурсивный случай (второе утверждение). Во втором утверждении используется оператор '=..', формирующий целевое утверждение на основе предиката (Р), входного элемента (X) и переменной (Y), которую предикат Р должен конкретизировать, чтобы образовать измененный элемент. Затем делается попытка согласовать цель Q, в результате чего Y конкретизируется, образуя голову третьего аргумента данного вызова предиката отобспис. Наконец, рекурсивный вызов отображает хвост первого аргумента в хвост второго.

Функции предиката преобразовать может выполнять предикат отобспис. Полагая, что предикат заменить определен как в гл. 3, такое использование отобспис могло бы выглядеть следующим образом:

?- отобспис(заменить,[уоu,аrе,а,computer],Z).

Z = [i, [am, not], a, computer]

Путем упрощения предиката отобспис получается предикат обрабспис, который просто обрабатывает список, применяя некоторый предикат от одного аргумента к каждому элементу списка. При этом новый список не порождается.

обрабспис(_,[]).

обрабспис(Р,[Х|L]):-Q =…[Р,Х],call(Q),обрабспис(Р,L).

Заметим, что предикат печать_строки из гл. 5 можно было бы заменить запросом вида обрабспис(put, L), где L – это строка, которую нужно напечатать.

Отображение применимо не только к спискам; оно может быть определено для структуры любого вида. Например, рассмотрим арифметическое выражение, составленное из функторов * и +, имеющих по два аргумента. Пусть мы хотим отобразить одно выражение в другое, устраняя при этом все умножения на 1. Это алгебраическое приведение могло быть определено с помощью предиката s такого, что s(Op, L, R,Ans) означает, что выражение, состоящее из операции Ор с левым аргументом L и правым аргументом R приводится к упрощенному выражению Ans. Факты, необходимые для устранения умножений на 1, могли бы выглядеть так (из-за коммутативности умножения нужны два факта):

s(*,X,1,X).

s(*,1,X,X).

Эта таблицы упрощений позволяет нам любое выражение вида 1*Х отобразить в X. Посмотрим, как можно воспользоваться этим в программе.

При приведении выражения Е с помощью такой таблицы упрощений, мы вначале должны привести левый аргумент Е, затем привести правый аргумент Е и, наконец, посмотреть, подходит ли этот приведенный результат под случаи, предусмотренные в нашей таблице. Если это так, то мы порождаем новое выражение в соответствии с указаниями таблицы. В качестве «листьев» дерева, представляющего выражение, фигурируют целые числа или атомы, поэтому для приведения листьев к ним самим в граничном условии мы должны использовать встроенный предикат atomic. Как и выше, мы можем использовать ' =..', чтобы разложить выражение Е на функтор и компоненты;

привести(Е,Е):- atomic(E), 1.

привести(Е,F):-Е =.. [Op,L,R],привести(L,Х),привести(R, Y),s(Op,X,Y,F).

Итак, предикат привести отображает выражение Е в выражение F, используя для этого факты, имеющиеся в таблице упрощений s. А что делать, если невозможны никакие упрощения? Чтобы избежать в этом случае неудачного завершения s(Op,X, Y, F), мы должны поместить в конец каждого раздела таблицы упрощений, относящегося к определенному оператору, правило-ловушку. Приведенная ниже таблица упрощений содержит правила для сложения и умножения. Кроме того, в ней выделены правила-ловушки для каждого вида операций.

s(+,X,0,X).

s(+,0,X,X).

s(+,X,Y,X + Y) /* ловушка для + */

s(*,_,0,0).

s(*,0,_,0).

s(*,1,X,X).

s(*,X,1,X).

s(*,X,Y,X*Y). /* ловушка для * */

При наличии правил-ловушек возникает вопрос о выборе способа упрощения некоторых выражений. Например, если нам дано выражение 3+0, мы можем либо использовать первый факт, либо применить правило-ловушку для +. Благодаря способу упорядочения фактов, прежде чем применить правило-ловушку Пролог всегда будет пытаться применить правила для специальных случаев. Поэтому первое решение, полученное предикатом привести, всегда будет являться действительно упрощенным выражением (если оно возможно). Однако альтернативные решения будут иметь не самый простой вид из всех возможных.

Другое упрощение, используемое при выполнении алгебраических преобразований с помощью ЭВМ, известно как свертка констант. В выражении 3*4+a константы 3 и 4 могут быть «свернуты», что дает в результате выражение 12+а. Правила свертки констант могут быть добавлены в соответствующие места приведенной выше таблицы упрощений. Правило для сложения констант выглядит следующим образом:

s(+,X,Y,Z):- integer(X), integer(Y), Z is X+Y.

Соответствующие правила для других арифметических операций имеют аналогичный вид.

В коммутативных операциях, таких как умножение и деление, указанные выше упрощения могут давать различный эффект на выражениях, которые записаны по-разному, но алгебраически эквивалентны. Например, если правило свертки констант задано для умножения, то предикат привести совершенно правильно преобразует 2*3*а в 6*а, но а*2*3 или 2*а*3 будут преобразовываться в самих себя. Чтобы понять, почему это так, подумайте над тем, как выглядят деревья, представляющие эти выражения (см. рис. 7.4).

В первом дереве самое нижнее умножение 2*3 можно свернуть, получив 6, но во втором дереве нет поддеревьев, которые было бы можно свернуть. Однако, используя коммутативность умножения, можно добавить к таблице следующее правило, которое позволит справиться с данным конкретным случаем:

s(*,X*Y,W,X*Z):- integer(Y), integer(W), Z is Y*W.

Более общая алгебраическая система может быть построена путем простого добавления дополнительных s-утверждений вместо увеличения объема программы для привести.

Рис. 7.4

В этой книге мы неоднократно сталкивались с применением встроенных предикатов. На самом деле многие из них можно определить на Прологе, используя более простые встроенные предикаты. В этом разделе мы рассмотрим несколько таких определений. Они могут найти практическое применение у тех программистов, которые используют неполную в каких-либо отношениях Пролог-систему, однако в любом случае они интересны, как примеры программирования на Прологе. Может быть, они наведут вас на мысль о разработке несколько отличающихся версий этих предикатов для своего собственного применения.

Мы можем определить с помощью предиката clause некоторую версию процедуры listing. Определим предикат распеч1 такой, что при согласовании цели распеч1(Х) с базой данных из последней будут выводиться на печать утверждения, заголовки которых совпадают с X. Поскольку определение распеч1 включает использование предиката clause, у которого X задан как первый аргумент, то мы вынуждены поставить условие, что переменная X конкретизирована таким образом, что главный функтор утверждения известен. Рассмотрим определение распеч1:

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

Как и всякое творчество, будь то сочинение музыки, литература или архитектура, программирование располагает множеством способов представления объектов и обработки этих объектов и отношений между ними в конкретной программе. В общем случае для некоторого элемента данных в программе существует несколько возможных способов его представления или обработки. Всякий раз, когда программист решает использовать в данной программе один из них, мы говорим, что программист принял проектное решение.

Новички, впервые столкнувшиеся с задачей выбора проектных решений, часто испытывают трудности. Помочь им может знание возможных вариантов решений, и, кроме того, важно, чтобы руководитель разъяснил им методику программирования в целом, поскольку искусство принятия проектных решений в программировании – это самостоятельная дисциплина. Мы уже пытались затронуть эту проблему в разд. 1.1, где обсуждались различные способы интерпретации утверждений. Эти вопросы связаны с представлением объектов и отношений. В разд. 7.7 мы снова столкнулись с этой проблемой при описании трех различных способов упорядочения списка объектов. Эти вопросы связаны с разными способами обработки объектов и отношений.

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

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

В этом разделе мы рассмотрим те ошибки, которые допускают как начинающие, так и опытные программисты, использующие Пролог. Эти ошибки делятся на две группы: синтаксические ошибки и ошибки управления последовательностью обработки.

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

• Одной из типичных синтаксических ошибок является отсутствие точки '.' в конце утверждения. Точкой должен заканчиваться и любой терм, считываемый с помощью предиката read. После точки нужно оставлять хотя бы один пробел. Поэтому избегайте заканчивать файл вместе с вводом точки последнего утверждения – убедитесь в том, что в самом конце вы не забыли нажать клавишу RETURN.

• Некоторые специальные литеры используются парами. К ним относятся круглые скобки '(' и ')', используемые для группирования термов, квадратные скобки '[' и ']', используемые для задания списков, и фигурные скобки '{' и '}', используемые для записи правил грамматики (см. гл. 9). Сюда же относятся двойные кавычки '"' используемые для ограничения строк и одиночная кавычка '", используемая для задания атомов. Составные скобки '/*' и '*/' используются для ограничения комментариев. Убедитесь, что скобок каждого вида задано не больше и не меньше чем необходимо.

• Остерегайтесь неправильного написания слов, особенно имен встроенных предикатов. Это может привести к самым неожиданным ошибкам, поскольку неверно записанные имена предикатов вряд ли сопоставятся с каким-либо утверждением в базе данных. Или наоборот, они могут неожиданно сопоставиться с утверждениями, заголовок которых случайно совпадает с получившимся именем.

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

• Когда имеете дело с операциями над списками, проверяйте себя с помощью следующих вопросов и ответов:

• Как сопоставляются [а,b,с] и [X|Y]? (X конкретизируется значением a, a Y - значением [b,с]).

• Сопоставимы ли [а] и [X|Y]? (Да, причем X конкретизируется значением a, a Y – значением []).

• Сопоставимы ли [] и [X|Y]? (Нет).

• Имеет ли смысл запись[X, Y|Z]? (Да).

• Имеет ли смысл запись [X|Y,Z]? (Нет).

• Имеет ли смысл запись [Х|[Y|Z]? (Да, это то же самое, что [X,Y|Z])

• Как сопоставляются [a, b] и [А |В]? (А конкретизируется значением а, а В - значением [b]).

• Существует ли более одного способа сопоставления приведенных выражений? (Нет, никогда).

Необходимо подчеркнуть, что когда приходится иметь дело со списками или другими структурами подобного рода, полезно прибегать к помощи «древовидных диаграмм», о которых говорилось в гл. 2.

Даже в тех случаях, когда вы уверены, что в программе нет синтаксических ошибок, она все-таки при попытке согласования целевых утверждений может вести себя непредсказуемо; характерными признаками этого являются: впечатление, что программа никогда не остановится («бесконечный цикл»), неожиданные появления отрицательных ответов (нет), или конкретизация переменных не теми значениями, какие ожидались. Приведем обычные причины подобных ошибок:

• Циклические определения, о которых упоминалось в гл. 3.

• Недостаточность граничных условий или какая-либо другая недоопределенность задачи.

• Бесполезные процедуры, которые переопределяют встроенные предикаты.

• Задание неверного количества аргументов для функтора. Это не рассматривается как синтаксическая ошибка, поскольку количество аргументов функтора может быть разным.

• Неожиданный выход на конец файла при выполнении предиката чтения read.

Остерегайтесь следующих заблуждений относительно принципов работы механизма возврата:

• Заблуждение: Одна из причин использования возвратного хода состоит в том, что Пролог может вернуться к предыдущему сопоставлению и выполнить его снова некоторым другим способом.

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

• Заблуждение: Запись списка [X|Y] может быть сопоставлена с любым отрезком списка, и при этом разбиение списков на части может быть осуществлено несколькими разными способами. Именно этим объясняется действие предиката присоединить (X, Y, [a,b,c,d]).

На самом деле: В записи списка [X|Y] X сопоставляется только с головой списка, a Y сопоставляется только с его хвостом. Цели с предикатом присоединить способны находить разные разбиения списков благодаря возможностям возвратного хода, а не возможностям сопоставления.

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

При использовании трассировки Пролог-система выводит на печать информацию о последовательности отработки целей, чтобы показать, какой стадии выполнения достигла программа. При этом, для того чтобы разобраться в том, что происходит, важно понять, когда и почему определенные цели выводятся на печать. В обычных языках программирования особый интерес представляют моменты входа в подпрограммы и выхода из них. Однако Пролог допускает написание недетерминированных программ, а это вносит сложности, связанные с механизмом возврата. Дело не ограничивается последовательностью входов в утверждения и выходов из них. Механизм возврата может неожиданно вновь запустить выполнение каких-либо утверждений, чтобы построить альтернативное решение. Кроме того предикат отсечения 'Г указывает для каких целей нельзя искать другие решения. Наибольшие трудности, с которыми приходится сталкиваться начинающим программистам, связаны именно с пониманием принципов работы механизма возврата: что на самом деле происходит, когда попытка согласования цели завершается неудачей и система неожиданно начинает возвратный ход. Мы надеемся, что этот процесс достаточно подробно описан в предыдущих главах. Впрочем, в предыдущих главах рассматривалась не только последовательность обработки целей, но также и то, как происходит конкретизация переменных, как цели сопоставляются с заголовками утверждений из базы данных, и, наконец, как согласуются с базой данных подцели. В модели трассировки выполнение Пролог-программ описывается в терминах четырех видов происходящих событий: CALL(ВЫЗОВ), ЕХIT(ВЫХОД), REDО(ПЕРЕДЕЛКА), FAIL(HEУДАЧА).

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

Событие EXIT фиксирует момент, когда некоторая цель только что согласована с базой данных. На наших диаграммах это обозначается стрелкой, выходящей снизу из прямоугольника.

Событие REDO фиксирует момент, когда система возвращается к цели, пытаясь повторно согласовать ее с базой данных. На наших диаграммах это обозначается стрелкой, которая возвращается в прямоугольник снизу.

Событие FAIL фиксирует момент, когда попытка согласовать цель с базой данных заканчивается неудачно. На наших диаграммах это соответствует выходу стрелки вверх из прямоугольника.

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

Обратимся к примеру. Рассмотрим следующее определение предиката потомок:

потомок(Х,Y):- отпрыск(Х,Y).

потомок(X,Z):- отпрыск(Х,Y), потомок(Y,Z).

Этот фрагмент программы находит прямых потомков некоторого лица по заданным в базе данных фактам отпрыск, например:

отпрыск(авраам,измаил).

отпрыск(авраам,исаак).

отпрыск(исаак,исав).

. . .

Первое утверждение программы указывает, что Y является потомком X если Y есть отпрыск X, а второе утверждение указывает, что Z является потомком X если Y есть отпрыск X и если Z является потомком Y. Рассмотрим вопрос:

?- потомок(авраам,Ответ), fail.

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

В заданном вопросе после первой цели следует fail. Это сделано для того, чтобы инициировать механизм возврата и тем самым, получить все возможные решения для цели потомок. Таким образом, в целом вопрос никак не может иметь положительного ответа. Однако цель нашей трассировки состоит в том, чтобы наглядно представить себе ход выполнения программы, вызванный несогласуемостью второй цели (fail).

В начале мы имеем прямоугольники, обозначающие две цели, в которые пока не входила стрелка, представляющая цепочку доказательств (см. рис. 8.1). Первое событие состоит в ВЫЗОВе (CALL) цели потомок. Это - обращение номер 1.

Риc. 8.1

(1) CALL: потомок(авраам,Ответ)

(2) CALL: отпрыск(авраам,Ответ)

Мы сопоставили с целью первое утверждение процедуры потомок и это привело к ВЫЗОВ цели отпрыск. В результате возникла ситуация, где стрелка движется вниз (см. рис. 8.2). Мы продолжаем:

Рис. 8.2.

(2) EXIT: отпрыск (авраам,измаил)

Сразу успешно согласуется первое утверждение и следует ВЫХОД (EXIT) из цели.

(1) EXIT: потомок(авраам,измаил)

Таким образом, мы согласовали первое утверждение процедуры потомок.

(3) CALL: fail

(3) FAIL: fail

(1) REDO: потомок(авраам,измаил)

Затем мы пытаемся согласовать fail, и, как и следовало ожидать, эта попытка завершается НЕУДАЧЕЙ (FAIL). Стрелка возвращается из прямоугольника fail назад выше в прямоугольник потомок. Изображение этой ситуации приведено на рис. 8.3. Стрелка движется вверх. Продолжаем:

Рис. 8.3.

(2) REDO: отпрыск(авраам,измаил)

(2) EXIT: отпрыск(авраам,исаак)

Для цели отпрыск выбрано альтернативное утверждение. Поэтому стрелка может снова выйти вниз из этого прямоугольника.

(1) EXIT: потомок(авраам,исаак)

(4) CALL: fail

(4) FAIL: fail

(1) REDO: потомок(авраам,исаак)

И снова fail заставляет нас отвергнуть это решение и начать возвратный ход. Заметим, что это было совершенно новое обращение к fail (мы вошли в него заново «сверху»).

(2) REDO: отпрыск(авраам,исаак)

(2) FAIL: отпрыск(авраам,Ответ)

На этот раз мы не можем предложить другое сопоставление для цели отпрыск, и потому продолжаем возвратный ход, стрелка отступает вверх, покидая прямоугольник отпрыск.

(5) CALL: отпрыск(авраам,Y)

Здесь произошло следующее: мы выбрали второе утверждение процедуры потомок и выполнили совершенно новое обращение к отпрыск, соответствующее первой подцели (рис. 8.4). Стрелка теперь снова движется вниз. Продолжаем:

Рис. 8.4.

(5) EXIT: отпрыск(авраам,измаил)

(6) CALL: потомок(измаил,Ответ)

Это дает решение, с которым мы теперь уже рекурсивно вызываем потомок. Следует новое обращение к потомок.

(7) CALL: отпрыск(измаил,Ответ)

(7) FAIL: отпрыск(измаил,Ответ)

(8) CALL: отпрыск(измаил, Y2)

(8) FAIL: отпрыск(измаил,Y2)

(6) FAIL: потомок(измаил,Ответ)

У Измаила нет детей (в данном примере) поэтому в обоих утверждениях процедуры потомок подцель отпрыск завершается неудачей, что приводит к неудаче всей цели потомок.

(5) REDO: отпрыск(авраам,измаил)

Мы возвращаемся назад для выбора новой альтернативы.

(5) EXIT: отпрыск(авраам.исаак)

(9) CALL: потомок(исаак,Ответ)

(10) CALL: отпрыск(исаак,Ответ)

(10) EXIT: отпрыск(исаак,исав)

Запускаем новое обращение к потомок и попытка согласовать подцель отпрыск завершается удачно (рис. 8.5). Продолжаем:

(9) EXIT: потомок(исаак,исав)

(1) EXIT: потомок(авраам,исав)

(11) CALL: fail

(11) FAIL: fail

(1) REDO: потомок(исаак,исав)

(9) REDO: потомок(исаак,исав)

Это дает окончательное решение исходного вопроса, однако fail вновь вынуждает включиться механизм возврата, поэтому мы возвращаемся назад по событиям REDO:

(10) REDO: отпрыск(исаак,исав)

(10) EXIT: отпрыск(исаак,иаков)

(9) EXIT: потомок(исаак,иаков)

(1) EXIT: потомок(авраам,иаков)

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

(12) CALL: fail

(12) FAIL: fail

(1) REDO: потомок(авраам,иаков)

(9) REDO: потомок(исаак,иаков)

(10) REDO: отпрыск(исаак,иаков)

(10) FAIL: отпрыск(исаак,Ответ)

(13) CALL: отпрыск(исаак,YЗ)

Теперь мы пытаемся применить второе утверждение процедуры потомок.

(13) EXIT: отпрыск(исаак,исав)

(14) CALL; потомок(исав, Ответ)

Еще одна рекурсия

(15) CALL: отпрыск(исав,Ответ)

(15) FAIL: отпрыск(исав,Ответ)

(16) CALL: отпрыск(исав,Y4)

(16) FAIL: отпрыск(исав,Y4)

(14) FAIL: потомок(исав,Ответ)

(13) REDO: отпрыск(исаак,исав)

(13) EXIT: отпрыск(исаак,иаков)

(17) CALL: потомок(иаков,Ответ)

Пытаемся использовать Иакова.

(18) CALL: отпрыск (иаков,Ответ)

(18) FAIL: отпрыск (иаков, Ответ)

(19) CALL: отпрыск(иаков,Y5)

(19) FAIL: отпрыск (иаков, Y5)

(17) FAIL: потомок(иаков,Ответ)

(13) REDO: отпрыск(исаак,иаков)

(13) FAIL: отпрыск(исаак,YЗ)

(9) FAIL: потомок(исаак,Ответ)

(1) FAIL: потомок(авраам,Ответ) нет

Наконец мы закончили. Надеемся, что этот утомительный пример дал вам возможность понять последовательность событий, происходящих при выполнении Пролог-программы. Вы, вероятно, уже заметили, что для любой цели всегда бывает только один ВЫЗОВ (событие CALL) и одна НЕУДАЧА (событие FAIL), хотя может быть сколько угодно ПЕРЕДЕЛОК (событие REDO) и соответствующих ВЫХОДов (событие EXIT). В следующем разделе мы рассмотрим процесс трассировки для более сложного примера – предиката присоединить.

Упражнение 8.1. В приведенной выше модели ничего не говорится о том, как обрабатывается цель – отсечение '!'. Расширьте эту модель, включив туда учет действия отсечения.

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

Основное назначение трассировки и контрольных точек состоит в том, чтобы программист получил информацию о попытках согласования определенных целей, возникающих в ходе выполнения его программы. Программист может принять решения относительно интересующих его целей и относительно уровня своего вмешательства в процесс их согласования. Первое решение сводится к выбору определенной комбинации полной трассировки и трассировки по контрольным точкам. Вообще говоря, полная трассировка означает выдачу информации обо всех целях, а контрольные точки позволяют программисту получить информацию лишь о тех предикатах, которые он задал. Однако эти возможности могут различными способами комбинироваться. Используемые при этом встроенные предикаты рассмотрены в разд. 6.13. Контрольная точка для какого-либо предиката устанавливается с помощью предиката spy (отмена контрольной точки выполняется предикатом nospy). Установка режима полной трассировки осуществляется предикатом trace (а ее отмена – предикатом notrace).

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

• Когда впервые делается попытка согласовать некоторую цель с базой данных, когда данная цель встречается впервые (событие CALL);

• Когда цель успешно согласована (событие EXIT);

• Когда готовится попытка повторного согласования цели (событие REDO), и

• Когда устанавливается несогласуемость цели с базой данных, поскольку все попытки вновь согласовать ее оказались безуспешными (событие FAIL).

Например, разумным представляется такой выбор: задать трассировку событий CALL и REDO как управляемую, а трассировку событий EXIT и FAIL – как неуправляемую. Более подробное описание этих четырех событий, происходящих при согласовании целей с базой данных, приведено в разд. 8.3,

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

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

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

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

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

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

Грамматика языка – это множество правил, позволяющих определить, какие последовательности слов приемлемы в качестве предложений этого языка. Она определяет, как из слов образуются словосочетания и какие последовательности этих словосочетаний допустимы. Если задана грамматика некоторого языка, то для любой последовательности слов мы можем сказать, является ли она допустимым предложением. И в случае, когда это предложение действительно является допустимым, в результате проверки мы определим, какие естественные группы слов имеются и как они связаны друг с другом. То есть будет определена внутренняя структура предложения.

Очень простой класс грамматик составляют так называемые контекстно-свободные грамматики. Вместо того, чтобы давать формальное определение понятия контекстно-свободной грамматики, мы проиллюстрируем его на одном простом примере. Приведенные ниже правила можно рассматривать как начальную часть грамматики предложений английского языка:

предложение--› группа_существительного, группа_глагола.

группа_существительного--› определитель, существительное.

группа_глагола--› глагол, группа_существительного.

группа_глагола--› глагол.

определитель--› [the].

существительное--› [apple].

существительное--› [man].

глагол--› [eats].

глагол--› [sings].

Рис. 9.1.

Эта грамматика состоит из множества правил, каждое из которых записано в отдельной строке. Каждое правило определяет форму словосочетания определенного вида. Первое правило показывает, что предложение состоит из словосочетания, называемого группа_существительного, за которым следует словосочетание, называемое группа_глагола. Эти два словосочетания есть не что иное, как подлежащее и сказуемое предложения (см. рис. 9.1).

Чтобы представлять, что значит правило в контекстно-свободной грамматике, их следует читать следующим образом: X--›Y как «X может иметь вид Y», а 'X, Y' как «X, за которым следует Y». Так первое правило может быть прочитано:

предложение может иметь вид: группа_существительного, за которой следует группа_ глагола.

Все это очень хорошо, но что представляют собой группа_существительного и группа_глагола? Как мы должны распознавать подобные объекты и как узнать их грамматическую структуру? Ответы на эти вопросы следуют из второго, третьего и четвертого правил грамматики. Например,

группа_существительного может иметь вид: определитель, за которым следует существительное.

Неформально, группа существительного – это группа слов, служащая для обозначения некоторого объекта (или объектов). Такая группа содержит слово – существительное, которое определяет главный класс, которому принадлежит этот объект. Так «the man» (человек) обозначает человека, «the program» (программа) обозначает программу и так далее. Кроме того, в соответствии с приведенной грамматикой, существительному должна предшествовать группа слов, названная «определитель» (см. рис. 9.2). Аналогично, внутренняя структура словосочетания группа_глагола описывается соответствующими правилами. Заметим, что для этого словосочетания существуют два правила. Это вызвано тем, что оно может принимать два вида. Словосочетание группа_глагола может содержать словосочетание группа_существительного, как в предложении «the man eats the apple» (человек ест яблоко), или группа_существительного может отсутствовать, как в предложении «the man sings» (человек поет).

Для чего нужны остальные правила грамматики? Эти правила показывают, как некоторые словосочетания могут быть построены из настоящих слов, а не сводят их к совокупности более мелких словосочетаний. Слова английского языка записываются в квадратных скобках, так что правило:

определитель--› [the].

можно читать так:

определитель может иметь вид: слово the.

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

можно ли разбить заданную последовательность на два словосочетания таким образом, чтобы первое из них было группа_существительного, а второе группа_глагола?

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

Рис. 9.2.

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

Мы увидели, как, имея грамматику языка, можно построить деревья разбора для предложений этого языка, чтобы показать их структуру. Задача построения дерева разбора предложения по заданной грамматике называется задачей синтаксического разбора (анализа). Программа для ЭВМ, которая строит деревья разбора для предложений языка, называется синтаксическим анализатором.

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

предложение

Рис. 9.3.

Основная структура данных, о которой идет речь при обсуждении задачи синтаксического анализа, представляет последовательность слов. Предполагается, что можно выделить подпоследовательности этой структуры, представляющие различные словосочетания, допустимые грамматикой, и, основываясь на этом, показать, что последовательность в целом допустима в качестве словосочетания типа предложение. Так как стандартным способом представления последовательности является список, то входные данные для синтаксического анализатора будут представлены как список языка Пролог. А какое же представление имеют сами слова? Для решаемой здесь задачи знание внутренней структуры слов представляется несущественным, так как все, что необходимо делать,- это сравнивать слова друг с другом. Поэтому естественно представлять слова как атомы языка Пролог,

Давайте разработаем программу, позволяющую определять, является ли заданная последовательность слов предложением в соответствии с приведенной выше грамматикой. Для того чтобы сделать это, программа будет должна выявить внутреннюю структуру заданных ей предложений. Далее будет показано, как разрабатывать программу, которая запоминает эту структуру и делает ее доступной для обозрения, но здесь этот вопрос не будет рассматриваться, чтобы не усложнять программу. Так как программа проверяет, является ли некоторая последовательность слов предложением, то давайте определим предикат предложение. Этот предикат использует лишь один аргумент и соответствует следующему утверждению:

предложение(Х) означает, что X является последовательностью слов, образующей грамматически правильное предложение.

Таким образом, предполагается, что можно задавать вопросы, подобные следующему:

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

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

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

До сих пор рассматривался лишь довольно ограниченный класс грамматических правил. В этом разделе мы введем одно полезное расширение, позволяющее использовать в грамматических правилах дополнительные аргументы. Это «расширение» не выходит за рамки стандартных средств, предоставляемых в Прологе для записи грамматических правил.

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

Давайте рассмотрим пример, показывающий, когда такие дополнительные аргументы полезны. Разберем задачу «согласования числа» между подлежащим и сказуемым предложения. Последовательности слов подобные

*The boys eats the apple.

*The boy eat the apple.

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

Рассматривавшиеся до сих пор грамматические правила, входящие в программу синтаксического анализатора, содержали информацию лишь о том, какая часть входной последовательности обрабатывается каждым из правил. Каждый элемент описания правил должен содержать указание о том, как обрабатывать два дополнительных аргумента, добавленных транслятором грамматических правил. Так что каждое целевое утверждение в результирующем утверждении Пролога обрабатывало определенную часть входной последовательности. Иногда может возникнуть желание определить целевые утверждения иного типа, не связанные непосредственно с обработкой входной последовательности, и рассматриваемый формализм грамматических правил позволяет сделать это. В языке принято следующее соглашение: каждое целевое утверждение, заключенное в фигурные скобки {}, при трансляции не меняется.

Рассмотрим несколько примеров ситуаций, в которых было бы полезно использовать эту возможность. Мы покажем, как можно улучшить «словарь» синтаксического анализатора, т. е. его «знания» о словах обрабатываемого языка.

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

В этом разделе мы подведем итог тем сведениям, которые мы получили о синтаксисе грамматических правил. Затем будут указаны некоторые из возможных расширений и показаны некоторые интересные способы использования грамматических правил. Лучший способ описать синтаксис грамматических правил – сделать это с помощью самих же грамматических правил. Таким образом, здесь приводится некоторое неформальное описание синтаксиса. Отметим, что оно не является абсолютно строгим, так как в нем не учитывается влияние приоритета операторов на синтаксис.

Язык программирования Пролог был разработан коллективом во главе с Колмерауэром приблизительно в 1970 году. Это была первая попытка в разработке языка, который позволял бы программисту описывать свои задачи средствами математической логики, а не с помощью традиционных для программирования конструкций, указывающих что и когда должна делать вычислительная машина. Эта идея нашла отражение в названии языка программирования «Пролог» (английское название «Prolog» является сокращением для Programming in Logic.- Перев.).

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

Если мы намерены обсуждать связь Пролога с математической логикой, то прежде всего необходимо установить, что мы понимаем под логикой. Первоначально логика развивалась как некоторый способ представления определенного класса высказываний, так чтобы можно было, используя формальную процедуру, проверить, справедливы они или нет. Таким образом, логика может быть использована для выражения высказываний, отношений между высказываниями и правил вывода одних высказываний из других. Логическое исчисление специального вида, о котором будет идти речь в этой главе, называется исчисление предикатов. Здесь мы лишь затронем некоторые вопросы исчисления предикатов. Хорошим введением в математическую логику является книга Hodges W. Logic, Penguin Books, 1977. Более подробное обсуждение предмета дано в книге Mendelson E. Intro ductiontoMathematicalLogic, VanNostrandReinhold.[15] Вы так же можете обратиться к любой книге по математической логике. Другая книга, представляющая интерес, написана Chin L. С, Lee R. С.-Т. Symbolic Logic and Mechanical Theorem Proving, Academic Press, 1973.^[16]

Для того чтобы делать высказывания о мире, необходимо уметь описывать объекты этого мира. В исчислении предикатов объекты представляются с помощью термов. Существуют термы трех типов:

• Константа. Это символ, обозначающий индивидуальный объект или понятие. Константы можно рассматривать как атомы языка Пролог и далее будет использоваться соответствующая форма записи. Так, грек, агата и мир являются константами.

• Переменная. Это символ, используемый в разное время для обозначения разных индивидуальных объектов. Переменные вводятся лишь одновременно с кванторами, о которых будет сказано далее. Термы, являющиеся переменными, можно рассматривать как переменные языка Пролог и далее для их обозначения будет использоваться синтаксис, принятый в Прологе. Таким образом, X, Человек и Грек являются переменными.

• Составной терм. Составной терм состоит из функционального символа и упорядоченного множества термов, являющихся его аргументами. Идея состоит в том, что составной терм обозначает тот или иной индивидуальный объект, зависящий от других индивидуальных объектов, представленных его аргументами. Функциональный символ описывает характер зависимости. Например, можно было бы иметь функциональный символ, обозначающий «расстояние» и имеющий два аргумента. В этом случае составной терм обозначает расстояние между объектами, представленными его аргументами. Составной терм можно рассматривать как структуру языка Пролог, имеющую в качестве функтора функциональный символ. Составные термы будут записываться по правилам синтаксиса Пролога так, что, например, жена(генри) может обозначать жену Генри, расстояние(точка1, X) может обозначать расстояние между некоторой заданной точкой и каким-то другим объектом, который будет указан, а классы(мэри, на_следующий_ день_после(Х)) может обозначать классы, в которых преподавала Мэри на следующий после X (необходимо указать день).

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

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

Используя атомарные высказывания, можно различными способами создавать составные высказывания. Именно здесь начинают появляться понятия не имеющие непосредственных аналогов в языке Пролог. Существует несколько способов построения более сложных высказываний из более простых. Прежде всего, можно использовать логические связки. Таким способом можно выразить понятия 'не', 'и', 'или', 'влечет' и 'является эквивалентным'. Далее приведено краткое описание этих связок и вкладываемых в них значений. Здесь ? и ? используются для обозначения произвольных высказываний (формул). В следующей таблице приводятся традиционная форма записи высказываний, используемая в исчислении предикатов, и форма записи, используемая в этой главе.

Так, например, конструкция

мужчина(фред) # женщина (фред)

могла бы быть использована для представления высказывания о том, что Фред является мужчиной или Фред является женщиной. Конструкция

мужчина(джон) -› человек (джон)

могла бы представлять высказывание: то, что Джон является мужчиной, влечет то, что он является человеком (если Джон мужчина, то он – человек). Понятия импликации и эквивалентности иногда при первом знакомстве с ними представляются несколько сложными. Мы говорим, что α влечет β, если всякий раз, когда α истинно, то β также истинно. Мы говорим, что α эквивалентно β, если α истинно в точности в тех же случаях, что и β. В действительности, эти понятия могут быть определены через понятия 'и', 'или', 'не'. А именно:

α-›β значит то же самое, что (~α)#β

α‹-›β значит то же самое, что и (α&β)#(~α&~β)

α‹-›β также значит то же самое, что и (α-›β)&(α-›β)

До сих пор ничего не было сказано о том, что значат переменные, входящие в состав высказывания. В действительности, использование переменных имеет смысл лишь в случае, когда они вводятся с помощью кванторов. Кванторы позволяют делать высказывания о множествах объектов и формулировать утверждения, истинные для этих множеств. В исчислении предикатов имеются два квантора. Если ν обозначает переменную, а ρ – это произвольное высказывание, то коротко значение кванторов можно выразить так:

Первый из кванторов называется квантором общности, так как он указывает на все объекты, существующие во вселенной («для всех ν,…»). Второй квантор называется квантором существования, так как он указывает на существование некоторого объекта (или объектов) («существует ν такой что…»). В качестве примера приведем формулу

all(X, мужчина(Х) -› человек(Х))

которая значит, что какое бы значение X мы не выбрали, если X является мужчиной, то тогда X – человек. Эту формулу можно прочитать так: для любого X, если X является мужчиной, то X является человеком. Или в более простой формулировке: каждый мужчина является человеком. Аналогично

exists(Z, отец(джон,2)& женщина(Z)))

значит, что существует объект, обозначаемый Z такой, что Джон является отцом Z и Z – женщина. Эту формулу можно прочитать так: существует Z такой, что Джон является отцом Z и Z – женщина. Или в более естественной формулировке: Джон имеет дочь. Ниже приведены две более сложные формулы исчисления предикатов:

all(X, животное(Х) -› exists(Y,мать(X,Y)))

all(X, формула_исчисления_предикатов(Х) ‹-› атомарная_формула(Х) # составная_формула(Х))

Как было показано в предыдущем разделе, формулы исчисления предикатов, записанные с использованием связок -› (импликация) и ‹-› (эквивалентность), могут быть переписаны лишь с использованием связок& (конъюнкция), # (дизъюнкция) и ~ (отрицание). В действительности, существует множество разных форм записи формул, и мы ни в коей мере не принесли бы в жертву выразительность формул, если бы должны были полностью отказаться от использования, например, #, -›, ‹-› и exists(X, P). Как следствие этой избыточности, существуют много различных способов записи одного и того же высказывания. При необходимости выполнять формальные преобразования формул исчисления предикатов это оказывается очень неудобным. Было бы значительно лучше, если бы все, что мы хотим сказать, можно было выразить единственным способом. Поэтому здесь будет рассмотрен способ преобразования формул исчисления предикатов к специальному виду – стандартной форме, - обладающему тем свойством, что число различных способов записи одного и того же утверждения меньше по сравнению с использованием других форм. В действительности будет показано, что высказывание исчисления предикатов, представленное в стандартной форме, очень похоже на некоторое множество утверждений языка Пролог. Так что исследование стандартной формы имеет существенное значение для понимания связи между Прологом и математической логикой. В приложении В будет коротко описана программа на Прологе, автоматически транслирующая формулы исчисления предикатов в стандартную форму.

Процесс приведения формулы исчисления предикатов к стандартной форме состоит из шести основных этапов.

Процедура начинается с замены всех вхождений -› и ‹-› в соответствии с их определениями, данными в разд. 10.1. Так, например, формула

аll(Х,мужчина(Х) -› человек(Х))

будет преобразована в формулу

аll(Х,~мужчина(Х) # человек(Х))

На этом этапе обрабатываются случаи применения отрицания к формулам, не являющимся атомарными. Если такой случай имеет место, то формула переписывается по соответствующим правилам. Так, например, формула

~(человек (цезарь)& существующий (цезарь))

преобразуется в

~человек(цезарь) # существующий (цезарь)

а

~аll(Х, человек (X))

преобразуется в

exists(Х,~человек(Х))

Преобразования, выполняемые на втором этапе, основаны на следующих фактах:

~(α&β) значит то же самое, что и (~α) # (~β)

~exists(ν,ρ) значит то же самое, что и all(ν,~ρ)

~all(ν,ρ) значит то же самое, что и exists(ν,~ρ)

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

На следующем этапе удаляются кванторы существования. Это делается путем введения новых констант – сколемовских констант - вместо переменных связанных (введенных) квантором существования. Вместо того чтобы говорить, что существует объект, обладающий некоторым множеством свойств, можно ввести имя для такого объекта и просто сказать, что он обладает данными свойствами. Это соображение лежит в основе введения сколемовских констант. Сколемизация более существенно изменяет логические свойства формулы, чем все обсуждавшиеся ранее преобразования. Тем не менее, она обладает следующим важным свойством. Если имеется формула, то интерпретация, в которой эта формула истинна, существует тогда и только тогда, когда существует интерпретация, в которой истинна формула, полученная из первой в результате сколемизации. Такая форма эквивалентности формул вполне достаточна для наших целей. Так, например, формула

exists(X,женщина(X)& мать(Х,ева))

в результате сколемизации преобразуется в формулу

женщина(g1)& мать(g1, ева)

где g1 – некоторая новая константа, не использовавшаяся ранее. Константа g1 представляет некоторую женщину, мать которой есть Ева. То, что для обозначения константы использован символ» отличный от использовавшихся ранее, существенно, так как в высказывании ничего не говорится о том, что какой-то конкретный человек является дочерью Евы. В утверждении говорится лишь о том, что такой человек существует. Может оказаться, что g1 будет соответствовать тот же самый человек, который соответствует другой константе, но это уже дополнительная информация, никак не выраженная в высказывании.

Если формула содержит кванторы общности, то процедура сколемизации уже не столь проста. Например, если в формуле ^[17]

аll(Х, человек(Х) -› exists(Y,мать(X,Y)))

(«каждый человек имеет мать») заменить каждое вхождение переменной V, связанной квантором существования, на константу g2 и удалить квантор существования, то получится:

all(X, человек(Х) -› мать(X,g2))

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

all(X, человек(Х) -› мать(Х, g2(Х)))

В этом случае функциональный символ g2 соответствует функции, которая каждому конкретному человеку ставит в соответствие его мать.

Этот этап очень прост. Каждый квантор общности просто выносится в начало формулы. Это не влияет на значение формулы. Так, например, формула

all(X, мужчина(Х) -› аll(Y,женщина(Y) -› нравится (X,Y)))

преобразуется в

аll(Х, аll(Y,мужчина(Х) -› (женщина(Y) -› нравится (X,Y))))

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

аll(Х,живой(Х) # мертвый(Х)& аll(Y,нравится(мэри,Y) #грязный(Y))

теперь можно представить так:

(живой(Х) # мертвый(Х))& (нравится(мэри,Y) # грязный (Y))

Эта формула значит, что, какие бы X и Y ни были выбраны, либо X живой, либо X мертвый, и либо Мэри нравится Y, либо Y – грязный.

На этом этапе исходная формула исчисления предикатов претерпела довольно много изменений. Формула больше не содержит в явном виде кванторов, а из логических связок в ней остались лишь & и # (помимо отрицания, входящего в состав литералов). Теперь формула преобразуется к специальному виду - конъюнктивной нормальной форме, характерной тем, что дизъюнктивные члены формулы не содержат внутри себя конъюнкцию. Таким образом, формулу можно преобразовать к такому виду, когда она будет представлять последовательность элементов, соединенных друг с другом конъюнкциями, а каждый элемент является либо литералом, либо состоит из нескольких литералов, соединенных дизъюнкцией. Чтобы привести формулу к такому виду, необходимо использовать следующие два тождества:

(А&В) # С эквивалентно (А # С)&(В # С)

А # (В&С) эквивалентно (А # В)&(А # С)

Так, например, формула:

выходной(Х) # (работает(крис, X) & (сердитый (крис) # унылый(крис)))

(Для каждого X либо X – выходной день, либо Крис работает в день X и при этом он либо сердитый, либо унылый) эквивалентна следующей:

выходной(Х) # (работает(крис,Х)) & (выходной(Х) # (сердитый(крис) # унылый(крис)))

(Для каждого X, во-первых, X является выходным днем или Крис работает в день X; во-вторых, либо X – выходной день, либо Крис сердитый или унылый).

Формула, имеющаяся к началу этого этапа, в общем случае представляет совокупность конъюнктивных членов, являющихся литералами или состоящих из литералов, соединенных дизъюнкцией. Давайте сначала рассмотрим структуру формулы на верхнем уровне, не вникая в детали организации конъюнктивных членов. Формула могла бы иметь, например, следующий вид:

(А & В) & (С & (D & Е))

где переменные обозначают, возможно, сложные высказывания (формулы), но при этом они не содержат внутри конъюнкций. На данном этапе нет никакой необходимости знать структуру вложенности, представляемую использованием скобок, так как все высказывания

(А & В) & (С & (D & Е)) А & (( В& С) & (D & Е)) (А & В) & ((С & D) & Е)

обозначают одно и то же. И хотя структурно эти формулы различны, они имеют один и тот же смысл. Это объясняется тем, что если установлена истинность всех высказываний из некоторого множества, то не имеет значения каким образом они группируются в сложное конъюнктивное высказывание. Не имеет значения, например, как сказать «А истинно и В и С также истинны» или «А и В истинны и С тоже истинно». Следовательно, скобки никак не влияют на смысл формулы. Можно просто написать (неформально):

A & B & C & D & E

Далее, порядок записи этих формул также не имеет значения. Безразлично, как сказать: «А и В истинны» или «В и А истинны», так как оба эти высказывания имеют одно и то же значение. И наконец, нет необходимости указывать знак конъюнкции (&) между формулами, так как заранее известно, что на верхнем уровне формула является конъюнкцией составляющих ее частей. Поэтому, в действительности, значение представленной формулы можно выразить значительно короче, представив ее в виде совокупности {А, В, С, D, Е}. Название «совокупность» подчеркивает, что порядок элементов не имеет значения. Совокупность {А, В, С, D, Е} в точности то же самое, что и {В, А, С, Е, D}, {Е, D, В, С, А} и так далее. Формулы, являющиеся элементами совокупности, полученной в результате преобразования некоторой формулы исчисления предикатов, называются дизъюнктами. Таким образом, каждая формула исчисления предикатов эквивалентна (в некотором смысле) совокупности дизъюнктов.

Давайте рассмотрим несколько подробнее, что представляют собой эти дизъюнкты. Как уже было сказано, они состоят из литералов, соединенных друг с другом с помощью дизъюнкции. В общем случае, дизъюнкт выглядит примерно так:

((V # W) # X) # (Y # Z)

где переменные являются литералами. Теперь те же самые рассуждения, которые были сделаны о структуре формулы на верхнем уровне, можно применить к дизъюнктам. Как и выше, скобки не влияют на значение дизъюнкта. Точно так же несуществен и порядок литералов. Таким образом, можно просто сказать, что дизъюнкт – это совокупность литералов (неявно соединенных дизъюнкцией). В последнем примере это будет {V, W, X, Y, Z}

Теперь исходная формула представлена в стандартной форме. Более того, использовавшиеся для преобразования правила не зависят от того, существует или нет интерпретация, при которой формула истинна. Стандартная форма состоит из совокупности дизъюнктов, каждый из которых представляет совокупность литералов. Литерал – это либо атомарная формула, либо отрицание атомарной формулы. Эта форма является достаточно лаконичной, так как в ней опущены логические связки конъюнкций, дизъюнкций и кванторы всеобщности. Но при этом, очевидно, следует помнить о принятых соглашениях. И каждый раз, имея дело со стандартной формой, понимать, где и что в ней опущено. Рассмотрим, что представляет собой стандартная форма некоторых формул (предполагается, что уже выполнены первые пять этапов преобразования). Прежде всего вернемся к уже рассматривавшемуся примеру:

(выходной(Х) # работает(крис,Х)) & (выходной(Х) # (сердитый(крис) # унылый(крис)))

Эта формула порождает два дизъюнкта. Первый дизъюнкт содержит литералы:

выходной(Х), работает(крис,Х)

а второй литералы:

выходной(Х), сердитый(крис), унылый(крис)

Другой пример. Формула

(человек(адам)& человек(ева))&

((человек(Х) # ~мать(Х,Y)) # ~человек(#))

дает три дизъюнкта. Два из них содержат по одному литералу каждый

человек (адам)

и

человек (ева)

Другой содержит три литерала:

человек(Х), ~мать(Х,Y), ~человек(Y)

В заключении этого раздела рассмотрим еще один пример, демонстрирующий все этапы приведения формулы к стандартному виду. Начнем с формулы

all(X, аll(Y,человек(Y) -› почитает(Y,Х) -› король(Х))

утверждающей, что, если все люди относятся с почтением к некоторому человеку, то этот человек является королем. (Для каждого X, если каждый Y является человеком, почитающим X, то X – это король). После устранения импликации (этап 1) получаем:

аll(Х,~(аll(Y,~человек(Y) # почитает(Y,Х))) # король(Х))

Перенос отрицания внутрь формулы (этап 2) приводит к следующему:

аll(Х,ехists(Y,человек(Y) & ~почитает(Y,Х)) # король(Х))

Затем, в результате сколемизации (этап 3) формула преобразуется к виду:

аll(Х,(человек(f1(Х)) & ~почитает(f1Х),Х)) # король(Х))

где f1 -сколемовская функция. Теперь производится удаление кванторов всеобщности (этап 4), что приводит к формуле;

(человек(f1(X)) & ~почитает(f1(Х),X)) # король(Х)

Затем формула преобразуется к конъюнктивной нормальной форме (этап 5), в которой конъюнкция не появляется внутри дизъюнктов:

(человек(f1(Х) # король(Х)) & (~почитает(f1(Х), X) # король(Х))

Эта формула содержит два дизъюнкта (этап 6). Первый дизъюнкт имеет два литерала:

человек(f1(Х)), король(Х)

а второй дизъюнкт имеет литералы:

почитает(f1(Х),Х), король(Х)

Очевидно, что для записи формул, представленных в стандартной форме, необходим соответствующий способ. Рассмотрим его. Прежде всего, стандартная форма представляет совокупность дизъюнктов. Договоримся записывать дизъюнкты последовательно один за другим, помня при этом, что порядок записи не имеет значения. В свою очередь, дизъюнкт является совокупностью литералов, часть из которых содержит отрицание, а часть не содержат его. Примем соглашение записывать сначала литералы без отрицания, а затем литералы с отрицанием. Эти две группы литералов будем разделять знаком ':-'. Литералы без отрицания при записи будем отделять друг от друга точкой с запятой (;) (помня, конечно, при этом, что порядок записи литералов в каждой группе неважен), а литералы с отрицанием будем записывать без знака отрицания (~), разделяя литералы запятыми. Запись каждого дизъюнкта будет заканчиваться точкой. При такой форме записи дизъюнкт, содержащий отрицания литералов K, L,… и литералы А, В,… мог бы быть представлен так:

A; B;…:- K, L,…

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

(А # В #…) # (~К # -L #…)

что эквивалентно

(A # B # …) # ~(K & L & …)

Это в свою очередь эквивалентно (К & L &…) -› (А # В #…)

Если записать ',' вместо 'и', ';' вместо 'или' и ':-' вместо 'является следствием', то дизъюнкт естественным образом примет следующий вид:

A; B;…:- K, L,…

С учетом этих соглашений формула

(человек(адам) & человек(ева)) &((человек(Х) # ~мать(Х,Y)) # ~человек(Y))

записывается так:

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

В 60-х годах в этой области наблюдалась большая активность, связанная с возможностью использования вычислительных машин для автоматического доказательства теорем. Именно эта область научной деятельности, по-прежнему остающаяся источником новых идей и методов, дала жизнь идеям, легшим в основу Пролога. Одним из фундаментальных достижений того времени явилось открытие Дж. А. Робинсоном принципа резолюций и его применение к автоматическому доказательству теорем. Резолюция – это правило вывода, говорящее о том, как одно высказывание может быть получено из других. Используя принцип резолюций, можно полностью автоматически доказывать теоремы, выводя их из аксиом. Необходимо лишь решать, к каким из высказываний следует применять правило вывода, а правильные следствия из них будут строиться автоматически.

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

Из

унылый(крист); сердитый(крис):- рабочий_день(сегодня), идет_дождь(сегодня).

и

неприятный(крис):- сердитый(крис), усталый(крис).

следует

унылый(крис); неприятный(крис):- рабочий_день(сегодня), идет_дождь(сегодня), усталый(крис).

На естественном языке это звучит так. Если сегодня рабочий день и идет дождь, то Крис – унылый или сердитый. Кроме того, если Крис сердитый и усталый, то он неприятен. Поэтому, если сегодня рабочий день, идет дождь и Крис усталый, то Крис является унылым или неприятным.

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

Рассмотрим один пример применения правила резолюций при наличии переменных:

человек(f1(Х)); король(Х):-. (1)

король(Y):- почитает(f1(Y),Y). (2)

почитает(Z,артур):- человек(Y). (3)

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

король(артур):- человек(f1(артур)). (4)

(Y в (2) сопоставлен с артур в (3), a Z в (3) сопоставлен с fl(Y) в (2)). Теперь можно применить правило резолюций к (1) и (4), что дает:

король(артур); король(артур):-.

Это эквивалентно факту, гласящему, что Артур является королем.

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

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

Метод резолюций имеет одно важное формальное свойство – он является полным для доказательства несовместности множества дизъюнктов. Это значит, что если множество дизъюнктов несовместно, то используя метод резолюций всегда можно вывести из данного множества дизъюнктов пустой дизъюнкт:

:-.

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

Каким образом это свойство метода резолюций может помочь нам? Имеет место следующий факт:

Если множество формул {А₁, A₂,…, А_n} совместно, то формула В является следствием формул {A_l, A₂,…, A_n} тогда и только тогда, когда множество формул {А₁, A₂,…, А_n ⌉В} - несовместно.

Таким образом, если множество гипотез совместно, то необходимо лишь добавить к нему дизъюнкты, соответствующие отрицанию высказывания, которое следует доказать. Резолюция даст пустой дизъюнкт в точности тогда, когда доказываемое высказывание следует из данных гипотез. Дизъюнкты, добавляемые к множеству гипотез, называются целевыми дизъюнктами. Отметим, что целевые дизъюнкты ничем не отличаются от гипотез – и те и другие являются дизъюнктами. Так что, если задано множество дизъюнктов {А₁, А₂, …, А_п} и требуется проверить несовместность этого множества дизъюнктов, то в действительности невозможно определить, идет ли речь о доказательстве того, что ⌉А₁ следует из A₂, А₃, …, А_п или что ⌉А₂ следует из A₁, A₃, …, А_n, или что ⌉А₃ следует из А₁, А₂, A₄,…, А_n и так далее. Именно это является причиной того, что необходимо указывать какие дизъюнкты в действительности являются целевыми дизъюнктами. Для системы, использующей метод резолюций, все перечисленные задачи эквивалентны.

Легко увидеть, как можно получить пустой дизъюнкт в примере с королем Артуром, если добавить целевой дизъюнкт:

:- король(артур). (5)

(это дизъюнкт для ~король(артур)). Ранее уже было показано, как дизъюнкт

король(артур); король(артур):-. (6)

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

король(артур):-. (7)

И наконец, резолюция дизъюнктов (6) и (7) дает

:-.

Таким образом, использование метода резолюций позволило доказать следствие, что Артур является королем.

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

На решение этих вопросов направлено много различных улучшений исходного принципа резолюций. В следующем разделе рассматриваются некоторые из них.

10.5. Хорновские дизъюнкты

Рассмотрим теперь модификацию метода резолюций, разработанную для случая, когда все дизъюнкты имеют некоторый определенный вид – когда они являются хорновскими дизъюнктами, Хорновский дизъюнкт – это дизъюнкт, содержащий не более одного литерала без отрицания. Оказывается, что если процедура доказательства теорем используется для определения значений вычислимых функций, то вполне достаточно использовать для этого лишь хорновские дизъюнкты. Так как метод резолюций в случае хорновских дизъюнктов также является относительно простым, то естественно выбрать хорновские дизъюнкты в качестве основы для процедуры доказательства теорем, применяемой в практической системе программирования, Рассмотрим коротко, что представляет метод резолюций, если ограничиться хорновскими дизъюнктами.

Прежде всего, очевидно, что существуют два вида хорнов-ских дизъюнктов – дизъюнкты, содержащие один литерал без отрицания и дизъюнкты, не содержащие таких литералов. Будем называть эти два типа хорновских дизъюнктов соответственно дизъюнктами с заголовком и дизъюнктами без заголовка. Следующие примеры иллюстрируют указанные типы дизъюнктов (необходимо помнить, что литералы без отрицания записываются слева от знака ':-'):

холостяк(Х):- мужчина(Х), неженат(Х).

:- холостяк(Х).

В действительности, рассматривая множества хорновских дизъюнктов (включая целевые утверждения), необходимо выделять лишь такие множества, в которых все дизъюнкты за исключением одного имеют заголовки. Это значит, что каждая разрешимая задача (задача доказательства теоремы), которая может быть выражена с помощью хорновских дизъюнктов, может быть представлена в таком виде, что:

• Имеется только один дизъюнкт без заголовка. Все остальные дизъюнкты имеют заголовки.

Так как совершенно не имеет значения, какие дизъюнкты считать целевыми, то можно принять решение рассматривать дизъюнкт без заголовка как целевой, а все остальные дизъюнкты – как гипотезы. Такое решение выглядит довольно естественно.

Почему мы должны рассматривать лишь такие совокупности хорновских дизъюнктов, которые вписываются в эту схему? Во-первых, легко видеть, что для того, чтобы задача была разрешима, необходимо наличие по крайней мере одного дизъюнкта без заголовка. Это объясняется тем, что в результате применения правила резолюций к двум хорновским дизъюнктам с заголовками вновь получается хорновский дизъюнкт с заголовком. Поэтому, если все дизъюнкты имеют заголовки, то единственное что можно делать – это выводить другие дизъюнкты с заголовками. Так как пустой дизъюнкт не имеет заголовка, то он никогда не будет выведен. Второе требование – это необходим лишь один дизъюнкт без заголовка – обосновать несколько труднее. Од-нако оказывается, что, если среди аксиом имеют несколько дизъюнктов без заголовка, то каждое доказательство нового дизъюнкта методом резолюций может быть преобразовано в доказательство, в котором используется не более чем один из них. Поэтому, если пустой дизъюнкт следует из данного множества аксиом, то он следует и из его подмножества, содержащего все дизъюнкты с заголовками и не более одного дизъюнкта без заголовка.

Давайте подведем итог и посмотрим, как Пролог вписывается в рассмотренную выше схему. Как было показано, некоторые формулы, представленные в виде совокупности дизъюнктов, выглядят в точности так же, как и утверждения в Прологе, в то время как другие формулы имеют несколько отличный вид. Формулы, имевшие вид утверждений Пролога, есть в действительности не что иное, как формулы, представимые в виде хорновских дизъюнктов. При записи хорновского дизъюнкта в соответствии с принятыми соглашениями, количество атомарных формул слева от знака ';-' не может превышать одну. В общем случае, дизъюнкты могут иметь несколько таких формул (они соответствуют литералам, представляющим атомарные формулы без отрицания). В Прологе непосредственно можно представить только хорновские дизъюнкты. Утверждения программы на Прологе соответствуют хорновским дизъюнктам с заголовком (в рамках определенной процедуры доказательства теорем). А что в Прологе соответствует целевому дизъюнкту? Очень просто, вопрос в Прологе

?- A₁, A₂,…, A_n

в точности соответствует хорновскому дизъюнкту без заголовка:- A₁, A₂,…, А_п

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

Пролог-система основывается на процедуре доказательства теорем методом резолюций для хорновских дизъюнктов. Конкретная стратегия, используемая при этом, является разновидностью линейной входной резолюции. При использовании этой стратегии, выбор дизъюнктов для резолюции на каждом шаге ограничен следующими условиями. Процедура начинается с применения правила резолюций к целевому дизъюнкту и к одной из гипотез, что дает новый дизъюнкт. Затем производится резолюция этого дизъюнкта и одной из гипотез, что дает еще один новый дизъюнкт. Затем правило резолюций применяется к последнему полученному дизъюнкту и к одной из гипотез и так далее. На каждом этапе правило резолюций применяется к последнему из вновь полученных дизъюнктов и к одной из исходных гипотез. Правило резолюций никогда не применяется, если оба дизъюнкта были выведены на предыдущих этапах или являются исходными гипотезами. С точки зрения Пролога, последний выведенный дизъюнкт можно рассматривать как конъюнкцию целевых утверждений, которые еще надо доказать (согласовать с базой данных). В начальный момент это вопрос, а в конце процесса, при благоприятных условиях,- это пустое утверждение. На каждом этапе ищется утверждение, заголовок которого сопоставим с одним из целевых утверждений. Если необходимо, происходит конкретизация переменных. Удаляется целевое утверждение, с которым произошло сопоставление, а затем к целевым утверждениям, которые необходимо согласовать, добавляется тело найденного утверждения, в котором произведена конкретизация переменных. Так, например, начав с вопроса

В нескольких последних разделах было показано, как используются в Прологе идеи доказательства теорем. Можно видеть, что наши программы довольно похожи на гипотезы о проблемной области, а вопросы очень похожи на теоремы, которые нам хотелось бы доказать. Таким образом, программирование на Прологе имеет мало общего с процессом выдачи машине указаний о том, что и когда следует делать. Оно скорее состоит в передаче машине информации, которая предполагается истинной, и обращении к ней с вопросами о возможных следствиях из этой информации. Идея о том, что программирование должно выглядеть именно так, привлекательна и она привела многих специалистов к исследованию концепции логического программирования, то есть программирования на языке логики, как практической альтернативы обычному. Такой подход резко отличается от использования традиционных языков программирования подобных Фортрану или Лиспу, при программировании на которых необходимо как можно более подробно описать что и когда должна делать вычислительная машина. Преимущества логического программирования должны проявиться в том, что программы станут более понятными. Они не будут содержать затрудняющие понимание детали относительно того как решать задачу, а скорее будут напоминать описание того, что собой представляет результат решения. Кроме этого, если программа выглядит как описание (спецификация) того, что предполагается получить, то и относительно проще проверить (вручную или, возможно, используя какие-то автоматические средства), делает ли она в действительности то, что требуется. Подводя итог, можно сказать: преимущества языка логического программирования были бы следствием того, что программы обладают как декларативной семантикой, так и процедурной. Мы бы знали что программа вычисляет, а не как она это делает. Мы не будем здесь рассматривать логическое программирование вообще. Интересующемуся этим вопросом читателю рекомендуем обратиться к книге Ко-walski R. Logic for Problem Solving, North Holland, 1979.

Давайте рассмотрим Пролог как кандидата на место языка логического программирования и посмотрим, насколько хорошо он для этого подходит. Прежде всего, ясно, что некоторые программы на Прологе действительно представляют описание проблемной области на языке логики. Запись:

В этой главе рассматривается перечень программных проектов, которые вы могли бы попытаться осуществить для развития навыков программирования на Прологе. Некоторые из этих проектов довольно просты, зато другие вполне могут быть предложены в качестве «курсовой работы» в рамках учебного курса по Прологу. Более простые проекты следует использовать как дополнение к упражнениям, приведенным в предыдущих главах. В целом при перечислении проектов мы не придерживались какого-то определенного порядка, хотя те из них, что содержатся в разд. 11.2, в большей мере допускают расширения, содержат вызов честолюбию, но и требуют некоторой подготовки или знакомства с литературой по различным вопросам искусственного интеллекта и информатики. Небольшая часть проектов требует знаний из определенных разделов науки, поэтому если вы не специалист в области математической физики, то не отчаивайтесь, если не сможете написать программу дифференцирования трехмерных векторных полей.

Целая подборка Пролог-программ опубликована в отчете Coehlo H., Cotta J. С, Pereira L. M. How to solve it with Prolog, Laboratorio Nacional de Engenharia Civil, Lisbon, Portugal. В нем содержится свыше ста небольших примеров, задач и упражнений из таких областей как вывод умозаключений на основе базы данных, естественный язык, символьное решение уравнений, и т. д. Этот отчет по своему характеру не рассчитан на использование для обучения, поэтому приведенные в нем Пролог-программы снабжены лишь краткими пояснениями.

1.Определить предикат лин для «линеаризации» списка путем построения нового списка, не содержащего списков в качестве элементов, но включающего все атомы исходного списка. Например, следующее целевое утверждение будет согласовано с базой данных:

?- лин([а,[b,с],[[d],[],е]], [a,b,c,d,e]).

Существует по меньшей мере шесть различных способов написания этой программы.

2. Составить программу для вычисления интервала (в днях) между двумя датами, заданными в формате День-Месяц, считая что обе они относятся к одному и тому же невисокосному году. Заметим, что '-' это просто инфиксная форма задания 2-х местного функтора. Например, следующее целевое утверждение будет согласовано с базой данных:

интервал(3-март, 7-апрель, 35).

3. В главе 7 приведены сведения, достаточные для составления программ дифференцирования и упрощения арифметических выражений. Усовершенствуйте эти программы так, чтобы они могли обрабатывать выражения с тригонометрическими функциями и, если есть желание, с операциями дифференциальной геометрии, такими как div, grad и rot.

4. Написать программу, осуществляющую символическое отрицание выражения исчисления высказываний. Это выражение строится из атомов, одноместного функтора not и двухместных функторов and (и), or (или) и implies (импликация). Задать соответствующие описания операторов для этих функторов. Выражение, являющееся результатом отрицания, должно быть представлено в простейшей форме, когда not применяется только к атомам. Например, отрицание выражения

р implies (q and not r)

должно выглядеть следующим образом: р and (not q or r)

5. Частотный словарь – это перечень слов, встречающихся в данном тексте, выписанный в алфавитном порядке с указанием числа вхождений каждого слова в тексте. Написать программу составления частотного словаря по списку слов, представленных в виде строк Пролога. Учтите, что строки – это списки кодов ASCII.

6. Написать программу, воспринимающую простые английские предложения, имеющие следующий формат

На основе ранее введенных предложений программа должна выдавать соответствующий ответ (yes (да), no (нет), ok (принято), unknown (неизвестно)). Например,

John is a man.

ok

A man is a person.

ok

Is John a person?

yes

Is Mary a person?

unknown

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

man(john).

person(X):- man(X).?- person (john).?- person(mary).

Если это окажется удобным, используйте правила грамматики. Головное утверждение для управления диалогом может иметь вид:

беседа:- repeat, read (Предложение), анализ(Предложение, Утверждение), ответ(Утверждение), Утверждение = stop.

7. Альфа-бета (α-β) алгоритм – это один из методов обхода дерева игры, который упоминается во многих книгах по искусственному интеллекту. Реализуйте альфа-бета алгоритм на Прологе.

8. Задача об N-ферзях также широко распространена в литературе по программированию. Реализовать программу нахождения всех способов размещения 4 ферзей на шахматной доске размером 4?4, причем так, чтобы ни один ферзь не угрожал другому. Один из возможных подходов состоит в создании генератора перестановок, который затем проверяет каждую перестановку, чтобы убедиться, что все ферзи размещены правильно.

9. Написать программу, которая переписывает выражение исчисления высказываний (см. задачу 4), заменяя все вхождения and, or, implies и not единственной связкой nand. Определение связки nand задается следующим тождеством

(α nand β)⌉≡(α∧β)

10. Один из способов представления целых положительных чисел состоит в том, чтобы представлять их в виде термов Пролога с использованием целого числа 0 и функтора S с одним аргументом. Так, число 0 представляет само себя, 1 представляется как S(0), 2 как S(S(0)) и т. д. (каждое число представляется в виде функтора S примененного к представлению числа, на единицу меньшего, чем данное). Написать определение стандартных арифметических операций: сложение, умножение и вычитание, использующих указанное представление чисел. Например, нужно определить предикат plus который действует следующим образом:

?- plus(s(s(0)),s(s(s(0))),X)

X=s(s(s(s(s(0)))))

(2+3=5). Для вычитания нужно ввести соглашение о том, что делать, когда результат операции не является положительным целым числом. Определите также предикат «меньше чем». Какие аргументы нужно конкретизировать, чтобы ваши определения работали правильно? Что произойдет, если этого не сделать? Как это соотносится со стандартными арифметическими операциями Пролога? Попытайтесь определить более сложные арифметические операции, такие как деление нацело и извлечение квадратного корня.

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

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

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

3. Написать процедуры обращения и умножения матриц.

4. Компиляцию с языка высокого уровня на язык низкого уровня можно представить себе как последовательное преобразование синтаксических деревьев. Написать такой компилятор сначала для компиляции арифметических выражений. Затем добавить управляющие структуры (типа if-then-else). Точное соблюдение синтаксиса ассемблера в данном случае не столь существенно. Например, арифметическое выражение х+1 может быть «упрощено» до ассемблерной операции inc x, где inc определена как одноместная операция. Проблема распределения регистров может быть отложена на потом за счет предположения, что объектный код предназначен для выполнения на машине с магазинной (стековой) памятью (безадресная машина),

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

6. Разработать формализм для описания набора аксиом, например, из теории групп, евклидовой геометрии, денотационной семантики, и исследовать проблему создания программы доказательства теорем для этих областей.

7. Интерпретатор утверждений Пролога может быть написан на самом Прологе. Напишите интерпретатор, реализующий иные семантики выполнения Пролога, такие как более гибкий порядок выполнения (вместо жесткого слева-направо), возможно, с использованием какого-нибудь «расписания» или планировщика.

8. Ознакомиться по литературе по искусственному интеллекту с вопросом построения планов решения задач, и реализовать генератор планов.

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

10. Написать программу, которая, используя правила грамматики, осуществляет разбор предложений вида;

Fred saw John.

Магу was seen by John.

Fred told Mary to see John.

John was believed to have been seen by Fred.

Was John believed to have told Mary to see Fred?

11. В исследованиях по искусственному интеллекту используется система специальных правил (продукций), которая представляет собой последовательность правил вида «Если ситуация, то действие». Как оказалось, в задачах искусственного интеллекта с помощью таких правил удобно описывать «экспертные знания». Например, для реальных экспертных систем, использующих такие правила, типичны следующие предложения, содержащие «экспертные знания»:

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

Игра в шахматы; Если белый король может быть придвинут к черному слону и при этом расстояние от белого короля до этого слона более одной клетки, то тогда этот слон в безопасности.

Медицина: Если культура высевается из крови и граммреакция организма отрицательна и морфологически организм есть палочка, и пациент является «хозяином» организма, то имеется 60% шансов на то, что этот организм есть Pseudomonas aeruqinosa.

Напишите Пролог-программу интерпретации набора продукционных правил. Рассмотрите такие области как определение растений или животных по характерным признакам. Например, подобное правило из ботаники могло бы выглядеть так:

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

Таким образом, если программа спросит нас: «у цветка квадратный стебель?», то ответив «нет» мы тем самым исключаем возможность того, что он принадлежит семейству Labiatae.

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

13. Написать программу доказательства теорем в исчислении предикатов.

14. Написать программу-«психиатр», которая выдает ответы, основанные на ключевых словах, имеющихся во вводимой информации. Эта программа напоминает ту, что рассматривалась в гл. 3, и которая заменяла ключевые слова в предложении на другие слова. Типичный диалог такой программы мог выглядеть следующим образом (ответы программы выделены курсивом):

What is your problem? На что жалуетесь?

This is too much work. Очень много работы.

What else do you regard as too much work? Что еще вы имеете в виду, говоря, что очень много работы?

Writing letters. Написание писем.

I see. Please continue.Понятно, продолжайте.

Also washing my mother's car. А также мытье машины моей матери.

Tell me more about your family. Расскажите подробнее о вашей семье.

Why should I? Зачем это?

Why should you what? Что зачем?

Здесь ключевыми словами были this is, mother и why. Недостаток подходящих ключевых слов вызывал ответ I see. Please continue.

15. Написать программу, разбирающую предложения с сообщениями о событиях в некотором учреждении, такие как «Smith will be in his office at 3 pm for a meeting.» (Смит будет в своем учреждении в 3 часа дня для участия в собрании). Программа должна выдавать на печать «суть» предложения, сообщая кто, где и когда, следующим образом:

who: smith Кто: Смит

where: office Где: контора

when: 3 pm Когда: 3 часа дня

what: meeting Что: собрание

Эта «суть» должна быть занесена в базу данных в виде утверждений, с тем чтобы можно было получить ответ на такие вопросы:

Where is Smith at 3 pm? Где Смит в 3 часа?

where: office Где: контора

what: meeting Что: собрание

16. Написать интерфейс для общения на естественном (английском) языке с файловой системой вашей ЭВМ, чтобы можно было получать ответы на такие вопросы:

How many files David own? Сколько файлов принадлежат Дейвиду?

Does Chris share PROG.MAC with David?  Использует ли Крис файл PROG.MAC совместно с Дейвидом?

When did Bill change file Когда Билл изменил свой VIDEO.C? файл VIDEO.C?

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