В данной главе приводится более полное описание тех элементов Пролога, которые были введены в предыдущей главе. Пролог предоставляет средства для структурирования данных, а также средства для структурирования той последовательности, в которой совершаются попытки согласовать целевые утверждения с базой данных. Для структурирования данных необходимо знание синтаксических правил, используемых для обозначения данных. Структурирование последовательности, в которой будут совершаться попытки согласовать целевые утверждения с базой данных, предполагает знание принципов работы механизма возврата.
2.1. Синтаксические правила
Синтаксические правила языка описывают допустимые способы соединения слов. В соответствии с нормами английского языка предложение «I see a zebra» («я вижу зебру») является синтаксически правильным в отличие от предложения «zebra see I а» («зебра видит я»). В первой главе синтаксис Пролога явно не обсуждался, просто показывалось на примерах, как выглядят некоторые элементы Пролога. В данном разделе приводится краткое описание синтаксических правил для уже знакомых нам элементов Пролога.
Пролог-программы состоят из термов. Терм – это либо константа, либо переменная, либо структура. Каждый из этих термов фигурировал в предыдущей главе, но не назывался там таким именем. Терм записывается как последовательность литер. Литеры делятся на четыре категории:
ABCDEFGHIJKLMNOPQRSTUVWXYZ
abсdefghijklmnopqrstuvwxyz
0123456789
+-*/\^<>~:.?@#$&
Первая строка состоит из прописных букв. Вторая строка – из строчных букв. В третьей строке – цифры. В четвертой строке перечислены специальные литеры (спецзнаки). В действительности спецзнаков больше, чем показано в четвертой строке, но остальные используются только в особых случаях, обсуждаемых ниже[5]В книге ничего не говорится о буквах русского алфавита. Мы будем считать, что в набор допустимых литер Пролога входят русские буквы – строчные и прописные. - Прим. ред.
. Для термов каждого типа, таких как константа, переменная, структура, имеются свои правила образования имен термов из литер. Ниже вкратце обсуждаются каждый из типов термов.
2.1.1. Константы
Константами являются поименованные конкретные объекты или конкретные отношения. Существует два вида констант: атомы и целые числа. Примерами атомов являются имена, приводившиеся в предыдущей главе:
нравится мэри джон книга вино имеет драгоценности может_украсть
Специальные символы, используемые Прологом для обозначения вопросов '?-' и правил ':-', также являются атомами. Есть два вида атомов: составленные из букв и цифр и составленные из спецзнаков. Первые, как мы видели в предыдущей главе, должны обычно начинаться со строчной буквы. Атомы, составленные из спецзнаков, как правило, состоят только из спецзнаков. Иногда возникает необходимость иметь атом, начинающийся с прописной буквы или цифры. Если атом заключается в одиночные кавычки, то его имя может содержать любые литеры. И наконец, для простоты чтения внутрь атома можно включать специальную литеру – подчеркивание '_'. Ниже приведено несколько атомов:
а
свободный
=
'джордж-смит'
--›
джордж_смит
ieh2304
Следующие объекты не являются атомами:
2304ieh
джордж-смит
Пустой
_ альфа
Другой вид констант, целые числа, используется для представления числовых данных, что позволяет выполнять над ними арифметические операции. В предыдущей главе не обсуждались способы выполнения арифметических операций в Прологе, такие средства будут определены ниже. Целые числа состоят только из цифр и не могут содержать десятичной запятой. В этой книге будут использоваться сравнительно небольшие положительные числа, такие как
0 1 999 512 8192 14765 6224
Пролог реализован на различных ЭВМ и в зависимости от того, на какой именно ЭВМ работает программист, ему может быть разрешено или не разрешено использовать большие или отрицательные числа. Однако в данной книге приводятся только примеры, допустимые для любой из существующих версий Пролога. Можно утверждать, что всегда разрешается использовать числа из диапазона от 0 до 16 383. Возможно, что на доступной читателю ЭВМ допустимы и другие числа (превышающие 16 383 или отрицательные), однако дальнейшее изложение этого не учитывает. Может быть, это покажется удивительным, однако в задачах, в которых оказался полезным Пролог, как правило, не нужны средства для работы с очень большими, дробными или отрицательными числами. Тем не менее, поскольку Пролог является расширяемым языком, программист, обладающий соответствующими ресурсами, может без особого труда добавить к системе предикаты, определяющие такие возможности. Например, некоторые Пролог-системы предоставляют пользователям библиотечные программы, определяющие операции над рациональными числами и числами произвольной точности.
2.1.2. Переменные
Второй разновидностью термов в Прологе являются переменные. Переменные внешне похожи на атомы, за исключением того, что они начинаются с прописной буквы или знака подчеркивания '_'. Переменная служит для представления объекта, на который нельзя сослаться по имени. Здесь можно провести аналогию с использованием местоимений в естественном языке. В приведенных выше примерах фигурировали переменные с такими именами как X, Y и Z. Однако имена могут быть сколь угодно длинными, например:
Ответ
Ввод
Большая_Выплата
_3_слепые_мыши
Иногда возникает необходимость в использовании переменной, имя которой не будет нигде употребляться. Например, если необходимо определить, нравится ли кому-нибудь Джон, и при этом не важно, кому именно он нравится, можно использовать анонимную переменную.
Анонимная переменная – это одиночный знак подчеркивания '_'. Наш пример с Джоном записывается на Прологе следующим образом:
?- нравится(_,джон).
Если в одно утверждение входят несколько анонимных переменных, их можно интерпретировать неоднозначно. Это характерная особенность, присущая только анонимной переменной. Она позволяет избавить программиста от необходимости придумывать разные имена переменным в тех случаях, когда эти имена в утверждении нигде больше не употребляются.
2.1.3. Структуры
Третьим видом терма, присутствующим в Пролог-программах, является структура. Структура – это единый объект, состоящий из совокупности других объектов, называемых компонентами. Компоненты группируются в структуру для удобства их использования.
В реальной жизни одним из примеров структур является карточка-указатель для библиотечной книги. Карточка-указатель содержит несколько компонент: сведения об авторе, название книги, дату издания, место, где книга хранится в библиотеке, и т. д. Некоторые из компонент в свою очередь тоже можно разбить на компоненты. Например, сведения об авторе состоят из фамилии и инициалов.
Структуры служат средством организации данных в программе, поскольку они позволяют рассматривать как единый объект (карточку-указатель) группу отдельных элементов данных. Способ, которым осуществляется разложение данных на компоненты, зависит от решаемой задачи, В книге будут приведены некоторые рекомендации на этот счет.
Структуры полезны также в тех случаях, когда имеется общий тип и может существовать много конкретных экземпляров объектов этого типа. Например, книги. В главе 1 приводился факт
имеет(джон, книга).
обозначающий, что у Джона есть некоторая конкретная книга. Если затем будет сформулирован факт
имеет(мэри, книга).
то это означает, что у Мэри есть тот же самый объект, что и у Джона, поскольку в обоих фактах фигурирует одно и то же имя. Не существует другого способа указания факта, что объекты различны, кроме присвоения им различных имен. Можно было бы уточнить приведенные факты:
имеет(джон,грозовой_перевал).
имеет(мэри,моби_дик).
явно указав, какие именно книги есть у Джона и Мэри. Однако в больших программах обилие различных констант, смысл которых из контекста не очевиден, может вызвать затруднения. Человек, читающий данную Пролог-программу, может не знать, что константа грозовой_перевал представляет собой название книги Эмили Бронте, жившей в Йоркшире (Англия) в 19-м веке. Можно было бы, скажем, предположить, что Джон назвал так своего любимого кролика. С помощью структур можно предоставить читателю необходимый контекст.
Структура записывается на Прологе с помощью указания ее функтора и компонент. Компоненты заключаются в круглые скобки и разделяются запятыми. Функтор записывается перед открывающей круглой скобкой. Рассмотрим факт, заключающийся в том, что у Джона есть книга с названием «Грозовой перевал», написанная Эмили Бронте:
имеет(джон,книга(грозовой_перевал, бронте)).
Внутри факта имеет находится структура с именем книга, имеющая две компоненты: название и автор. Поскольку структура книга появляется внутри факта как один из его аргументов, она действует как объект, принимая участие в отношении. При желании можно было бы создать еще одну структуру – для идентификации автора, поскольку существовали три писательницы с фамилией Бронте:
имеет(джон,книга(грозовой_перевал, автор(эмили, бронте))).
Структуры с переменными в качестве компонент могут появляться в вопросах. Например, можно было бы спросить, есть ли у Джона какая-либо книга сестер Бронте:
?- имеет(джон,книга(Х,автор(Y, бронте))).
Если будет доказано, что это утверждение согласовано с базой данных, то значением X будет название книги, а значением Y – имя автора. В тех случаях, когда переменные в дальнейшем не используются, можно употребить анонимную переменную:
?- имеет(джон, книга(_, автор(_,бронте))).
Напомним, что анонимные переменные не «сцепляются» друг с другом.
Структуру книга можно было бы еще улучшить, добавив аргумент, указывающий экземпляр книги. Например, третий аргумент, на место которого следует ставить целое число, дал бы нам возможность однозначно идентифицировать книгу:
имеет(джон, книга (улисc, автор(джеймс,джойс), 3129)).
что соответствует следующей фразе на естественном языке: Джон имеет 3129-й экземпляр книги Джеймса Джойса «Улисс». Если у читателя сложилось впечатление, что синтаксис структур совпадает с синтаксисом фактов, то нам остается только подтвердить его правоту. Предикат (используемый в фактах и правилах) является на самом деле функтором некоторой структуры. Аргументы факта или правила – это компоненты структуры. Представление самих Пролог-программ в виде структур обладает многими достоинствами. Сейчас преждевременно обсуждать эти достоинства, однако читателю все же следует помнить, что все части Пролога, даже сами Пролог-программы, состоят из констант, переменных и структур.
2.2.
Литеры
Имена констант и переменных образованы цепочками литер. Хотя для каждого вида имени (атом, целое число, переменная) имеются специальные правила, указывающие, из каких литер оно может составляться, полезно знать, что представляет собой весь набор литер, распознаваемых Прологом. Это связано с тем, что литера сама может рассматриваться как самостоятельный элемент данных. Поскольку мы уже знакомы с целыми числами, можно теперь описать, как литеры представляются небольшими целыми числами. Над литерами чаще всего выполняются операции «ввод» и «вывод». Эти операции будут обсуждаться в гл. 5.
В Прологе имеются два типа литер: печатаемые литеры и непечатаемые литеры. Печатаемые литеры обладают визуальным образом, появляющимся на терминале при выводе. Непечатаемые литеры такого образа не имеют, но при выводе они вызывают выполнение некоторых действий. Этими действиями могут быть пропуск пустого места («печать» пробела), переход на новую строку, подача звукового сигнала. Ниже приведены все печатаемые литеры, которые можно использовать в Пролог-программах.
ABCDEFGHIJKLMNOPQRSTUVWXYZ
abedefghijklmnopqrstuvwxyz
0123456789
!"#$%&'()=–~^|\{}[] _`@ +;*:‹›,.?/
Читатель должен заметить, что данный набор более полон, чем приводившийся в начале главы. Некоторые из этих литер имеют специальное значение. Например, круглые скобки используются для выделения компонент структур. Однако, как мы увидим в последующих главах, любая литера может рассматриваться в Пролог-программе как и информационный элемент данных. Литеры могут печататься, вводиться с клавиатуры, сравниваться и принимать участие в арифметических операциях.
Литеры на самом деле интерпретируются как небольшие целые числа – из диапазона от 0 до 127. Каждой литере поставлено в соответствие некоторое целое число, называемое ее ASCII-кодом. Аббревиатура ASCII расшифровывается следующим образом: American Standard Code for Information Interchange (Американский стандартный код для обмена информацией). Этот код широко используется на вычислительных машинах и в языках программирования во всем мире. Таблицу кодов ASCII можно найти почти в любом руководстве по работе на ЭВМ. Коды букв упорядочены в алфавитном порядке, так что выяснение порядка следования литер в алфавите сводится к сравнению их кодов с помощью операторов отношений, описываемых ниже в данной главе. Коды всех печатаемых литер больше 32.
Хотя польза кода ASCII в данный момент может быть для читателя и не очевидной, мы вновь вернемся к этому вопросу в разд. 3.2. и 3.5.
2.3. Операторы
Иногда удобно записывать некоторые функторы как операторы. Это особая форма синтаксиса, облегчающая чтение соответствующих структур. Например, арифметические операции обычно записываются как операторы. В арифметическом выражении 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 = X.
Внутри всякого утверждения X всегда равно X, и это свойство использовано нами при определении предиката равенства.
При согласовании с базой данных цели вида X = Y, где X и Y – любые термы, в которых могут содержаться неконкретизированные переменные, действуют следующие правила:
• если X представляет собой неконкретизированную переменную, а переменная Y конкретизирована (какое именно значение ей дано, неважно), то X и Y равны. Кроме того, X станет конкретизированной – ей будет дано то же значение, что и Y. Например, следующий вопрос приведет к тому, что X будет присвоено значение в виде структуры: ехать(клерк, велосипед):
?- ехать(клерк, велосипед) = X.
• целые числа и атомы всегда равны самим себе. Например, попытки согласовать следующие целевые утверждения дадут результаты, показанные справа:
полицейский = полицейский /* верно */
бумага = карандаш /* ложно */
1066=1066 /* верно */
1206=1583 /* ложно */
• Две структуры равны, если они имеют один и тот же функтор и одинаковое число аргументов, причем все соответствующие аргументы равны. Например, при согласовании следующего целевого утверждения X будет присвоено конкретное значение велосипед:
ехать(клерк,велосипед) = ехать(клерк,Х).
Структуры могут быть вложены одна в другую на любую глубину. Если такие вложенные структуры проверяются на равенство, проверка займет больше времени, поскольку необходимо проверить все структуры. Попытка согласовать следующую цель:
a(b,C,d(e,F,g(h,i,J)))=a(B,c,d(E,f,g(H,i,j))).
будет успешной, а переменные В, С, F, Е, J будут конкретизированы, им будут присвоены соответственно значения b, с, f, e, j. Что произойдет, если мы попытаемся приравнять две неконкретизированные переменные? Это специальный случай первого из вышеприведенных правил. Так, цель будет согласована и две переменные станут сцепленными. Если две переменные сцеплены, то при конкретизации одной из них второй переменной будет автоматически присвоено то же самое конкретное значение, что и первой. Таким образом, в следующем правиле второй аргумент будет конкретизирован так же, как первый:
ничего_не_делать(Х,Y):- Х = Y.
Целевое утверждение X=Y всегда верно (т. е. согласуется с базой данных), если один из аргументов неконкретизирован. Более простой способ записи такого правила заключается в использовании того факта, что переменная равна самой себе:
ничего_не_делать(Х,Х).
Пролог предоставляет также предикат '\=' соответствующий не равно. Целевое утверждение Х\=Y верно в тех случаях, когда не доказуемо утверждение X=Y, и наоборот. Таким образом, Х\=Y означает, что X не может быть сделано равным Y.
Упражнение 2.1. Скажите, верны ли следующие целевые утверждения, какие переменные будут конкретизированы и какие им будут даны значения:
пилоты(А, Лондон) = пилоты(лондон, париж)
точка(Х,Y,Z) = точка(Х1,Y1,Z1) = слово(буква)
существительное(альфа) = альфа
'викарий' = викарий
f(X,X) = f(a,b)
f(X,a(b,c)) = f(Z,a(Z,c)
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
Отметим, что символ «меньше или равно» записывается не так, как во многих других языках программирования (обычно ‹=). Это сделано в Прологе для того, чтобы программист мог использовать похожий на стрелку атом ‹= для своих собственных нужд.
Поскольку операторы сравнения являются предикатами, можно было бы предположить, что в Прологе допустим следующий факт:
2›3.
утверждающий, что 2 на самом деле больше 3. Факты, подобные этому, с формальной стороны полностью соответствует правилам Пролога. Однако Пролог не разрешает добавлять факты к «встроенным» предикатам. Такая особенность предотвращает непредсказуемые изменения смысла встроенных предикатов. В главе 6 будут описаны все встроенные предикаты, в том числе и те, с которыми мы уже познакомились.
В качестве первого примера использования чисел предположим, что у нас есть база данных, содержащая сведения о принцах, правивших Уэльсом в 9-м и 10-м веках. Предикат правил(Х,Y,Z) истинен, если принц с именем X находился у власти с года Y по год Z. Список фактов базы данных выглядит следующим образом:
правил(родри,844,878).
правил(анаравд,878,916).
правил(хивел_дда,916,950).
правил(лаго_ад_идвал,950,979).
правил(хивел_аб_иеуаф,979,985).
правил(кадваллон,985,986).
правил(маредудд, 986,999).
Теперь предположим, что мы хотим узнать, кто был на троне Уэльса в каком-то конкретном году. Можно было бы определить правило, аргументами которого являлись бы имя и дата и которое просматривало бы базу данных и сравнивало заданную дату с теми, что указаны в фактах. Давайте определим предикат принц(X, Y), который истинен, если принц по имени X был на троне в год Y:
X был
принцем в год Y, если:
X правил с года А по год В и
Y находится между А и В или совпадает с А или В.
Первое целевое утверждение будет согласовываться с базой данных путем поиска подходящего факта. Второе целевое утверждение верно, если Y равно А, или Y равно В, или Y лежит между А и В. Для проверки можно использовать утверждения Y›=А и Y=‹В. Переписав это на Прологе, получаем следующее правило:
принц (X,Y):-правил(Х,А,В),Y ›= А,Y =‹ В.
Ниже приведено несколько возможных запросов и ответов, даваемых Пролог-системой.
?- принц(кадваллон,986).
да
?- принц(родри,1979).
нет
?- принц(Х,900).
Х = анаравд
да
?- принц(X,979).
X = лаго_ад_идвал;
X = хивел_аб_иеуаф да
Заметьте использование переменных в последних примерах. Убедитесь, что вы понимаете, как работает механизм поиска Пролога при ответе на подобные вопросы.
Арифметические операции могут также использоваться для вычислений. Например, если имеются сведения о населении и площади некоторой страны, то можно вычислить среднюю плотность населения для этой страны. Средняя плотность населения показывает, сколь тесно было бы в данной стране, если бы ее население было равномерно распределено по всей ее территории.
Рассмотрим следующую базу данных, содержащую сведения о населении и площади некоторых стран в 1976 г. Для представления связи между страной и ее населением будет использоваться предикат нас. В наши дни население обычно характеризуется довольно большими числами. Не все версии Пролога позволяют работать с такими числами. Поэтому будем исчислять население в миллионах: нас(Х, Y) означает, что население страны X составляет примерно «Y миллионов» людей. Предикат площадь будет обозначать связь между страной и ее площадью (в миллионах квадратных километров):
нас(сша,203).
нас(индия, 548).
нас(китай,800).
нас(бразилия,108).
площадь(сша,8).
площадь(индия,3).
площадь(китай,9).
площадь(бразилия,8).
Теперь для того, чтобы найти среднюю плотность населения некоторой страны, мы должны использовать правило, гласящее, что значение плотности получается делением числа, представляющего население, на число, представляющее площадь.
Введем предикат плотность(Х, Y), где X – это страна, a Y – плотность населения в данной стране, и запишем соответствующее правило на Прологе:
плотность(X,Y):-нас(Х,Р), площадь(Х,А), Y is Р/А.
Данное правило читается следующим образом:
Плотность населения страны X представляется числом Y, если:
Население X - это Р, и Площадь X - это A, и Y вычисляется делением Р на A.
В правиле используется оператор деления '/' введенный в предыдущем разделе. Операция деления выполняется на самом деле как целочисленное деление, сохраняющее только целую часть результата.
Новым здесь является инфиксный оператор 'is'. Его правый аргумент – терм, интерпретируемый как арифметическое выражение. Для того чтобы выполнить 'is', Пролог сначала вычисляет его правый аргумент в соответствии с правилами арифметики. Результат вычислений проверяется на соответствие с левыми аргументами, чтобы определить, доказуемо ли целевое утверждение. В вышеприведенном примере переменная Y до исполнения is не конкретизирована, и она остается в таком состоянии до вычисления выражения. Когда выражение вычислено, Y принимает значение, равное полученной величине. Это означает, что должны быть известны значения всех переменных, находящихся справа от is.
Предикат is нужно использовать каждый раз, когда требуется вычислить арифметическое выражение. Напомним, что конструкции вида Р/А являются такими же обычными структурами Пролога, как и автор(эмили,бронте). Но если некоторая структура интерпретируется как арифметическое выражение, то к ней применяется специальная операция, заключающаяся в фактическом выполнении арифметических действий над двоичными представлениями элементов структуры и получении соответствующего результата. Эта операция называется вычислением арифметического выражения. Не любую структуру можно вычислить как арифметическое выражение. Например, очевидно, что нельзя вычислить структуру автор, поскольку функтор автор не определен как арифметическая операция.
Вернемся к примеру со средней плотностью населения. Нетрудно видеть, что типичные вопросы и ответы на них выглядят следующим образом:
?- плотность(китай,X).
X=89
?= плотность(турция,X).
нет
Х=89 в первом вопросе представляет собой ответ Пролог-системы, означающий 89 человек на квадратный километр. Второй запрос не выполним, поскольку в базе данных нашего примера невозможно найти сведения о населении Турции.
Набор допустимых арифметических операций зависит от используемой ЭВМ. Однако все Пролог-системы обеспечивают выполнение следующих операций:
X+Y сумма X и Y
X–Y разность X и Y
X*Y произведение X и Y
X/Y частное от деления X на Y
X mod Y остаток от деления X на Y
Этот список вместе со списком операторов сравнения, приведенным выше, содержит все, что необходимо для решения простых арифметических задач. Поскольку Пролог в основном ориентирован на нечисловые задачи, арифметические возможности не так важны, как в других языках программирования.
2.6. Общая схема согласования целевых утверждений
Для ответа на вопрос, поступивший от программиста, Пролог выполняет решение некоторой задачи. Вопрос содержит конъюнкцию целевых утверждений, которые необходимо попытаться доказать, т. е. проверить на согласованность с базой данных. Для доказательства целевых утверждений Пролог использует известные утверждения. Факт может привести к немедленному доказательству (согласованию) целевого утверждения, в то время как правило может только свести данную задачу к конъюнкции предикатов-подцелей. Однако использование некоторого утверждения возможно только, когда оно «подходит» к рассматриваемому целевому утверждению, т. е. соответствует ему (сопоставимо с ним). Если целевое утверждение не доказано, возбуждается процесс возврата. Процесс возврата заключается в пересмотре проделанной работы и попытках передоказать (вновь согласовать) целевые утверждения путем поиска альтернативных путей доказательства. Более того, если программист неудовлетворен ответом на свой вопрос, он может сам инициировать процесс возврата, нажав на клавиатуре клавишу ';', после того как Пролог информирует его о найденном решении. В данном разделе будут представлены диаграммы, показывающие, как Пролог пытается доказать и передоказать целевые утверждения.
2.6.1. Успешное доказательство конъюнкции целевых утверждений
Пролог пытается согласовать с базой данных входящие в конъюнкцию целевые утверждения в том порядке, в каком они написаны (слева направо), где бы они ни появились – в теле правила или в вопросе. Это означает, что Пролог не будет проверять некоторое утверждение, пока не будет доказан его сосед слева. А сосед справа будет рассматриваться только после доказательства данного целевого утверждения. Рассмотрим следующую простую программу о семейных связях:
родители (С,M,F):- мать(С,М), отец(C,F).
мать(джон,анна).
мать(мэри,анна).
отец(мэри,фред). отец(джон,фред).
Давайте рассмотрим последовательность событий, позволяющую дать ответ на вопрос:
?-женщина(мэри), родители(мэри,М,Р), родители(джон,М,Р).
Данный вопрос позволяет определить, является ли мэри сестрой джона. Для того чтобы дать ответ Прологу, необходимо согласовать с базой данных последовательность подцелей, приведенных на рис. 2.1.
Представим целевые утверждения в виде прямоугольников, распределенных по странице. Стрелка, начинающаяся в верхней части страницы, указывает, какие целевые утверждения уже согласованы. Прямоугольники, через которые стрелка уже прошла, соответствуют согласованным целевым утверждениям. Прямоугольники, лежащие ниже острия стрелки, соответствуют целевым утверждениям, которые Пролог еще не рассматривал. При выполнении программы стрелка движется вверх и вниз по странице в соответствии с переходом Пролога от одного целевого утверждения к другому. Будем называть ее цепочкой доказательств. В данном примере стрелка начинается в верхней части страницы, как показано выше. По мере согласования трех целевых утверждений она будет удлиняться вниз, проходя через соответствующие прямоугольники. Конечная ситуация представлена на рис. 2.2. Отметим, что в ходе доказательства согласованности целевых утверждений с базой данных были найдены значения для переменных М и F.
Такая диаграмма иллюстрирует общую структуру происходящего, но она не показывает, как доказывались эти три целевых утверждения. Для того чтобы показать это, поместим внутрь прямоугольников больше информации. Давайте посмотрим, как доказывалось второе целевое утверждение. Доказательство согласованности целевого утверждения с базой данных включает в себя поиск в базе данных соответствующих (сопоставимых) утверждений, пометку этого места базы данных и затем доказательств возникших подцелей. Этот процесс для второго целевого утверждения можно проиллюстрировать, включив в прямоугольник родители индикацию выбранного утверждения и возникшие подцели. Выбранное утверждение обозначается числом в скобках, в данном случае (1). Это число указывает номер выбранного утверждения в наборе утверждений с соответствующим предикатом. Таким образом, число 1 означает, что было выбрано первое утверждение с данным предикатом. Эта информация достаточна для отметки места в базе данных. Подцели заключены в маленькие прямоугольники, помещенные в прямоугольник данного целевого утверждения. В момент, когда выбрано утверждение родители, ситуация выглядит так, как показано на рис. 2.3.
Рис. 2.3.
Стрелка вошла в прямоугольник родители и прошла через скобки, указывая, что выбрано некоторое утверждение. Данное утверждение создало две подцели – мать и отец. В данный момент для получения ответа на вопрос необходимо, чтобы стрелка прошла через два маленьких прямоугольника, вышла из прямоугольника родители и затем прошла через второй прямоугольник родители. Когда стрелка проходит через маленькие прямоугольники, необходимо выполнить те же самые шаги: выбор соответствующего утверждения и доказательство порождаемых им подцелей. В данном примере для каждого из этих двух целевых утверждений в базе данных находится соответствующий факт, и их согласованность с базой данных доказывается. На рис. 2.4 приведено более детальное изображение ситуации в момент получения ответа на вопрос.
Рис. 2.4.
Отметим, что для полноты картины нам необходимо было бы показать, как доказываются целевые утверждения женщина(мэри) и родители(джон,анна,фред). Однако столь подробная диаграмма не поместилась бы на одной странице.
Данный пример иллюстрирует общую схему рассмотрения целевых утверждений, объединенных в конъюнкцию, для случая, когда все цели согласуются с базой данных. Стрелка перемещается вниз по странице, по очереди проходя через прямоугольники. Когда стрелка входит в какой-либо прямоугольник, выбирается некоторое утверждение и отмечается его позиция. Если данное утверждение сопоставимо с целью и является фактом, стрелка может покинуть прямоугольник (такая ситуация имела место для целевых утверждений мать и отец). Если же утверждение сопоставимо с целью, но является правилом, создаются прямоугольники для подцелей, и стрелка должна пройти через них, прежде чем она сможет покинуть первоначальный прямоугольник.
2.6.2. Рассмотрение целевых утверждений при использовании механизма возврата
Когда целевое утверждение недоказуемо (проверены все возможные утверждения или пользователь нажал клавишу ';'), «цепочка доказательств» проходит назад тот путь, по которому она пришла в данную точку. Она возвращается в покинутые перед этим прямоугольники для того, чтобы попытаться передоказать (вновь согласовать) соответствующие целевые утверждения. Когда стрелка возвращается в то место, где было выбрано какое-то утверждение (это событие изображается числом в скобках), Пролог пытается найти альтернативное утверждение, соответствующее данной цели. Сначала делаются неопределенными все переменные, которые были конкретизированы в ходе доказательства данного целевого утверждения. Затем возобновляется поиск в базе данных, начиная с того места, где был оставлен маркер. Если будет найдено другое утверждение, соответствующее целевому, Пролог помечает это место, и дальше события развиваются, как было описано выше в разд. 2.6.1. Отметим, что рассмотрение любых целевых утверждений, находящихся «ниже» данного (даже если они были пройдены в ходе рассмотрения предыдущей альтернативы), всегда начинается с самого начала. Пролог пытается доказать их без учета положения маркера (т. е. это не передоказательство). Если не удается найти другое подходящее утверждение, данное целевое утверждение считается недоказуемым и стрелка продолжает возвращаться назад до следующего маркера. В нашем примере, если целевое утверждение родители(джон,анна,фред) недоказуемо, стрелка уйдет назад из прямоугольника родители(джон,анна,фред) и войдет в прямоугольник родители (мэри,анна,фред) снизу для того, чтобы попытаться передоказать данное целевое утверждение (см. рис. 2.5).
Рис. 2.5.
Отступая дальше, стрелка достигнет места, где было выбрано утверждение, соответствующее целевому утверждению отец. В первую очередь освобождаются все переменные, которые были конкретизированы в результате использования данного утверждения. Это означает, что переменная F вновь становится неконкретизированной. Затем Пролог просматривает базу данных, начиная с утверждения, следующего за первым утверждением с предикатом отец (здесь находится маркер), пытаясь найти альтернативное утверждение. Если предположить, что мэри имеет только одного отца, то этот процесс успехом не завершится. Поэтому стрелка продолжит отступление. Она покинет прямоугольник отец(мэри, F) (это целевое утверждение недоказуемо) и вернется в прямоугольник мать(мэри,анна) (для того, чтобы попытаться передоказать данное целевое утверждение) (см. рис. 2.6).
Рис. 2.6.
Отступление стрелки будет продолжаться до успешного доказательства соответствующего целевого утверждения.
Эти примеры иллюстрируют общую схему повторного рассмотрения целевых утверждений в процессе возврата. Когда некоторое целевое утверждение недоказуемо, стрелка возвращается из соответствующего прямоугольника в прямоугольник с предшествующим целевым утверждением. Стрелка отступает до тех пор, пока не встретится маркер. Все переменные, которые были конкретизированы в результате предыдущего выбора сопоставимого утверждения, становятся неконкретизированными. Затем Пролог возобновляет поиск в базе данных сопоставимого утверждения, начиная с маркера. Если сопоставимое утверждение будет найдено, новое место помечается маркером, создаются прямоугольники для целевых подутверждений и стрелка опять начинает движение вниз. В противном случае стрелка продолжает отступать вверх в поисках другого маркера.
2.6.3. Установление соответствия
Правила, определяющие, подходит ли некоторое утверждение для согласования с целевым утверждением, выглядят следующим образом. Отметим, что при выборе утверждения все переменные сначала неконкретизированы.
• Неконкретизированная переменная соответствует любому объекту. Этот объект становится значением переменной.
• Целое число или атом соответствуют только самим себе.
• Между структурами можно установить соответствие, только если они имеют одинаковый функтор, одинаковое число параметров и соответствующие параметры соответствуют друг другу.
Особым случаем является установление соответствия между двумя неконкретизированными переменными. В этом случае мы говорим, что переменные сцеплены. Две сцепленные переменные обладают следующим свойством: как только одна из них принимает конкретное значение, то же самое конкретное значение принимает и другая.
Если читатель заметил сходство между установлением соответствия и приравниванием аргументов (разд. 2.4), то он совершенно прав. Дело в том, что предикат '=' пытается сделать свои аргументы равными путем установления соответствия между ними.
Попытаемся применить на практике наши знания об операторах, арифметических действиях и установлении соответствия. Предположим, что в базе данных находятся следующие факты:
сумма(5).
сумма(З).
сумма(X+Y).
Рассмотрим вопрос:
?- сумма(2+3).
Какой из вышеприведенных фактов будет соответствовать данному запросу? Если вы думаете, что таковым будет первый факт, вам следует вернуться назад и еще раз прочесть разделы о структурах и операторах. В вопросе аргументом структуры сумма является структура с функтором + и компонентами 2 и 3. На самом деле указанной цели соответствует третий факт, при этом переменные X и Y принимают конкретные значения 2 и 3.
С другой стороны, если программист действительно хочет вычислить сумму, ему следовало бы воспользоваться предикатом is. Он должен был бы написать
?- X is 2+3.
или (в качестве развлечения) он мог бы определить предикат сложить, связывающий два целых числа и их сумму:
сложить (X, Y, Z):- Z is X+Y.
В этом определении X и Y должны быть конкретизированы, а Z неконкретизирована.