Арифметические выражения

Некоторые из заранее определенных операций могут использоваться в качестве основных арифметических операций. К ним относятся перечисленные ниже.

• +. Сложение

• -. Вычитание.

• *. Умножение.

• /. Деление.

• **. Возведение в степень.

• //, Целочисленное деление.

• mod. Деление по модулю, вычисление остатка от целочисленного деления.

Обратите внимание на то, что это и есть тот исключительный случай, в котором оператор может фактически вызвать на выполнение операцию. Но даже в таких слу­чаях для осуществления арифметических действий требуется дополнительное указа­ние. Например, следующий вопрос представляет собой наивную попытку потребовать выполнения арифметического вычисления:

?- X = 1 + 2.

Система Prolog "послушно" ответит

X = 1 + 2

а не X = 3, как следовало ожидать. Причина этого проста — выражение 1 + 2 про­сто обозначает терм Prolog, в котором знак + является функтором, а I и 2 - его па­раметрами. В приведенной выше цели нет ничего, что могло бы вынудить систему Prolog фактически активизировать операцию сложения. Для преодоления этой про­блемы предусмотрена специальная предопределенная операция is. Операция is вы­нуждает систему выполнить вычисление, поэтому правильный способ вызова ариф­метической операции состоит в следующем:

?- X is 1 + 2.

В этом случае будет получен ответ:

X = 3

При этом операция сложения была выполнена с помощью специальной процеду­ры, которая связана с операцией is. Подобные процедуры принято называть встро­енными процедурами.

В различных реализациях Prolog могут применяться немного разные обозначения для арифметических операций. Например, знак операции "/" может обозначать це­лочисленное деление или деление действительных чисел. В данной книге знак "/" обозначает деление действительных чисел, знак "//"- целочисленное деление, a "mod" — вычисление остатка от деления. В соответствии с этим на вопрос ?- X is 5/2,

Y is Ъ/П,

2 is 5mod 2.

будет получен следующий ответ:

X = 2.5

Y = 2

г = 1

Левым операндом операции is служит простой объект, а правым операндом — арифметическое выражение, состоящее из арифметических операций, чисел и пере­менных. Поскольку операция is вынуждает систему выполнить вычисление, то все переменные в выражении ко времени выполнения данной цели уже должны быть конкретизированы числовыми значениями. Приоритет заранее определенных ариф­метических операций (см.листинг 3.1) является таковым, что ассоциативность па-

Часть I. Язык Prolog

раметроз с операциями соответствует обычным правилам математики. Для обозначе­ния других ассоциаций могут применяться круглые скобки. Обратите внимание, что операции + , -, *, и div определены как yfx, а это означает, что их вычисление выполняется слева направо; например, терм х is S - 2 - 1

интерпретируется следующим образом: X is (5 - 2) - 1

Кроме того, в реализациях Prolog обычно предусмотрены такие стандартные функции, как sin ( X}, cos ( х;, atan( X), log ( X) , ехр( X] и т.д. Эти функции могут находиться справа от знака операции is.

Кроме того, при выполнении арифметических операций возникает необходимость сравнивать числовые значения. Например, с помощью следующей цели может быть выполнена проверка того, больше ли произведение чисел 271 и 37 по сравнению с числом 10000:

?- 277 * 37 > 10000. yes

Обратите внимание на то, что операция ">", как и операция is, вынуждает сис­тему вычислять арифметические выражения.

Предположим, что в программе имеется отношение born, которое устанавливает связь между именами людей и годами их рождения. В таком случае можно выпол­нить выборку имен людей, родившихся в период между 1980 и 1990 годами включи­тельно, с помощью следующего вопроса: ?- ьогщ Наше, Year), Year >= 1980,

Year =< 1990.

Ниже перечислены операции сравнения.

X > Y X больше Y

X < У. X меньше Y

X >= Y X больше или равен У.

X =< у. X меньше или равен Y

X -: - Y. Значения X и Y равны.

X «V Y. Значения X и Y не равны.

Следует отметить, что операция сопоставления "-" и операция проверки на равен­ство "- г -" отличаются друг от друга; например, они по-разному ведут себя в целях X = Y и X -:■= Y. Первая цель вызывает согласование объектов X и У, а если объек­ты X и Y согласуются, может приводить к конкретизации некоторых переменных в термах X и Y. В этом случае вычисление не выполняется. С другой стороны, опера­ция X =: = Y вызывает вычисление арифметических выражений, но не может стать причиной какой-либо конкретизации переменных. Это отличие можно проиллюстри­ровать на следующих примерах: ?-1+2-:-2+1. yes

