Зная, когда использовать разрез в прологе
Я взял курс, в котором я выучил некоторый пролог. Я не мог понять, как / когда использовать сокращения. Даже при том, что я получаю общее представление о порезах, я не могу их правильно использовать. Может кто-нибудь объяснить это кратко или дать хороший учебник (это не learnprolognow.org) о "сокращениях", которые они могут порекомендовать?
5 ответов
TL;DR: нет.
Порезанный чернослив поисковое дерево Пролога. То есть, если использовать чистую программу Prolog без обрезки и ту же программу с обрезками, единственное отличие состоит в том, что программа с обрезками может проводить меньше времени в бесплодных ветвях и, следовательно, более эффективна; может иметь меньше ответов; это может также прекратить, тогда как оригинальная программа этого не делает.
Звучит довольно безобидно... или даже полезно, не так ли? Ну, в большинстве случаев все сложнее.
Красные порезы
Срезы часто используются таким образом, что программа без срезов не имеет никакого смысла вообще. Такие порезы называются красными порезами. В лучших случаях он используется для реализации грубой формы немонотонного отрицания. А в некоторых других случаях это наполовину отрицание, наполовину некое процедурное значение, которое очень трудно понять. Не только для читателя программы, но и для ее автора. На самом деле, часто такие виды использования непреднамеренно лишены стойкости. В любом случае: эти сокращения не помещаются в существующую программу. Они должны быть в этой программе с самого начала.
Для более структурированного использования таких красных порезов лучше использовать once/1, (\+)/1, или же (;)/2 - если-то-еще как ( If -> Then ; Else ) вместо. Еще лучше попытаться защитить такие конструкции от непреднамеренного использования, выпуская instantiation_error s. Или использовать when/2 (предлагается в SWI, YAP, SICStus).
Зеленые порезы
Срезы, которые удаляют бесполезные точки выбора (а также избыточные ответы), называются зелеными срезами. Но будьте осторожны: вы не можете поместить их в свою программу, просто нажав ! и немного #00ff00, Большую часть времени вам нужна чистая защита только для чтения, чтобы гарантировать, что этот отрезок не повернется #ff0000, Существует также простой способ безопасного удаления некоторых оставшихся точек выбора: call_semidet/1, Вот несколько связанных случаев:
Вырезать не совершать
Наконец, позвольте мне указать, что cut не является оператором фиксации. Иногда это немного похоже на это, но для этого нужно много ограничений. Оператор фиксации не может (ab) использоваться для реализации (\+)/1, Для фиксации требуется, чтобы каждое предложение использовалось независимо друг от друга. Таким образом, каждый пункт нуждается в полной охране; он не может полагаться на то, что его судят только после того, как некоторые другие пункты были опробованы первыми. Кроме того, фиксация должна происходить в каждом предложении предиката. Разрез может произойти где угодно.
Перед использованием разреза я требую, чтобы мои предикаты соответствовали этим двум критериям:
- дает правильные ответы без разреза
- дает правильные ответы, если пункты переупорядочены
Как только мой предикат ведет себя таким образом, я иногда добавляю сокращение, чтобы обрезать нежелательный недетерминизм.
Например, предикат для проверки, является ли число положительным, отрицательным или нулевым.
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
).
Сокращение связывает доказательство цели Пролога с выбором.
Он должен использоваться тогда, когда программист знает, что любая доступная альтернатива не должна использоваться.
Наиболее выдающееся применение - реализация отрицания по ошибке.
fact(a).
fact(b).
/* 1 */ neg(X) :- call(X), !, fail.
/* 2 */ neg(_).
Здесь я (пере) определил стандартный оператор отрицания, обычно это ( \ +) / 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([]).
Отредактируйте учебник: я обнаружил, что "Clause and Effect" Уильяма Клоксина содержит подробный обзор, связанный с сокращением: глава 4 "Выбор и обязательство", полностью посвященная изучению плюсов и минусов. В итоге, в основном минусы...
Предикат Cut предотвращает возврат. Предикат Cut указывается как восклицательный знак (!). Cut обрезает дерево поиска и укорачивает дорожку путём интерпретатора пролога. Семантически это всегда успешно.
read(a).
read(b).
color(p, red) :- red(p).
color(p,black) :- black(p),!.
color(p,unknown).
?-color(X,Y).
X = a,
Y = red;
X = b,
Y = black;
Без среза голы показывают Y= неизвестно после Y= черный.
Существует два типа предиката разреза:
Зеленое сокращение: зеленое сокращение - один тип сокращения, которое не влияло на декларативное значение. Он используется только для повышения эффективности, а также для избежания ненужных вычислений. Удаление зеленого среза из программы не меняет смысла программы.
Красный Разрез: Красный разрез - это тот, который оказал влияние на декларативное значение. Удаление красного среза из программы меняет смысл программы.
Вырезает все, но исчез из моего кода, как только я нашел 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)).