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

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

130 4 Logic Programming Languages

void trail (ref u) {

if (u < S[BP −2]) {

TP ← TP + 1;

[TP] ← u;

}

void reset (ref x, ref y) {

for (ref u ← y; x < u; u−−)

H[T[u]] ← (R, T[u]);

}

The stack location S[BP − 2] contains the value of the heap pointer from the last

backtrack point. The test in the function trail

() gives a simple criterion whether a

reference should be recorded on the trail or not.

4.7.2 Putting It All Together

Assume that the predicate q

/k is deﬁned by the sequence of clauses rr ≡ r

,...,r

where f

> 1. Code is required ﬁrst to initialize the backtrack point. It must be

ensured that the different alternatives are tried in turn. At the end, the backtrack

point should be released. Consequently, we generate the following code:

code

rr = q/k : setbtp

try A

...

try A

f −1

delbtp

jump A

: code

...

: code

Interestingly, the backtrack point is released already before trying the last alternative

and control is directly transferred to this last alternative. The reason is that after a

failure of the last alternative, control will never return to this stack frame.

Example 4.7.1 Consider the following predicate:

(X) ⇐ t(

)

s(X) ⇐

= a

According to our scheme, the translation of the predicate s produces:

4.8 The Finalization of Clauses 131

s/1: setbtp A : pushenv 1 B : pushenv 1

try A mark C putref 1

delbtp putref 1 uatom a

jump B call t

/1 popenv

C : popenv



New instructions are required for our translation scheme. The instruction setbtp cre-

ates a backtrack point. It saves the registers HP, TP and BP (Fig. 4.29). The in-

setbtp

FPFP

S[FP −2] ← HP; S[FP −3] ← TP;

[FP − 4] ← BP; BP ← FP;

Fig. 4.29. The instruction setbtp

struction try A tries the alternative with start address A and stores the value of the

PC in the current stack frame as the negative continuation address: the value of the

PC is the address of the next instruction in the try chain (Fig. 4.30). The instruction

delbtp ﬁnally restores the previous value of the backtrack pointer (Fig. 4.31).

4.8 The Finalization of Clauses

The only aspect left open so far when translating clauses and predicates is the in-

struction popenv. This instruction is responsible for the ﬁnal treatment of the stack

frame when the body of a clause has been successfully executed. Let us recall the

translation of clauses:

132 4 Logic Programming Languages

A29

try A

PCPC

S[FP −5] ← PC; PC ← A;

Fig. 4.30. The instruction try A

delbtp

FPFP

BP ← S[FP −4];

Fig. 4.31. The instruction delbtp

code

r = pushenv m

code

...

code

popenv

Naturally, we attempt to release the current stack frame when reaching the end of

the body. This, however, is not always possible. The current stack frame can be a

backtrack point with further open alternatives. Also, when executing the literals in

4.8 The Finalization of Clauses 133

the body of the clause, new backtrack points could have been created on top of the

current stack frame. In fact, these are the only two obstacles to releasing the current

stack frame. A simple test for the release of the frame is to compare the current BP

with FP.IfBP

< FP, the stack frame can safely be released, otherwise it must be

preserved.

This comparison is performed by the instruction popenv (Fig.s 4.32 and 4.33).

First,theinstruction attempts to releasethestack frame. Then, itrestoresthe registers

FP and PC. Despiteitsname, the instructionpopenv might not alwayspop the stack

popenv

if (BP < FP) SP ← FP − 6;

← S[FP −1]; PC ← S[FP];

Fig. 4.32. The instruction popenv when releasing the stack frame

frame. If a stack frame of the body of a clause could not be released, still further data

42 42

popenv

Fig. 4.33. The instruction popenv without release of the stack frame

134 4 Logic Programming Languages

may be pushed onto the top of the stack. When returning to the stack frame of the

clause, the local variables may have an arbitrary distance from the Stack Pointer, but

still can be addressed through the FP.

4.9 Queries and Programs

So far, we have translated all constituent parts of a PROL program. The only remain-

ing aspect is how to translate programs as a whole. Assume that program p consists

of predicate deﬁnitions rr

.....rr

together with the query ⇐ g

,...,g

. The code

for program p then consists of the following parts:

• code for evaluating the query

⇐ g

,...,g

• an instruction no for failure, and

• code for the predicates rr

Before program execution, we assume that SP

= FP = BP = TP = −1 and

= HP = 0. Before evaluating the query, registers SP, FP and BP must be

initialized and the ﬁrst stack frame must be pushed onto the stack. Afterwards, the

result substitution is returned (or failure is reported):

code p

= init A

pushenv d

code

...

code

halt d

A : no

code

...

code

Here {X

,...,X

} = free(g

,...,g

) is the set of variablesin the query g

,...,g

and

)=i for i = 1,...,d holds.

