Prolog unification broken when argument order is changed

Question

I can’t seem to wrap my head around this. Consider the following dummy predicate:

foo(X, a) :- X < 10.
foo(X, b) :- X > 20.

When consulting:

?- foo(1, a).
true; 
false.

I am not sure I completely understand how the choice point is created anyway (Perhaps because the two possible foo predicates are in a kind of or relationship and Prolog just tries to unify with both? Based on this line in the trace: Redo: (24) test:foo(8, a) and the subsequent fail, I suppose this is the case), but what really confuses me is why it works when the argument order is changed:

foo(a, X) :- X < 10.
foo(b, X) :- X > 20.

?- foo(a, 1).
true.

No choice point. What am I missing here?

Prolog will normally "index" on the first parameter. So it knows that b can never be a good match, and skips it. — Willem Van Onsem
Okay, but why doesn’t it know that in the first case even though X could match, b still doesn’t? — bp99
because for most Prolog interpreters, this indexing is only done on the first parameter. Often Prolog programs are written such that distinction on the functor, first parameter is used to boost efficiency. — Willem Van Onsem
It's not really important either (except the if leftover choicepoints start to hit performance in long-running / deep programs - which is indeed quickly the case). As long as findall(found, foo(1,a), All) spits out a single solution, [found], it's good. Add a "!" or a "-"> to make the Prolog processor "commit" to its clause after the guard test: foo(X) :- guard(X),!,do_sth(X). or (maybe clearer) foo(X) :- guard(X) -> do_sth(X). to increase determinacy while making sure the solutions collected by findall/3 stay constant. — David Tonhofer
I see, so this is just like this in Prolog. @DavidTonhofer why would I do that rather than just using foo(1, a), !. when I am already cutting? And thank you both, can one of you please create an answer as well so I can select it as the solution? — bp99

TA_intern TA_intern · Accepted Answer · 2020-11-01T16:31:32

TL;DR: read the documentation of the Prolog you are using. Pay attention to "clause indexing" or something of the kind.

You are missing that whichever Prolog implementation you are using is just clever enough to do indexing on the first argument in your second example. So when you pose the query ?- foo(a, Something). it never considers the other clause.

But this is really a matter of Prolog implementation, and not a matter of Prolog as a language. Maybe there are Prologs that can also avoid the choice point in the first example. Or maybe it provides a different mechanism to achieve the same. For example SWI-Prolog (among other Prologs) has something called "tabling". With it, you can do it like this:

:- table foo/2.

foo(X, a) :- X < 10.
foo(X, b) :- X > 20.

bar(a, X) :- X < 10.
bar(b, X) :- X > 20.

Now neither foo/2 nor bar/2 has the unexpected choice point:

?- foo(1, a).
true.

?- bar(a, 1).
true.

Prolog unification broken when argument order is changed

1 Answers