На этом шаге мы рассмотрим прерывание поиска с возвратом: отсечение.

    Пролог предусматривает возможность отсечения, которая используется для прерывания поиска с возвратом; отсечение обозначается восклицательным знаком (!). Действует отсечение просто: через него невозможно совершить откат (поиск с возвратом).

    Отсечение помещается в программу таким же образом, как и подцель в теле правила. Когда процесс проходит через отсечение, немедленно удовлетворяется обращение к cut и выполняется обращение к очередной подцели (если таковая имеется). Однажды пройдя через отсечение, уже невозможно произвести откат к подцелям, расположенным в обрабатываемом предложении перед отсечением, и также невозможно возвратиться к другим предложениям, определяющим обрабатывающий предикат (предикат, содержащий отсечение).

    Существуют два основных случая применения отсечения.

• Если вы заранее знаете, что определенные посылки никогда не приведут к осмысленным решениям (поиск решений в этом случае будет лишней тратой времени), - примените отсечение, - программа станет быстрее и экономичнее. Такой прием называют зеленым отсечением.
• Если отсечения требует сама логика программы для исключения из рассмотрения альтернативных подцелей. Это - красное отсечение.

Использование отсечений

    На этом шаге даются примеры, показывающие, как следует использовать отсечение, рассматриваются несколько условных правил (r1, r2 и r3), которые определяют условный предикат r, а также несколько подцелей - а, b, с и т. д.

Предотвращение поиска с возвратом к предыдущей подцели в правиле

    rl:-
       а, b,
       !,
       c.

    Такая запись является способом сообщить Прологу о том, что вас удовлетворит первое решение, найденное им для подцелей a и b. Имея возможность найти множественные решения при обращении к с путем поиска с возвратом, Пролог при этом не может произнести откат (поиск с возвратом) через отсечение и найти альтернативное решение для обращений а и b. Он также не может возвратиться к другому предложению, определяющему предикат r1.

   predicates
      by_саr (symbol, symbol)
      car(symbol,symbol,integer)
      colors(symbol, symbol)
   clauses
      buy_car (Model,Color) :-
         car(Model,Color, Price),
         colors(Color,sexy),
         !,
         Price < 25000.
      car(maserati,green, 25000).
      car(corvette,black, 24000). 
      car(corvette, red, 26000).
      car(porsche,red, 24000).
      colors(red,sexy).
      colors(black,mean).
      colors(green,preppy).
   goal
      buy_car(corvette,Y).
 

    И данном примере поставлена цель: найти Corvette (Корвет) приятного цвета, подходящий по стоимости. Отсечение в правиле buy_car означает, что поскольку в базе данных содержится только один "Корвет" приятного цвета, хоть и со слишком высокой ценой, то нет нужды искать другую машину.

    Получив целевое утверждение

   buy_car(corvette, Y)

1. Пролог обращается к саr, первой подцели для предиката buy_car.
2. Выполняет проверку для первой машины, Maserati, которая завершается неудачно.
3. Затем проверяет следующее предложение саr и находит соответствие, связывая переменную Color со значением black.
4. Переходит к следующему обращению и проверяет, имеет ли выбранная машина прияный цвет. Черный цвет не является приятным в данной программе, таким образом проверка завершается неудачно.
5. Выполняет поиск с возвратом к обращению car и снова ищет Corvette, удовлеряющий этому критерию.
6. Находит соответствие и снова проверяет цвет. На этот раз цвет оказывается приятным, и Пролог переходит к следующей подцели в правиле: к отсечению. Отсечение немедленно выполняется, "замораживая" все переменные, ранее связанные в этом предложении.
7. Переходит к следующей (и последней) подцели в правиле, к сравнению
   Price < 25000.
8. Проверка завершается неудачно, и Пролог пытается совершить поиск с возвратом с целью найти другую машину для проверки. Отсечение предотвращает попытку решить последнюю подцель, и наше целевое утверждение завершается неудачно.

Предотвращение поиска с возвратом к следующему предложению

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

    r(1):-
       !,
       а,b,с.
    r(2) :-
       !,
       d.
    r(3) :-
       !,
       с.
    r(_) :-
       write("This is a catchall clause.").

    Использование отсечения делает предикат r детерминированным. В данном случае Пролог выполняет обращение к r с единственным целым аргументом. Предположим, что произведено обращение r(l). Пролог просматривает программу в поисках соответствия для обращения; он находит его с первым предложением, определяющим r. Поскольку имеется более чем одно возможное решение для данного обращения, Пролог проставляет точку возврата около этого предложения.

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

    Обратите внимание, что конструкция такого типа весьма похожа на конструкции case в других языках программирования; ycловие проверки записывается в заголовке правил. Вы могли бы написать такие предложения:

    r(Х) :-
       X=1,
       !,
       a,b,с.
    r(X) : -
       X=2,
       !,
       d.
    r(X) :-
       X=3,
       !,
       c.
    r(_) :-
       write("This is a catchall clause.").

    Однако следует, по возможности, помещать проверочное условие именно в заголовок правила, - это повышает эффективность программы и упрощает ее чтение.

   predicates
      friend(symbol,symbol)
      girl(symbol)
      likes(symbol,symbol)
   clauses
      friend(bill,jane):-
         girl (jane),
         likes(bill,jane),
         !.
      friend(bill,jim):-
         likes(jim,baseball),
         !.
      friend(bill,sue):-
         girl(sue).
      girl(marу).
      girl (jane).
      girl(sue) .
      likes(jim,baseball).
      likes(bill,sue).
   goal
      friend(bill,Who).
 

    Если бы и программе не было отсечения, то Пролог предложил бы два решения: Билл является другом как Джейн, так и Сью. Однако отсечение в первом преложении, определяющем friend, говорит о том, что если это предложение согласовано, то друг Билла уже найден, и нет нужды продолжать поиск других кандидатур. Поиск с возвратом может иметь место внутри предложений в попытке согласовать обращение, но, однажды обнаружив решение, Пролог проходит через отсечение. Предложения friend, записанные так, как показано выше, возвратят одного и только одного друга Билла (если друг вообще может быть найден).

    На следующем шаге мы рассмотрим детерминизм и отсечения.

Предыдущий шаг Содержание Следующий шаг