Structure and Interpretation of Computer Programs

a. Exercise 5.27 asked you to determine, as a function of n, the number of pushes and the maximum

stack depth needed by the evaluator to compute n! using the recursive factorial procedure given above. 

Exercise 5.14 asked you to do the same measurements for the special-purpose factorial machine shown

in figure 5.11. Now perform the same analysis using the compiled 

factorial

 procedure.

Take the ratio of the number of pushes in the compiled version to the number of pushes in the

interpreted version, and do the same for the maximum stack depth. Since the number of operations and

the stack depth used to compute n! are linear in n, these ratios should approach constants as n becomes

large. What are these constants? Similarly, find the ratios of the stack usage in the special-purpose

machine to the usage in the interpreted version.

Compare the ratios for special-purpose versus interpreted code to the ratios for compiled versus

interpreted code. You should find that the special-purpose machine does much better than the

compiled code, since the hand-tailored controller code should be much better than what is produced by

our rudimentary general-purpose compiler.

b. Can you suggest improvements to the compiler that would help it generate code that would come

closer in performance to the hand-tailored version? 

Exercise 5.46.  Carry out an analysis like the one in exercise 5.45 to determine the effectiveness of

compiling the tree-recursive Fibonacci procedure

(define (fib n)

  (if (< n 2)

      n

      (+ (fib (- n 1)) (fib (- n 2)))))

compared to the effectiveness of using the special-purpose Fibonacci machine of figure 5.12. (For

measurement of the interpreted performance, see exercise 5.29.) For Fibonacci, the time resource used

is not linear in n; hence the ratios of stack operations will not approach a limiting value that is

independent of n. 

Exercise 5.47.  This section described how to modify the explicit-control evaluator so that interpreted

code can call compiled procedures. Show how to modify the compiler so that compiled procedures can

call not only primitive procedures and compiled procedures, but interpreted procedures as well. This

requires modifying 

compile-procedure-call

 to handle the case of compound (interpreted)

procedures. Be sure to handle all the same 

target

 and 

linkage

 combinations as in 

compile-proc-appl

. To do the actual procedure application, the code needs to jump to the

evaluator’s 

compound-apply

 entry point. This label cannot be directly referenced in object code

(since the assembler requires that all labels referenced by the code it is assembling be defined there),

so we will add a register called 

compapp

 to the evaluator machine to hold this entry point, and add an

instruction to initialize it: 

  (assign compapp (label compound-apply))

  (branch (label external-entry))      ; branches if flag is set

read-eval-print-loop

  ...

To test your code, start by defining a procedure 

f

 that calls a procedure 

g

. Use 

compile-and-go

 to

compile the definition of 

f

 and start the evaluator. Now, typing at the evaluator, define 

g

 and try to

call 

f

. 

---

Exercise 5.48.  The 

compile-and-go

 interface implemented in this section is awkward, since the

compiler can be called only once (when the evaluator machine is started). Augment the

compiler-interpreter interface by providing a 

compile-and-run

 primitive that can be called from

within the explicit-control evaluator as follows:

;;; EC-Eval input:

(compile-and-run

 ’(define (factorial n)

    (if (= n 1)

        1

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

;;; EC-Eval value:

ok

;;; EC-Eval input:

(factorial 5)

;;; EC-Eval value:

120

Exercise 5.49.  As an alternative to using the explicit-control evaluator’s read-eval-print loop, design a

register machine that performs a read-compile-execute-print loop. That is, the machine should run a

loop that reads an expression, compiles it, assembles and executes the resulting code, and prints the

result. This is easy to run in our simulated setup, since we can arrange to call the procedures 

compile

 and 

assemble

 as ‘‘register-machine operations.’’ 

Exercise 5.50.  Use the compiler to compile the metacircular evaluator of section 4.1 and run this

program using the register-machine simulator. (To compile more than one definition at a time, you can

package the definitions in a 

begin

.) The resulting interpreter will run very slowly because of the

multiple levels of interpretation, but getting all the details to work is an instructive exercise. 

Exercise 5.51.  Develop a rudimentary implementation of Scheme in C (or some other low-level

language of your choice) by translating the explicit-control evaluator of section 5.4 into C. In order to

run this code you will need to also provide appropriate storage-allocation routines and other run-time

support. 

Exercise 5.52.  As a counterpoint to exercise 5.51, modify the compiler so that it compiles Scheme

procedures into sequences of C instructions. Compile the metacircular evaluator of section 4.1 to

produce a Scheme interpreter written in C. 

33

 This is a theoretical statement. We are not claiming that the evaluator’s data paths are a particularly

convenient or efficient set of data paths for a general-purpose computer. For example, they are not

very good for implementing high-performance floating-point calculations or calculations that

intensively manipulate bit vectors. 

34

 Actually, the machine that runs compiled code can be simpler than the interpreter machine, because

we won’t use the 

exp

 and 

unev

 registers. The interpreter used these to hold pieces of unevaluated

expressions. With the compiler, however, these expressions get built into the compiled code that the

register machine will run. For the same reason, we don’t need the machine operations that deal with

expression syntax. But compiled code will use a few additional machine operations (to represent

compiled procedure objects) that didn’t appear in the explicit-control evaluator machine. 

---