?- 1 + 2 = 2 + 1.

RQ

? - 1 + А = В + 2.

А = 2

Ъ - 1

Рассмотрим более подробно использование арифметических операций на двух простых примерах. В первом из ним решается задача вычисления наибольшего об­щего делителя, а во втором — подсчета элементов в списке.

Если даны два положительных целых числа, X и Y, то их наибольший общий де­литель, D, можно определить с учетом перечисленных ниже трех случаев.

Глава 3. Списки, операции, арифметические выражения

1. Если X и Y равны, то D равен X.

2. Если X < Y, то D равен наибольшему общему делителю X и разности Y - X

3. Если Y < X, то для нахождения наибольшего общего делителя применяется такое же правило, как и в случае 2), после перестановки местами X и Y

Можно легко показать на примере,что эти триправила действительно позволяют решить поставленную задачу. Например, если заданы значения х = 20 и Y - 2Ъ, то выполнение приведенных выше правил приводит к получению значения D = 5 после ряда вычитаний.

Эти правила можно сформулировать в виде программы Prolog, определив отноше­ние с тремя параметрами, например, следующим образом:

gcd( X, Y, D)

После этого три правила можно представить в виде трех предложений следующим образом:

gcd{ х, X, X) . gcd{ X, Y, D) :-

X < Y,

Yl is Y - X,

gcd( X, Yl, D). gcd( X, Y, D) :-

Y < X,

gcd( S, X, D) .

Безусловно, последнюю цель в третьем предложении можно равнозначно заменить такими двумя целями: XI is х - Y,

gcd [ XI, Y, D)

Во втором примере требуется выполнить подсчет, а для этого обычно необходимо предусмотреть некоторые арифметические операции. Примером такой задачи являет­ся определение длины списка; иными словами, подсчет количества элементов в спи­ске. Определим такую процедуру length; List, n)

которая подсчитывает количество элементов в списке List и конкретизирует N зна­чением полученного числа. Как и в случае предыдущих отношений, касающихся списков, целесообразно рассмотреть два описанных ниже случая.

1. Если список пуст, то его длина равна 0.

2. Если список не пуст, то List = [Head | Tail]; в таком случае его длина равна 1 плюс длина хвоста Tail.

Эти два случая соответствуют следующей программе:

length( [] ,0).

length( [_ | Tail], M) :-

length С Tail, N1) ,

N is 1 + HI.

В качестве примера применения программы length рассмотрим следующий вопрос: ?- lengthf [a,b, tcdi ,ei , В).

N = 4

Обратите внимание на то, что во втором предложении программы length две це­ли, применяемые в теле, нельзя менять местами. Причина этого состоит в том, что переменная Ml должна быть конкретизирована для того, чтобы появилась возмож­ность обработать цель: N is 1 + Ml

Вместе со встроенной процедурой is в программу было введено отношение, воз­можность выполнения которого зависит от порядка обработки, и поэтому процедур­ные соображения выступили на первый план.

Часть I.

Любопытно понаблюдать за тем, что произойдет при попытке создать программу для отношения length без использования операции is. Пример такой попытки по­казан ниже.

lengthl([],0).

lengthlt [_ ITail], N} :-

lengthKTail, N1},

N= 1 + HI.

Теперь после ввода цели

?- lengthK |a,b, [c,d] ,e] , К).

будет получен следующий ответ: Я = l+(l+(l+(l+0))}.

Системе не была передана на выполнение операция, которая явно вынуждает произвести операцию сложения, и поэтому такая операция так и не была осуществ­лена. Но, р отличие от length, вариант lengthl допускает перестановку целей во втором предложении, следующим образом:

length! ( [_ | Tail], N) :-

и - 1 + Ml,

lengthl( Tail, N1).

Эта версия lengthl вырабатывает такой же результат, как и первоначальная версия. Кроме того, для нее можно использовать более короткую запись следующим образом: lengthK [_ | Tail}, 1 + N) :-

lengthK Tail, H) . которая также обеспечивает получение аналогичного результата. Но программу lengthl все равно можно использовать для определения количества элементов в списке, как показано ниже.

