Structure and Interpretation of Computer Programs

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

The primitive and compound branches, like the true and false branches in 

compile-if

, are

appended using 

parallel-instruction-sequences

 rather than the ordinary 

append-instruction-sequences

, because they will not be executed sequentially.

Applying compiled procedures

The code that handles procedure application is the most subtle part of the compiler, even though the

instruction sequences it generates are very short. A compiled procedure (as constructed by 

compile-lambda

) has an entry point, which is a label that designates where the code for the

procedure starts. The code at this entry point computes a result in 

val

 and returns by executing the

instruction 

(goto (reg continue))

. Thus, we might expect the code for a compiled-procedure

application (to be generated by 

compile-proc-appl

) with a given target and linkage to look like

this if the linkage is a label 

 (assign continue (label proc-return))

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

 (goto (reg val))

proc-return

 (assign <target> (reg val))   ; included if target is not val

 (goto (label <linkage>))   ; linkage code

or like this if the linkage is 

return

. 

 (save continue)

 (assign continue (label proc-return))

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

 (goto (reg val))

proc-return

 (assign <target> (reg val))   ; included if target is not val

 (restore continue)

 (goto (reg continue))   ; linkage code

This code sets up 

continue

 so that the procedure will return to a label 

proc-return

 and jumps to

the procedure’s entry point. The code at 

proc-return

 transfers the procedure’s result from 

val

 to

the target register (if necessary) and then jumps to the location specified by the linkage. (The linkage is

always 

return

 or a label, because 

compile-procedure-call

 replaces a 

next

 linkage for the

compound-procedure branch by an 

after-call

 label.)

---

In fact, if the target is not 

val

, that is exactly the code our compiler will generate.

39

 Usually,

however, the target is 

val

 (the only time the compiler specifies a different register is when targeting

the evaluation of an operator to 

proc

), so the procedure result is put directly into the target register

and there is no need to return to a special location that copies it. Instead, we simplify the code by

setting up 

continue

 so that the procedure will ‘‘return’’ directly to the place specified by the

caller’s linkage: 

<set up continue for linkage>

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

(goto (reg val))

If the linkage is a label, we set up 

continue

 so that the procedure will return to that label. (That is,

the 

(goto (reg continue))

 the procedure ends with becomes equivalent to the 

(goto

(label <linkage>))

 at 

proc-return

 above.) 

(assign continue (label <linkage>))

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

(goto (reg val))

If the linkage is 

return

, we don’t need to set up 

continue

 at all: It already holds the desired

location. (That is, the 

(goto (reg continue))

 the procedure ends with goes directly to the

place where the 

(goto (reg continue))

 at 

proc-return

 would have gone.) 

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

(goto (reg val))

With this implementation of the 

return

 linkage, the compiler generates tail-recursive code. Calling a

procedure as the final step in a procedure body does a direct transfer, without saving any information

on the stack.

Suppose instead that we had handled the case of a procedure call with a linkage of 

return

 and a

target of 

val

 as shown above for a non-

val

 target. This would destroy tail recursion. Our system

would still give the same value for any expression. But each time we called a procedure, we would

save 

continue

 and return after the call to undo the (useless) save. These extra saves would

accumulate during a nest of procedure calls.

40

Compile-proc-appl

 generates the above procedure-application code by considering four cases,

depending on whether the target for the call is 

val

 and whether the linkage is 

return

. Observe that

the instruction sequences are declared to modify all the registers, since executing the procedure body

can change the registers in arbitrary ways.

41

 Also note that the code sequence for the case with target 

val

 and linkage 

return

 is declared to need 

continue

: Even though 

continue

 is not explicitly

used in the two-instruction sequence, we must be sure that 

continue

 will have the correct value

when we enter the compiled procedure.

(define (compile-proc-appl target linkage)

  (cond ((and (eq? target ’val) (not (eq? linkage ’return)))

         (make-instruction-sequence ’(proc) all-regs

           ‘((assign continue (label ,linkage))

             (assign val (op compiled-procedure-entry)

                         (reg proc))

             (goto (reg val)))))

        ((and (not (eq? target ’val))

---