Structure and Interpretation of Computer Programs

body is compiled, 

compile-lambda-body

 extends the compile-time environment by a frame

containing the procedure’s parameters, so that the sequence making up the body is compiled with that

extended environment. At each point in the compilation, 

compile-variable

 and 

compile-assignment

 use the compile-time environment in order to generate the appropriate

lexical addresses.

Exercises 5.39 through 5.43 describe how to complete this sketch of the lexical-addressing strategy in

order to incorporate lexical lookup into the compiler. Exercise 5.44 describes another use for the

compile-time environment.

Exercise 5.39.  Write a procedure 

lexical-address-lookup

 that implements the new lookup

operation. It should take two arguments -- a lexical address and a run-time environment -- and return

the value of the variable stored at the specified lexical address. 

Lexical-address-lookup

should signal an error if the value of the variable is the symbol 

*unassigned*

.

46

 Also write a

procedure 

lexical-address-set!

 that implements the operation that changes the value of the

variable at a specified lexical address. 

Exercise 5.40.  Modify the compiler to maintain the compile-time environment as described above.

That is, add a compile-time-environment argument to 

compile

 and the various code generators, and

extend it in 

compile-lambda-body

. 

Exercise 5.41.  Write a procedure 

find-variable

 that takes as arguments a variable and a

compile-time environment and returns the lexical address of the variable with respect to that

environment. For example, in the program fragment that is shown above, the compile-time

environment during the compilation of expression <e1> is 

((y z) (a b c d e) (x y))

. 

Find-variable

 should produce

(find-variable ’c ’((y z) (a b c d e) (x y)))

(1 2)

(find-variable ’x ’((y z) (a b c d e) (x y)))

(2 0)

(find-variable ’w ’((y z) (a b c d e) (x y)))

not-found

Exercise 5.42.  Using 

find-variable

 from exercise 5.41, rewrite 

compile-variable

 and 

compile-assignment

 to output lexical-address instructions. In cases where 

find-variable

returns 

not-found

 (that is, where the variable is not in the compile-time environment), you should

have the code generators use the evaluator operations, as before, to search for the binding. (The only

place a variable that is not found at compile time can be is in the global environment, which is part of

the run-time environment but is not part of the compile-time environment.

47

 Thus, if you wish, you

may have the evaluator operations look directly in the global environment, which can be obtained with

the operation 

(op get-global-environment)

, instead of having them search the whole

run-time environment found in 

env

.) Test the modified compiler on a few simple cases, such as the

nested 

lambda

 combination at the beginning of this section. 

Exercise 5.43.  We argued in section 4.1.6 that internal definitions for block structure should not be

considered ‘‘real’’ 

define

s. Rather, a procedure body should be interpreted as if the internal

variables being defined were installed as ordinary 

lambda

 variables initialized to their correct values

using 

set!

. Section 4.1.6 and exercise 4.16 showed how to modify the metacircular interpreter to

accomplish this by scanning out internal definitions. Modify the compiler to perform the same

transformation before it compiles a procedure body. 

---

Exercise 5.44.  In this section we have focused on the use of the compile-time environment to produce

lexical addresses. But there are other uses for compile-time environments. For instance, in 

exercise 5.38 we increased the efficiency of compiled code by open-coding primitive procedures. Our

implementation treated the names of open-coded procedures as reserved words. If a program were to

rebind such a name, the mechanism described in exercise 5.38 would still open-code it as a primitive,

ignoring the new binding. For example, consider the procedure

(lambda (+ * a b x y)

  (+ (* a x) (* b y)))

which computes a linear combination of 

x

 and 

y

. We might call it with arguments 

+matrix

, 

*matrix

, and four matrices, but the open-coding compiler would still open-code the 

+

 and the 

*

 in 

(+ (* a x) (* b y))

 as primitive 

+

 and 

*

. Modify the open-coding compiler to consult the

compile-time environment in order to compile the correct code for expressions involving the names of

primitive procedures. (The code will work correctly as long as the program does not 

define

 or 

set!

these names.) 

5.5.7  Interfacing Compiled Code to the Evaluator

We have not yet explained how to load compiled code into the evaluator machine or how to run it. We

will assume that the explicit-control-evaluator machine has been defined as in section 5.4.4, with the

additional operations specified in footnote 38. We will implement a procedure 

compile-and-go

that compiles a Scheme expression, loads the resulting object code into the evaluator machine, and

causes the machine to run the code in the evaluator global environment, print the result, and enter the

evaluator’s driver loop. We will also modify the evaluator so that interpreted expressions can call

compiled procedures as well as interpreted ones. We can then put a compiled procedure into the

machine and use the evaluator to call it:

(compile-and-go

 ’(define (factorial n)

    (if (= n 1)

        1

        (* (factorial (- n 1)) n))))

 ;;; EC-Eval value:

ok

 ;;; EC-Eval input:

(factorial 5)

;;; EC-Eval value:

120

To allow the evaluator to handle compiled procedures (for example, to evaluate the call to 

factorial

 above), we need to change the code at 

apply-dispatch

 (section 5.4.1) so that it

recognizes compiled procedures (as distinct from compound or primitive procedures) and transfers

control directly to the entry point of the compiled code:

48

 

apply-dispatch

  (test (op primitive-procedure?) (reg proc))

  (branch (label primitive-apply))

  (test (op compound-procedure?) (reg proc))  

  (branch (label compound-apply))

  (test (op compiled-procedure?) (reg proc))  

---