Structure and Interpretation of Computer Programs (109 page)

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.)

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:
⁴⁸

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))  
  (branch (label compiled-apply))
  (goto (label unknown-procedure-type))
compiled-apply
  (restore continue)
  (assign val (op compiled-procedure-entry) (reg proc))
  (goto (reg val))

Note the restore of
continue
at
compiled-apply
. Recall that the
evaluator was arranged so that at
apply-dispatch
, the continuation would
be at the top of the stack. The compiled code entry point, on the other hand,
expects the continuation to be in
continue
, so
continue
must be
restored before the compiled code is executed.

To enable us to run some compiled code when we start the evaluator
machine, we add a
branch
instruction at
the beginning of the evaluator machine, which causes the machine to
go to a new entry point if the
flag
register is set.
⁴⁹

  (branch (label external-entry))      
; branches if 
flag
 is set
read-eval-print-loop
  (perform (op initialize-stack))
  
...

External-entry
assumes that the machine is started with
val
containing the location of an instruction sequence that
puts a result into
val
and ends with
(goto (reg
continue))
. Starting at this entry point jumps to the location designated
by
val
, but first assigns
continue
so that execution will return
to
print-result
, which prints the value in
val
and then goes to
the beginning of the evaluator's read-eval-print loop.
⁵⁰

external-entry
  (perform (op initialize-stack))
  (assign env (op get-global-environment))
  (assign continue (label print-result))
  (goto (reg val))

Now we can use the following procedure to compile a procedure definition,
execute the compiled code, and run the read-eval-print loop so we can try the
procedure. Because we want the compiled code to return to the location in
continue
with its result in
val
, we compile the expression with a
target of
val
and a linkage of
return
. In order to transform the
object code produced by the compiler into executable instructions for the
evaluator register machine, we use the procedure
assemble
from the
register-machine simulator (section 
5.2.2
). We then initialize
the
val
register to point to the list of instructions, set the
flag
so that the evaluator will go to
external-entry
, and start
the evaluator.

(define (compile-and-go expression)
  (let ((instructions
         (assemble (statements
                    (compile expression 'val 'return))
                   eceval)))
    (set! the-global-environment (setup-environment))
    (set-register-contents! eceval 'val instructions)
    (set-register-contents! eceval 'flag true)
    (start eceval)))

If we have set up stack monitoring, as at the end of
section 
5.4.4
, we can examine the
stack usage of compiled code:

(compile-and-go
 '(define (factorial n)
    (if (= n 1)
        1
        (* (factorial (- n 1)) n))))
(total-pushes = 0 maximum-depth = 0)
 ;;; EC-Eval value:
ok
 ;;; EC-Eval input:
(factorial 5)
(total-pushes = 31 maximum-depth = 14)
;;; EC-Eval value:
120

Compare this example with the evaluation of
(factorial 5)
using
the interpreted version of the same procedure, shown at the end of
section 
5.4.4
. The interpreted version required
144 pushes and a maximum stack depth of 28. This illustrates the
optimization that results from our compilation strategy.

With the programs in this section, we can now experiment with the
alternative execution strategies of interpretation and
compilation.
⁵¹
An interpreter raises
the machine to the level of the user program; a compiler lowers the
user program to the level of the machine language. We can regard the
Scheme language (or any programming language) as a coherent family of
abstractions erected on the machine language. Interpreters are good
for interactive program development and debugging because the steps of
program execution are organized in terms of these abstractions, and
are therefore more intelligible to the programmer. Compiled code can
execute faster, because the steps of program execution are organized
in terms of the machine language, and the compiler is free to make
optimizations that cut across the higher-level
abstractions.
⁵²

The alternatives of interpretation and compilation also lead to
different strategies for porting languages to new computers. Suppose
that we wish to implement Lisp for a new machine. One strategy is
to begin with the explicit-control evaluator of section 
5.4
and translate its instructions to instructions for the
new machine. A different strategy is to begin with the compiler and
change the code generators so that they generate code for the new
machine. The second strategy allows us to run any Lisp program on
the new machine by first compiling it with the compiler running on our
original Lisp system, and linking it with a compiled version of the
run-time library.
⁵³
Better yet, we can compile the compiler itself, and run
this on the new machine to compile other Lisp programs.
⁵⁴
Or we can
compile one of the interpreters of section 
4.1
to
produce an interpreter that runs on the new machine.

Exercise 5.45.
  
By comparing the stack operations used by compiled code to the stack
operations used by the evaluator for the same computation, we can
determine the extent to which the compiler optimizes use of the stack,
both in speed (reducing the total number of stack operations) and in
space (reducing the maximum stack depth). Comparing this optimized
stack use to the performance of a special-purpose machine for the same
computation gives some indication of the quality of the compiler.

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.”