Besides the sequencing of goals and clauses, Prolog provides one other very important facility for specifying control information. This is the cut, written ‘!’. It is inserted in the program just like a goal, but is not to be regarded as part of the logic of the program and should be ignored as far as the declarative semantics is concerned.
The effect of the cut is as follows. When first encountered as a goal, cut succeeds immediately. If backtracking should later return to the cut, then the effect is to fail the parent goal, i.e. the goal that matched the head of the clause containing the cut, and caused the clause to be activated. In other words, the cut operation commits the system to all choices made since the parent goal was invoked, and causes other alternatives to be discarded. The goals thus rendered determinate are the parent goal itself, any goals occurring before the cut in the clause containing the cut, and any subgoals that were executed during the execution of those preceding goals.
For example, the procedure
member(X, [X|L]). member(X, [Y|L]) :- member(X, L).
can be used to test whether a given term is in a list:
| ?- member(b, [a,b,c]).
returns the answer ‘yes’. The procedure can also be used to extract elements from a list, as in
| ?- member(X, [d,e,f]).
With backtracking this will successively return each element of the list. Now suppose that the first clause had been written instead:
member(X, [X|L]) :- !.
In this case, the second call above would extract only the first element of the list (‘d’). On backtracking, the cut would immediately fail the entire procedure.
Another example:
x :- p, !, q. x :- r.
This is analogous to “if p then q else r” in an Algol-like language.
Note that a cut discards all the alternatives subsequent to the parent goal, even when the cut appears within a disjunction. This means that the normal method for eliminating a disjunction—by defining an extra predicate—cannot be applied to a disjunction containing a cut.
A proper use of the cut is usually a major difficulty for new Prolog programmers. The usual mistakes are to over-use cut, and to let cuts destroy the logic. A cut that does not destroy the logic is called a green cut; a cut that does is called a red cut. We would like to advise all users to follow these general rules. Also see Writing Efficient Programs.
To illustrate the last issue, suppose that you want to write a
predicate max/3
that finds the greater of two numbers. The
pure version is:
max(X, Y, X) :- X >= Y. max(X, Y, Y) :- X < Y.
Now since the two conditions are mutually exclusive, we can add a green cut to the first clause:
max(X, Y, X) :- X >= Y, !. max(X, Y, Y) :- X < Y.
Furthermore, if the X >= Y
test fails, then we know that X < Y
must be true, and therefore it is tempting to turn the green cut into
a red one and drop the X < Y
test:
max(X, Y, X) :- X >= Y, !. max(X, Y, Y).
Unfortunately, this version of max/3
can give wrong answers,
for example:
| ?- max(10, 0, 0). yes
The reason is that the query does not match the head of the first
clause, and so we never executed the X >= Y
test. When we
dropped the X < Y
test, we made the mistake of assuming that
the head of the first clause would match any query. This is an example
of a predicate that is not steadfast. A steadfast version is:
max(X, Y, Z) :- X >= Y, !, Z = X. max(X, Y, Y).