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

What if `b/1` introduced a side effect, such as `b(4) :- asserta(c(2)).`? Not saying it's impossible, but it isn't trivial either, because some random unification can produce a lot of secondary effects. — Daniel Lyons, Sep 02 '17 at 21:51
For the sake of the question, can we consider that the database is static? — Alberto Illobre, Sep 02 '17 at 21:55
If you want to suggest an optimization that only works on a trivial subset of your language, you also have to explain how the compiler will figure out whether some piece of code is trivial to see whether the optimization will be activated. Often, this determination is tantamount to executing the code, which balloons the compiler's time complexity. So no, I don't think you can consider the database static. To do so is to discuss a different language than Prolog, and if you want to ask why an optimization is or isn't performed, you probably want to know the real reason why, in the real language. — Daniel Lyons, Sep 04 '17 at 04:28

Willem Van Onsem · Accepted Answer · 2017-09-03T13:32:00.333

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:

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.
b/1 might raise an exception in a second, third, ... path. In which case we probably want to handle the error;
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.
A lot of Prolog interpreters have a non-backtrackable store such that the different backtracking paths, can share information with each other.
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).

Prolog: Redundant results in clauses involving anonymous variables

1 Answers1