?- lengthK[a,b,c], К), Length is N. N = 1 + [1+(1 + 0) ) Length= 3

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

• Для выполнения арифметических операций можно использовать встроенные процедуры.

• Выполнение арифметических операций необходимо явно затребовать с помо­щью встроенной процедуры is. С такими предопределенными операциями, как +, -, *,/, div и mod, также связаны встроенные процедуры.

• Ко времени вычисления арифметического выражения все его параметры должны быть уже конкретизированы числовыми значениями.

• Значения арифметических выражений можно сравнивать с помощью таких операций, как <, =< и т.д. Эти операции вынуждают систему выполнять вы­числения их параметров.

Упражнения

3.16. Определите отношение

max! X,Y, Мах.)

такое, что мах является наибольшим из двух чисел, X и Y.

3.17. Определите предикат

maxlistfList, Max)

такой, что Мах является максимальным числом в списке чисел List.

3.18. Определите предикат

eoalistl List, Sura)

Глава 3, Списки, операции, арифметические выражения

такой, что Sum — сумма заданного списка чисел List.

3.19.Определите предикат

orderedt List)

который является истинным, если List— упорядоченный список чисел, на­пример ordered ( [1,5,6,6,9,12]}.

3.20. Определите предикат
subsuiM Set, sum, SubSet)

такой, что Set является списком чисел, SubSet — подмножеством этих чисел,

а сумма чисел в Subset равнаSum, например:

7- subsum? [1,2,5,3,2], S, Sub).

Sub - [1,2,2];

Sub = [2,3];

Sub - [ 5 ] ;

3.21. Определите процедуру

between( N1, N2, X)

которая для двух заданных целых чисел Ml иN2 с помощью перебора с воз­вратами определяет все целые числа X, соответствующие ограничению N1 =< X =< N2.

3.22. Определите операторы "if, "then","else" и ": = " такимобразом, чтобы сле­
дующий терм стал действительным:

if X > Y then Z := X else Z := Y

Выберите приоритеты таким образом, чтобы "if был главным функтором. За­тем определите отношение "if, чтобы оно выполняло функции своего рода небольшого интерпретатора для операторов "if-then-else" в следующей форме: if vail > Val2 then Var := Val3 else Var := Val4

где Va Val2, Val3 и Vai4 являются числами (или переменными, конкрети­зированными значениями чисел), a Var представляет собой переменную. От­ношение "if должно иметь следующую интерпретацию: если значение Vail больше, чем значение Val2, то Var конкретизируется значением Val3, в про­тивном случае — значением Val4. Ниже приведен пример использования та­кой интерпретации.

?- х = 2, Y = 3,

Val2 is 2*X,

val<3 is 4*X,

if У > Val2 then Z : = Y else Z : = Val4,

if Z> 5 then И :- 1 else W := 0.

X - 2

Y = 3

z = в

Ш 1

Vcii 2 = 4

Veil 4 = a

Резюме

■ Список — это широко используемая структура. Он может либо быть пустым, либо состоять из головы и хвоста, который также является списком. В языке Prolog для списков предусмотрен специальный формат записи.

■ К числу обычных операций со списками, программы для выполнения которых рассматриваются в данной главе, относятся следующие: проверка принадлеж-

96 Часть I. Язык Prolog

ности к списку, конкатенация, добавление элемента, удаление элемента, выде­ление подсписка.

■ Запись в операторной форме позволяет программисту приспосабливать синтак­сис программ к конкретным потребностям. Применение операций предостав­ляет возможность намного повысить удобство программ для чтения.

■ Новые операции можно определить с помощью директивы ор, указав знак операции, ее тип и приоритет.

■ В принципе, с операциями не связаны какие-либо действия; знаки операций представляют собой синтаксические обозначения, позволяющие применять альтернативный синтаксис для термов.

■ Арифметические действия выполняются с помощью встроенных процедур. Система принуждается к выполнению арифметического выражения с помощью процедуры is и операций (предикатов) сравнения: <, =< и т.д.

■ В этой главе введены следующие понятия:

• список, голова списка, хвост списка;

• списочное обозначение;

• операторы, запись в операторной форме;

• инфиксные, префиксные и постфиксные операторы;

• приоритет оператора;

• арифметические встроенные процедуры.

Глава 3. Списки, операции, арифметические выражения