The Cut Symbol

Besides the sequencing of goals and clauses, Prolog provides one other very important facility for specifying control information. This is the cut symbol, 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 symbol is as follows. When first encountered as a goal, cut succeeds immediately. If backtracking should later return to the cut, 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:

     member(X, [X|_]).
     member(X, [_|L]) :- member(X, L).
     

This predicate can be used to test whether a given term is in a list. E.g.:

     | ?- member(b, [a,b,c]).
     

returns the answer yes. The predicate 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|_]) :- !.
     

In this case, the above call would extract only the first element of the list (d). On backtracking, the cut would immediately fail the whole predicate.

     x :- p, !, q.
     x :- r.
     

This is equivalent to

     x := if p then q else r;
     

in an Algol-like language.

It should be noticed that a cut discards all the alternatives since 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 doesn't 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.