Запись в операторной форме

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

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 у знак х обозначает опе­ранд, приоритет которого строго меньше по сравнению с операцией, а у обо­значает операнд, приоритет которого меньше или равен приоритету этой операции.