Knowing when to use cut in prolog

Question

I've took a course in which I learned some prolog. I couldn't figure out how / when to use cuts. Even though I get the general idea of cuts, I can't seem to use them properly. Can anyone explain it briefly or give a good tutorial (that's not learnprolognow.org) on "cuts" that they can recommend?

Answer 1

TL;DR: Don't.

The cut prunes Prolog's search tree. That is, given a pure Prolog program without cut and the same program with cuts the only difference is that the program with cuts might spend less time in fruitless branches, and thus is more efficient ; might have fewer answers ; it might also terminate whereas the original program doesn't.

Sounds pretty harmless ... or even useful, doesn't it? Well, most of the time things are more complex.

Red cuts

Cuts are often used in a way such that the program without cuts has no sensible meaning at all. Such cuts are called red cuts. In the better cases it is used to implement a crude form of non-monotonic negation. And in some other cases it is half negation, half some procedural meaning that is very difficult to understand. Not only for the reader of the program but also for its writer. In fact, often such uses unintentionally lack steadfastness. In any case: these cuts are not placed into an existing program. They are meant to be in that program right from the beginning.

For the more structured uses of such red cuts, better use once/1, (\+)/1, or (;)/2 – if-then-else like ( If -> Then ; Else ) instead. Even better, try to guard such constructs against unintended uses by issuing instantiation_errors. Or use iwhen/2 which produces instantiation errors or when/2 (offered in SWI, YAP, SICStus) which delays goals.

Green cuts

Cuts that remove useless choicepoints (and also redundant answers) are called green cuts. But beware: You cannot place them into your program simply pressing ! and some #00ff00. Most of the time you need a clean read-only guard to ensure that there is no way this cut turns #ff0000. There is also a simple way to remove some leftover choicepoints safely: call_semidet/1. Here are some related cases:

• What's the SLD tree for this query?

• Prolog append with cut operator

• What are the optimal green cuts for successor arithmetics sum?

• Implementing "last" in Prolog

Cut is not commit

Finally, let me point out that cut is not a commit-operator. It sometimes acts a bit like it, but would need lots of restrictions to be one. A commit-operator cannot be (ab)used to implement (\+)/1. A commit requires that each clause is tried independently of each other. Each clause thus needs a full guard ; it cannot rely on being tried only after some other clauses have been tried first. Also, a commit would have to occur in each clause of a predicate. The cut can occur anywhere.