Структуры полезны также в тех случаях, когда имеется общий тип и может существовать много конкретных экземпляров объектов этого типа. Например, книги. В главе 1 приводился факт
имеет(джон, книга).
обозначающий, что у Джона есть некоторая конкретная книга. Если затем будет сформулирован факт
имеет(мэри, книга).
то это означает, что у Мэри есть тот же самый объект, что и у Джона, поскольку в обоих фактах фигурирует одно и то же имя. Не существует другого способа указания факта, что объекты различны, кроме присвоения им различных имен. Можно было бы уточнить приведенные факты:
имеет(джон,грозовой_перевал).
имеет(мэри,моби_дик).
явно указав, какие именно книги есть у Джона и Мэри. Однако в больших программах обилие различных констант, смысл которых из контекста не очевиден, может вызвать затруднения. Человек, читающий данную Пролог-программу, может не знать, что константа грозовой_перевалпредставляет собой название книги Эмили Бронте, жившей в Йоркшире (Англия) в 19-м веке. Можно было бы, скажем, предположить, что Джон назвал так своего любимого кролика. С помощью структур можно предоставить читателю необходимый контекст.
Структура записывается на Прологе с помощью указания ее функтораи компонент.Компоненты заключаются в круглые скобки и разделяются запятыми. Функтор записывается перед открывающей круглой скобкой. Рассмотрим факт, заключающийся в том, что у Джона есть книга с названием «Грозовой перевал», написанная Эмили Бронте:
имеет(джон,книга(грозовой_перевал, бронте)).
Внутри факта имеетнаходится структура с именем книга,имеющая две компоненты: название и автор. Поскольку структура книгапоявляется внутри факта как один из его аргументов, она действует как объект, принимая участие в отношении. При желании можно было бы создать еще одну структуру – для идентификации автора, поскольку существовали три писательницы с фамилией Бронте:
имеет(джон,книга(грозовой_перевал, автор(эмили, бронте))).
Структуры с переменными в качестве компонент могут появляться в вопросах. Например, можно было бы спросить, есть ли у Джона какая-либо книга сестер Бронте:
?- имеет(джон,книга(Х,автор(Y, бронте))).
Если будет доказано, что это утверждение согласовано с базой данных, то значением Xбудет название книги, а значением Y– имя автора. В тех случаях, когда переменные в дальнейшем не используются, можно употребить анонимную переменную:
?- имеет(джон, книга(_, автор(_,бронте))).
Напомним, что анонимные переменные не «сцепляются» друг с другом.
Структуру книгаможно было бы еще улучшить, добавив аргумент, указывающий экземпляр книги. Например, третий аргумент, на место которого следует ставить целое число, дал бы нам возможность однозначно идентифицировать книгу:
имеет(джон, книга (улисc, автор(джеймс,джойс), 3129)).
что соответствует следующей фразе на естественном языке: Джон имеет 3129-й экземпляр книги Джеймса Джойса «Улисс».Если у читателя сложилось впечатление, что синтаксис структур совпадает с синтаксисом фактов, то нам остается только подтвердить его правоту. Предикат (используемый в фактах и правилах) является на самом деле функтором некоторой структуры. Аргументы факта или правила – это компоненты структуры. Представление самих Пролог-программ в виде структур обладает многими достоинствами. Сейчас преждевременно обсуждать эти достоинства, однако читателю все же следует помнить, что все части Пролога, даже сами Пролог-программы, состоят из констант, переменных и структур.
2.2. Литеры
Имена констант и переменных образованы цепочками литер. Хотя для каждого вида имени (атом, целое число, переменная) имеются специальные правила, указывающие, из каких литер оно может составляться, полезно знать, что представляет собой весь набор литер, распознаваемых Прологом. Это связано с тем, что литера сама может рассматриваться как самостоятельный элемент данных. Поскольку мы уже знакомы с целыми числами, можно теперь описать, как литеры представляются небольшими целыми числами. Над литерами чаще всего выполняются операции «ввод» и «вывод». Эти операции будут обсуждаться в гл.5.
В Прологе имеются два типа литер: печатаемыелитеры и непечатаемыелитеры. Печатаемые литеры обладают визуальным образом, появляющимся на терминале при выводе. Непечатаемые литеры такого образа не имеют, но при выводе они вызывают выполнение некоторых действий. Этими действиями могут быть пропуск пустого места («печать» пробела), переход на новую строку, подача звукового сигнала. Ниже приведены все печатаемые литеры, которые можно использовать в Пролог-программах.
ABCDEFGHIJKLMNOPQRSTUVWXYZ
abedefghijklmnopqrstuvwxyz
0123456789
!"#$%&'()=–~^|\{}[] _`@ +;*:‹›,.?/
Читатель должен заметить, что данный набор более полон, чем приводившийся в начале главы. Некоторые из этих литер имеют специальное значение. Например, круглые скобки используются для выделения компонент структур. Однако, как мы увидим в последующих главах, любая литера может рассматриваться в Пролог-программе как и информационный элемент данных. Литеры могут печататься, вводиться с клавиатуры, сравниваться и принимать участие в арифметических операциях.
Литеры на самом деле интерпретируются как небольшие целые числа – из диапазона от 0 до 127. Каждой литере поставлено в соответствие некоторое целое число, называемое ее ASCII-кодом. Аббревиатура ASCII расшифровывается следующим образом: American Standard Code for Information Interchange (Американский стандартный код для обмена информацией) [6]. Этот код широко используется на вычислительных машинах и в языках программирования во всем мире. Таблицу кодов 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. Общая схема согласования целевых утверждений