Finding query for which a prolog program gives inc

Question

This Prolog program defines the third argument to be the maximum value of the first 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?

Answer 1

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.

Answer 2

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).