Artificial Intelligence Question posted in
ChatGBT is becoming a world-wide phenomena, try it out here.

Reading a cut ! in Prolog – Artificial Intelligence

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?

Tags:

2

Answers


  1. 0

    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.

    Login or Signup to reply.
  2. 0

    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.

    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search