Structure and Interpretation of Computer Programs

;; compute (- n 1), which is the argument for factorial

  (assign proc (op lookup-variable-value) (const -) (reg env))

  (assign val (const 1))

  (assign argl (op list) (reg val))

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

  (assign argl (op cons) (reg val) (reg argl))

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

  (branch (label primitive-branch8))

compiled-branch7

  (assign continue (label after-call6))

  (assign val (op compiled-procedure-entry) (reg proc))

  (goto (reg val))

primitive-branch8

  (assign val (op apply-primitive-procedure) (reg proc) (reg argl))

after-call6   ; val now contains result of (- n 1)

  (assign argl (op list) (reg val))

  (restore proc) ; restore factorial

;; apply factorial

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

  (branch (label primitive-branch11))

compiled-branch10

  (assign continue (label after-call9))

  (assign val (op compiled-procedure-entry) (reg proc))

  (goto (reg val))

primitive-branch11

  (assign val (op apply-primitive-procedure) (reg proc) (reg argl))

after-call9      ; val now contains result of (factorial (- n 1))

  (restore argl) ; restore partial argument list for *

  (assign argl (op cons) (reg val) (reg argl))

  (restore proc) ; restore *

  (restore continue)

;; apply * and return its value

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

  (branch (label primitive-branch14))

compiled-branch13

;; note that a compound procedure here is called tail-recursively

  (assign val (op compiled-procedure-entry) (reg proc))

  (goto (reg val))

primitive-branch14

  (assign val (op apply-primitive-procedure) (reg proc) (reg argl))

  (goto (reg continue))

after-call12

after-if3

after-lambda1

;; assign the procedure to the variable factorial

  (perform

   (op define-variable!) (const factorial) (reg val) (reg env))

  (assign val (const ok))

Figure 5.17:  (continued)

Figure 5.17:  (continued)

Exercise 5.35.  What expression was compiled to produce the code shown in figure 5.18? 

  (assign val (op make-compiled-procedure) (label entry16)

                                           (reg env))

  (goto (label after-lambda15))

entry16

  (assign env (op compiled-procedure-env) (reg proc))

  (assign env

          (op extend-environment) (const (x)) (reg argl) (reg env))

  (assign proc (op lookup-variable-value) (const +) (reg env))

  (save continue)

  (save proc)

  (save env)

  (assign proc (op lookup-variable-value) (const g) (reg env))

  (save proc)

  (assign proc (op lookup-variable-value) (const +) (reg env))

  (assign val (const 2))

  (assign argl (op list) (reg val))

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

  (assign argl (op cons) (reg val) (reg argl))

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

  (branch (label primitive-branch19))

compiled-branch18

  (assign continue (label after-call17))

  (assign val (op compiled-procedure-entry) (reg proc))

  (goto (reg val))

primitive-branch19

  (assign val (op apply-primitive-procedure) (reg proc) (reg argl))

after-call17

  (assign argl (op list) (reg val))

  (restore proc)

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

  (branch (label primitive-branch22))

compiled-branch21

  (assign continue (label after-call20))

  (assign val (op compiled-procedure-entry) (reg proc))

  (goto (reg val))

primitive-branch22

  (assign val (op apply-primitive-procedure) (reg proc) (reg argl))

Figure 5.18:  An example of compiler output (continued on next page). See exercise 5.35.

Figure 5.18:  An example of compiler output (continued on next page). See exercise 5.35.

---

after-call20

  (assign argl (op list) (reg val))

  (restore env)

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

  (assign argl (op cons) (reg val) (reg argl))

  (restore proc)

  (restore continue)

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

  (branch (label primitive-branch25))

compiled-branch24

  (assign val (op compiled-procedure-entry) (reg proc))

  (goto (reg val))

primitive-branch25

  (assign val (op apply-primitive-procedure) (reg proc) (reg argl))

  (goto (reg continue))

after-call23

after-lambda15

  (perform (op define-variable!) (const f) (reg val) (reg env))

  (assign val (const ok))

Figure 5.18:  (continued)

Figure 5.18:  (continued)

Exercise 5.36.  What order of evaluation does our compiler produce for operands of a combination? Is

it left-to-right, right-to-left, or some other order? Where in the compiler is this order determined?

Modify the compiler so that it produces some other order of evaluation. (See the discussion of order of

evaluation for the explicit-control evaluator in section 5.4.1.) How does changing the order of operand

evaluation affect the efficiency of the code that constructs the argument list? 

Exercise 5.37.  One way to understand the compiler’s 

preserving

 mechanism for optimizing stack

usage is to see what extra operations would be generated if we did not use this idea. Modify 

preserving

 so that it always generates the 

save

 and 

restore

 operations. Compile some simple

expressions and identify the unnecessary stack operations that are generated. Compare the code to that

generated with the 

preserving

 mechanism intact. 

Exercise 5.38.  Our compiler is clever about avoiding unnecessary stack operations, but it is not clever

at all when it comes to compiling calls to the primitive procedures of the language in terms of the

primitive operations supplied by the machine. For example, consider how much code is compiled to

compute 

(+ a 1)

: The code sets up an argument list in 

argl

, puts the primitive addition procedure

(which it finds by looking up the symbol 

+

 in the environment) into 

proc

, and tests whether the

procedure is primitive or compound. The compiler always generates code to perform the test, as well

as code for primitive and compound branches (only one of which will be executed). We have not

shown the part of the controller that implements primitives, but we presume that these instructions

make use of primitive arithmetic operations in the machine’s data paths. Consider how much less code

would be generated if the compiler could open-code primitives -- that is, if it could generate code to

directly use these primitive machine operations. The expression 

(+ a 1)

 might be compiled into

something as simple as 

43

 

---