The instruction halt d terminates program execution and outputs the ﬁnal bind-

ings of variable d or initiates backtracking – if demanded by the user.

The instruction init A initializes SP, FP and PC and records the address A in

the stack frame as the negative continuation address (Fig. 4.34). We have placed the

instruction no at address A. This instruction is executed when the query has failed. It

prints no to the standard output and halts.

Now we can translate the ﬁrst complete P

RO L program.

Example 4.9.1 Consider the following small program:

(X) ⇐

= bq(X) ⇐ s(

) s(X) ⇐

= a

⇐ q(X), t(

) s(X) ⇐ t(

) ⇐ p

4.10 Optimization I: Last Goals 135

init AFP

SP ← FP ← BP ← 5;

[0] ← A; S[1] ← S[2] ←−1;

[3] ← 0;

Fig. 4.34. The instruction init A

The translation generates:

init N popenv q

/1: pushenv 1 E : pushenv 1

pushenv 0 p

/0: pushenv 1 mark D mark G

mark A mark B putref 1 putref 1

call p

/0 putvar 1 call s/1 call t/1

A : halt 0 call q

/1 D : popenv G : popenv

N : no B : mark Cs

/1: setbtp F : pushenv 1

/1: pushenv 1 putref 1 try E putref 1

putref 1 call t

/1 delbtp uatom a

uatom bC: popenv jump F popenv



4.10 Optimization I: Last Goals

Aswithfunctionalprograms,theefﬁciencyofthegeneratedcode can be signiﬁcantly

increased through simple optimizations. Consider, for instance, the predicate app/3

from the introduction:

app

(X, Y, Z) ⇐ X =[], Y = Z

app

(X, Y, Z) ⇐ X =[H|X



], Z =[H|Z



], app(X



, Y, Z



)

The recursive call is the last goal in the last clause. After (successful) completion of

this goal, control does not return to the current caller. We want to treat such a goal

as a last call as we did in the translation of functional programs. If possible, no new

stack frame should be allocated. Instead, the call should be evaluated in the current

stack frame.

136 4 Logic Programming Languages

Consider a clause r of the form

,...,X

) ⇐ g

,...,g

with m local variables, where the last goal g

is the literal q(t

,...,t

). Let us look

more closely at the cooperation between code

and code

code

r = pushenv m

code

...

code

n−1

mark B

code

...

code

call q/h

B : popenv

As an optimization, we replace the mark B instruction with the new instruction

lastmark andthesequencecallq

/h; popenv withthenew instructionlastcall q/hm.

Then, we obtain:

code

r = pushenv m

code

...

code

n−1

lastmark

code

...

code

lastcall q/hm

If the current clause is not the last or g

,...,g

n−1

has produced backtrack points,

then FP

≤ BP. In this case, the current stack frame cannot be released before the

lastcall.Instead,the lastmark instruction must allocateanewframewithareference

to the predecessor of the current frame (Fig. 4.35). If, on the other hand, FP

> BP,

then the current stack frame can be reused for the last call. The lastmark instruction

then does nothing.

The lastcall q

/hminstruction again compares the registers FP and BP (Fig.

4.36). If FP

