Prolog query order and efficiency (is trace misleading?)

Prolog ByExample 0
Viewed 68

Consider the following simple prolog program.

hairy(dog).
hairy(cat).

colour(dog, brown).
colour(dog, black).
colour(cat, grey).
colour(cat, white).

The following queries are logically equivalent.

?- colour(X, white), hairy(X).
?- hairy(X), colour(X, white).

Although the two queries are logically equivalent, the procedural execution is different.

Prolog's trace appears to confirm that one is more efficient than the other.

trace, colour(X, white), hairy(X).
 Call:colour(_3844,white)
 Exit:colour(cat,white)
 Call:hairy(cat)
 Exit:hairy(cat)

and

trace, hairy(X), colour(X, white).
 Call:hairy(_4052)
 Exit:hairy(dog)
 Call:colour(dog,white)
 Fail:colour(dog,white)
 Redo:hairy(_476)
 Exit:hairy(cat)
 Call:colour(cat,white)
 Exit:colour(cat,white)

Question: Is the first query actually more efficient than the second?

That is, is the longer set of trace steps for the second query misleading?

For example, in the shorter trace the first task is to find which X satisfies colour(X, white) and the trace exits immediately with X=cat, but in reality is the fact that it has to search through the previous three colour/2 facts hidden from us?

Motivation

I want to conclude that ordering the query predicates such that variables are instantiated correctly soonest is a good strategy for optimal or efficient queries. I'd welcome comments on this, which is the broader motivation for the question.

prolog
1 Answers

is trace misleading?

Yes, very much so. For one, the trace does not distinguish between determinate Exit and non-determinate ones. You can figure this out only indirectly by looking at the complete trace. Also, the example is artificially small and it produces exactly one answer. This is rather the exceptional case. Most of the time you have many more facts and there, the situation could reverse.

But in any case, if you want to understand the exact mechanisms behind, rather rely on the prolog-toplevel.

Your first query is ?- colour(X, white), hairy(X). Instead, look at the first goal alone.

?- colour(X, white).
X = cat.

So this tells you that there is exactly one white entity (or animal) in your database. SWI is really sure about this and so it stops immediately with a . at the end of its answer. Is this plausible in general? Certainly there are many more white animals, so with a more realistic version of your database all these animals would have to be enumerated.

Now for the start of your second question:

?- hairy(X).
X = dog ;
X = cat.

Here are two such solutions which means that both cases have to be explored and that's the reason the trace of the second query is longer.

How many hairy animals are there compared to white animals? We cannot be that sure, but whichever is significantly smaller, would be a better first goal. In any case, such considerations are often leading to a lot of micro-optimizations which are not worth the time to think about them. Also, the precise mechanisms behind (indexing of the first or second argument) may blur this completely.

What is much more important in Prolog is to master termination which includes understanding non-termination.

false0
Related