Программирование на языке пролог
Шрифт:
Синтаксис терма, содержащего операторы, частично зависит от их позиций.Операторы, подобные знакам сложения (+), вычитания (-), умножения (*) и деления (/), записываются между своими аргументами и называются поэтому инфикснымиоператорами. Можно также помещать операторы перед их аргументами. Так, в выражении - х+уминус перед хобозначает арифметическую операцию изменения знака. Операторы, записываемые перед своими аргументами, называются префикснымиоператорами. Наконец, некоторые операторы могут помещаться после своего аргумента. Например, оператор вычисления факториала, употребляемый математиками, помещается после числа, для которого необходимо вычислить факториал. В математических обозначениях факториал хзаписывается
Теперь рассмотрим приоритет операторов. Когда нам необходимо проинтерпретировать терм х+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.