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

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

70 3 Functional Programming Languages

This is not as unreasonable as it might seem. Although the register SP changes

continuously during program execution,it points at each program point to an address

on the stack that has a ﬁxed distance to SP

, the state the SP had at the last entrance

of the enclosing function (Fig. 3.8). Moreover, this ﬁxed distance sl

= SP − SP

can be computed at translation time. It is the stack level, which we have used as an

additional parameter to our code generation functions.

m−1

Fig. 3.8. The stack level of the MAMA

To the formal parameters x

, x

,...we consecutively assign the non-positive

relative addresses 0,

−1, −2,..., that is,

=(L, −i).

The absolute address of the i-th formal parameter is given by:

+(−i)=(SP −sl) −i = SP −(sl + i)

The local variables y

, y

,...introduced via let or let rec constructs, are consec-

utively pushed on top of the stack (Fig. 3.9). Thus, the variables y

receive positive

relative addresses 1,2,3,..., that is,

=(L, j). The absolute address of the local

variable y

is given by:

+ j =(SP −sl)+j = SP −(sl − j)

In the case of CBN, we translate a variable access as follows:

code

sl = getvar x

eval

The instruction eval checks whether the valuehas been already computed or whether

itstillneedstobeevaluated. This instruction is explainedlater. In the case of CBV,no

closures are constructed. Since we can assume that the required values are available,

the instruction eval is not necessary.

3.5 Access to Variables 71

k−1

Fig. 3.9. The local variables of the MAMA

Themacrogetvarselectstheactualinstructionforthevariableaccess,depending

on the current address environment and the level of the stack. The macro getvar is

deﬁned by:

getvar x

sl = match

x with

(L, i) → pushloc (sl −i)

| (

G, j) → pushglob j

New instructions are required for handling local and global variables. To access a

local variable, the instruction pushloc n is used (Fig. 3.10). This instruction pushes

the contents of the stack location with address n relative to the current SP on top of

the stack. Let sp and sl be the current value of the stack pointer SP and the stack

pushloc n

S[SP + 1] ← S[SP − n]; SP++;

Fig. 3.10. The instruction pushloc n

72 3 Functional Programming Languages

level, respectively. Our ﬁxed reference point in the stack is given by SP

= sp −sl.

The instruction pushloc

(sl − i) therefore is guaranteed to load the contents of the

stack location with address:

−(sl −i)=(sp −sl)+i = sp

+ i

Access to global variables is much easier. For this, the instruction pushglob j is

introduced(Fig.3.11).Thisinstructionextractstheentrywithindex j fromthevector

to which register GP points, and pushes the entry onto the stack.

VGP

pushglob j

S[SP + 1] ← H[GP].v[ j]; SP++;

Fig. 3.11. The instruction pushglob j

Example 3.5.1 Consider the expression e ≡ (b + c) for the address environment

= {b → (L,1), c → (G,0)} and a stack level sl = 1. Then, we obtain for CBN:

code

1 = getvar b

1 = 1 pushloc 0

eval 2 eval

getbasic 2 getbasic

getvar c

22pushglob 0

eval 3 eval

getbasic 3 getbasic

add 3 add

mkbasic 2 mkbasic

In the ﬁrst column we have generated all instructions for the expression, except those

for accessing variables.These are determined in the second column using the respec-

tive stack levels before each instruction. These stack levels are displayed to the left

of each instruction. The argument of the instruction pushloc therefore is determined

as:

3.6 let Expressions 73

sl −

b = 1 −1 = 0



3.6 let Expressions

Consider local variables introduced by a let construct. Let e ≡ let x = e

in e

be a

let expression. The translation of e must generate an instruction sequence that pushes

a new local variable x onto the stack. In the case of CBV, the expression e

must be

evaluated and x be bound to its value. In the case of CBN, evaluating the expression

is postponed until its value is actually required. Instead of computing the value of

, a closure must be constructed for e

, and a reference to it is recorded in x. Finally,

the expression e

must be evaluated and its value returned.

In the case of CBN, we therefore generate:

code

sl = code

code

(

⊕{x → (L, sl + 1)})(sl + 1)

slide 1

The instruction slide releases the space for the local variable x. In the case of CBV,

thevalueofthevariable x mustbecomputedimmediately.Inthiscase,theexpression

is translated by means of the code function code

, instead by means of code

Example 3.6.1 Consider the following expression:

≡ let a = 19 in let b = a · a in a + b

for

