Structure and Interpretation of Computer Programs

after-lambda1

  (perform (op define-variable!)

           (const factorial)

           (reg val)

           (reg env))

  (assign val (const ok))

A procedure body is always compiled (by 

compile-lambda-body

) as a sequence with target 

val

and linkage 

return

. The sequence in this case consists of a single 

if

 expression:

(if (= n 1)

    1

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

Compile-if

 generates code that first computes the predicate (targeted to 

val

), then checks the

result and branches around the true branch if the predicate is false. 

Env

 and 

continue

 are preserved

around the predicate code, since they may be needed for the rest of the 

if

 expression. Since the 

if

expression is the final expression (and only expression) in the sequence making up the procedure

body, its target is 

val

 and its linkage is 

return

, so the true and false branches are both compiled

with target 

val

 and linkage 

return

. (That is, the value of the conditional, which is the value

computed by either of its branches, is the value of the procedure.)

  <save continue, env if modified by predicate and needed by branches>

  <compilation of predicate, target val, linkage next>

  <restore continue, env if saved above>

  (test (op false?) (reg val))

  (branch (label false-branch4))

true-branch5

  <compilation of true branch, target val, linkage return>

false-branch4

  <compilation of false branch, target val, linkage return>

after-if3

The predicate 

(= n 1)

 is a procedure call. This looks up the operator (the symbol 

=

) and places this

value in 

proc

. It then assembles the arguments 

1

 and the value of 

n

 into 

argl

. Then it tests whether 

proc

 contains a primitive or a compound procedure, and dispatches to a primitive branch or a

compound branch accordingly. Both branches resume at the 

after-call

 label. The requirements to

preserve registers around the evaluation of the operator and operands don’t result in any saving of

registers, because in this case those evaluations don’t modify the registers in question.

  (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-branch17))

compiled-branch16

  (assign continue (label after-call15))

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

---

  (goto (reg val))

primitive-branch17

  (assign val (op apply-primitive-procedure)

              (reg proc)

              (reg argl))

after-call15

The true branch, which is the constant 1, compiles (with target 

val

 and linkage 

return

) to

  (assign val (const 1))

  (goto (reg continue))

The code for the false branch is another a procedure call, where the procedure is the value of the

symbol 

*

, and the arguments are 

n

 and the result of another procedure call (a call to 

factorial

).

Each of these calls sets up 

proc

 and 

argl

 and its own primitive and compound branches. 

Figure 5.17 shows the complete compilation of the definition of the 

factorial

 procedure. Notice

that the possible 

save

 and 

restore

 of 

continue

 and 

env

 around the predicate, shown above, are

in fact generated, because these registers are modified by the procedure call in the predicate and

needed for the procedure call and the 

return

 linkage in the branches. 

Exercise 5.33.  Consider the following definition of a factorial procedure, which is slightly different

from the one given above: 

(define (factorial-alt n)

  (if (= n 1)

      1

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

Compile this procedure and compare the resulting code with that produced for 

factorial

. Explain

any differences you find. Does either program execute more efficiently than the other? 

Exercise 5.34.  Compile the iterative factorial procedure 

(define (factorial n)

  (define (iter product counter)

    (if (> counter n)

        product

        (iter (* counter product)

              (+ counter 1))))

  (iter 1 1))

Annotate the resulting code, showing the essential difference between the code for iterative and

recursive versions of 

factorial

 that makes one process build up stack space and the other run in

constant stack space. 

---

;; construct the procedure and skip over code for the procedure body

  (assign val

          (op make-compiled-procedure) (label entry2) (reg env))

  (goto (label after-lambda1))

entry2     ; calls to factorial will enter here

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

  (assign env

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

;; begin actual procedure body

  (save continue)

  (save env)

;; compute (= n 1)

  (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-branch17))

compiled-branch16

  (assign continue (label after-call15))

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

  (goto (reg val))

primitive-branch17

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

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

  (restore env)

  (restore continue)

  (test (op false?) (reg val))

  (branch (label false-branch4))

true-branch5  ; return 1

  (assign val (const 1))

  (goto (reg continue))

false-branch4

;; compute and return (* (factorial (- n 1)) n)

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

  (save continue)

  (save proc)   ; save * procedure

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

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

  (save argl)   ; save partial argument list for *

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

  (assign proc

          (op lookup-variable-value) (const factorial) (reg env))

  (save proc)  ; save factorial procedure

Figure 5.17:  Compilation of the definition of the 

factorial

 procedure (continued on next page).

Figure 5.17:  Compilation of the definition of the 

factorial

 procedure (continued on next page).

---