Отсечение cut (!)

Урок про оператор отсечения ! — главный инструмент управления перебором в Prolog и одновременно главный источник коварных багов.

Отсечение (cut, !) — встроенная цель, которая всегда успешна и при этом отбрасывает все точки выбора, созданные с момента входа в текущее правило.

До сих пор Prolog сам решал, какие решения перебирать. Но иногда мы точно знаем: как только сработало одно правило, искать дальше не нужно. Перебор оставшихся вариантов — это лишняя работа, а порой и неверные ответы. ! даёт программисту рычаг, чтобы вмешаться в бэктрекинг.

Что такое точка выбора

Когда у цели есть несколько подходящих предложений (clauses) или несколько способов унификации, Prolog запоминает точку выбора — закладку, к которой он вернётся при бэктрекинге, чтобы попробовать следующий вариант. Именно так получается несколько решений.

color(red).
color(green).
color(blue).

?- color(X).
X = red ;
X = green ;
X = blue.

Вывод:

X = red ;
X = green ;
X = blue.

Три факта — три точки выбора. Отсечение позволяет «обрезать» этот веер.

Что делает !

Цель ! всегда истинна и сразу же выбрасывает все точки выбора, накопленные с момента вызова текущего предиката — как для альтернативных предложений этого предиката, так и для целей, стоявших в теле до отсечения.

first_color(X) :- color(X), !.

?- first_color(X).
X = red.

Вывод:

X = red.

Здесь после color(X) Prolog нашёл red и тут же наткнулся на !. Отсечение убрало точки выбора для green и blue, поэтому решение ровно одно. Без ! запрос дал бы все три цвета.

Классический пример: max/3

Предикат «максимум из двух чисел» отлично показывает, зачем нужен cut.

max(X, Y, X) :- X >= Y, !.
max(_, Y, Y).

?- max(7, 3, M).
M = 7.

?- max(2, 9, M).
M = 9.

Вывод:

M = 7.

Если X >= Y, первое предложение даёт ответ и ! запрещает заходить во второе. Если же X < Y, проверка проваливается до отсечения, и срабатывает второе предложение. Без ! запрос max(7, 3, M) при запросе второго решения ошибочно вернул бы M = 3 — потому что второе предложение тоже подходит структурно.

Зелёное и красное отсечение

Различают два вида cut по тому, меняет ли он смысл программы.

Зелёное отсечение

Зелёное отсечение можно убрать — и множество ответов не изменится. Оно просто экономит перебор, отрезая ветви, которые всё равно провалятся. Это безопасный и желательный вид cut.

Красное отсечение

В max/3 выше отсечение красное: второе предложение max(_, Y, Y) не содержит условия X < Y, и корректность держится только на ! в первом предложении. Уберите ! — и появится лишнее, неверное решение. Красный cut короче, но опаснее: код перестаёт читаться декларативно.

Как работает под капотом

Внутри Prolog хранит стек точек выбора. При входе в предикат он запоминает текущую вершину стека. Когда исполнение доходит до !, движок откатывает стек до этой запомненной отметки, выбрасывая все точки выбора, созданные внутри данного предиката после входа.

До cut:  [ ... | red? green? blue? ]   <- много закладок
              ^ вход в предикат
После !: [ ... ]                       <- закладки удалены

Важное следствие: при бэктрекинге, который пришёл снаружи и докатился до отсечённого предиката, движок уже не сможет ни перебрать оставшиеся предложения, ни откатиться к целям перед ! в теле. Отсечение «защёлкивает» сделанный выбор.

Частые ошибки

• Красный cut вместо явного условия. Полагаться на порядок предложений и ! вместо честной проверки во втором правиле — хрупко. Лучше добавить X < Y и оставить cut зелёным.
• Cut в недетерминированном предикате. Если предикат должен давать несколько решений, ! молча обрежет их до одного.
• Cut слишком рано. Поставив ! до нужной проверки, можно отсечь точки выбора, которые ещё пригодились бы для правильного ответа.
• Cut не «прыгает» через предикат. Отсечение влияет только на точки выбора текущего предиката, а не на вызывающий. Это и плюс (локальность), и источник недопонимания.

Итог

• ! всегда успешно и отбрасывает точки выбора текущего предиката.
• Зелёное отсечение — только оптимизация, семантика без него та же.
• Красное отсечение меняет смысл программы: без него появляются новые ответы.
• Типичное применение — детерминированные предикаты вроде max/3.
• Cut делает код быстрее, но менее декларативным — применяйте осознанно.