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