Глава 5 Управление перебором

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

5.1. Ограничение перебора

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

Рис. 5.1. Двухступенчатая функция

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

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

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

Правило 2 : если 3 ≤ X и 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) X уже конкретизирован каким-либо числом; это необходимо для выполнения операторов сравнения.

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

5.1.1. Эксперимент 1

Проанализируем, что произойдет, если задать следующий вопрос:

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

Рис. 5.2.  В точке, помеченной словом "ОТСЕЧЕНИЕ", уже известно, что правила 2 и 3 должны потерпеть неудачу.

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

2 < 0

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

Три правила, входящие в отношение f, являются взаимоисключающими, поэтому успех возможен самое большее в одном из них. Следовательно, мы (но не пролог-система) знаем, что, как только успех наступил в одном из них, нет смысла проверять остальные, поскольку они все равно обречены на неудачу. В примере, приведенном на рис. 5.2, о том, что в правиле 1 наступил успех, становится известно в точке, обозначенной словом "ОТСЕЧЕНИЕ". Для предотвращения бессмысленного перебора мы должны явно указать пролог-системе, что не нужно осуществлять возврат из этой точки. Мы можем сделать это при помощи конструкции отсечения. "Отсечение" записывается в виде символа ' !' , который вставляется между целями и играет роль некоторой псевдоцели. Вот наша программа, переписанная с использованием отсечения:

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, порождены не будут.

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

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