Wilhelm R., Seidl H. Compiler Design. Virtual Machines

Подождите немного. Документ загружается.

110 4 Logic Programming Languages

S f/n

a atom

variable

unbound variable

structure

1 location

(n+1) locations

Fig. 4.3. The heap objects of the WIM

the node. To realize this idea we require a WIM instruction for each possible type of

node.

Example 4.3.1 Consider the following term:

(g(X, Y), a, Z)

Here, X is assumed to have been initialized already, that is, S[FP +

(X)] con-

tains already a reference. In contrast, the variables Y and Z are assumed to still be

unbound. Then, the heap must be extendedas shownin Fig. 4.4. Note that our alloca-

tion strategy implies that references in heap locations with higher addresses always

point to heap locations with lower(or equal) addresses. We will alwaystryto achieve

this direction for references whenever possible. If we could enforce this invariant

throughout, younger heap objects could be released without producing references to

deallocated objects (dangling references).



Our Example 4.3.1 indicates that bound and unbound variables must be treated dif-

ferently. To differentiate them, we mark occurrences of already initialized variables

with a top bar (

X in the example). Arguments are always initialized, but anonymous

variables, on the other hand, never are. According to this discussion, we deﬁne:

4.3 Allocation of Terms in the Heap 111

A a

S f/3f/3S

S g/2

reference to X

Fig. 4.4. Theheapforthetermf (g(

X, Y

), a, Z)

code

= putatom a

code

= putvar

(X)

code

= putref

(X)

code

= putanon

code

f (t

,...,t

)

= code

...

code

putstruct f /n

Example 4.3.2 For the term f

(g(

X, Y

), a, Z) of Example 4.3.1 and an address en-

vironment

= {X → 1, Y → 2, Z → 3}, we produce the sequence:

putref 1 putatom a

putvar 2 putvar 3

putstruct g

/2 putstruct f /3



In this way, code can be generated for constructing terms. We now implement the

instructions that are required for this purpose.

The instruction putatom a creates an atom in the heap (Fig. 4.5).

The instruction putvar i creates a new, not initialized, variable and additionally

initializes a corresponding location in the stack frame (Fig. 4.6).

112 4 Logic Programming Languages

A a

putatom a

SP++; H[HP] ← (A, a);

[SP] ← HP; HP++;

Fig. 4.5. The instruction putatom a

putvar i

SP++; H[HP] ← (R, HP);

[FP + i] ← S[SP] ← HP; HP++;

Fig. 4.6. The instruction putvar i

The instruction putanon creates a new unbound variable, pushes a reference to

it onto the stack, but does not save a reference for it in the stack frame (Fig. 4.7).

FPFP

putanon

SP++; H[HP] ← (R, HP);

[SP] ← HP; HP++;

Fig. 4.7. The instruction putanon

The instruction putref i pushes the reference from S[FP + i] onto the stack and then

4.3 Allocation of Terms in the Heap 113

FP FP

putref i

SP++; S[SP] ← deref (S[FP + i]);

Fig. 4.8. The instruction putref i

dereferences it as much as possible. For this we use the auxiliary function deref():

ref deref

(ref v) {

if (H[v]=(R, w) ∧ v = w)) return deref (w);

else return v;

}

The instruction putstruct f /n creates an application of the constructor f /n in the

heap (Fig. 4.9). Our translation scheme together with the deﬁnitions of the new

putstruct f/n

f/nS

SP ← SP −n + 1; H[HP] ← (S, f /n);

for

(i ← 0; i < n; i++) H[HP + 1 + i] ← S[SP + i];

[SP] ← HP; HP ← HP + n;

Fig. 4.9. The instruction putstruct f

virtual instructions creates references that always point to lower heap addresses, not

onlyfortheexampletermfromExample4.3.1butingeneralwhenbuildingupterms.

114 4 Logic Programming Languages

4.4 The Translation of Literals

Literals in PRO L are treated like procedure calls in imperative languages. Therefore,

a stack frame is allocated for their evaluation. Representations of terms are con-

structed in the heap that serve as actual parameters and references to these are stored

within this stack frame. Finally, control is transferred to the code for the procedure,

that is, the predicate. This results in the following translation scheme for literals:

code

q(t

,...,t

)

= mark B // allocate a stack frame

code

...

code

call q/k // call the procedure q/k

B : ...

Example 4.4.1 Consider the literal q

(a, X, g(

X, Y

)). In an address environment

= {X → 1, Y → 2}, our translation scheme results in:

mark B putref 1 call q

putatom a putvar 2 B : ...

putvar 1 putstruct g

/2 

Before we implement the WiM instruction mark B, we must understand howa stack

frame of the W

IM is organized (Fig. 4.10). The simplest organization places ﬁrst the

organizationalcellswithintheframe.Above them, the actual parametersof the literal

are allocated, possibly followed by further local variables of the selected clause. As

with the virtual machine for C, the parameters and local variables are addressed

relative to FP. As usual, we letthecurrent FP pointtothelastorganizationalcell.We

have already identiﬁed two organizational cells. One such cell is needed for storing

the current PC,thepositive continuation address, which is the location in the code

at which execution should continue if the literal has been completed successfully.

This is similar to the return address in the C-Machine. One further memory cell is

required for saving the contents of the register FP before the call. It turns out that,

for the implementation of backtracking, four further registers and, accordingly, four

more organizational cells are required.

Now we can implement the instruction mark B (Fig. 4.11). This instruction

allocates space for six organizational cells on the stack. Then, it saves the current FP

and saves B as the positive continuation address.

The instruction call q

/k makes the register FP point to the topmost organiza-

