Зная, когда использовать разрез в прологе

Ответ 1

TL; DR: Не.

Дерево поиска Prolog. То есть, учитывая чистую программу Prolog без разреза и одну и ту же программу с разрезами, единственное различие заключается в том, что программа с разрезами может тратить меньше времени на бесплодные ветки и, следовательно, более эффективна; может быть меньше ответов; он может также прекратиться, тогда как исходная программа не делает этого.

Звучит довольно безобидно... или даже полезно, не так ли? Ну, в большинстве случаев все сложнее.

Красные разрезы

Сокращения часто используются таким образом, что программа без разрезов не имеет никакого смысла. Такие сокращения называются красными разрезами. В лучших случаях он используется для реализации грубой формы немонотонного отрицания. И в некоторых других случаях это половина отрицания, половина некоторых процедурных значений, которые очень трудно понять. Не только для читателя программы, но и для ее автора. На самом деле часто такое использование непреднамеренно испытывает недостаток в стойкости. В любом случае: эти сокращения не помещаются в существующую программу. Они должны быть в этой программе с самого начала.

Для более структурированного использования таких красных разрезов лучше использовать once/1, (\+)/1 или (;)/2 – if-then-else как ( If -> Then ; Else ). Еще лучше попытайтесь защитить такие конструкции от непреднамеренного использования, выпустив instantiation_error s. Или используйте when/2 (предлагается в SWI, YAP, SICStus).

Зеленые срезы

Отрубы, которые удаляют бесполезные точки выбора (а также избыточные ответы), называются зелеными срезами. Но будьте осторожны: вы не можете поместить их в свою программу, просто нажимая ! и некоторые #00ff00. Большую часть времени вам нужен чистая защита только для чтения, чтобы гарантировать, что этот разрез не станет #ff0000. Существует также простой способ безопасного удаления некоторых оставшихся точек выбора: call_semidet/1. Вот некоторые связанные случаи:

• Что такое дерево SLD для этого запроса?

• Prolog append с оператором cut

• Каковы оптимальные зеленые сокращения для суммы арифметических преемников?

• Реализация "last" в Prolog

Вырезать не commit

Наконец, позвольте мне отметить, что вырезание не является оператором фиксации. Иногда это немного похоже на это, но для этого потребуется множество ограничений. Оператор commit не может быть (ab) использован для реализации (\+)/1. Конец требует, чтобы каждое предложение проверялось независимо друг от друга. Таким образом, каждая статья нуждается в полной защите; он не может полагаться на то, чтобы быть судимым только после того, как вначале были рассмотрены некоторые другие положения. Кроме того, в каждом предложении предиката должно произойти фиксация. Сокращение может происходить где угодно.

Ответ 2

Вырежьте, чтобы цель Prolog была проверена на выбор.

Он должен использоваться тогда, когда программист знает, что любая альтернативная версия не должна быть проверена.

Наиболее заметным из них является использование отрицания при неудаче.

fact(a).
fact(b).

/* 1 */ neg(X) :- call(X), !, fail.
/* 2 */ neg(_).

Здесь я (re) определил стандартный оператор отрицания, обычно он (\+)/1

?- neg(fact(c)).
true.

call(fact(c)) по правилу 1 не может быть доказано, и затем выполняется альтернативное правило 2.

?- neg(fact(a)).
false.

потому что fact(a) может быть доказано, разрез отбрасывает альтернативу перед сбоем.

?- neg(fact(X)).
false.

существует хотя бы неизвестный X такой, что факт (X) преуспевает.

?- neg(neg(fact(X))).
true.

двойное отрицание приводит к тому, что переменные не связаны. Это может быть полезно при выполнении метапрограмм, для извлечения предложений без изменения их "структуры". С оперативной точки зрения ясно (?), Что происходит, но программа потеряет свое декларативное свойство.

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

print_list([E|Es]) :- print_element(E), !, print_list(Es).
print_list([]).

Редактирование об учебнике: я обнаружил, что "Положение и следствие" Уильяма Часового содержит подробный обзор, связанный с сокращением: глава 4 "Выбор и приверженность" полностью посвящена преодолению плюсов и минусов. В нижней строке, в основном минусы...

Ответ 3

Прежде чем использовать разрез, я требую, чтобы мои предикаты отвечали этим двум критериям:

• он дает правильные ответы без вырезания
• он дает правильные ответы, если предложения переупорядочены

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

Например, предикат, чтобы проверить, является ли число положительным, отрицательным или нулевым.

sign(N, positive) :-
    N > 0.
sign(N, negative) :-
    N < 0.
sign(N, zero) :-
    N =:= 0.

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

Можно написать аналогичный предикат без вырезания с помощью -> ;, но некоторые не любят, как он выглядит:

sign(N, Sign) :-
    (   N > 0 -> Sign=positive
    ;   N < 0 -> Sign=negative
    ;            Sign=zero
    ).

Ответ 4

Обрезает все, но исчез из моего кода, как только я нашел предикат once. Внутренне он действует как

once(X) :- X, !.

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

Например, вот мой стандартный мета-интерпретатор. Предложение maybe1/1 имеет уникальные функции в своих аргументах, поэтому, как только они будут известны, правая maybe1/1 может быть выбрана отлично.

Задача об обнаружении этой уникальной функции предоставляется препроцессору maybe0/2, который устанавливает Y в "что делать выражение" около X.

Без once, это могло бы быть пронизано разрезами. Например. в maybe1 есть три/две разные интерпретации X/Y и or, которые нам нужно проверить сверху вниз. Но проверьте это - нет разрезов.

maybe(X) :- 
    once(maybe0(X,Y)), maybe1(Y).

maybe0(true,       true).
maybe0((X,Y),      (X,Y)).
maybe0((X;Y),      or(L))          :- o2l((X;Y),L).
maybe0(X,          calls(X))       :- calls(X).
maybe0(X/Y,        fact(X/Y))      :- clause(X/_, true).
maybe0(X/Y,        rule(X/Y))      :- clause(X/_,_).
maybe0(X/Y,        abducible(X/Y)).
maybe0(or([H|T]),  or([H|T])).
maybe0(or([]),     true).

maybe1(true).
maybe1((X,Y))        :- maybe(X),maybe(Y).
maybe1((X;Y))        :- maybe(X);maybe(Y).
maybe1(abducible(X)) :- assume(X,0).
maybe1(fact(X))      :- assume(X,1), one(X).
maybe1(rule(X))      :- assume(X,2), one(clause(X,Y)), maybe(Y).
maybe1(calls(X))     :- one(clause(X,Y)), maybe(Y).
maybe1(or([H|T]))    :- any(One,Rest,[H|T]), ignore(maybe(One)), maybe(or(Rest)).