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