Structure and Interpretation of Computer Programs (105 page)

(define (compile-if exp target linkage)
  (let ((t-branch (make-label 'true-branch))
        (f-branch (make-label 'false-branch))                    
        (after-if (make-label 'after-if)))
    (let ((consequent-linkage
           (if (eq? linkage 'next) after-if linkage)))
      (let ((p-code (compile (if-predicate exp) 'val 'next))
            (c-code
             (compile
              (if-consequent exp) target consequent-linkage))
            (a-code
             (compile (if-alternative exp) target linkage)))
        (preserving '(env continue)
         p-code
         (append-instruction-sequences
          (make-instruction-sequence '(val) '()
           `((test (op false?) (reg val))
             (branch (label ,f-branch))))
          (parallel-instruction-sequences
           (append-instruction-sequences t-branch c-code)
           (append-instruction-sequences f-branch a-code))
          after-if))))))

Env
is preserved around the predicate code because it could be needed by
the true and false branches, and
continue
is preserved because it could
be needed by the linkage code in those branches. The code for the true and
false branches (which are not executed sequentially) is appended using a
special combiner
parallel-instruction-sequences
described in
section 
5.5.4
.

Note that
cond
is a derived expression, so all that the
compiler needs to do handle it is to apply the
cond->if
transformer (from section 
4.1.2
) and
compile the resulting
if
expression.

The compilation of sequences (from procedure bodies or explicit
begin
expressions) parallels their evaluation. Each expression of the
sequence is compiled – the last expression with the linkage specified
for the sequence, and the other expressions with linkage
next
(to execute the rest of the sequence).
The instruction sequences for the individual expressions are appended
to form a single instruction sequence, such that
env
(needed for
the rest of the sequence) and
continue
(possibly needed for the
linkage at the end of the sequence) are preserved.

(define (compile-sequence seq target linkage)
  (if (last-exp? seq)
      (compile (first-exp seq) target linkage)
      (preserving '(env continue)
       (compile (first-exp seq) target 'next)
       (compile-sequence (rest-exps seq) target linkage))))

Lambda
expressions construct procedures.
The object code for a
lambda
expression must have the form

<
construct procedure object and assign it to target register
>
<
linkage
>

When we compile the
lambda
expression, we also generate the code for the
procedure body. Although the body won't be executed at the time of procedure
construction, it is convenient to insert it into the object code right after
the code for the
lambda
. If the linkage for the
lambda
expression
is a label or
return
, this is fine. But if the linkage is
next
,
we will need to skip around the code for the procedure body by using a linkage
that jumps to a label that is inserted after the body. The object code thus
has the form

 <
construct procedure object and assign it to target register
>
 <
code for given linkage
>
or
 
(goto (label after-lambda))
 <
compilation of procedure body
>
after-lambda

Compile-lambda
generates the code for constructing the procedure
object followed by the code for the procedure body.
The procedure object will be constructed at run time by combining
the current environment (the environment at the point of definition)
with the entry point to the compiled procedure body (a newly generated
label).
³⁸

(define (compile-lambda exp target linkage)
  (let ((proc-entry (make-label 'entry))
        (after-lambda (make-label 'after-lambda)))
    (let ((lambda-linkage
           (if (eq? linkage 'next) after-lambda linkage)))
      (append-instruction-sequences
       (tack-on-instruction-sequence
        (end-with-linkage lambda-linkage
         (make-instruction-sequence '(env) (list target)
          `((assign ,target
                    (op make-compiled-procedure)
                    (label ,proc-entry)
                    (reg env)))))
        (compile-lambda-body exp proc-entry))
       after-lambda))))

Compile-lambda
uses the special combiner
tack-on-instruction-sequence
(section 
5.5.4
) rather than
append-instruction-sequences
to append the procedure body to the
lambda
expression code, because the body is not part of the sequence of instructions
that will be executed when the combined sequence is entered; rather, it is in
the sequence only because that was a convenient place to put it.

Compile-lambda-body
constructs the code for the body of the
procedure. This code begins with a label for the entry point. Next
come instructions that will cause the run-time evaluation environment
to switch to the correct environment for evaluating the procedure
body – namely, the definition environment of the procedure, extended
to include the bindings of the formal parameters to the arguments with
which the procedure is called. After this comes the code for the
sequence of expressions that makes up the procedure body.
The sequence is compiled with linkage
return
and target
val
so that it will end by returning from the procedure with the
procedure result in
val
.

(define (compile-lambda-body exp proc-entry)
  (let ((formals (lambda-parameters exp)))
    (append-instruction-sequences
     (make-instruction-sequence '(env proc argl) '(env)
      `(,proc-entry
        (assign env (op compiled-procedure-env) (reg proc))
        (assign env
                (op extend-environment)
                (const ,formals)
                (reg argl)
                (reg env))))
     (compile-sequence (lambda-body exp) 'val 'return))))

The essence of the compilation process is the compilation of procedure
applications.
The code for a combination compiled with a given target and linkage
has the form

<
compilation of operator, target 
proc
, linkage 
next
>
<
evaluate operands and construct argument list in 
argl
>
<
compilation of procedure call with given target and linkage
>

The registers
env
,
proc
, and
argl
may have to be
saved and restored during evaluation of the operator and operands.
Note that this is the only place in the compiler where a target other
than
val
is specified.

The required code is generated by
compile-application
. This
recursively compiles the operator, to produce code that puts the
procedure to be applied into
proc
, and compiles the operands, to
produce code that evaluates the individual operands of the
application. The instruction sequences for the operands are combined
(by
construct-arglist
) with code that constructs the list of
arguments in
argl
, and the resulting argument-list code is
combined with the procedure code and the code that performs the
procedure call (produced by
compile-procedure-call
). In
appending the code sequences, the
env
register must be preserved
around the evaluation of the operator (since evaluating the operator
might modify
env
, which will be needed to evaluate the
operands), and the
proc
register must be preserved around the
construction of the argument list (since evaluating the operands might
modify
proc
, which will be needed for the actual procedure
application).
Continue
must also be preserved throughout, since
it is needed for the linkage in the procedure call.

(define (compile-application exp target linkage)
  (let ((proc-code (compile (operator exp) 'proc 'next))
        (operand-codes
         (map (lambda (operand) (compile operand 'val 'next))
              (operands exp))))
    (preserving '(env continue)
     proc-code
     (preserving '(proc continue)
      (construct-arglist operand-codes)
      (compile-procedure-call target linkage)))))

The code to construct the argument list will evaluate each operand into
val
and then
cons
that value onto the argument list being
accumulated in
argl
.
Since we
cons
the arguments onto
argl
in sequence, we must
start with the last argument and end with the first, so that the
arguments will appear in order from first to last in the resulting list.
Rather than waste an instruction by initializing
argl
to the empty list
to set up for this sequence of evaluations,
we make the first code sequence construct the initial
argl
.
The general form of the argument-list construction is thus as follows:

<
compilation of last operand, targeted to 
val
>
(assign argl (op list) (reg val))
<
compilation of next operand, targeted to 
val
>
(assign argl (op cons) (reg val) (reg argl))
...
<
compilation of first operand, targeted to 
val
>
(assign argl (op cons) (reg val) (reg argl))

Argl
must be preserved around each operand evaluation except
the first (so that arguments accumulated so far won't be lost), and
env
must be preserved around each operand evaluation
except the last (for use by subsequent operand evaluations).

Compiling this argument code is a bit tricky, because of
the special treatment of the first operand to be evaluated and the
need to preserve
argl
and
env
in different places.
The
construct-arglist
procedure takes as arguments the code that
evaluates the individual operands. If there are no operands at all, it simply
emits the instruction

(assign argl (const ()))

Otherwise,
construct-arglist
creates code that initializes
argl
with the last argument, and appends code that evaluates
the rest of the arguments and adjoins them to
argl
in
succession. In order to process the arguments from last to
first, we must reverse the list of operand code sequences from the order
supplied by
compile-application
.

(define (construct-arglist operand-codes)
  (let ((operand-codes (reverse operand-codes)))
    (if (null? operand-codes)
        (make-instruction-sequence '() '(argl)
         '((assign argl (const ()))))
        (let ((code-to-get-last-arg
               (append-instruction-sequences
                (car operand-codes)
                (make-instruction-sequence '(val) '(argl)
                 '((assign argl (op list) (reg val)))))))
          (if (null? (cdr operand-codes))
              code-to-get-last-arg
              (preserving '(env)
               code-to-get-last-arg
               (code-to-get-rest-args
                (cdr operand-codes))))))))
(define (code-to-get-rest-args operand-codes)
  (let ((code-for-next-arg
         (preserving '(argl)
          (car operand-codes)
          (make-instruction-sequence '(val argl) '(argl)
           '((assign argl
              (op cons) (reg val) (reg argl)))))))
    (if (null? (cdr operand-codes))
        code-for-next-arg
        (preserving '(env)
         code-for-next-arg
         (code-to-get-rest-args (cdr operand-codes))))))

After evaluating the elements of a combination, the compiled code must
apply the procedure in
proc
to the arguments in
argl
. The
code performs essentially the same dispatch as the
apply
procedure in the
metacircular evaluator of section 
4.1.1
or the
apply-dispatch
entry point in the explicit-control evaluator of
section 
5.4.1
. It checks whether the
procedure to be applied is a primitive procedure or a compiled
procedure. For a primitive procedure, it uses
apply-primitive-procedure
; we will see shortly how it handles
compiled procedures. The procedure-application code has the following
form:

 (test (op primitive-procedure?) (reg proc))
 (branch (label primitive-branch))
compiled-branch
 <
code to apply compiled procedure with given target and appropriate linkage
>
primitive-branch
 (assign <
target
>
         (op apply-primitive-procedure)
         (reg proc)
         (reg argl))
 <
linkage
>
after-call

Observe that the compiled branch must skip around the primitive
branch. Therefore, if the linkage for the original procedure call was
next
, the compound branch must use a linkage that jumps to a
label that is inserted after the primitive branch. (This is similar
to the linkage used for the true branch in
compile-if
.)

(define (compile-procedure-call target linkage)
  (let ((primitive-branch (make-label 'primitive-branch))
        (compiled-branch (make-label 'compiled-branch))
        (after-call (make-label 'after-call)))
    (let ((compiled-linkage
           (if (eq? linkage 'next) after-call linkage)))
      (append-instruction-sequences
       (make-instruction-sequence '(proc) '()
        `((test (op primitive-procedure?) (reg proc))
          (branch (label ,primitive-branch))))
       (parallel-instruction-sequences
        (append-instruction-sequences
         compiled-branch
         (compile-proc-appl target compiled-linkage))
        (append-instruction-sequences
         primitive-branch
         (end-with-linkage linkage
          (make-instruction-sequence '(proc argl)
                                     (list target)
           `((assign ,target
                     (op apply-primitive-procedure)
                     (reg proc)
                     (reg argl)))))))
       after-call))))