Knowing when to use cut in prolog

问题:

I've took a course in which I learned some prolog. I couldn't figure out how / when to use cuts. Even though I get the general idea of cuts, I can't seem to use them properly. Can anyone explain it briefly or give a good tutorial (that's not learnprolognow.org) on "cuts" that they can recommend?

回答1:

TL;DR: Don't.

The cut prunes Prolog's search tree. That is, given a pure Prolog program without cut and the same program with cuts the only difference is that the program with cuts might spend less time in fruitless branches, and thus is more efficient ; might have fewer answers ; it might also terminate whereas the original program doesn't.

Sounds pretty harmless ... or even useful, doesn't it? Well, most of the time things are more complex.

Red cuts

Cuts are often used in a way such that the program without cuts has no sensible meaning at all. Such cuts are called red cuts. In the better cases it is used to implement a crude form of non-monotonic negation. And in some other cases it is half negation, half some procedural meaning that is very difficult to understand. Not only for the reader of the program but also for its writer. In fact, often such uses unintentionally lack steadfastness. In any case: these cuts are not placed into an existing program. They are meant to be in that program right from the beginning.

For the more structured uses of such red cuts, better use once/1, (\+)/1, or (;)/2 – if-then-else like ( If -> Then ; Else ) instead. Even better, try to guard such constructs against unintended uses by issuing instantiation_errors. Or use iwhen/2 which produces instantiation errors or when/2 (offered in SWI, YAP, SICStus) which delays goals.

Green cuts

Cuts that remove useless choicepoints (and also redundant answers) are called green cuts. But beware: You cannot place them into your program simply pressing ! and some #00ff00. Most of the time you need a clean read-only guard to ensure that there is no way this cut turns #ff0000. There is also a simple way to remove some leftover choicepoints safely: call_semidet/1. Here are some related cases:

• What's the SLD tree for this query?

• Prolog append with cut operator

• What are the optimal green cuts for successor arithmetics sum?

• Implementing "last" in Prolog

Cut is not commit

Finally, let me point out that cut is not a commit-operator. It sometimes acts a bit like it, but would need lots of restrictions to be one. A commit-operator cannot be (ab)used to implement (\+)/1. A commit requires that each clause is tried independently of each other. Each clause thus needs a full guard ; it cannot rely on being tried only after some other clauses have been tried first. Also, a commit would have to occur in each clause of a predicate. The cut can occur anywhere.

回答2:

A cut commits the Prolog goal being proved to the choices done.

It must be used then when the programmer knows that any alternative available must not be tried.

The most prominent use it's the implementation of negation by failure.

fact(a).
fact(b).

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

Here I've (re)defined the standard negation operator, normally it's (\+)/1

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

call(fact(c)) by rule 1 can't be proved, and the alternative rule 2 then succeeds.

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

because fact(a) can be proved, the cut discard the alternative before failing.

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

there exist at least an unknown X such that fact(X) succeed.

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

the double negation has the effect that variables don't get bound. This can be useful when doing meta programming, to fetch clauses without altering their 'structure'. From the operational viewpoint, it's clear (?) what's going on, but the program does lose its declarative property.

Another use, useful only in rudimentary interpreters, was to instruct the system to perform last call optimization, prefixing the recursive call with a cut. Then the system can avoid to allocate the stack space normally required to keep track of alternative point. A dummy example:

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

edit about a tutorial: I found that 'Clause and Effect' by William Clocksin contains a detailed survey related to cut: chapter 4 'Choice and Commitment' it's fully devoted to cut pros and cons. At bottom line, mainly cons...

回答3:

Before using a cut, I require that my predicates meet these two criteria:

• it gives correct answers without a cut
• it gives correct answers if clauses are reordered

Once my predicate behaves that way, I sometimes add a cut to trim away unwanted nondeterminism.

For example, a predicate to test whether a number is positive, negative or zero.

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

Each clause stands completely independent of the others. I can reorder these clauses or remove a clause and the remaining clauses still give the expected answer. In this case, I might put a cut at the end of the positive and negative clauses just to tell the Prolog system that it won't find any more solutions by examining the other clauses.

One could write a similar predicate without cut by using -> ;, but some dislike how it looks:

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

回答4:

Cuts all but disappeared from my code once I found the once predicate. Internally it acts like

once(X) :- X, !.

and I found it very useful for making a firm decision on how to do something before I did that something.

For example, here is my standard meta-interpreter. The maybe1/1 clause has unique functors in its arguments so once they known, then the right maybe1/1 can be selected, perfectly.

The job of finding that unique function is given to the maybe0/2 pre-processor that sets Y to a "what to do statement" about X.

Without once, this could would have to be riddled with cuts. E.g. in maybe1, there are three/two different interpretations of X/Y,and or that we need to check in a top down manner. But check it out- no cuts.

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)).

回答5:

Cut predicate prevents backtracking.Cut predicate is specified as an exclamation point (!). Cut prunes the search tree and shortens the path track by prolog interpreter.Semantically it always succeed.

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;

Without cut the goals shows Y=unknown after Y=black.

There are two types of cut predicate :

Green Cut : Green cut is one type of cut which had no effect on the declarative meaning. It is only use to improve efficiency as well as avoid unnecessary computation. The removal of green cut from the program does not changes the meaning of the program.

Red Cut : Red cut is one which had effect on the the declarative meaning. The removal of red cut from the program changes the meaning of the program.