Prolog - differences between red cut and green cut

Question

I started learning prolog, and wanted to make the whole cuts thing clearer. I have read that "green cut doesnt change declarative meaning of the program, while red cut does". But, the meaning of the program isnt really pure declarative (just from the fact that prolog actually backtracks for all options).

Here is an example:

p(1).
p(2) :- !.
p(3).

it has been said that this is green cut. But if I run this:

p(X), X =:= 3.

I will get "true" without a cut, and "false" with a cut. so, what do I miss?

Thanks in advance.

Giralda

It's not a green cut. Where did you read it's a green cut? – Manlove

Where did you read that definition of green and red cut? – Unseen

both from the lectures papers :-\. you sure this isnt green cut? and if it isnt the definition so what is? thanks. – Giralda

The book, The Art of Prolog, 2nd Ed, says [pp.194-5], "The addition and removal of a green cut from a program do not affect the program's meaning. 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. – Unseen

There are already many answers explaining red and green cuts see tag prolog-cut. – Afebrile

Answer 1

The cut is very straight-forward to interpret operationally, or if you prefer, procedurally. However, since the majority of literature on the topics of logic programming and Prolog has a bias towards the declarative meaning of Prolog programs (for good reasons), difficulties in explaining the cut arise. One attempt to rectify this is by "coloring" cuts depending on their effects.

Here is my attempt to make everything even less clear.

The operational meaning of the cut,

1. From SWI-Prolog's reference manual: "Discard all choice points created since entering the predicate in which the cut appears. In other words, commit to the clause in which the cut appears and discard choice points that have been created by goals to the left of the cut in the current clause."

2. From "The Art of Prolog" by Sterling and Shapiro: "The goal succeeds and commits Prolog to all the choices made since the parent goal was unified with the head of the clause the cut occurs in [emphasis not mine]. Although this definition is complete and precise, its ramifications and implications are not always intuitively clear or apparent."

3. From "The Craft of Prolog" by O'Keefe: "[The cut] prunes the stack of choice points back to where it was when the predicate which lexically contains the cut was called. Another way of saying this is that the cut succeeds and commits Prolog to all the choices made since the parent goal was called [again, emphasis not mine]"

I suggest you read the sections on the cut and its uses at least from the two books cited above. It will definitely help you understand what is actually going on.

One common discussion is on the difference between finding solutions vs. answers vs. proofs. We (users, programmers) usually want answers. The result of evaluating Prolog predicates are solutions. However, what Prolog is actually looking for are proofs.

To take your example. You have the database p(1). p(2). p(3).. You now want to ask Prolog, "Is there a p(X) such that X =:= 3,

?- p(X), X =:= 3.
X = 3.

You get a single solution, X = 3. You also get an answer to your question: yes, there is such a p(X), and X is 3, and there are clearly no more answers.

(Try the query ?- p(X), X =:= 2.. Does it behave identically to the original query?)

Your proof tree can be seen (in a fashion) by tracing the query:

?- trace(p/1), trace(=:=).
%         p/1: [call,redo,exit,fail]
%         (=:=)/2: [call,redo,exit,fail]
true.

[debug]  ?- p(X), X =:= 3.
 T Call: (7) p(_G1004)
 T Exit: (7) p(1)
 T Call: (7) 1=:=3
 T Fail: (7) 1=:=3
 T Redo: (7) p(_G1004)
 T Exit: (7) p(2)
 T Call: (7) 2=:=3
 T Fail: (7) 2=:=3
 T Redo: (7) p(_G1004)
 T Exit: (7) p(3)
 T Call: (7) 3=:=3
 T Exit: (7) 3=:=3
X = 3.

Basically, each of the clauses of p/1 is tried in turn. The first two do not yield a proof, as the second subgoal of the conjunction fails. The search for a proof continues each time from the last choice point (the next clause of p/1). The last one can be proven, and you get a solution and an answer to your query.

Now you put a cut in the body of the second clause of p/1: p(1). p(2) :- !. p(3).. You tell Prolog (in terms of definition 3. from above), "when the search for a proof reaches the second clause of p/1, the one that unifies its argument with 2, prune the stack of choice points to where it was when p/1 was called." When p/1 was called, there were no choice points. So, when X =:= 3 fails, the search for a proof is complete, the conjunction cannot be proven, there are no solutions, and you get no answers.

(Try the query ?- p(X), X =:= 2.. Is it identical to the same query when you did not have the cut?)

Now to the colors..... In the context of the conjunction p(X), X =:= 3., this cut pruned away a solution, and a proof. You didn't get the answer you expected. This cut is red.

It would be nice if we could tell Prolog that we mean a cut to be either green or red (or green or grue or red or blue), but Prolog does not allow us to do that. The "color" is a consequence of the intended meaning of the program (the programmer's intention) and the operational (procedural) effects of the cut.

But really, try to get a book and read the section on cuts. Or even two books.

Carpology