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

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

• +. Сложение

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

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

• /. Деление.

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

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

• 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

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. Списки, операции, арифметические выражения

Рандомно подобранные статьи с сайта:

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


Похожие статьи:

admin