7

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?

Guy Coder
  • 24,501
  • 8
  • 71
  • 136
Bram Vanroy
  • 27,032
  • 24
  • 137
  • 239
  • 1
    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 Dec 02 '16 at 15:58
  • 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 Dec 02 '16 at 18:02
  • @WillNess Thank you for the clarifying comment. I added an example from Bratko's book to question my understanding further. – Bram Vanroy Dec 06 '16 at 10:38
  • @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 Dec 06 '16 at 11:10
  • @WillNess Done, new topic [here](http://stackoverflow.com/questions/40994026/how-to-interpret-this-prolog-goal-with-a-cut-and-improve-efficiency). – Bram Vanroy Dec 06 '16 at 11:16

2 Answers2

6

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.

Community
  • 1
  • 1
  • Hi Boris, thank you a lot for your information. To make sure I grasp the concept, I added an example from Bratko's book to my original post and my interpretation alongside it -- and a small question concerning it. Could you review the added information and question? Thank you in advance! – Bram Vanroy Dec 06 '16 at 10:37
  • Edit: WillNess advised me to post a new question for the follow-up issue so new topic [here](http://stackoverflow.com/questions/40994026/how-to-interpret-this-prolog-goal-with-a-cut-and-improve-efficiency). – Bram Vanroy Dec 06 '16 at 11:16
  • This is a prime example of what is known as a red cut. I was taught that it is good practice to use cuts only to improve efficiency, not as a way to implement if/else logic. In other words, the logic of your code should work correctly without cuts; once this is working, you can add cuts to remove unnecessary backtracking storage and thereby improve efficiency; such cuts are known as green cuts. – Stewart Dec 19 '20 at 20:23
2

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.

Stewart
  • 3,935
  • 4
  • 27
  • 36