У Клоксин - ПРОГРАММИРОВАНИЕ НА ЯЗЫКЕ ПРОЛОГ

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

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

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

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

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

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

1.1. Факты

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

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

Важно соблюдать следующие правила:

• Имена всех отношений и объектов должны начинаться со строчной буквы. Например, нравится, джон, мэри.

• Сначала записывается имя отношения. Затем через запятую записываются имена объектов, а весь список имен объектов заключается в круглые скобки.

• Каждый факт должен заканчиваться точкой.

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

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

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

ценный(золото). Золото является ценным,

женщина(джейн). Джейн — женщина.

владеет(джон,золото). Джон владеет золотом.

отец(джон,мэри). Джон является отцом Мэри.

дает(джон,книга,мэри). Джон дает Мэри книгу.

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

Теперь пришла пора сказать несколько слов о терминологии. Имена объектов, список которых в каждом факте заключен в круглые скобки, называются аргументами. Заметим, что в программировании значение слова «аргумент» не имеет ничего общего с его общеупотребительным значением, используемым в контексте слов «диспут», «дебаты», «дискуссия», «спор» и т. п. Имя отношения, которое записывается непосредственно перед круглыми скобками, называется предикат.[2] Таким образом, ценный – это предикат, имеющий один аргумент, а нравится – предикат с двумя аргументами.

Имена объектов и отношений являются полностью произвольными. Например, вместо терма нравится(джон,мэри) мы могли бы с таким же успехом представить это как a(b,c), помня при этом, что а значит нравится, b означает Джон, а с – Мэри. Однако обычно мы выбираем имена таким образом, чтобы они сами напоминали нам, что они значат. Следовательно, мы заранее должны решить, что значат наши имена и каким должен быть порядок аргументов. С этого момента необходимо последовательно придерживаться принятых соглашений.

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

играть(джон,мэри,футбол).

играть(джейн, джим,бадминтон).

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

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

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

1.2. Вопросы

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

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

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

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