Structure and Interpretation of Computer Programs

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

49

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

50

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.

Interpretation and compilation

With the programs in this section, we can now experiment with the alternative execution strategies of

interpretation and compilation.

51

 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.

52

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.

53

 Better yet, we can compile the compiler

itself, and run this on the new machine to compile other Lisp programs.

54

 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.

---