Программирование на языке Пролог для искусственного интеллекта - Иван Братко

mod модуль, остаток от целочисленного деления

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

?- X = 1 + 2.

Пролог-система "спокойно" ответит

X = 1 + 2

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

?- X is 1 + 2.

Вот теперь ответ будет

X = 3

Сложение здесь выполняется специальной процедурой, связанной с оператором +. Мы будем называть такие процедуры встроенными.

В Прологе не существует общепринятой нотации для записи арифметических действий, поэтому в разных реализациях она может слегка различаться. Например, оператор '/' может в одних реализациях обозначать целочисленное деление, а в других — вещественное. В данной книге под '/' мы подразумеваем вещественное деление, для целочисленного же будем использовать оператор div. В соответствии с этим, на вопрос

?- X is 3/2,

 Y is 3 div 2.

ответ должен быть такой:

X = 1.5

Y = 1

Левым аргументом оператора is является простой объект. Правый аргумент — арифметическое выражение, составленное с помощью арифметических операторов, чисел и переменных. Поскольку оператор is запускает арифметические вычисления, к моменту начала вычисления этой цели все ее переменные должны быть уже конкретизированы какими-либо числами. Приоритеты этих предопределенных арифметических операторов (см. рис. 3.8) выбраны с таким расчетом, чтобы операторы применялись к аргументам в том порядке, который принят в математике. Чтобы изменить обычный порядок вычислений, применяются скобки (тоже, как в математике). Заметьте, что +, -, *, / и div определены, как yfx, что определяет порядок их выполнения слева направо. Например,

X is 5 - 2 - 1

понимается как

X is (5 - 2) - 1

Арифметические операции используются также и при сравнении числовых величин. Мы можем, например, проверить, что больше — 10000 или результат умножения 277 на 37, с помощью цели

?- 277 * 37 > 10000.

yes            (да)

Заметьте, что точно так же, как и is, оператор '>' вызывает выполнение вычислений.

Предположим, у нас есть программа, в которую входит отношение рожд, связывающее имя человека с годом его рождения. Тогда имена людей, родившихся между 1950 и 1960 годами включительно, можно получить при помощи такого вопроса:

?- рожд( Имя, Год),

 Год >= 1950,

 Год <= 1960.

Ниже перечислены операторы сравнения:

X > Y   X больше Y

X < Y   X меньше Y

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

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

X =:= Y величины X и Y совпадают (равны)

X == Y величины X и Y не равны

Обратите внимание на разницу между операторами сравнения '=' и '=:=', например, в таких целях как X = Y и X =:= Y. Первая цель вызовет сопоставление объектов X и Y, и, если X и Y сопоставимы, возможно, приведет к конкретизации каких-либо переменных в этих объектах. Никаких вычислений при этом производиться не будет. С другой стороны, X =:= Y вызовет арифметическое вычисление и не может привести к конкретизации переменных. Это различие можно проиллюстрировать следующими примерами:

?- 1 + 2 =:= 2 + 1.

yes

?- 1 + 2 = 2 + 1.

no

?- 1 + А = В + 2.

А = 2

В = 1

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

Если заданы два целых числа X и Y, то их наибольший общий делитель Д можно найти, руководствуясь следующими тремя правилами:

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

(2) Если X > Y, то Д равен наибольшему общему делителю X разности Y – X.

(3) Если Y < X, то формулировка аналогична правилу (2), если X и Y поменять в нем местами.

На примере легко убедиться, что эти правила действительно позволяют найти наибольший общий делитель. Выбрав, скажем, X = 20 и Y = 25, мы, руководствуясь приведенными выше правилами, после серии вычитаний получим Д = 5.

Эти правила легко сформулировать в виде прологовской программы, определив трехаргументное отношение, скажем

нод( X , Y, Д)

Тогда наши три правила можно выразить тремя предложениями так:

нод( X, X, X).

нод( X, Y, Д) :-

 X < Y,

 Y1 is Y - X,

 нод( X, Y1, Д).

нод( X, Y, Д) :-

 Y < X,

 нод( Y, X, Д).

Разумеется, с таким же успехом можно последнюю цель в третьем предложении заменить двумя:

X1 is X - Y,

нод( X1, Y, Д)

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

длина( Список, N)

которая будет подсчитывать элементы списка Список и конкретизировать N полученным числом. Как и раньше, когда речь шла о списках, полезно рассмотреть два случая:

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

(2) Если он не пуст, то Список = [Голова1 | Хвост] и его длина равна 1 плюс длина хвоста Хвост.

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

длина( [], 0).

длина( [ _ | Хвост], N) :-

 длина( Хвост, N1),

 N is 1 + N1.

Применить процедуру длина можно так:

?- длина( [a, b, [c, d], e], N).

N = 4

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

N is 1 + N1

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

Интересно посмотреть, что произойдет, если мы попытаемся запрограммировать отношение длина без использования is. Попытка может быть такой:

длина1( [ ], 0).

длина1( [ _ | Хвост], N) :-

 длина1( Хвост, N1),

 N = 1 + N1.

Теперь уже цель

?- длина1( [a, b, [c, d], e], N).

породит ответ:

N = 1+(1+(1+(1+0)))

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

длина1( _ | Хвост], N) :-

 N = 1 + N1,

 длина1( Хвост, N1).

Такая версия длина1 будет давать те же результаты, что и исходная. Ее можно записать короче:

длина1( [ _ | Хвост], 1 + N) :-

 длина1( Хвост, N).

и она и в этом случае будет давать те же результаты. С помощью длина1, впрочем, тоже можно вычислять количество элементов списка:

?- длина( [а, b, с], N), Длина is N.

N = 1+(1+(l+0))

Длина = 3

Итак:

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

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

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

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