= ∅ and sl = 0. In case of CBV, it is tranlated into:

0 loadc 19 3 getbasic 3 pushloc 1

1 mkbasic 3 mul 4 getbasic

1 pushloc 02 mkbasic 4 add

2 getbasic 2 pushloc 13 mkbasic

2 pushloc 13 getbasic 3 slide 1

2 slide 1



The instruction slide k releases the space of k local variables (Fig. 3.12). This more

general M

AMA instruction suggests that it is impractical to free the space of each

local variable in a nested sequence of let instructions, as in Example 3.6.1. Instead, a

sequence of k slide 1 instructions should always be condensed into a single instruc-

tion slide k.

74 3 Functional Programming Languages

slide k

S[SP − k] ← S[SP]; SP ← SP −k;

Fig. 3.12. The instruction slide k

3.7 Function Deﬁnitions

Let us now turn to the implementation of a function:

≡ fun x

...x

k−1

→ e

For the function f , code must be generated that constructs a functional value for f in

the heap. This requires code for:

• creating a global vector for the free variables of f ;

• creating an F-object that consists of an (initially empty) argument vector as well

as the start address of the code for the evaluation of the body of the function; and

ﬁnally,

• evaluating the body.

We convert these tasks directly into a translation scheme:

code

(fun x

...x

k−1

→ e)

sl = getvar z

getvar z

(sl + 1)

...

getvar z

g−1

(sl + g − 1)

mkvec g

mkfunval A

jump B

A : targ k

code



return k

B : ...

where

,...,z

g−1

} = free(fun x

...x

k−1

→ e) and



= {x

→ (L, −i) | i = 0,...,k −1}∪

{

→ (G, j) | j = 0,...,g − 1}

3.7 Function Deﬁnitions 75

Note that the set of global variables is statically known: it can be determined by

means of the function free. The sequence of calls to the macro getvar pushes the

referencestotheglobalvariablesofthefunctionsuccessivelyontothestack.Foreach

further reference, the stack level is increased accordingly. The instruction mkvec g

(Fig. 3.13) creates a vector in the heap that consists of the sequence of references to

global variables from the top of the stack. It removes the corresponding references

from the stack and pushes a reference to the newly constructed V-object onto the

stack. The instruction mkfunval A (Fig. 3.14) constructs the F-object for a function

mkvec g V g

h ← new V (g);

← SP − g + 1;

for

(i ← 0; i < g; i++) H[h].v[i] ← S[SP + i];

[SP] ← h;

Fig. 3.13. The instruction mkvec g

where A is the start address of the code, and the global vectoris taken from the stack.

Additionally, this instruction initializes the argumentvector of the new F-object with

an empty vector.

mkfunval A V 0

S[SP] ← new F (A, new V (0), S[SP]);

Fig. 3.14. The instruction mkfunval A

76 3 Functional Programming Languages

Our translation scheme also generates the code executed when an application

of the function is to be evaluated. This is sensible as this code must use the same

assignment of global variables to positions in the global vector that was used when

including the variable bindings. On the other hand, this instruction sequence must

not be executed when constructing the F-object itself: this code section therefore is

skipped to continue at the location B.

The code for evaluating a function call, thus, is between the labels A and B.Es-

sentially, it consists of the V-code for the body decorated with an instruction targ

k at the beginning and an instruction return k at the end where k is the number of

arguments of the function. These two instructions are discussed in Sect. 3.9.Here

we just mention that the instruction targ k is responsible for undersupply with argu-

ments, whereas the instruction return k is responsible for ﬁnalizing the evaluation

of the call and a possible oversupply with arguments.

Example 3.7.1 Consider the function f

≡ fun b → a + b for an address environ-

ment

= {a → (L,1)} and stack level sl = 1. The call code

1 is translated

into:

1 pushloc 00pushglob 02getbasic

2 mkvec 11eval 2 add

2 mkfunval A 1 getbasic 1 mkbasic

2 jump B 1 pushloc 11return 1

0 A : targ 12eval 2 B : ...



3.8 Function Application

Function applications are analogous to function calls in C. The instruction sequence

generated for a function application must ensure that the state of the stack satisﬁes

the assumptions of the code for the function deﬁnition when the function is entered.

The necessary actions for evaluating a function application e



... e

m−1

are:

• allocating a stack frame;

• passing of parameters, that is, evaluating the actual parameters in the case of

CBV or constructing closures for the actual parameters in the case of CBN;

