;; 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