Procedural semantics of swi-Prolog: failure to understand the resulting substitution

user_13281865 0
Viewed 72

I fail to understand swi-prolog's behavior when the database

on(a,b).

is queried with

:- on(A,B),on(C,D).

To my best understanding, what is supposed to happen is the following: first, the leftmost goal in the query is matched against the database. This succeeds immediately, leading to the removal of said goal from the query as well as to the substitution

[A=a,B=b]

Next, this substitution is applied to the remaining goal, which does nothing, since neither A nor B appear in the second goal. Now, the remaining goal is matched against the database, which again succeeds. Now we are done, and we should be left with the substitution

[A=a,B=b,C=a,D=b]

And this should be the only substitution the interpreter is able to come up with, provided my understanding of prologs procedural semantics is correct. Unfortunately, swi-prolog thinks otherwise. Instead it comes up with the substitution

[A=C,B=D,C=a,D=b]

If you are very generous, you could say that "both answers mean the same", but I am never generous when it comes to understanding what a program does, and I ran into this in a context where it actually matters. So I would be most appreciative if someone could help me to figure out what's going on.

prolog semantics substitution
3 Answers

Something close to the output you want but using the usual Prolog pair representation:

bindings(Query, Bindings) :-
    term_variables(Query, Variables),
    copy_term(Query, Copy),
    term_variables(Copy, VariablesCopy),
    call(Copy),
    pairs_keys_values(Bindings, Variables, VariablesCopy).

Sample call:

?- bindings((on(A,B),on(C,D)), Bindings).
Bindings = [A-a, B-b, C-a, D-b].

The only non-standard predicate is pairs_keys_values/3 but this is available in several libraries. Above I used library(pairs) from SWI-Prolog. Logtalk (which you can run with most Prolog systems) provides a pairs library object with a keys_values/3 predicate with the same semantics and argument order.

user_6346290

But the two substitutions are the same.

We can only know a thing by its interactions; for any valid implementation of substitute( Term, Substitution, Substituted_term ) no difference can be observed with either of the two forms you show.

It is thus purely a matter of representation. Any representation can be chosen as long as the observable results remain the same.

user_8498910

Note that the result is even valid for:

on(a,b).
on2(a,b).

?- on(A,B),on2(C,D).
A = C, C = a,
B = D, D = b.

In any case it would be nicer of Prolog to write

A = C = a,
B = D = b.

Here is a diagram from earlier I adapted. I have no idea whether things are implemented like that, Maybe NULL pointers are used when the variable is "fresh"? It's not important.

Variables and their bindings

user_8844630
Related