• evaluating the function e



to an F-object;

• applying this function.

For CBN, this leads to the following translation scheme:

3.8 Function Application 77

code



... e

m−1

)

sl = mark A

code

m−1

(sl + 3)

code

m−2

(sl + 4)

...

code

(sl + m + 2)

code



(sl + m + 3)

apply

A : ...

This scheme corresponds to the translation scheme for calls of C functions. The in-

struction mark A sets up a stack frame for the application. The actual parameters

are evaluated from right to left. In the case of CBN semantics, code for construct-

ing the required closures is generated. For this reason, code

is used for the actual

parameters e

. In the case of CBV semantics, code is generated for evaluating the

arguments, that is, code

instead of code

is used for the e

. Note that with each

reference pushed onto the stack, the stack level for the next call of the code genera-

tion function is increased.

After the actual parameters are translated, code is generated for determining the

appliedfunction.Thishappensbyapplying the code generation function code

toe



At run-time, the generated instruction sequence will push a reference to an F-object

onto the stack. A further instruction therefore is needed to unpack this F-object and

start the code for executing the function. This is realized by the instruction apply.

Example 3.8.1 For a call

( f 42) in the address environment

= {f → (L,2)}

with a stack level sl = 2 our scheme generates for CBV:

2 mark A 6 mkbasic 7 apply

5 loadc 42 6 pushloc 43A : ...

As a slightly larger example, consider the expression:

let a

= 17 in let f = fun b → a + b in f 42

We have already dealt with parts of this expression in previous examples. With CBV

semantics, we obtain for sl

= 0 altogether:

0 loadc 17 2 jump B 2 getbasic 5 loadc 42

1 mkbasic 0 A : targ 1 2 add 5 mkbasic

1 pushloc 0 0 pushglob 0 1 mkbasic 6 pushloc 4

2 mkvec 1 1 getbasic 1 return 1 7 apply

2 mkfunval A 1 pushloc 1 2 B : mark C 3 C : slide 2



Before we describe the implementation of the new instructions, we must clarify how

stack frames for evaluating a function call should be organized (Fig. 3.15). Like

78 3 Functional Programming Languages

FPold

PCold

GPold

FP 0

-1

-2

local stack

3 org. cells

arguments

Fig. 3.15. The stack frame of the MAMA

the C-Machine, the MAMA requires three organizational cells, in which the values

of the registers GP, FP, and PC are saved before the call, so that their values can

be restored after the call. We ﬁx that the frame pointer FP points to the topmost

organizational cell. The arguments of the function are, thus, placed above the FP.

The local stack for intermediate results and further local variables is placed above

the arguments.

Now we are able to implement the instruction mark A (Fig. 3.16). In contrast

V V

mark A

S[SP + 1] ← GP;

[SP + 2] ← FP;

[SP + 3] ← A; FP ← SP ← SP + 3;

Fig. 3.16. The instruction mark A

to the corresponding instruction of the C-Machine, this instruction saves all three

registers. As with the C-Machine, the return address is pushed onto the stack at the

3.8 Function Application 79

very end. For this reason, it requires as an argument the address to which program

execution is supposed to resume after the return from the function call. Further, it

sets the new Frame Pointer to the topmost organizational cell, here the saved PC.

The instruction apply must unpack the F-object to which (hopefully) a reference

is found on top of the stack, and must continue at the address cp provided by the F-

object (Fig. 3.17). We remark that the 0-th element of the argument vector is pushed

42F

ap gpcp

PC 42

apply

V n

h ← S[SP];

(H[h] =(F, _, _, _)) error (“no fun!”);

← H[h].ap; n ← H[a].n;

for

(i ← 0; i < n; i++) S[SP + i] ← H[a].v[i];

← SP + n − 1;

← H[h].gp; PC ← H[h].cp;

Fig. 3.17. The instruction apply

onto the stack ﬁrst. This conventionmust be observedwhen constructing an F-object

for a function with an undersupply of arguments.This 0-th element of the vectorthus

represents the outermost argument reference of such a function.

From the whole task of implementing functions, we now have dealt with the

following subtasks: generating F-objects from function deﬁnitions and, embedded

within, translating the function body in the correct environment; setting up a stack

frame for the function application and subsequently pushing of references to the ar-

guments onto the stack; and, ﬁnally, starting the code for the function. What remains

is the decoration around the translation of the function body, namely, the instructions

targ k and return k. These are dealt with in the next section.