В математике широко используются выражения, аналогичные приведенному ниже.
2 * а + Ь * с
где + и * представляют собой знаки операций сложения и умножения, а 2, а, Ь — операнды. Б частности, операции + и * называются инфиксными, поскольку знаки этих операций находятся между двумя операндами. Подобные выражения могут быть представлены в виде деревьев, как показано на рис. 3,6, а также записаны с помощью термов языка Prolog с использованием знаков и * в качестве функторов:
+ (* (2,а), * <Ь,с))
Поскольку обычно удобнее записывать такие выражения в привычной, инфикс ной форме с использованием знаков операций, в языке Prolog предусмотрена возможность задавать выражение в операторной записи, поэтому в программе Prolog допускается вводить подобные выражения в следующем виде: 2*а + Ь*с
Рис. 3.6. Древовидное представ ление выражения 2*a + b*c
Но следует учитывать, что это только внешнее представление соответствующего объекта, которое автоматически преобразуется системой в обычную форму термов Prolog, а при выводе подобный терм будет снова представлен для пользователя в его внешней, инфиксной форме.
Таким образом, применение знаков операции в языке Prolog представляет собой альтернативный способ записи выражений. Если в программе встретится конструкция а + ь, система Prolog обработает ее точно так же, как если бы она была записана в форме +{ а, Ь). Но для того чтобы система Prolog могла правильно трактовать такие выражения, как а + Ь*с, она должна иметь информацию о том, что знак * связывает сильнее, чем +. Формально это выражается в том, что + имеет более высокий приоритет, чем *, поэтому правильная интерпретация выражений зависит от приоритета знаков операций. Например, выражение а + b-с можно было бы в принципе трактовать либо как
+ {а, Mb,С))
либо как
*(+(а,Ь!, с)
Общее правило состоит в том, что в выражении без скобок знак операции с наивысшим приоритетом является главным функтором терма. Если выражения, содержащие знаки операции + и *, должны обрабатываться в системе в соответствии с общепринятыми соглашениями, то знак + должен иметь более высокий приоритет, чем знак *. В этом случае выражение а + to*с означает то же, что и а + (Ь*с). Если же требуется другая интерпретация, то ее необходимо явно обозначить с помощью круглых скобок, например, как [а + Ъ) *с.
Глава 3. Списки, операции, арифметические выражения 87
Программист может определять свои собственные знаки операции. Поэтому, например, в программе можно определить атомы has и supports как инфиксные знаки операции, а затем записывать в программе факты наподобие следующих;
peter has information.
floor supports table.
Эти факты полностью эквивалентны следующим:
has(peter, information). Supports! floor, table).
Программист может определять новые операции, вставляя в программу предложения специального типа, иногда называемые директивами (directive), которые действуют как определения операций. Определение операции должно находиться в программе перед любым выражением, содержащим эту операцию. В данном примере знак операции has должен быть правильно определен с помощью следующей директивы:
:- ор[ 600, xtX, has).
Такая конструкция сообщает системе Prolog, что предусмотрено использование атома "has" в качестве знака операции, которая имеет приоритет £300 и относится к типу "х£х"; этот тип характеризует некоторые инфиксные операции. Такая форма спецификатора "xfx" указывает, что данный знак операции, обозначенный как "f", должен находиться между двумя операндами, обозначенными как "х".
Следует отметить, что определения операций не задают каких-либо манипуляций или действий. В принципе, со знаком операции не связаны никакие операции над данными (за исключением очень редких случаев). Знаки операции, как и функторы, обычно используются только для объединения объектов в структуры, а не для активизации действий над данными, хотя на первый взгляд кажется, что слово "операция" предполагает выполнение какого-либо действия.
Знаки операции, называемые также операторами, представляют собой атомы. Приоритет операции не должен выходить из определенного диапазона, который зависит от реализации. В дальнейшем предполагается, что этот диапазон находится в пределах 1-1200.
Типы операций подразделяются на три группы, которые обозначаются спецификаторами типа, такими как xfx. Эти три группы перечислены ниже.
1. Инфиксные операции трех типов: xfx xfy y-fx
2. Префиксные операции двух типов:
Ex fy
3. Постфиксные операции двух типов:
xf yf
Спецификаторы выбираются таким образом, чтобы они отражали структуру выражения, где "f представляет знак операции, а "х" и "у" — операнды. Присутствие обозначения "f" между операндами указывает на то, что операция является инфиксной, Спецификаторы префиксных и постфиксных операций имеют только один операнд, который, соответственно, следует или предшествует знаку операции.
Между обозначениями "х" и "у" имеется определенное различие. Для описания этого различия необходимо ввести понятие приоритета операнда. Если операнд заключен в круглые скобки или представляет собой неструктурированный объект, то его приоритет равен 0; если операнд представляет собой структуру, то его приоритет равен приоритету его главного функтора. Знак V обозначает операнд, приоритет которого должен быть строго меньше, чем у операции, а знак "у" представляет операнд, приоритет которого меньше или равен приоритету операции.
Эти правила позволяют устранять неоднозначность при анализе выражений, состоящих из нескольких операций с одинаковым приоритетом. Например, выражение а - Ь - с
Часть |. Язык Prolog
обычно интерпретируется как (а - Ь) - с, а не как а - (Ь - с). Для обеспечения такой правильной интерпретации тип операции "-" должен быть определен как yfx. На рис. 3.7 показано, почему вторая интерпретация при этом будет исключена.
|
приоритет 500 приоритет 50О
Рис. 3.7. Две интерпретации выражения в - Ь - с, в которых предполагается, что операция " -" имеет приоритет 500. Если операция •"-" относится к типу yfx, то вторая интерпретация является недействительной. поскольку приоритет выражения Ь - с не меньше приоритета операции "-"
В качестве еще одного примера рассмотрим префиксную операцию not. Если операция not определена как fy, то выражение not not р
является допустимым, но если операция not определена как fx, то это выражение недопустимо, поскольку операндом первой операции not является выражение not p, имеющее такой же приоритет, как и сама операция not. В последнем случае данное выражение должно записываться с круглыми скобками, следующим образом:
nOt(not р)
Для удобства некоторые операции определены в системе Prolog заранее, таким образом, чтобы их можно было сразу же использовать, поэтому для них не требуется вводить определение. Каковы эти операции и какими являются их приоритеты, зависит от реализации Prolog. Мы предполагаем, что этот набор "стандартных" операций соответствует определениям, заданным с помощью предложений, которые приведены в листинге 3.1. Операции в этом листинге представляют собой подмножество операций, которые определены в стандарте Prolog, с добавлением операции not. Кроме того, как показано в листинге 3.1, в одном предложении может быть объявлено несколько операций, если все они имеют одинаковый приоритет и относятся к одному и тому же типу. В таком случае знаки операций записываются в виде списка.
Использование операций позволяет намного повысить удобство программ для чте
ния. В качестве примера предположим, что разрабатывается программа для обработ
ки логических выражений, В такой программе может потребоваться, например, вве
сти одну из теорем эквивалентности де Моргана (de Morgan), которая с помощью ма
тематических обозначений может быть записана следующим образом:
-(А ь в) <---- > -a v -в
Один из способов формулировки этого утверждения в языке Prolog может предусматривать использование следующего предложения: equivalence (not (and (А, В)), or (not < А), not (В))).
Листинг 3.1. Множество заранее определенных операций
:- ор< 1200, xfx, [:-,->']]'.:- ор(1200, fx, [:-,?-]).:- ор(1100, xfy, ';').
Глава3. Списки, операции, арифметические выражения
:- ор(1050, xfy, ->).
:- ор(1000, xfy, ',') -
:- opt 900, fy, [ not, ' X + 'll.
:- opt 700, xfx, [ -„ \~, -, \--, =..]).
:- op | 700, xfx, [ is, =:=, = \=, <, =<, >, >-, @<, @=<, @>, <a>=])
:- op(500, yfx, [ -, -]).
:- op(400, yfx, [ *, /, //, rood]).
:- op(200, xfx, **].
:- op(200, xfy, -).
:- op{ 200, fy, -).
Но обычно в программировании следует стремиться к тому, чтобы сохранялось максимально возможное сходство между первоначальной системой обозначений, применяемой в проблемной области, и системой обозначений, используемой в программе. В данном примере эту задачу можно выполнить почти полностью с использованием операций. Подходящий набор операций для данного назначения можно определить следующим образом: :- ор(ЁОО, xfx, <—>J .:- ор(700, xfy, v).:- ор(600, xfy, &) .:- ор(500, fy, -).
Теперь теорему де Моргана можно записать как следующий факт:
-(ASB) <—> -A v -В.
В соответствии с приведенной выше спецификацией операций этот терм будет интерпретироваться, как показано на рис. 3.8.
D — —
/\ I I
Д В А В
Рис. 3.8. Интерпретация терма ~ (A S в)
<™> -A v -В
На основании изложенного можно сделать приведенные ниже заключения.
• Удобство программ для чтения часто можно повысить с помощью записи в операторной форме. Операции могут быть инфиксными, префиксными или постфиксными.
• В принципе, со знаками операций не связаны какие-либо операции над данными, если не считать некоторых частных случаев. Определения операций не определяют конкретные действия; они лишь вводят новые обозначения. Знаки операций, как и функторы, применяются только для соединения компонентов структур.
• Программист может определять свои собственные операции. В определении каждой операции необходимо указать ее знак, приоритет и тип.
• Приоритет — это целое число, не выходящее за пределы определенного диапазона, обычно 1-1200. Знак операции с наивысшим приоритетом в выражении
Часть I. Язык Prolog
является главным функтором выражения. Операции с более низким приоритетом связывают операнды сильнее, чем операции с более высоким приоритетом. • Тип операции зависит, во-первых, от положения знака операции по отношению к ее операндам и, во-вторых, от приоритета операндов в сравнении с приоритетом самой операции. Б спецификаторе типа xf у знак х обозначает операнд, приоритет которого строго меньше по сравнению с операцией, а у обозначает операнд, приоритет которого меньше или равен приоритету этой операции.
