Prolog is good at backtracking but uncontrolled backtracking can be a nuisance.
The cut symbol (written as !) is a special subgoal used to
provide a limited form of control over backtracking, by committing the
Prolog interpreter to a particular portion of the potential search space.
An example will help start to explain how this works. The code for
this example can be found in Section 13.2 and further
discussion appears in Sterling & Shapiro ``The Arto fo Prolog''.
We start with the following definition of minimum/3:
% minimum(+Number1, +Number2, ?Minimum).
% Succeeds if Minimum is the minimum value of Number1 and Number2.
minimum(X, Y, X):-
X =< Y.
minimum(X, Y, Y):-
X > Y.
The potential search tree for the goal minimum(1,2,X) is:
minimum(1, 2, X)
/ \
/ \
minimum(1, 2, 1) minimum(1, 2, 2)
/ \
/ \
/ \
1 =< 2 1 > 2
In other words, the Prolog interpreter, in trying to satisfy
minimum(1,2,X) would first test whether 1 =< 2, which
succeeds giving the result minimum(1,2,1). However, if forced to
backtrack it would also try the second clause and try to establish
1 > 2, which will fail. It would be useful to have some way of
telling the Prolog interpreter, once it had established 1 =< 2
that there is no point in looking for any other ways of finding a
solution. This information can be given by putting a cut after the
first subgoal of the first clause, as shown in gc_minimum/3.
% gc_minimum(+Number1, +Number2, ?Minimum).
%Identical to minimum/3 but with a cut in the first clause.
gc_minimum(X, Y, X):-
X =< Y, !.
gc_minimum(X, Y, Y):-
X > Y.
The potential search tree for the goal gc_minimum(1,2,X) is:
gc_minimum(1, 2, X)
/ \
/ *<--- This branch is pruned from the tree
/ \ once the ! has been reached.
gc_minimum(1, 2, 1) gc_minimum(1, 2, 2)
/ \
/ \
/ \
1 =< 2, ! 1 > 2
/
/
!
Notice that this doesn't alter the set of results which can be
obtained from running the program. All it does is pre--empt search
which would be fruitless. Having put the cut into gc_minimum/3
we might go one step further and remove the X > Y test in the
second subgoal. The argument for doing this might be that if we know
that the cut in the first clause will prevent the second clause ever
being tried if X =< Y then the only condition under which the
second clause is reached is when X > Y, so we don't need to
make this test explicit. By making this change we get
rc_minimum/3 as shown below:
% rc_minimum(+Number1, +Number2, ?Minimum).
% Like to gc_minimum/3 but with the check in the second clause
% left out, because the programmer thinks it isn't needed (given
% that Y should be the chosen minimum if X isn't).
rc_minimum(X, Y, X):-
X =< Y, !.
rc_minimum(_, Y, Y).
The potential search tree for the goal rc_minimum(1,2,X) is:
rc_minimum(1, 2, X)
/ \
/ *<--- This branch is pruned from the tree
/ \ once the ! has been reached.
rc_ minimum(1, 2, 1) rc_minimum(1, 2, 2)
/
/
/
1 =< 2, !
/
/
!
But there is a major flaw in this reasoning, as shown by
calling the goal minimum(1, 2, 2), which will (erroneously)
succeed, since the first clause doesn't match and the cut is therefore
never reached. Thus the intended meaning of rc_minimum/3 is
different from that of minimum/3.
Some people refer to cuts which don't alter the meaning of the program
as ``green cuts'' and cuts which do alter the meaning of the program
as ``red cuts''.