Cut & if-then-else

Backtracking explores alternatives, but sometimes you know there's only one right answer and want Prolog to stop looking. That's the cut, written !.

When Prolog executes ! it commits: it throws away every choice made since the clause was entered, including the choice of this clause over the ones below it.

If X >= Y succeeds, the cut commits and the second clause is never tried. Without the cut, max(9, 2, M) would answer 9 and then, on backtracking, also 2.

A red cut: when removing it changes the meaning

The cut in max/3 is subtly wrong. Ask it a question where the answer is given instead of asked for:

max(3, 2, 2) says "the larger of 3 and 2 is 2", and Prolog agrees! The first clause's head max(X, Y, X) doesn't unify with max(3, 2, 2) (3 ≠ 2), so the cut is never reached and the permissive second clause fires. This is a red cut: the program is only correct because of the cut, and it breaks for other modes of use.

The fix is to delay the output unification until after the cut:

If-then-else

Most uses of cut are really "if … then … else". Prolog has syntax for that:

( Condition -> Then ; Else )

It evaluates Condition (at most once), and runs Then if it succeeded, otherwise Else. It's clearer than a cut and harder to get wrong.

Leave out the ; Else and a failing condition makes the whole thing fail.

once/1 and committing to a first answer

once(Goal) runs Goal and keeps only its first solution:

Why a cut? The limits of resolution

The pervasive branching nature of Prolog resolution, along with backtracking, is considered one of the "features" of Prolog. But in certain situations it is "a bug": certain predicates have spurious solutions one wants to discard, and handling branching situations in certain predicates violates DRY (don't repeat yourself) and can cause performance issues.

So Prolog offers extra-relational predicates to control "how many" or "which" solutions one wants to extract from a goal. A very important, primitive one is the cut, performed by the 0-ary predicate symbol !. Its usage is very frequent, and must be well mastered.

Cut motivation: dropping spurious solutions

merge/3 merges two sorted lists. Here is the version without cut:

The first goal gives two equivalent solutions (both facts match the pair of empty lists). The second finds its one answer, but then Prolog keeps checking the remaining alternatives and ends in a spurious, costly no. In general, checking unnecessary conditions can lead to useless (possibly long) computations: when one of the tests succeeds, we do not need to check any of the others. We may want to prune the resolution tree.

The cut predicate: details

Syntax: simply a 0-ary ! predicate, defined at the library level, to be used as one of the goals in the body of a rule.

Intended meaning: it causes certain local pending branches to be discarded: those of successive matching clauses, and the pending solutions of the goals to the left of ! in the current body.

Precise semantics: it is always positively executed, causing a side effect on the part of the resolution tree yet to be explored: all pending branches below the node that first generated the executed cut are pruned (erased away).

What cut prunes

Take this program, where the cut occurs in the second clause of p:

go :- p, a.
go :- ...
r.
r.
p :- q.
p :- r, !, t, u.
p :- v.
p :- z.

go
├── p, a
│   ├── q, a                 ... (as usual)
│   ├── r, !, t, u, a
│   │   ├── !, t, u, a   ← the cut runs here
│   │   │   └── t, u, a  ... (as usual)
│   │   └── !, t, u, a       ← pruned: the second `r` (a goal to the left of the cut)
│   ├── v, a                 ← pruned: the next clauses of `p`
│   └── z, a                 ← pruned
└── ...                      ← pruned: the next clause of `go`

Once ! is executed, the red alternatives (pending solutions of goals to the left of the cut) and the green ones (the successive matching clauses) disappear. The execution of the resolvent after the cut goes on as usual.

Cut motivation: the solution of merge/3

File merge-cut.pl:

Now there is a single answer for the first goal. The first cut prunes the pending branch of the second fact; the second cut prunes the pending branch of the second rule. Note that in the last rule we do not need to check X >= Y again: if the cut after X < Y was not reached, then X >= Y must hold.

Applications: a single result in first_index_of/3

File first-index-of.pl:

first_index_of([a,b,b,c], b, N)
first_index_of([b,b,c], b, N'), N is N' + 1
!, N' is 0 + 1  ...  (pruned)
N is 0 + 1
{N/1}

As soon as !, N is 0 + 1 moves on to N is 0 + 1, all pending branches below the first_index_of([b,b,c], ...) node are pruned: the activation of the second clause is excluded.

Applications: an alternative approach, with the cut after the call

File index-of.pl. Here index_of/3 returns all indexes, and first_index_of2/3 cuts after the call:

As soon as !:{N/1} moves on to {N/1}, all pending branches below the index_of([b,b,c], ...) node are pruned, so the additional solutions of index_of([a,b,b,c], b, N) are excluded. Compare the two approaches: the cut inside the definition changes what the predicate means; the cut after the call keeps index_of/3 pure and commits only where it is used.

Another example: quicksort

File quicksort.pl. The cut in partition/4 makes the two clauses exclusive: