Reading a cut ! in Prolog

6
votes

I am reading through Learn Prolog Now! 's chapter on cuts and at the same time Bratko's Prolog Programming for Artificial Intelligence, Chapter 5: Controlling Backtracking. At first it seemed that a cut was a straight-forward way to mimic an if-else clause known from other programming languages, e.g.

# Find the largest number
max(X,Y,Y):- X =< Y,!. 
max(X,Y,X).

However, as is noted down the line this code will fail in cases where all variables are instantiated even when we expect false, e.g.

?- max(2,3,2).
true.

The reason is clear: the first rule fails, the second does not have any conditions connected to it anymore, so it will succeed. I understand that, but then a solution is proposed (here's a swish):

max(X,Y,Z):- X =< Y,!, Y = Z. 
max(X,Y,X).

And I'm confused how I should read this. I thought ! meant: 'if everything that comes before this ! is true, stop termination including any other rules with the same predicate'. That can't be right, though, because that would mean that the instantiation of Y = Z only happens in case of failure, which would be useless for that rule.

So how should a cut be read in a 'human' way? And, as an extension, how should I read the proposed solution for max/3 above?

2
prologprolog-cutswi-prolog-for-sharing
Almost everything you say is correct, but the following is missing: Operationally, !/0 always succeeds. Therefore, the error in your reasoning stems from confusing the notions of terminating, failing, succeeding and cutting the search tree. This confusion is reflected in the wording "stop termination". To answer your question: A 'human' way to read !/0 is to say: "From here on, I can no longer understand all consequences of what I'm doing." This is because it quickly becomes too hard to reason about programs that contain such impure constructs. - mat
it is if everything that comes before this ! is true, stop keeping in mind any other rules with the same predicate (to continue with, in case of failure) -- and go on with what you've got so far as the one and only truth. so, as you've successfully reached this ! because everything before it was true, the instantiation of Y = Z only happens in case of success, not failure. - Will Ness
@WillNess Thank you for the clarifying comment. I added an example from Bratko's book to question my understanding further. - Bram Vanroy
@BramVanroy It'd be much more helpful if you'd asked a new, followup question with all the new stuff from your new edit, linking to this entry for reference. That way there's less confusion in each Q&A entry about what is asked, and what is answered. - Will Ness
@WillNess Done, new topic here. - Bram Vanroy

2 Answers

6
votes

See also this answer and this question.

how should I read the proposed solution for max/3 above?

max(X,Y,Z):- X =< Y, !, Y = Z. 
max(X,Y,X).

You can read this as follows:

When X =< Y, forget the second clause of the predicate, and unify Y and Z.

The cut throws away choice points. Choice points are marks in the proof tree that tell Prolog where to resume the search for more solutions after finding a solution. So the cut cuts away parts of the proof tree. The first link above (here it is again) discusses cuts in some detail, but big part of that answer is just citing what others have said about cuts elsewhere.

I guess the take home message is that once you put a cut in a Prolog program, you force yourself to read it operationally instead of declaratively. In order to understand which parts of the proof tree will be cut away, you (the programmer) have to go through the motions, consider the order of the clauses, consider which subgoals can create choice points, consider which solutions are lost. You need to build the proof tree (instead of letting Prolog do it).

There are many techniques you can use to avoid creating choice points you know you don't need. This however is a bit of a large topic. You should read the available material and ask specific questions.

0
votes

The problem with your code is that the cut is never reached when evaluating your query.

The first step of trying to evaluate a goal with a rule is pattern matching.

The goal max(2,3,2) doesn't match the pattern max(X,Y,Y), since the second and third arguments are the same in the pattern and 3 and 2 don't pattern-match with each other. As such, this rule has already failed at the pattern matching stage, thus the evaluator doesn't get as far as testing X =< Y, let alone reaching the !.

But your understanding of cuts is pretty much correct. Given this code

a(X) :- b(X).
a(X) :- c(X).
b(X) :- d(X), !.
b(X) :- e(X).
c(3).
d(4).
d(5).
e(6).

and the goal

?- a(X).

The interpreter will begin with the first rule, by trying to satisfy b(X). In the process, it discovers that d(4) provides a solution, so binds the value 4 to X. Then the cut kicks in, which discards the backtracking on b(X), thus no further solutions to b(X) are found. However, it does not remove the backtracking on a(X), therefore if you ask Prolog to find another solution then it will find X = 3 through the a(X) :- c(X). rule. If you changed the first rule to a(X) :- b(X), !. then it would fail to find X = 3.

Although the cut means no X = 5 solution is found, if your query is

?- a(5).

then the interpreter will return true. This is because the a(5) calls b(5), which calls d(5), which is defined to be true. The d(4) fact fails pattern matching, therefore it does not trigger the cut like it does when querying a(X).

This is an example of a red cut (see my comment on user1812457's answer). Perhaps a good reason to avoid red cuts, besides them breaking logical purity, is to avoid bugs resulting from this behaviour.