Prolog: variable instantiation in satisfying a goal

Question

Question arose when reading from Programming in Prolog (2003) by Clocksin, Mellish.

Suppose we use lists to map from one sentence to another

change(keith, he).
change(very, too).
change(X, X).

alter([], []). 
alter([H|T], [X|Y]) :- change(H, X), alter(T, Y).

Could someone elucidate how the variables are instantiated? My book was not particularly in depth on this.

For instance, when using trace:

Call: (7) alter([keith, is, very, cool], _G2676) ? creep
Call: (8) change(keith, _G2756) ? creep
Exit: (8) change(keith, he) ? creep
Call: (8) alter([is, very, cool], _G2757) ? creep
Call: (9) change(is, _G2759) ? creep
Exit: (9) change(is, is) ? creep
Call: (9) alter([very, cool], _G2760) ? creep
Call: (10) change(very, _G2762) ? creep
Exit: (10) change(very, too) ? creep
Call: (10) alter([cool], _G2763) ? creep
Call: (11) change(cool, _G2765) ? creep
Exit: (11) change(cool, cool) ? creep
Call: (11) alter([], _G2766) ? creep
Exit: (11) alter([], []) ? creep
Exit: (10) alter([cool], [cool]) ? creep
Exit: (9) alter([very, cool], [too, cool]) ? creep
Exit: (8) alter([is, very, cool], [is, too, cool]) ? creep
Exit: (7) alter([keith, is, very, cool], [he, is, too, cool]) ? creep
B = [he, is, too, cool] .

I see several memory address references opened up, as in when alter is encountered in the rule, and recursively paired as:

alter([is, very, cool], ???? tail of Z

It seems the new Y would take the value of the tail of Z, but since Z is just a reference to a spot on the memory, how are these variables assigned values before returning? Also stemming from this confusion is that I am unable to articulate how the values in the head of the tail, X, in the alter predicate is then able to "build up", as it where, to retain the new values from the change predicate.

Answer 1

You're bringing a lot of procedural ideas ("baggage") to reading this trace. Let's try and read it with Prolog eyes:

Call: (7) alter([keith, is, very, cool], _G2676) ? creep

Prolog just restating your goal here. You can ignore the number in the generated variable _G2676; it isn't a memory location, the method of generating these variable names varies from implementation and platform, there's no mechanism in Prolog to read an arbitrary memory location, and these generated variable numbers are inaccessible to you in pretty much every sense. It's just an internal bookkeeping thing.

You probably issued a query like this:

?- alter([keith, is, very, cool], B).

Think about it like this. You're asking Prolog, "prove alter([keith, is, very, cool], B) and tell me what B is." So it's going to try to do it.

Call: (8) change(keith, _G2756) ? creep

What happened here? Prolog looked at your query and saw that you're using alter/2. It replaced the head of alter/2 with the body of alter/2. Quick Prolog anatomy lesson:

alter([H|T], [X|Y]) :- change(H, X), alter(T, Y).
-------------------    --------------------------
   "the head"                  "the body" 

So Prolog said, "to prove alter([keith,is,very,cool], B) I must prove alter([H|T], [X|Y]) with [keith,is,very,cool] = [H|T] and B = [X|Y]. (Prolog manages these variable names in the sensible way.) So now Prolog replaces the active query with change(H, X), alter(T, Y). Except, [H|T] = [keith|[is,very,cool]] and B = [X|Y]. So what gets printed in the trace is:

Call: (8) change(keith, _G2756) ? creep

Now Prolog has to take a look at its first clause of change/2, which it does, and finds change(keith, he). So Prolog says, "Aha! X = he" and then prints:

Exit: (8) change(keith, he) ? creep

Prolog now says, "OK, I just need to finish that query I started a second ago by looking at the next step in the body of alter/2, which is:

Call: (8) alter([is, very, cool], _G2757) ? creep

Well, just like before, Prolog is now going to replace the alter/2 query with the body of alter/2 and try to fulfill it, which means it must now prove:

Call: (9) change(is, _G2759) ? creep

This one is slightly more interesting, because the first clause of change/2 does not match. Prolog cannot unify keith with is, so it fails and moves on to the second clause. It cannot unify is with very, so it moves on to the third clause and unifies is with itself:

Exit: (9) change(is, is) ? creep

This process repeats, handing very/too and cool/cool, and then Prolog runs out of list constituents and you enter your base case of alter/2:

Call: (11) alter([], _G2766) ? creep
Exit: (11) alter([], []) ? creep

If you're paying attention, you should notice that the query line with the anonymous variable begins Call: to signify that Prolog is changing the question, and when Prolog answers the question, the line begins with Exit:. There are a few other things a line can begin with that tell you something else about Prolog's execution model: Retry: and Fail:. But you don't have those here because your query actually works on the first try.

From here out, you just get Exit because everything has successfully unified and Prolog is basically done. But this is where the "building up" is happening:

Exit: (11) alter([], []) ? creep
Exit: (10) alter([cool], [cool]) ? creep
Exit: (9) alter([very, cool], [too, cool]) ? creep
Exit: (8) alter([is, very, cool], [is, too, cool]) ? creep
Exit: (7) alter([keith, is, very, cool], [he, is, too, cool]) ? creep

What's happening here is that alter([], []) is proven, so it returns to the outer call (notice the numbers there; they are telling you about the call stack), which means Prolog now has proven that alter([cool], [cool]) is true, which means it has proven alter([very, cool], [too, cool]) is true, and so forth. This is just tail recursion working the way one would expect. Finally it outputs that your query succeeded:

B = [he, is, too, cool] .

So, there's really no memory addresses being opened up here, as you put it.

It seems the new Y would take the value of the tail of Z, but since Z is just a reference to a spot on the memory, how are these variables assigned values before returning?

In a "normal" programming language, you call a function with some values and you get one value back as a return value. Prolog is not a normal programming languages; you are not defining functions, you are defining relations. A relation is less constrained than a function: sometimes your parameters are inputs and sometimes they are outputs. Variables in Prolog are not "references to spots in memory." They are just names for data; they can be ground or free depending on whether they have been figured out.

Each step of evaluation in Prolog, Prolog is searching for bindings for the free variables. This is called unification and is the fundamental execution model in Prolog. When you issue a query like change(keith, X) you are asking Prolog to prove that change(keith, X) is true and supply you with the value X that makes it true. Prolog will look at that and come back with true, X = he. But you can also ask it change(X, he) and Prolog will look at it and say, true, X = keith. This is part of what makes it a relation and not a function. You can also say change(X, Y) and it will come back with true, X = keith & Y = he; X = very & Y = too; X = Y and that multiplicity of results is another way you know you are dealing with relations and not functions.

So in Prolog a variable is not a "spot in memory", it is a binding between a name and a value, and Prolog is able to establish that binding at any step in the evaluation, not just on the way in or during a computation, but on the way out of a successful computation as well!

I bet if you look back in your book, you'll see that it goes into plenty of detail about this. It's one of the best Prolog books out there, and it certainly details this stuff. But I hope this helps anyway!