Точно Не проект 2 / Не books / Источник_1

Если оператор объявлен со спецификатором xfy, то он является правоассоциативным.

Таблица 6.1 – Операторы языка Пролог

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

Язык Пролог предназначен, главным образом, для программирования задач символьной обработки информации. Тем не менее, в любую пролог систему включаются все обычные арифметические операторы: + (сложение), - (вычитание), * (умножение), / (деление), mod (остаток от деления целых чисел), div (целочисленное деление).

ВПролог входят также все необходимые операторы сравнения чисел:

<(меньше), > (больше), >= (больше или равно), =< (меньше или равно), =\= (не равно), =:= (равенство целочисленных выражений).

Арифметические выражения в Прологе строят из арифметических операторов, числовых переменных, констант и скобок. При этом арифметические выражения представляют собой структуры. Например, выражение 1+2*3 представляется структурой, изображенной на рисунке 6.3. Если пролог-системе задать вопрос

? – Х=1+2*3.

то в результате получим Х=1+2*3, а не Х=7.

Рисунок 6.3 – Представление арифметического выражения 1+2*3.

Объясняется это тем, что оператор “=” выполняет сопоставление и переменной Х ставит в соответствие структуру, изображенную на рисунке 6.3. При этом арифметическое выражение не вычисляется. Для того чтобы заставить пролог-систему выполнить необходимые вычисления, следует применить специальный оператор is. Например,

? – X is 1+2*3.

В этом случае ответ будет Х=7.

Оператор is определен как инфиксный оператор, который в общем виде записывается так:

X is Y.

Здесь Х – или число, или не конкретизированная переменная, а Y – арифметическое выражение. Если Х – число, то вычисляется значение выражения Y, которое сравнивается с X. При равенстве значений X и Y попытка доказательства Х is Y заканчивается успехом. Если Х – не конкретизированная переменная, то вычисленное значение выражения Y приписывается переменной X. Примеры:

?– 3 is 1+2. Yes

?– X is 7-2. X=5

?– 1+2 is 1+2. No

?– X=1, X is X+1. No

Рассмотрим еще один пример. Определим функцию двух переменных f(x, y)=x+y+1:

f(X,Y,F):- F is X+Y+1.

Тогда в ответ на вопрос

? – f(1, 2, F).

будут получен ответ F=4. Однако доказательство целевого утверждения

? – f(X,2,4).

завершится неудачей, так как оператор is “работает” только в направлении справа налево.

Точно так же, как и оператор is, операторы сравнения вычисляют свои аргументы перед выполнением:

?– 5+3-1>2+1. Yes

Вбольшинстве современных реализаций языка Пролог имеются встроенные предикаты для вычисления элементарных функций: возведение в квадрат (sqr), логарифм (ln), синус (sin), косинус (cos), абсолютное значение (abs) и др.

6.5.Списки и рекурсия

Список – это структура данных, составленная их произвольного числа элементов. Элементы списка отделяются друг от друга запятыми и заключаются в квадратные скобки. Например, список из четырех элементов 'a', 'b', 'c', 'd' на языке Пролог запишется в виде:

['a', 'b', 'c', 'd'].

Список полезно рассматривать как структуру данных, состоящую из двух частей: головы списка и хвоста списка. Для приведенного выше списка элемент 'a' – это голова списка, а подсписок ['b', 'c', 'd'] – хвост списка.

Во внутреннем представлении списки – это структуры, состоящие из головы и хвоста. В качестве функтора, объединяющего голову и хвост, используется “.” . Поэтому список можно представить в виде:

.(Голова, Хвост)

Представляя список ['a', 'b', 'c', 'd'] в виде структуры, получаем

.(a, . (b, . (c, . (d, [ ] ))))

курсивный вызов определяемого предиката, аргументом которого является хвост списка.

Определим, например, предикат реверс(Х,Y), где список Y представляет инверсную копию списка Х:

