Давайте сначала рассмотрим простую программу, процесс вычислений, по которой содержит ненужный перебор. Мы выделим те точки этого процесса, где перебор бесполезен и ведет к неэффективности.

Рассмотрим двухступенчатую функцию, изображенную на рис. 5.1. Связь между Х и Y можно определить с помощью следующих трех правил:

Правило 1:        если Х < 3, то Y = 0

Правило 2:        если 3 <= X и Х < 6, то Y = 2

Правило 3:        если 6 <= X, то Y = 4

На Прологе это можно выразите с помощью бинарного отношения

        f( X, Y)

так:

        f( X, 0) :- X < 3.                             % Правило 1

        f( X, 2) :- 3 =< X,  X < 6.              % Правило 2

        f( X, 4) :- 6 =< X.                           % Правило 3

В этой программе предполагается, конечно, что к моменту начала вычисления  f( X, Y)  Х   уже конкретизирован каким-либо числом; это необходимо для выполнения операторов сравнения.

Мы проделаем с этой программой два эксперимента. Каждый из них обнаружит в ней свой источник неэффективности, и мы устраним оба этих источника по очереди, применив оператор отсечения.

При вычислении первой цели  f( l, Y)   Y конкретизируется нулем. Поэтому вторая цель становится такой:

        2 < 0

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

        f( X, 0) :- X < 3,  !.

        f( X, 2) :- 3 =< X,  X < 6,  !.

        f( X, 4) :- 6 =< X.

Символ  '!'  предотвращает возврат из тех точек программы, в которых он поставлен. Если мы теперь спросим

        ?-  f( 1, Y),  2 < Y.

то пролог-система породит левую ветвь дерева, изображенного на рис. 5.2. Эта ветвь потерпит неудачу на цели  2  <  0.   Система попытается сделать возврат, но вернуться она сможет не далее точки, помеченной в программе символом   '!' .  Альтернативные ветви, соответствующие правилу 2 и правилу 3, порождены не будут.

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

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

Более точный смысл механизма отсечений можно сформулировать следующим образом:

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

Чтобы прояснить смысл этого определения, рассмотрим предложение вида

        Н :- В1, В2, ..., Вm, !, ..., Вn.

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

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

        С :- Р, Q, R, !, S, Т, U.
        С :- V.
        А :- В, С, D.
        ?-  А.

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

        С :- V.

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

        А :- В, С, D.

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