In a Warren's Abstract Machine, how does bind work, if one of the arguments is a register?

Question

I'm trying to create my own WAM implementation and I'm stuck at the exercise 2.4

I can't understand how to execute instruction unify_value X4 in figure 2.4.

As far as I understand, this instruction should unify Y from the program with f(W) from the query.

unify_value X4 calls unify (X4,S) where S=2 (see Figure 2.1) and a corresponding heap cell is "REF 2", and X4 is "STR 5".

Unify (Figure 2.7) should bind those values, but I do not understand how to deref a register.

"REF 2" is in the heap, "STR 5" is in a register. How do you bind something to a register?

Answer 1

We are talking about Warren's "New" Engine, WAM and not the Old Engine, known as PLM.

In the WAM variables are allocated in two places.

1. the local stack (environment stack)

2. the heap

Registers cannot hold variables. However, they may hold references to variables. Note that references from the heap only point into the heap.

Much related to your question is the pretty ingenious way how the WAM maintains this order and at the same time has very cheap last-call optimization. At the point in time of a (determinate) last call, the local variables that are arguments of the last call must be moved somehow. In more traditional Prolog machines like the ZIP this is an extremely laborious undertaking which essentially requires to scan the environment frame for variables still sitting in them.

The WAM however has a much better calling convention: Most variables are already in a safe place, which can be trivially analyzed during compilation. The very few remaining need an explicit PUT_UNSAFE instruction where the value is checked, and should it still be a local variable that variable is transferred onto the heap.

Consider what is a safe variable in the WAM:

1. All variables occurring in the head

2. All variables that appear as an argument of a structure

Thus only variables that appear first in a goal and in the last goal and that do not appear in some structure must have a PUT_UNSAFE. That is not that much. Further, the dynamic check may reduce the actual copying onto the heap to a minimum.

At first this PUT_UNSAFE looks like a lot of work, but never forget that the WAM permits to remove many PUTs, while the ZIP has to execute at least one instruction for each argument.

Here is a tiny typical example using GNU:

a --> b, c.

expanded to:

a(S0,S) :- b(S0,S1), c(S1,S).

and compiled using the command pl2wam to:

predicate(a/2,1,static,private,monofile,global,[
    allocate(2),
    get_variable(y(0),1),                   % S
    put_variable(y(1),1),                   % S1
    call(b/2),
    put_unsafe_value(y(1),0),               % S1
    put_value(y(0),1),                      % S
    deallocate,
    execute(c/2)]).