Первое утверждение фиксирует условия выхода из рекурсии, a второе – определяет правило преобразования списка Х в список Y. Для того чтобы выполнить инверсию списка [H|T] , необходимо выполнить инверсию хвоста Т и получить список Ys, а затем добавить голову Н в конец списка Ys и получить результирующий список Y. Интересно отметить, что предикат реверс(Х,Y) позволяет не только выполнять преобразование списка Х в список Y, но и осуществлять обратные преобразования. Например, на вопрос

? – реверс(Х, [1, 2, 3]).

будет получен ответ Х=[3, 2, 1].

Удаление элемента Х из списка L можно представить в виде предиката

удалить(X, L, L1),

где L1 – результирующий список. Если Х является головой списка L, то результирующий список L1 – это хвост списка L. Если Х находится в хвосте списка L, то для удаления Х необходимо рекурсивно вызвать предикат удалить, подставив в качестве второго аргумента хвост списка L. Данным правилам будет соответствовать следующее определение [7]

удалить(Х, [X|T], T). удалить(Х, [H|T], [H|T1]): –

удалить(Х, Т, Т1).

Предикат удалить можно использовать и в обратном порядке. Напри-

мер,

? – удалить (1, L, ['a', 'b']). L=[1, 'a', 'b'];

L=['a', 1, 'b'];

L=['a', 'b', 1].

В данном случае выполняется вставка элемента 1 в произвольные позиции списка. В итоге получаются различные списки L, исключив из которых элемент 1, получим список ['a', 'b'].

деления 2 не должна выполняться. Для того чтобы пролог-системе сообщить это, воспользуемся предикатом отсечения. Введем третье определение предиката abs(X,Y):

% определение 3

abs(X, Y): - X>=0, !, Y is X; Y is -X.

Предикат отсечения “!” всегда успешно выполняется. Использование предиката “!” требует осторожности, так как после его выполнения невозможен возврат к точкам выбора, порождаемым определением, в котором используется предикат отсечения.

Рассмотрим дерево вывода целевого утверждения ? – abs(3, -3), изображенное на рисунке 6.4. Здесь показано, что определение 3 порождает альтернативы, которым соответствуют две ветви, исходящие из узла ? – abs(3, -3). После успешной проверки условия 3>=0, выполняется предикат отсечения, который стирает альтернативную ветвь определения. Теперь, после неудачной проверки выполнимости утверждения -3 is 3, про- лог-система не имеет возможности вернуться к альтернативной версии и возвращает в качестве результата значение No (нет). Таким образом, в рассмотренном примере предикат отсечения был использован для программирования взаимоисключающих версий определения.

Рисунок 6.4 – Дерево вывода для вопроса ? – abs(3, -3)

деленных друг от друга точкой с запятой. Группа позволяет, с одной стороны, рассматривать совокупность вариантов как одно утверждение, а с другой – ограничивать область действия связки ”или”. По существу, группа – это тело правила без головы.

Уточним область действия предиката отсечения. Рассмотрим пример. Определим предикат абсолютный_элемент(X,L), который будет иметь истинное значение, если список L будет содержать числовой элемент, абсолютное значение которого равно Х. Приведем два определения этого предиката:

%Определение 1 абсолютный_элемент(X, L): –

элемент(E, L), abs(E, X).

%Определение 2

абсолютный_элемент(X, L): –

элемент(E, L), (E>=0, !, X is E;

X is –E).

Во втором определении предикат abs(E,X) заменен группой, которая представляет его тело. Предикат элемент(E,L) соответствует предикату member(E,L), определенному в §4.1.7. Проверим данные определения на вопросе:

? – абсолютный_элемент(3, [2, -3]).

При использовании первого определения ответ на вопрос будет положительным, а применение второго определения даст отрицательный ответ No (нет). Происходит это из-за того, что предикат отсечения расширил область своего действия. В первом определении он действует локально в пределах определения abs(E,X). Во втором определении областью его действия является весь предикат абсолютный_элемент(X,L). Поясним сказанное с помощью дерева вывода, изображенного на рисунке 6.5.

Как видно из рисунка, предикат “!” отсекает не только альтернативные ветви, порождаемые определением abs(E,X), но и ветви, обусловленные недетерминированным исполнением предиката элемент. Поэтому правильным будет первое определение предиката абсолютный_элемент.

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