Menu
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?
559
The cut, in Prolog, is a goal, written as !, which always succeeds, but cannot be backtracked. Cuts can be used to prevent unwanted backtracking, which could add unwanted solutions and/or space/time overhead to a query. The cut should be used sparingly.
If we want to restrict backtracking we can control which sub-goals can be redone using the cut !. We use it as a predicate within the body of clause. It succeeds when called, but fails the parent goal (the goal that matched the head of the clause containing the cut) when an attempt is made to redo it on backtracking.
Green cuts prune only computational paths that do not lead to new solutions. Cuts that are not green are red." A red cut prunes away solutions that might otherwise be there. Your example acts as a red cut. If you do a Google search on "Prolog red green cut" you'll see similar definitions.
As a first step, let's introduce another built-in predicate: fail/0 . As its name suggests, fail/0 is a special symbol that will immediately fail when Prolog encounters it as a goal. That may not sound too useful, but remember: when Prolog fails, it tries to backtrack .
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.
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.
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
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.
158
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