tional cell of the stack frame and calls the k-ary predicate q

/k (Fig. 4.12).

4.5 Uniﬁcation 115

Fig. 4.10. The stack frame of the WIM

mark B

FP FP

S[SP + 5] ← FP; S[SP + 6] ← B; SP ← SP + 6;

Fig. 4.11. The instruction mark B

4.5 Uniﬁcation

The most important operation when executing a logic program is uniﬁcation.The

goal of the uniﬁcation of two terms is to ﬁnd a most general substitution of the

variables occurring within the terms such that the two terms become equal.

Example 4.5.1 Consider the two terms:

(X, g(a, X)) and f (h(b), g(Y, Z))

A substitution that uniﬁes both terms is given by:

posForts.

FPold

-4

-5

-1

-2

-3

local variables

local stack

6 org. cells

further stack frames

116 4 Logic Programming Languages

call q/k

q/k

FP ← SP − k; PC ← q/k;

Fig. 4.12. The instruction call q

{X → h(b), Y → a, Z → h(b)}

In this example there is only one unifying substitution. This is not always the case.

For the two terms:

(X, g(a, X)) and f (h(Z), g(a, Y))

there is an inﬁnite number of possible substitutions. One minimal unifying substitu-

tion, which is the one that substitutes a minimal number of variables, for these two

terms is given by:

{X → h(Z), Y → h(Z)}

Such a minimal unifying substitution has the nice property that all other unifying

substitutions can be produced from it by substituting further variables. Therefore,

we call such unifying substitutions most general uniﬁers.

As the reader probably already realized, a uniﬁcation may fail. Consider, for

instance, these two terms:

(X, a) and f (h(Z), g(a, Y))

There is no substitution of variables that makes these two terms equal. A special case

is when a variable X is supposed to be uniﬁed with a term that is not itself equal to

X, butcontains the variable X, such as f

(X, a). In this case, there is also no unifying

substitution – at least no unifying substitution that binds variablesto ﬁnite terms.



Our goal is to translate a uniﬁcation equation X = t. If the variable X on the left-

hand side is not initialized, we set:

code

(X = t)

= putvar

(X)

code

bind

The term t is constructed and then the reference object for X bound to t. This last

task is realized by the instruction bind (Fig. 4.13.). The variable that is bound by

4.5 Uniﬁcation 117

R R

bind

H[S[SP − 1]] ← (R, S[SP]); trail (S[SP −1]); SP ← SP − 2;

Fig. 4.13. The instruction bind

the bind instruction may additionally be recorded through the call of the run-time

function trail, which we will discuss later.

It remains to explain uniﬁcation for the case that the left-hand side X is already

bound. As in the case of an unbound variable, a reference to (the binding of) X is

pushed onto the stack and on top of it a reference to the term t. Unifying the two

terms, that is, creating the required bindings of the variables occurring in the two

terms, is delegated to a dedicated instruction unify. This results in the following

translation scheme:

code

(

= t)

= putref

(X)

code

unify

Example 4.5.2 Consider the following equation:

= f (g(

X, Y

), a, Z)

For the address environment:

= {X → 1, Y → 2, Z → 3, U → 4}

we have:

putref 4 putref 1 putatom a unify

putvar 2 putvar 3

putstruct g

/2 putstruct f /3



The instruction unify calls the run-time function unify() for the two topmost stack

references (Fig. 4.14).

The function unify

() of the r un-time system receives as input two heap addresses

and performs the uniﬁcation. As an optimization, it exploits the fact that equal heap

118 4 Logic Programming Languages

unify

unify (S[SP − 1], S[SP]); SP ← SP −2;

Fig. 4.14. The instruction unify

addresses are already uniﬁed. When binding two variables, the younger with the

higher address s hould always be bound to the older with the lower address. When

binding a variable to a term, it must be checked that this variable does not occur

within the term. This check is called the occur-check. Additionally, all bindings that

have been introduced must be recorded so that theycan be reversed later if necessary.

Finally, the uniﬁcation may fail. In this case, backtracking is initiated.

4.5 Uniﬁcation 119

bool unify (ref u, ref v) {

if (u = v) return true;

(H[u]=(R, _)) {

if (H[v]=(R, _)) {

if (u > v) {H[u] ← (R, v); trail (u); return true; }

else {H[v] ← (R, u); trail (v); return true; }

}

else if (check (u, v)) {

H[u] ← (R, v); trail (u); return true;

} else {backtrack(); return false; }

}

if ((H[v]=(R, _)) {

if (check (v, u)) {

H[v] ← (R, u); trail (v); return true;

} else {backtrack(); return false; }

}

if (H[u]=(A, a) ∧ H[v]=(A, a)) return true;

(H[u]=(S, f /n) ∧ H[v]=(S, f /n)) {

for (int i ← 1; i ≤ n; i++)

if (¬unify (deref (H[u + i]), deref (H[v + i])) return false;

return true;

}

backtrack(); return false;

}

The uniﬁcation of the terms in Fig. 4.15 sets references according to Fig. 4.16.Note

that our implementation makes, whenever possible, references at higher addresses

point to objects with lower addresses.

Our implementation uses three auxiliary functions. The auxiliary function trail

()

records new bindings. The auxiliary function backtrack() initiates the backtracking.

These two functions will be discussed later. The auxiliary function check

() imple-

ments the occur-check. It checks whether the variable in the ﬁrst argument appears

in the term whose representation is pointed to by the second argument. For efﬁciency

reasons, this test is left out in some implementations. Then it is realized by:

bool check

(ref u, ref v) { return true; }

Otherwise, it can be implemented as follows: