Prolog: Redundant results in clauses involving anonymous variables

Question

Consider the following Prolog program.

a(X) :- b(_), c(X).

b(1).
b(2).
b(3).

c(1).

Running the query:

a(X).

in SWI-Prolog, we get three results, all X = 1.

Given that we do not care about the anonymous variable, what is preventing SWI-Prolog to return a single result? Why isn't this optimization performed?

Thanks

Answer 1

Well for Prolog the underscore is simply an anonymous variable. So the a/1 predicate is equivalent to:

a(X) :-
    b(Y),
    c(X).

Now it may look useless to backtrack over the b(Y) clause, since once it is satisfied, the Y is nowhere used, and thus should not have impact on the rest of the program. Furthermore Y has no effect on X so b(Y) should not have the slightest influence on X.

In real Prolog however, there are some things that might have impact:

1. the b/1 predicate might perform I/O. Say that the predicate is implemented as:

   b(a) :-
       print(a).
   b(a) :-
       print(b).
   

   then it will print a in the first branch and b in the second one.

2. b/1 might raise an exception in a second, third, ... path. In which case we probably want to handle the error;

3. b/1 might use asserta/1, assertz/1, etc. and alter the program. It might for instance add facts for c/1 such that in the second run c/1 has other results.

4. A lot of Prolog interpreters have a non-backtrackable store such that the different backtracking paths, can share information with each other.

5. other coding facilities such that the outcome of b/1 might have impact on c/1.

You can avoid this backtracking over b/1 by using the once/1 meta-predicate. For instance:

a(X) :-
    once(b(_)),
    c(X).