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