Finding query for which a prolog program gives incorrect result

Question

This Prolog program defines the third argument to be the maximum value of the first two numeric arguments:

max(X, Y, X) :- X >= Y, !.
max(X, Y, Y).

I think that this program works just fine. But I am told that it can give incorrect result. Can you tell when and why?

Familiarity

What if X,Y are not bound to integers or real numbers? – Tribadism

we assume that the arguments are numeric values – Familiarity

Answer 1

This is a textbook example.

?- max(5,1,1).
true.

Homework: Why is the program wrong? How do we make the program correct?

EDIT

max(X, Y, X) :- X >= Y, !.
max(X, Y, Y).

Our intention is to say:

If X is greater than Y, then Max is X. Otherwise, Max must be Y.

Instead, what is say is:

When the first and third arguments (X and Max) can be unified, and X is greater than Y, succeed. Otherwise, if the second and third arguments (Y and Max) can be unified, succeed.

The obvious problem arises then the first and third arguments cannot be unified, but the second and the third can.

Instead:

max(X, Y, X) :- X >= Y.
max(X, Y, Y) :- X < Y.

or

max(X, Y, Max) :- X >= Y, !, Max = X.
max(_, Max, Max).

Davidadavidde

This definition of max/3 only works if all arguments are instantiated. However, one will typically not only want to test but also find solutions, for example, what is the maximum of two given numbers? Or for example, which numbers have a given maximum? A modern solution for such questions are constraints, for example, with finite domain constraints: M #= max(X, Y). It can be used in all directions, to find and test solutions. – Chuck

@Chuck Absolutely. But this is, after all, a clear cut case of an exam/tutorial question and obviously going after the textbook answer. I wish that people would read at least "The Art of Prolog" when they take the course in university and Stackoverflow discussions can finally move on from the questions that have been answered decades ago onto greener pastures. Unfortunately, it is not happening, and the Prolog tag is flooded by non-productive chewing over of age-old dried up stuff. – Davidadavidde

@Chuck not all, but at least the first two, actually. If you use SWI-Prolog notation it would be max(+A, +B, -Max) – Davidadavidde

Answer 2

It does work fine, provided the third argument is uninstantiated. The danger here would be if there were a way to backtrack into the second rule, or if the third argument is instantiated to the same value as the second. It's not particularly safe looking because max(X, Y, Y). is equal to max(_, Y, Y) which just sets the result to the second value without any thought. The cut at the end of the first rule effectively ensures that backtracking will not commence if X >= Y, so the second rule should only be entered when X < Y and Z is not already equal to Y.

Though it mostly works, it's not a good habit to get into. People new to Prolog tend to think procedurally and making use of the cut like this to ensure a particular result through procedural trickery ultimately holds you back and leads to convoluted Prolog that cannot be driven in different and interesting ways. There are several other ways of writing this predicate that work just as well but do not rely on the cut to ensure their behavior, for instance:

max(X, Y, X) :- X >= Y.
max(X, Y, Y) :- X < Y.

or

max(X, Y, Z) :- X >= Y -> Z = X ; Z = Y.

Neither of these is vulnerable to the problem of the third being instantiated. Interestingly, this is a great illustration of the difference between a red cut and a green cut. Your code has a red cut, where the behavior is dependent on the cut, but if I simply change my first solution to this:

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

That's a green cut, because the behavior is not dependent on the cut, but Prolog's performance may improve slightly since it won't backtrack into the second clause to try it. Here we're explicitly telling Prolog, don't both making the next check because we know it will fail. With a red cut, there's no other check which will fail.

It's unfortunate that stating the condition twice feels redundant but relying on a single rule feels clunky. In practice, my experience is that scenarios like these are not ultimately all that common; usually you have atoms or structures you can match in the head of the clause that create behavior like we have in my first substitute, but without needing a body. For example:

perform(scan(target, X, Y)) :- ...
perform(scan(calibration, X)) :- ...

This has the same effect: Prolog will backtrack until it unifies successfully, then it will back track again, but the exclusive nature of the matching will prevent another body from being executed. If we find out it's spending too much time backtracking we can add cuts to improve the performance, but in practice it's unlikely to be a problem.

Greensward

Your reasoning in the first paragraph is wrong. When the second and third arguments are instantiated to the same number, the first clause is not considered at all. – Davidadavidde

But why would you instantiate the third argument to the lesser number of the two, when you want it to be the greater? – Familiarity

@Boris Good call. Will fix. – Greensward