Эксперимент 2

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

?- 1! 7, Y).

Y - 4

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

• Попытка применить правило 1. Цель 7 < 3 не достигается; выполнить возврат и попытаться применить правило 2 (оператор отсечения не был применен).

• Попытка применить правило 2. Цель 3 =< 7 достигается, но затем не достигается цель 7 < 6; выполнить возврат и попытаться применить правило 3 (оператор отсечения не был применен).

• Попытка применить правило 3. Цель 6 =< 7 достигается.

Глава 5. Управление перебором с возвратами 123

Эта трассировка выполнения позволяет обнаружить еще один источник неэффективности. Вначале было установлено, что выражение X < 3 не является истинным (цель 7 < 3 не достижима). Следующей целью является 3 =< X (цель 3 =< 1 достижима). Но нам известно, что после неудачного завершения первой проверки вторая проверка обязательно будет успешной, поскольку она является отрицанием первой. Следовательно, вторая проверка является избыточной и соответствующая цель может быть опущена. Справедливым является также аналогичное утверждение в отношении цели 6 «< X в правиле 3. Эти рассуждения приводят к созданию приведенной ниже более лаконичной формулировки трех правил.

Если X < 3, то Y = О,

иначе, если *.'. •: 6, тс Y = Г., иначе Y = 4.

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

f (X, 0):- X < 3,!. f (X, 2):- X < 6,!. flX, 4).

Эта программа вырабатывает такие же результаты, что и первоначальная версия, но является более эффективной по сравнению с обеими предыдущими версиями. Но что произойдет, если операторы отсечения будут удалены именно в этой версии? Программа примет следующий вид: fiх, 0):- х < з.

£(X, 2):- X < 6. f (X, 4).

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

?- f (1, YI.

У = 0;

У = 2;

Y = 4;

ПО

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

Более точное значение механизма отсечения описано ниже.

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

Чтобы пояснить это определение, рассмотрим некоторое предложение, заданное в следующей форме:

Н: - Б1, В2,..., Вт,!,..., Вп.

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

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

^

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

!, 5, Т, V.

С :- Р, Q, R,

С : - V.

А :- В, С, D.

? - к.

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

также отбрасывается. Но перебор с возвратами в пределах списка целей S, Т, и все еще возможен. Родительской целью в предложении, содержащем оператор отсечения, является цель С в следующем предложении:

А:- В, С, D.

Рис. 5.3. Влияние оператора отсечения на выполнение программы. Начиная с терма А, сплошные стрелка обозначают последовательность вызовов, а пунктирные стрелки перебор с возвратами. Между термами R и S возможно только "одностороннее движение"

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