Читаем Prolog полностью

Prolog

Будем считать, что это предложение активизировалось, когда некоторая цель G сопоставилась с Н. Тогда G является целью-родителем. В момент, когда встретилось отсечение, успех уже наступил в целях В1, ..., Вm. При выполнении отсечения это (текущее) решение В1, ..., Вm "замораживается" и все возможные оставшиеся альтернативы больше не рассматриваются. Далее, цель G связывается теперь с этим предложением: любая попытка сопоставить G с головой какого-либо другого предложения пресекается.

Применим эти правила к следующему примеру:

С :- Р, Q, R, !, S, Т, U.

С :- V.

А :- В, С, D.

?- А.

Здесь А, В, С, D, Р и т.д. имеют синтаксис термов. Отсечение повлияет на вычисление цели С следующим образом. Перебор будет возможен в списке целей Р, Q, R; однако, как только точка отсечения будет достигнута, все альтернативные решения для этого списка изымаются из рассмотрения. Альтернативное предложение, входящее в С:

С :- V.

также не будет учитываться. Тем не менее, перебор будет возможен в списке целей S, Т, U. "Цель-родитель" предложения, содержащего отсечения, -это цель С в предложении

А :- В, С, D.

Поэтому отсечение повлияет только на цель С. С другой стороны, оно будет "невидимо" из цели А. Таким образом, автоматический перебор все равно будет происходить в списке целей В, С, D, вне зависимости от наличия отсечения в предложении, которое используется для достижения С.

Назад | Содержание | Вперёд

5. 2. Примеры, использующие отсечение

5. 2. 1. Вычисление максимума

Процедуру нахождения наибольшего из двух чисел можно запрограммировать в виде отношения

mах( X, Y, Мах)

где Мах = X, если Х больше или равен Y, и Мах есть Y, если Х меньше Y. Это соответствует двум таким предложениям:

mах( X, Y, X) :- Х >= Y.

max( X, Y, Y) :- Х < Y.

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

если Х >= Y, то Мах = X,

иначе Мах = Y.

На Прологе это записывается при помощи отсечения:

mах( X, Y, X) :- Х >= Y, !.

mах( X, Y, Y).

5. 2. 2. Процедура проверки принадлежности списку, дающая единственное решение

Для того, чтобы узнать, принадлежит ли Х списку L, мы пользовались отношением

принадлежит( X, L)

Программа была следующей:

принадлежит( X, [X | L] ).

принадлежит X, [Y | L] ) :- принадлежит( X, L).

Эта программа дает "недетерминированный" ответ: если Х встречается в списке несколько раз, то будет найдено каждое его вхождение. Исправить этот недостаток не трудно: нужно только предотвратить дальнейший перебор сразу же после того, как будет найден первый X, а это произойдет, как только в первом предложении наступит успех. Измененная программа выглядит так:

принадлежит( X, [X | L] ) :- !.

принадлежит( X, [Y | L] ) :- принадлежит( X, L).

Эта программа породит только одно решение. Например:

?- принадлежит( X, [а, b, с] ).

Х = а;

nо (нет)

5. 2. 3. Добавление элемента к списку, если он в нем отсутствует (добавление без дублирования)

Часто требуется добавлять элемент Х в список L только в том случае, когда в списке еще нет такого элемента. Если же Х уже есть в L, тогда L необходимо оставить без изменения, поскольку нам не нужны лишние дубликаты X. Отношение добавить имеет три аргумента:

добавить( X, L, L1)

где Х - элемент, который нужно добавить, L - список, в который его нужно добавить, L1 - результирующий новый список. Правила добавления можно сформулировать так:

если Х принадлежит к L, то L1 = L,

иначе L1 - это список L с добавленным к нему

элементом X.

Проще всего добавлять Х в начало списка L так, чтобы Х стал головой списка L1. Запрограммировать это можно так:

добавить( X, L, L) :- принадлежит( X, L), !.

добавить( X, L, [X | L] ).

Поведение этой процедуры можно проиллюстрировать следующим примером:

?- добавить( а, [b,с], L).

L = [a, b, c]

?- до6авить( X, [b, с], L).

L = [b, с]

Х = b