Structure and Interpretation of Computer Programs

(assign val (op lookup-variable-value) (const a) (reg env))

(assign val (op +) (reg val) (const 1))

In this exercise we will extend our compiler to support open coding of selected primitives.

Special-purpose code will be generated for calls to these primitive procedures instead of the general

procedure-application code. In order to support this, we will augment our machine with special

argument registers 

arg1

 and 

arg2

. The primitive arithmetic operations of the machine will take their

inputs from 

arg1

 and 

arg2

. The results may be put into 

val

, 

arg1

, or 

arg2

.

The compiler must be able to recognize the application of an open-coded primitive in the source

program. We will augment the dispatch in the 

compile

 procedure to recognize the names of these

primitives in addition to the reserved words (the special forms) it currently recognizes.

44

 For each

special form our compiler has a code generator. In this exercise we will construct a family of code

generators for the open-coded primitives.

a.  The open-coded primitives, unlike the special forms, all need their operands evaluated. Write a

code generator 

spread-arguments

 for use by all the open-coding code generators. 

Spread-arguments

 should take an operand list and compile the given operands targeted to

successive argument registers. Note that an operand may contain a call to an open-coded primitive, so

argument registers will have to be preserved during operand evaluation.

b.  For each of the primitive procedures 

=

, 

*

, 

-

, and 

+

, write a code generator that takes a combination

with that operator, together with a target and a linkage descriptor, and produces code to spread the

arguments into the registers and then perform the operation targeted to the given target with the given

linkage. You need only handle expressions with two operands. Make 

compile

 dispatch to these code 

generators.

c.  Try your new compiler on the 

factorial

 example. Compare the resulting code with the result

produced without open coding.

d.  Extend your code generators for 

+

 and 

*

 so that they can handle expressions with arbitrary

numbers of operands. An expression with more than two operands will have to be compiled into a

sequence of operations, each with only two inputs. 

5.5.6  Lexical Addressing

One of the most common optimizations performed by compilers is the optimization of variable lookup.

Our compiler, as we have implemented it so far, generates code that uses the 

lookup-variable-value

 operation of the evaluator machine. This searches for a variable by

comparing it with each variable that is currently bound, working frame by frame outward through the

run-time environment. This search can be expensive if the frames are deeply nested or if there are

many variables. For example, consider the problem of looking up the value of 

x

 while evaluating the

expression 

(* x y z)

 in an application of the procedure that is returned by

(let ((x 3) (y 4))

  (lambda (a b c d e)

    (let ((y (* a b x))

          (z (+ c d x)))

      (* x y z))))

---

Since a 

let

 expression is just syntactic sugar for a 

lambda

 combination, this expression is

equivalent to

((lambda (x y)

   (lambda (a b c d e)

     ((lambda (y z) (* x y z))

      (* a b x)

      (+ c d x))))

 3

 4)

Each time 

lookup-variable-value

 searches for 

x

, it must determine that the symbol 

x

 is not 

eq?

 to 

y

 or 

z

 (in the first frame), nor to 

a

, 

b

, 

c

, 

d

, or 

e

 (in the second frame). We will assume, for the

moment, that our programs do not use 

define

 -- that variables are bound only with 

lambda

.

Because our language is lexically scoped, the run-time environment for any expression will have a

structure that parallels the lexical structure of the program in which the expression appears.

45

 Thus,

the compiler can know, when it analyzes the above expression, that each time the procedure is applied

the variable 

x

 in 

(* x y z)

 will be found two frames out from the current frame and will be the

first variable in that frame.

We can exploit this fact by inventing a new kind of variable-lookup operation, 

lexical-address-lookup

, that takes as arguments an environment and a lexical address that

consists of two numbers: a frame number, which specifies how many frames to pass over, and a 

displacement number, which specifies how many variables to pass over in that frame. 

Lexical-address-lookup

 will produce the value of the variable stored at that lexical address

relative to the current environment. If we add the 

lexical-address-lookup

 operation to our

machine, we can make the compiler generate code that references variables using this operation, rather

than 

lookup-variable-value

. Similarly, our compiled code can use a new 

lexical-address-set!

 operation instead of 

set-variable-value!

.

In order to generate such code, the compiler must be able to determine the lexical address of a variable

it is about to compile a reference to. The lexical address of a variable in a program depends on where

one is in the code. For example, in the following program, the address of 

x

 in expression <e1> is (2,0)

-- two frames back and the first variable in the frame. At that point 

y

 is at address (0,0) and 

c

 is at

address (1,2). In expression <e2>, 

x

 is at (1,0), 

y

 is at (1,1), and 

c

 is at (0,2).

((lambda (x y)

   (lambda (a b c d e)

     ((lambda (y z) <e1>)

      <e2>

      (+ c d x))))

 3

 4)

One way for the compiler to produce code that uses lexical addressing is to maintain a data structure

called a compile-time environment. This keeps track of which variables will be at which positions in

which frames in the run-time environment when a particular variable-access operation is executed. The

compile-time environment is a list of frames, each containing a list of variables. (There will of course

be no values bound to the variables, since values are not computed at compile time.) The compile-time

environment becomes an additional argument to 

compile

 and is passed along to each code

generator. The top-level call to 

compile

 uses an empty compile-time environment. When a 

lambda

---