4.2.3.1 The Cut

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

• Write each clause as a self-contained logic rule, which just defines the truth of goals that match its head. Then add cuts to remove any fruitless alternative computation paths that may tie up memory.
• Cuts are hardly ever needed in the last clause of a predicate.
• Use cuts sparingly, and only at proper places. A cut should be placed at the exact point that it is known that the current choice is the correct one; no sooner, no later, usually placed right after the head, sometimes preceded by simple tests.
• Make cuts as local in their effect as possible. If a predicate is intended to be determinate, define it as such; do not rely on its callers to prevent unintended backtracking.
• Binding output arguments before a cut is a common source of programming errors. If a predicate is not steadfast, it is usually for this reason.

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 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 doesn't 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).