≤ BP, lastcall q/hmbehaves like an ordinary call q/h.If,onthe

other hand, FP

> BP, the current parameters in locations S[FP + 1], S[FP +

2],...,S[FP + h] are replaced, and control jumps to q/h.

The difference between the original and the new addresses of the actual parame-

ters of q

/h is SP − h − FP = m, that is, the number of local variables in the stack

frame.

4.10 Optimization I: Last Goals 137

lastmark

FPFP

BP BP

if (FP ≤ BP) {SP ← SP + 6; S[SP] ← S[FP]; S[SP − 1] ← FP; }

Fig. 4.35. The instruction lastmark

q/h

lastcall q/h m

PCPC

if (FP ≤ BP) call q/h;

else {

slide mh;

jump q

/h;

}

Fig. 4.36. The instruction lastcall q

/hm

138 4 Logic Programming Languages

Example 4.10.1 Consider the clause r:

(X, Y) ⇐ f (

X, X

), a(

The optimization of last goals produces for code

r in the address environment

{X → 1, Y → 2, X1 → 3}:

mark AA: lastmark

pushenv 3 putref 1 putref 3

putvar 3 putref 2

call f

/2 lastcall a/23



If the last literal of the last clause is also the only literal in this clause, lastmark can

be completely discarded, and lastcall q

/hmcan be simpliﬁed to the sequence slide

mh;jumpq

/h.

Example 4.10.2 Consider the last clause of the predicate app/3:

app

(X, Y, Z) ⇐

=[H|X



Z =[



], app(



)

Here, the last goal is the only literal in this clause. Consequently, we obtain:

A : pushenv 6 uref 4 bind

putref 1 B: putvar 4 son 2 E : putref 5

ustruct

[|]/2 B putvar 5 uvar 6 putref 2

son 1 putstruct

[|]/2 up E putref 6

uvar 4 bind D : check 4 slide 63

son 2 C : putref 3 putref 4 jump app

uvar 5 ustruct

[|]/2 D putvar 6

up C son 1 putstruct

[|]/2

For the predicate app/3, we thus managed to translate the recursion in the last call

into a loop.



4.11 Optimization II: Trimming of Stack Frames

As stack frames must be kept in the stack much more often than with MAMA,imple-

mentations of logic languages suffer from increased stack usage. Any possibility to

systematically save space in the stack is welcome. One idea is to organize the local

variables of a clause according to their life-ranges. A local variable X

that is not a

formalparameter and no longer occurs in the remaining sequence of goals of a clause

is considered as dead at this program point. Dead variables can safely be removed

from the stack whenever possible.

4.11 Optimization II: Trimming of Stack Frames 139

Example 4.11.1 Consider the following clause:

(X, Z) ⇐ p

(

X, X

), p

(

, X

), p

(

, X

), p

(

After the literal p

(

, X

) the variable X

is dead. After the literal p

(

, X

) the

variable X

is also dead. 

Assume that there is a non-last goal after which only the ﬁrst m variables are alive.

Then an instruction trim m can be inserted (Fig. 4.37). Dead local variables, how-

FP FP

trim m

if (FP ≥ BP) SP ← FP + m;

Fig. 4.37. The instruction trim m

ever, can only be removed if no backtrack points have been created whose new eval-

uationrequires further access to the dead variables.Therefore, the instruction trim m

compares the registers FP and BP and only removes the dead variables if FP

≥ BP.

Example 4.11.2 Consider again the clause from Example 4.11.1:

(X, Z) ⇐ p

(

X, X

), p

(

, X

), p

(

, X

), p

(

According to the life-ranges we obtain the following order of variables:

= {X → 1, Z → 2, X

→ 3, X

→ 4, X

→ 5}

This allows us to insert trim instructions as follows:

pushenv 5 A : mark B mark C lastmark

mark A putref 5 putref 4 putref 3

putref 1 putvar 4 putvar 3 putref 2

putvar 5 call p

/2 call p

/2 lastcall p

/23

call p

/2 B : trim 4 C : trim 3

