Skip to content
Tutorials Center
My learning

Topics

Lesson 23 of 40 ยท Arithmetic and Control

The Cut: Controlling Backtracking

Learn what the Prolog cut does, how it prunes choice points, the difference between green and red cuts, how to write deterministic predicates, and the classic mistakes to avoid.

Prolog explores alternatives by backtracking: when a goal fails, it returns to the most recent choice point and tries the next option. This is powerful, but sometimes you know that no other option can be right, or that exploring further would give wrong answers or waste time. The cut, written !, lets you say so. It is the only built-in way to take control of the search.

This lesson explains exactly what a cut removes, shows the difference between harmless and dangerous cuts, and gives the idioms that use cut safely. Because Prolog is not available on this site, the runnable examples use a Python stand-in engine that implements facts, rules, backtracking and the cut.

What the cut does

When Prolog executes ! inside a clause body, it does two things:

  1. It commits to the clause: the other clauses of the same predicate, which have not been tried yet, are discarded.
  2. It discards the choice points created by goals to the left of the cut in that clause body.

The cut itself always succeeds. Goals to the right of the cut still backtrack normally. If a goal after the cut fails, the whole call to the predicate fails; it does not try the next clause.

What a cut removes

Later clauses Never tried for this call.
Earlier choice points Goals left of ! stop offering alternatives.
Goals to the right Still backtrack as usual.

The cut is local to the predicate whose clause contains it.

1 / 2

A first example

PROLOG
num(1).
num(2).
num(3).

first(X) :- num(X), !.
PROLOG
?- num(X).
X = 1 ;
X = 2 ;
X = 3.

?- first(X).
X = 1.

first/1 calls num(X), which creates a choice point with three options. After X = 1, the cut removes the choice point, so there is no second answer.

Green cuts and red cuts

A green cut only prunes branches that could never lead to a different answer. Removing it leaves the logic of the program unchanged; it only makes it faster or leaves fewer choice points.

A red cut prunes branches that would have produced answers, so the program depends on the cut to be correct. Red cuts are legal and common, but they make the clause stop meaning what it says. Compare these two versions of max/3:

PROLOG
max(X, Y, X) :- X >= Y, !.
max(_, Y, Y).

At first glance this looks right: if X >= Y, the answer is X; otherwise it is Y. And ?- max(7, 3, M). does give M = 7. But ask a different question:

PROLOG
?- max(5, 3, 3).
true.

The program says true, and that is wrong. The call never reaches the cut, because the first clause head max(X, Y, X) fails to unify with max(5, 3, 3) (the third argument is 3, not 5). The second clause then happily accepts any third argument equal to Y. The cut was doing the job of the missing test X < Y in the second clause, and moving the output unification after the cut repairs it:

PROLOG
max(X, Y, Z) :- X >= Y, !, Z = X.
max(_, Y, Y).

Now max(5, 3, 3) fails: the first clause is entered, 5 >= 3 succeeds, the cut commits, and 3 = 5 fails, so the call fails without trying clause two. The rule of thumb: put the output unification after the cut, so that the cut cannot be skipped by a head match. The even safer alternative is to make clauses mutually exclusive without a cut at all:

PROLOG
max(X, Y, X) :- X >= Y.
max(X, Y, Y) :- X < Y.

The stand-in engine below lets you watch all three versions. It is the same engine used in later lessons; read the top part as "the interpreter" and the bottom as the program and queries.

Python The max/3 trap (Python stand-in engine)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Where the cut stops

A cut only affects the clause it appears in and the predicate that clause belongs to. Inside findall/3, \+, call/1 and the condition of ->, a cut is local: it cuts only within that goal. The next example shows first/1 and a variation where the cut sits in the middle of a body.

Python Cut in the middle of a body

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

You should see pair(X, Y) produce three answers with X = 1 (the cut commits X, but num(Y) is to the right so it still backtracks), while twice(X, Y) produces only X = 1, Y = 1.

Idioms that use the cut

Once-only. once(Goal) runs Goal and keeps only its first solution. It behaves like call(Goal), ! and is what you usually want instead of writing a cut yourself. SWI-Prolog has it built in.

Default case. A last catch-all clause that applies only when the earlier clauses did not match:

PROLOG
grade(Score, pass) :- Score >= 50, !.
grade(_, fail).

Here the cut is a red cut: the second clause is correct only because the first did not commit. Calling grade(70, fail) would wrongly succeed, for the same reason as max/3 above. To keep it safe, either call only with unbound output (grade(70, G)) or write grade(Score, G) :- ( Score >= 50 -> G = pass ; G = fail ). with the if-then-else of the next lesson.

Fail-fast and negation. The cut-fail combination is how negation as failure is defined:

PROLOG
not(Goal) :- call(Goal), !, fail.
not(_).

If Goal succeeds, the cut commits and fail makes the whole call fail; otherwise the second clause succeeds. Use the built-in \+ in real programs.

Deterministic recursion. For predicates like len/2 over lists, first-argument indexing already avoids choice points in SWI-Prolog, so no cut is needed. Add a cut only after you measured or understood the problem.

Cut pitfalls

  • Cuts make clause order significant. Reordering clauses with red cuts changes the program.
  • A cut hides bugs: a missing test often goes unnoticed until you call the predicate with a different instantiation pattern (like max(5, 3, 3)).
  • Do not use cut to implement something the language already offers: once/1, \+, if-then-else.
  • A predicate with cuts may stop being reversible: max(X, 3, 7) and similar calls with unbound inputs usually misbehave.
  • Prefer designing mutually exclusive clauses first. Add a cut only to remove a choice point you have understood.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. After p :- a, !, b. runs the cut, which can still backtrack?

    The cut removes choice points left of it and the remaining clauses of p. Goals after the cut, like b, still backtrack.
  2. 2. What is a red cut?

    A green cut only saves work; a red cut removes answers that would otherwise be found, so the program depends on it.
  3. 3. Why does max(5, 3, 3) succeed with max(X, Y, X) :- X >= Y, !. max(_, Y, Y).?

    Head unification fails on the third argument, so the cut is skipped and the unconditional second clause applies. Unify the output after the cut.
  4. 4. Which built-in keeps only the first solution of a goal?

    once(Goal) is Goal, ! packaged so the cut stays local.

Summary

  • ! commits to the current clause and discards earlier choice points and later clauses for that call; goals after it still backtrack.
  • Green cuts only improve efficiency; red cuts change meaning and need care.
  • Unify outputs after the cut so a head match cannot bypass it.
  • Cuts inside \+, call/1, findall/3 and conditions are local.
  • Prefer once/1, \+ and if-then-else over hand-written cuts.

Next: Negation and If-Then-Else