5.5 Compilation - CloneableX/SICP-learning GitHub Wiki
5.4 章节的显示控制求值器其实是一台寄存器机器，它通过控制器描述解释 Scheme 程序。在本节，我们要研究在寄存器机器中 Scheme 程序具体的运行过程，不过此时的寄存器机器控制器不再是 Scheme 解释器。
显示控制求值器是通用的，它能够运行使用 Scheme 描述的任何计算过程。求值器的控制器负责安排数据通路，以此达成符合预计的计算过程。所以求值器的数据通路也是通用的，只要提供合适的控制器，它便能够满足任何计算过程的运行。
商业通用计算机也是由一组寄存器按数据通路组装而成的寄存器机器。一台商业通用计算机的控制器也就是一台寄存器机器语言的解释器，这些机器语言与我们在前面章节使用的类似。这种语言被称为机器的 自然语言（native language），或者简称 机器语言（machine language）。使用机器语言编写的程序是一组按照数据通路描述的指令。例如，显示控制求值器指令序列可以被视作通用计算机的机器语言程序，而不是一台特殊解释器机器的控制器。
在跨越高级语言和寄存器机器语言的鸿沟时通常有两种策略。显示控制求值器表示的是解释策略。这种策略下，使用自然语言编写的机器能够执行使用有别于机器自然语言的程序语言（也称为 源语言（source language） 编写的程序。源语言的基础程式由机器自然语言编写的程序库提供。被解释的程序（也称为 源程序（source program））通过一种数据结构表示。解释器将遍历此数据结构并分析源程序。分析结束后，解释器通过调用库中合适的基础程序模拟源语言期望的行为。
在本章节，我们主要研究另一种策略—— 编译（compilation）。源语言的编译器会将源程序翻译为与机器自然语言等价的程序（称为 对象程序（object program））。本章节我们将实现一个编译器，该编译器能够将 Scheme 编写的程序翻译为显示控制求值器正常执行的指令序列。
相比解释策略，编译能够在程序上更加高效，具体原因我们稍后解释。另一方面，解释器能够为交互式程序的开发和错误排查提供更好的环境，因为源程序在运行时也能够校验和修改。而且，由于完整的基础程式库的存在，在错误排查期间依然可以构建和向系统添加新程序。
由于编译策略和解释策略的优势互补，所以现代开发环境主要使用混合策略。Lisp 解释器也是采用了混合策略，所以解释程式和编译程式都能够相互调用。于是程序员能够在排查程序期间编译这部分程序，因此从编译策略中获益的同时，也保留了解释策略开发和程序排查时的交互性。在实现编译器之后，我们将讲解如何向解释器暴露接口，使它们相互结合形成解释器-编译器开发系统。
编译器与解释器在结构和调用函数上都是十分相似。因此，编译器分析表达式的机制与解释器的应用也十分类似。而且，为了编译器和解释的对接更加便利，我们在设计编译器时打算使用与解释器一致的寄存器。环境由 env 寄存器持有，参数列表由 argl 寄存器收集，proc 中存储应用程式，计算返回的结果由 val 寄存器保存，以及由 continue 寄存器记录计算完成后回返的节点。通常情况下，编译器与翻译器在处理相同的源程序时的核心执行方法基本一致。
上述介绍向我们提供了实现一个低级编译器的思路，我们可以采用与解释器类似的方法遍历表达式。不过解释器在遇到寄存器指令时会执行它，但在编译器中不需要执行这些指令，只需要将它们收集起来。收集的指令序列就是对象程序。接着我们来解释编译器对比解释器的效率优势。每次解释器计算表达式（例如 (f 84 96)）时，它都要进行表达式类型识别工作，并检测运算数列表是否结束。对于编译器而言，只需要进行一次表达式分析，因为源程序编译期间已经生成的指令序列。由编译器生成的对象程序只包含对运算符和运算数执行计算的指令。
我们在 4.1.7 章节实现求值器语法分析时也进行了类似的性能优化。但在代码编译期间有更多的机会能够提高效率。所以对于解释器而言，它在运行时一定需要一个能够对指定语言的所有表达式都可应用的过程。相对而言，编译后的代码片段就表示对特定表达式的执行过程。这其中有着巨大的区别，比如在堆栈的使用上。当解释器计算一个表达式时，它需要为任何突发事件做好准备。在计算子表达式前，解释器需要将所有稍后用到的寄存器存入堆栈，否则子表达式的计算可能会占用某些寄存器。对于编译器而言，它只是按照表达式的结构生成代码，这样可以避免许多不必要的堆栈操作。
现在我们思考 (f 84 96) 表达式。在解释器计算该表达式的运算符前，它需要将存储参数和环境的寄存器存入堆栈。然后解释器才能计算运算符的值，并将计算结果存入 val 寄存器，然后需要从堆栈中取回之前存储的寄存器内容，最后才能将 val 的结果转入 proc 寄存器中。但是在上述表达式的计算中，运算符是标识 f，需要通过操作方法 lookup-variable-value 获取结果，实际上这个操作本身并不会改变任何寄存器的内容。所以稍后我们实现的编译器会避免这种浪费，并用下列指令生成计算运行符的指令。
(assign proc (op lookup-variable-value)
(const f)
(reg env))上述代码不仅避免了不必要的堆栈数据存储和取回，同时也直接将运算符的查询结果存入寄存器 proc，不再需要 val 作为中间转换的寄存器。
编译器也能够优化环境的访问操作次数。在分析代码程序时，编译器能够知晓变量位于哪个框架中，并直接访问该框架，不再需要通过 lookup-variable-value 查找。在 5.5.6 章节我们将讨论变量访问的实现方案。不过到目前为止，我们一直在探讨寄存器和堆栈的优化。其实编译器中还有许多优化点，例如将某些基础操作进行“在线处理”，不再需要使用 apply 机制，不过这并不是本章节的重点。本章节的主要目标是通过生动有趣的内容讲解编译过程。
在 4.1.7 章节我们将分析部件从原来的元循环求值器中拆分了出来。在分析表达式时，每个表达式的分析都会产生一个需要环境和待执行操作作为参数的执行程式。编译器的核心工作与分析部件的工作类似。不过编译器产生的不是可执行程式，而是由寄存器机器运行的指令序列。
compile 程式是编译器的顶层派发程式。它与 4.1.1 章节的 eval、4.1.7 章节的 analyze 程式和显示控制求值器中的 eval-dispatch 类似。编译器与解释器一样，也需要使用 4.1.2 章节中定义的表达式语法程式。compile 按表达式的类型执行相应的程序编译。不同类型的表达式将由对应的代码生成器处理。
(define (compile exp target linkage)
(cond ((self-evaluating? exp)
(compile-self-evaluating exp target linkage))
((quoted? exp) (compile-quoted exp target linkage))
((variable? exp)
(compile-variable exp target linkage))
((assignment? exp)
(compile-assignment exp target linkage))
((definition? exp)
(compile-definition exp target linkage))
((if? exp) (compile-if exp target linkage))
((lambda? exp) (compile-lambda exp target linkage))
((begin? exp)
(compile-sequence
(begin-actions exp) target linkage))
((cond? exp)
(compile (cond->if exp) target linkage))
((application? exp)
(compile-application exp target linkage))
(else
(error "Unknown expression type: COMPILE" exp))))compile 和代码生成器在调用时都出现了两个参数，分别是 target 和 linkage。其中 target 表示表达式的编译结果存储的寄存器。linkage 用于描述表达式的编译结果运行结束时应该如何进行下一步。linkage 描述器能够完成下列任意一个目的。
- 继续执行指令序列中的下一个指令（一般用
next表示） - 从编译的程式中返回（一般用
return表示） - 跳转至某个节点（一般用节点标识名称表示）
例如，编译表达式 5 时，target 和 linkage 的值分别是 val 和 next，所以生成的指令为 (assign val (const 5))。
当 linkage 的值为 return 时编译同样的表达式生成的指令如下。
(assign val (const 5))
(goto (reg continue))在第一种情况中，当前指令执行结束后将继续执行指令序列中的下一指令。在第二种情况中，将回到程式调用时决定的节点。不过这两种事例最终都会将表达式计算结果存入 val 寄存器中。
每个代码生成器都将返回一个指令序列，指令序列中包含了由表达式生成的对象程序。复合表达式的代码生成器由基础代码生成器的结果组合而成，就像复合表达式的计算过程一样。
组合指令序列最简单的方法就是调用程式 append-instruction-sequence。它能够将任意数量的指令序列拼接并返回。如果 <seq1> 和 <seq2> 都是指令序列，则 (append-instruction-sequences <seq1> <seq2>) 的计算结果为下列指令序列。
<seq1>
<seq2>当需要保存寄存器内容时，编译器代码会使用 preserving，它是另一种更加精细的拼接指令序列方法。preserving 有三个参数，分别是一组寄存器和两个顺序执行的指令序列。如果第二个指令序列执行时需要的寄存器，会被它在第一个指令序列执行时将内容保存下来。所以，如果第一个指令序列会修改寄存器内容，而第二个指令序列又希望使用寄存器的原始数据，preserving 将分别在第一个指令序列和第二个指令序列前使用 save 和 restore 存入和取回寄存器数据。否则 preserving 将直接将指令序列拼接返回。因此 (preserving (list <reg1> <reg2>) <seg1> <seg2>) 会因两个指令序列对 <reg1> 和 <reg2> 的使用情况产生下列几种拼接结果。
<seq1>
<seq2>(save <reg1>)
<seq1>
(restore <reg1>)
<seq2>(save <reg2>)
<seq1>
(restore <reg2>)
<seq2>(save <reg2>)
(save <reg1>)
<seq1>
(restore <reg1>)
(restore <reg2>)
<seq2>通过 perserving 拼接指令序列，编译器能够避免不必要的堆栈操作。同时这也将生成 save 和 restore 指令的细节从不同的代码生成器分离出来。事实上由代码生成器产生的指令是不包含 save 和 restore 指令的。
在一般观念中，我们会将指令序列通过指令列表的方式表示。append-instruction-sequences 通过调用 append 程式将指令序列拼接。但是 perserving 明显是一个更加复杂的方法，因为它需要分析指令序列，并根据分析结果决定寄存器的使用。preserving 可能由于它的复杂性导致低效，因为它需要分析指令序列中的每个参数，即使这些指令序列本身就是通过 perserving 拼接而成，已经经过分析。为了避免重复分析，我们会将指令语句使用的寄存器与该指令语句关联。在构建基础指令序列时，我们要明确地提供这些信息，然后通过指令语句关联的寄存器使用信息拼接指令序列。
指令序列的信息包含三个部分。
- 在序列中指令被执行前必须进行初始化的寄存器组（也可以说这些寄存器被该指令序列需要）
- 被指令序列中的指令修改的寄存器组
- 序列中实际的指令（也称为 语句（statement））
我们将使用列表形式表示指令序列的上述三部分信息。所以指令构造器的程式如下。
(define (make-instruction-sequence
needs modifies statements)
(list needs modifies statements))例如，两个指令序列都需要查找当前环境中的变量 x 的值，并将结果分配给寄存器 val，然后返回，所以需要初始化的寄存器是 env 和 continue，会被修改的寄存器是 val。于是这段指令序列要按如下形式构建。
(make-instruction-sequence
'(evn continue)
'(val)
'((assign val
(op lookup-variable-value) (const x) (reg env))
(goto (reg continue))))有时候也需要构建没有指令语句的指令序列，可以使用下列程式。
(define (empty-instruction-sequence)
(make-instruction-sequence '() '() '()))拼接指令序列的程式将在 5.5.4 章节讲解。
现在我们先实现代码生成器的 compile 程式。
通常情况下，每个代码生成器的输出最终都是由 compile-linkage 产生。如果 linkage 值是 return，则我们需要生成 (goto (reg continue)) 指令。该指令会用到 continue 寄存器，但不会修改任何寄存器内容。如果 linkage 值为 next，我们不需要增加任何指令。如果 linkage 的值是节点标识时，应该生成 goto 指令跳转至指令标识，该指令不需要任何寄存器，也不会修改任何寄存器。
(define (compile-linkage linkage)
(cond ((eq? linkage 'return)
(make-instruction-sequence '(continue) '()
'((goto (reg continue)))))
((eq? linkage 'next)
(empty-instruction-sequence))
(else
(make-instruction-sequence '() '()
`((goto (label ,linkage)))))))由于 return 情况下生成的指令需要 continue 寄存器，所以通过 perserving 将其与指令序列拼接。如果拼接的指令序列会修改 continue 寄存器的内容，则是 continue 寄存器的内容将被保存和取回。
(define (end-with-linkage linkage instruction-sequence)
(preserving '(continue)
instruction-sequence
(compile-linkage linkage)))自计算表达式、引用字符和变量的代码生成器生成的指令序列都是将计算结果分配给目标寄存器，然后根据 linkage 的值继续进行。
(define (compile-self-evaluating exp target linkage)
(end-with-linkage linkage
(make-instruction-sequence '() (list target))
`((assign ,target (const ,exp)))))
(define (compile-quoted exp target linkage)
(end-with-linkage linkage
(make-instruction-sequence '() (list target)
`((assign ,target (const ,(text-of-quotation exp)))))))
(define (compile-variable exp target linkage)
(end-with-linkage linkage
(make-instruction-sequence '(env) (list target)
`((assign ,target
(op lookup-variable-value)
(const ,exp)
(reg env))))))所有的赋值指令都会修改目标寄存器，关于变量表达式的指令还将从 env 寄存器查找变量。
赋值和定义表达式由解释器负责绝大多数处理过程。编译器只需要递归生成计算数值的指令，然后将生成的指令与设置或定义变量指令及向目标寄存器赋值的指令拼接即可。递归编译的目标寄存器为 val，linkage 的值为 next，这样才能够将计算结果存入 val，然后继续执行随后的指令。拼接指令序列时需要守护 env 的内容，当需要向环境中设置或定义变量时，变量值计算的代码会因为存在修改寄存器的可能性而演变为一个复杂表达式的编译。
(define (compile-assignment exp target linkage)
(let ((var (assignment-variable exp))
(get-value-code
(compile (assignment-value exp) 'val 'next)))
(end-with-linkage linkage
(preserving '(env)
get-value-code
(make-instruction-sequence '(env val) (list target)
`((perform (op set-variable-value!)
(const ,var)
(reg val)
(reg env))
(assign ,target (const ok))))))))
(define (compile-definition exp target linkage)
(let ((var (definition-variable exp))
(get-value-code
(compile (definition-value exp) 'val 'next)))
(end-with-linkage linkage
(perserving '(env)
get-value-code
(make-instruction-sequence '(env val) (list target)
`((perform (op define-variable!)
(const ,var)
(reg val)
(reg env))
(assign ,target (const ok))))))))上述拼接的两个指令都需要 val 和 env 寄存器，并且都会修改寄存器 target。虽然我们在指令序列的拼接中守护了 env 寄存器，但我们并没有守护 val 寄存器，因为 get-value-code 明确将计算结果存入了 val 寄存器。实际上，如果我们守护 val 寄存器可能会出现问题，因为这可能导致 val 之前的内容在 get-value-code 之后被取出。
编译后的条件表达式代码会根据具体的目标寄存器和 linkage 数值产生类似下列的指令序列。
<compilation of predicate, target val, linkage next>
(test (op false?) (reg val))
(branch (label false-branch))
true-branch
<compilation of consequent with given target
and given linkage or after-if>
false-branch
<compilation of alternative with given target and linkage>
after-if生成上述代码时，我们分别需要编译谓词语句、肯定表达式和否定表达式，并将它们的指令序列根据谓词指令的计算结果拼接起来，同时还要为肯定分支和否定分支标识不同的分支节点名称。如果谓词指令计算结果为 false，则需要跳过肯定分支。此处复杂的地方在于如何处理肯定分支的 linkage。如果条件表达式的 linkage 是 return 或节点标识，那么肯定分支和否定分支都使用相同的 linkage。如果 linkage 是 next，则肯定分支需要在结束跳转至否定分支之后的节点。
(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) '()
`((text (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 寄存器在谓词指令中需要守护，因为在稍后在肯定分支和否定分支中可能使用到 env，continue 由于可能在肯定分支或否定分支中因 linkage 为 return 而使用，所以也需要被守护。其中肯定分支与否定分支的指令序列是通过 parallel-instruction-sequences 程式拼接，我们会在 5.5.4 章节解释。
cond 是一种派生表达式，编译器只需要通过 cond->if 转换为 if 表达式再编译即可。
表达式序列的复杂点在于需要对其进行平行计算。序列中的每个表达式被编译后，只有最后一个表达式会根据 linkage 跳转，其他表达式的 linkage 都是 next。每个表达式的指令序列都是独立的指令序列拼接，也就是说 env 和 continue 都需要受到守护。
(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 表达式最终会构建为程式。所以 lambda 表达式的对象程序将表现为如下形式。
<construct procedure object and assign it to target register>
<linkage>在编译 lambda 表达式时，同时会生成程式体代码。尽管程式体在程式构建期间不会被执行，但为了方便我们会将程式体对象代码插入在 lambda 代码之后。如果 lambda 的 linkage 是 return，则是正常编译即可。如果 linkage 的值为 next 时，我们需要跳过程式体代码，并执行程式体之后的代码。所以 lambda 的对象代码形式如下。
<construct procedure object and assign it to target register>
<code for given linkage> or (goto (label after-lambda))
<compilation of procedure body>
after-lambdacompile-lambda 会构建程式并生成程式体代码。程式对象在运行时将编译后的程式体指令节点结合当前环境构建。
(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 需要使用 tack-on-instruction-sequence 将 lambda 表达式代码与程式体拼接，因为程式体并不是指令序列拼接时将要执行的指令序列的一部分，但将程式体在此时插入能够为后面的工作带来便利。
compile-lambda-body 用于构建程式体代码。程式体代码以入口节点标识开始。随后在运行程式体时需要切换至正确的环境，该环境扩展时需要包含程式体调用时所需要的形参绑定关系。这就是构成程式体的表达式序列的代码。该表达式序列编译时 linkage 是 return，目标寄存器是 val，所以程式的计算结果将存入 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))))编译过程的核心其实是对应用程式的编译。组合式的编译结果形式如下。
<compilation of operator, target proc, linkage next>
<evaluate operands and construct argument list in argl>
<compilation of procedure call with given target and linkage>其中寄存器 env、proc 和 argl 必须在计算运算符和运算数时进行存储和取回操作。并且需要注意这段编译过程目标寄存器不止 val。
应用程式需要通过 compile-application 编译。首先会递归地编译运算符，并将编译后的应用程式存入 proc 中，然后再编译运算数，并逐个编译每个运算数。运算数的指令序列由参数列表 argl 组成，最终的编译结果会结合参数列表指令和应用程式指令。在拼接指令代码的过程中，env 寄存器在编译运算符的过程中需要被守护，因为运算符的计算可能会修改 env 寄存器内容。而 proc 寄存器在构建参数列表的过程中也需要存储，因为计算实际应用的参数值时可能会进行新的应用程式计算。continue 在整个过程中也需要被守护，因为它需要在程式调用后进行跳转。
(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)))))构建参数列表的过程将计算 val 中的每个运算数，然后将计算结果通过 cons 收集至 argl 中。当我们将参数通过 cons 收集至 argl 时，必须要最后一个参数开始，以第一个参数结束，这样才能保证参数列表与参数应用顺序一致。为了避免在起始阶段需要初始化 argl 为空列表的浪费行为，我们会将第一段指令序列作为初始 argl 使用。参数列表的通用构建形式如下。
<compilation of last operand, target 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 应该在除第一个参数运算之外的其他参数运算中都进行保护，以此保证在参数收集的过程中不会丢失参数列表，env 应该在除最后一个参数之外的其他参数运算中都进行保护，因为 env 可能在运算数的计算过程中被使用。
参数的编译确实比较棘手，因为第一个参数的计算过程中需要保护 argl 和 env 寄存器内容，造成了它的特殊性。construct-arglist 程式的参数是每个运算数的指令代码。如果没有任何运算数，则它会应用指令 (assign argl (const ()))。
否则 construct-arglist 会利用最后一个参数初始化 argl，然后将其他的参数不断加入 argl 中。为了按照从最后一个参数向第一个参数的顺序处理，需要先将参数指令列表反转。
(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))))))在组合式的每个元素都编译完成后，还需要向 proc 中的程式应用 argl 中的参数列表。执行程式的过程实际上与元循环求值器中的 apply 类似。该程式需要检查应用程式是基础程式还是被编译的程式。对于基础程式，直接使用 apply-primitive-procedure 即可。对于被编译的程式我们稍后再讲解处理过程。程式应用的指令序列形式如下。
(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其中编译分支需要跳过基础程式分支。因此如果初始程式调用时的 linkage 是 next，则是复合程式的分支将通过 after-call 节点跳过基础程式分支，这与 compile-if 中对 linkage 的使用类似。
(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))))基础程式分支和复合程式分支就如同 compile-if 中的肯定分支和否定分支一样，它们都需要通过 parallel-instruction-sequences 拼接，因为它们并不是按顺序执行的。
虽然处理程式应用的部分生成的指令序列不长，但它仍然是编译器中较为复杂的部分。被编译的程式（也就是由 compile-lambda 构建的指令序列）会存在一个节点标识，通过该标识能够定位程式的起始指令。被编译的程式指令序列会将计算结果存入 val 寄存器中，然后执行 (goto (reg continue)) 返回。所以，我们希望应用编译的程式序列为如下形式。
(assign continue (label proc-return))
(assign val (op compiled-procedure-entry) (reg proc))
(goto (reg val))
proc-return
(assign <target> (reg val))
(goto (label <linkage>))如果 linkage 的值为 return 时形式如下。
(save continue)
(assign continue (lable proc-return))
(assign val (op compiled-procedure-entry) (reg proc))
(goto (reg val))
proc-return
(assign <target> (reg val))
(restore continue)
(goto (reg continue))上述指令通过设置 continue 的方式在程式调用完成后跳转至 proc-return。proc-return 中指令序列将 val 的内容转入目标寄存器中，然后再根据 linkage 的情况进行跳转。通常 linkage 都是 return 或节点标识，因为 compile-procedure-call 会在复合程式分支中 linkage 为 next 的情况下将跳转节点替换为 after-call。
实际上，如果目标寄存器不是 val，则正是我们编译将要生成的代码。然而，通常情况下目标寄存器都是 val，只有要编译运算符时才会将使用 proc 作为目标寄存器，所以程式计算结果会直接传入目标寄存器，不需要我们再进行一次拷贝。接着，我们简单地设置 continue，便能根据 linkage 的内容直接跳转。
<set up continue for linkage>
(assign val (op compiled-procedure-entry) (reg proc))
(goto (reg val))如果 linkage 是一个节点标识，则我们要设置 continue，使程式调用结束后能够跳转至目标节点。也就是程式结束后的指令 (goto (reg continue)) 要与 (goto (label <linkage>)) 等价。
(assign continue (lable <linkage>))
(assign val (op compiled-procedure-entry) (reg proc))
(goto (reg val))如果 linkage 是 return，就不需要设置 continue 的值，因为它已经持有了目标地址。因为程式调用的最后会直接执行指令 (goto (reg continue)) 跳转至目标节点。
(assign val (op compiled-procedure-entry) (reg proc))
(goto (reg val))这种对于 return 的实现使编译生成的指令为尾递归过程。调用程式的程式体最后一步会直接转换，不需要再向堆栈存入数据。
假如不做简化直接按照之前的形式生成指令序列，则将不构成尾递归。虽然系统仍然会计算出表达式的正确结果，但每次调用程式时无用的 continue 的数据将在程式内嵌调用期间不断在堆栈中累积。
compile-proc-appl 生成指令序列时只需要处理四种不同的情况，这些情况主要由 val 和 linkage 是否为 return 决定。这个指令序列将修改所有的寄存器，因为程式体的运行过程中随时可能修改任何一个寄存器。同时要注意目标寄存器为 val，linkage 为 return 的情况下需要 continue，即使在两个指令序列中没有明确使用 continue，我们也必须保证程式调用结束后 continue 的值保持正确。
(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))
(not (eq? linkage 'return)))
(let ((proc-return (make-label 'proc-return)))
(make-instruction-sequence '(proc) all-regs
`((assign continue (label ,proc-return))
(assign val (op compiled-procedure-entry)
(reg proc))
(goto (reg val))
,proc-return
(assign ,target (reg val))
(goto (label ,linkage))))))
((and (eq? target 'val) (eq? linkage 'return))
(make-instruction-sequence
'(proc continue)
all-regs
'((assign val (op compiled-procedure-entry)
(reg proc))
(goto (reg val)))))
((and (not (eq? target 'val))
(eq? linkage 'return))
(error "return linkage, target not val: COMPILE"
target))))这部分内容将描述组合指令序列的细节。回想 5.5.1 章节，指令由需要寄存器组、被修改的寄存器组和实际的指令语句以列表形式组成。同时还要考虑指令序列中出现的节点标识，因为节点标识并不会修改任何寄存器。所以为了确定指令序列需要的寄存器和修改的寄存器，我们需要使用下列程式。
(define (registers-needed s)
(if (symbol? s) '() (car s)))
(define (registers-modified s)
(if (symbol? s) '() (cadr s)))
(define (statements s)
(if (symbol? s) (list s) (caddr s)))同时为了判断某个寄存器是否指令列表需要的或修改的寄存器，我们可以使用下列程式。
(define (needs-register? seq reg)
(memq reg (registers-needed seq)))
(define (modifies-register? seq reg)
(memq reg (registers-modified seq)))我们将在实现指令组合的整个过程中使用以上程式。
最基础的组合器就是 append-instruction-sequences。它能够将任意数量的指令序列合并，并使生成的指令序列按顺序执行。比较复杂的处理过程在于确定合并后指令序列需要的和修改的寄存器。组合后的指令序列将修改所有指令序列修改寄存器的总和，需要的寄存器也是同理。
每拼接一对指令序列都通过 append-22-sequence。该程式只接收两个指令序列 seq1 和 seq2，并将指令序列合并后返回，并且将合并的指令序列需要的和修改的寄存器都进行了收集。注意在合并寄存器列表时需要去除重复的部分。append-instruction-sequences 的实现如下。
(define (append-instruction-sequences . seqs)
(define (append-2-sequences seq1 seq2)
(make-instruction-sequence
(list-union
(registers-needed seq1)
(list-difference (registers-needed seq2)
(registers-needed seq1)))
(list-union (registers-modified seq1)
(registers-modified seq2))
(append (statements seq1) (statements seq2))))
(define (append-seq-list seqs)
(if (null? seqs)
(empty-instruction-sequence)
(append-2-sequences
(car seqs)
(append-seq-list (cdr seqs)))))
(append-seq-list seqs))上述程式使用简洁的操作将 set 像列表一样操作。
(define (list-union s1 s2)
(cond ((null? s1) s2)
((memq (car s1) s2) (list-union (cdr s1) s2))
(else (cons (car s1) (list-union (cdr s1) s2)))))
(define (list-difference s1 s2)
(cond ((null? s1) '())
((memq (car s1) s2) (list-difference (cdr s1) s2))
(else (cons (car s1)
(list-difference (cdr s1) s2)))))另一个主要的指令合并器是 preserving，它的参数为寄存器列表 regs 和两个按顺序执行的指令序列 seq1 和 seq2。它将 seq1 和 seq2 按先后顺序拼接，并在 seq1 和 seq2 周围根据它们对 regs 寄存器的使用情况将寄存器 save 和 restore。要实现这个功能，preserving 需要先创建一个 seq1 周围起先 save 和 restore 的指令序列。然后将 seq1 中使用到的寄存器在 seq1 前保存，然后在 seq1 使用完寄存器后将寄存器恢复。然后再按常规方式将 seq2 拼接。下列是该程式的实现。
(define (preserving regs seq1 seq2)
(if (null? regs)
(append-instruction-sequences seq1 seq2)
(let ((first-reg (car regs)))
(if (and (needs-register? seq2 first-reg)
(modifies-register? seq1 first-reg))
(preserving (cdr regs)
(make-instruction-sequence
(list-union (list first-reg)
(registers-needed seq1))
(list-difference (registers-modified seq1)
(list first-reg))
(append `((save ,first-reg))
(statements seq1)
`((restore ,first-reg))))
seq2)
(preserving (cdr regs) seq1 seq2)))))tack-on-instruction-sequence 也是一个组合器，它用于编译 lambda 表达式时将程式体与其他指令序列拼接。因为程式体并不是与拼接指令序列同级执行的，所以它使用的寄存器不需要合并至整个指令序列的使用寄存器列表中去。所以在该程式中，我们应该忽略程式体使用的寄存器。
(define (tack-on-instruction-sequence seq body-seq)
(make-instruction-sequence
(registers-needed seq)
(registers-modified seq)
(append (statements seq)
(statements body-seq))))compile-if 和 compile-procedure-call 都使用了 parallel-instruction-sequences 拼接两种情况的指令分支。这两个指令分支不会都执行，如果某个分支进行了运算，则其他分支将会跳过。因此，第二个分支需要的寄存器也是合并后指令序列需要的寄存器，即使这些寄存器会被第一个分支修改。
(define (parallel-instruction-sequences seq1 seq2)
(make-instruction-sequence
(list-union (registers-needed seq1)
(registers-needed seq2))
(list-union (registers-modified seq1)
(registers-modified seq2))
(append (statements seq1)
(statements seq2))))现在我们已经展示了编译的所有内容，接下来让我们检验一下它的功能。我们打算编译 factorial 程式。
(compile
'(define (factorial n)
(if (= n 1)
1
(* (factorial (- n 1)) n)))
'val
'next)define 表达式的结果最终会存入 val 寄存器中。我们并不关心 define 的编译结果，所以我们随意将 linkage 的值设置为 next。
compile 通过判断表达式的定义，决定调用 compile-definition 编译代码，并将结果存入目标寄存器中，然后将程式定义装载至环境中，最终根据 linkage 的值进行跳转。env 在计算过程中会受到保护，因为要保证程式定义装载的环境正确。由于 linkage 的值是 next，也就表示接下来不会存在任何跳转指令。所以编译后的整个指令框架如下。
<save env if modified by code to compute value>
<compilation of definition value, target val, linkage next>
<restore env if saved above>
(perform (op define-variable!)
(const factorial)
(reg val)
(reg env))
(assign val (const ok))最终编译产生的 factorial 是个 lambda 表达式，该表达式的计算结果就是阶乘的计算结果。compile 通过调用 compile-lambda 处理整个过程，它将编译程式体，并为程式体建立节点标识，然后在节点标识内生成程式体集成的指令序列，以及集成程式体运行环境，然后将结果分配给 val。该指令序列会跳过程式体指令部分。程式体指令只会在程式归属的环境进行形参绑定后再开始执行。如果变量值的代码没有修改 env 寄存器，则生成的指令序列中不会存在相应的 save 和 restore 指令。所以编译结果的形式如下。
(assign val
(op make-compiled-procedure)
(label entry2)
(reg env))
(goto (label after-lambda1))
entry2
(assign env (op compiled-procedure-env) (reg proc))
(assign env
(op extend-environment)
(const (n))
(reg argl)
(reg env))
<compilation of procedure body>
after-lambda1
(perform (op define-variable!)
(const factorial)
(reg val)
(reg env))
(assign val (const ok))程式体问题被编译为目标寄存器为 val，linkage 为 return 的指令序列。在这个示例中程式体指令序列由 if 表达式组成。
(if (= n 1)
1
(* (factorial (- n 1)) n))compile-if 将生成谓词表达式的指令序列，然后根据谓词表达式的计算结果跳转相应分支。如果后继 if 表达式还要使用 env 和 continue 的话，它们会在谓词指令周围受到保护。如果 if 表达式是整个指令序列的最后的表达式，则它的目标寄存器就是 val，linkage 值是 return，所以此时的肯定分支和否定分支都按照目标寄存器为 val，linkage 为 return 的情况编译。
<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其中谓词 (= n 1) 也是一个程式调用。它将查找运算符对应的程式存入 proc 中。然后将 1 和 n 收集到 argl 中。然后检查 proc 中的程式是基础程式还是复合程式，然后调用相应的处理过程操作。不论是哪种程式最终都会进入 after-call 节点标识。运算符和运算数的计算过程中并不会导致任何寄存器被保存，因为该程式的计算中修改寄存器并不会导致问题。
(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如果进入肯定分支，编译结果如下。
(assign val (const 1))
(goto (reg continue))否定分支的指令是对另一个程式的调用，然后应用标识为 * 的程式，它的参数是 n 和另一个程式的调用。无论是基础程式还是复合程式都需要设置 proc 和 argl 的值。需要注意在谓词表达式计算时对 continue 寄存器保护，因为这些寄存器会由于谓词程式的调用被修改，并且需要在程式运行结束后根据 linkage 的值 return 跳转。
编译器执行过程中最常见的优化就是对变量查找的优化。我们实现的编译器通过 lookup-variable-value 查找变量值。它会在运行环境中逐个框架进行绑定关系中的变量比对。如果此时框架内嵌过深查询过程将变得低效，或者变量较多时也会降低效率。例如，思考下列程式中进行 (* x y z) 运算时查找变量 x 的问题。
(let ((x 3) (y 4))
(lambda (a b c d e)
(let ((y (* a b x)) (z (+ c d x)))
(* x y z))))因为 let 其实是 lambda 表达式语法糖，上述程式的真实情况如下。
((lambda (x y)
(lambda (a b c d e)
((lambda (y z) (* x y z))
(* a b x)
(+ c d x))))
3
4)每次查找变量 x 时，lookup-varialbe-value 都需要判断 x 与 y、z、a、b、c、d 或 e 是否相等。我们目前程序中没有通过 define 绑定变量，变量的绑定都是通过 lambda 构建。由于我们使用语言的词法作用域，任何表达式的运行时环境都拥有一个结构，该结构使得表达式出现的程序词法结构保持平行。因此，当编译分析前一个表达式时，编译器都知道每次向变量 x 应用程式 (* x y z) 时，需要查找当前框架外部的第二个框架，并且变量 x 一定是目标框架的首个变量。
我们可以利用该现象开发一个新的变量查询操作—— lexical-address-lookup。它的参数为环境和 词法地址（lexical address），其中词法地址由两个数字构成，分别是 框架数（frame number） 和 置换数（displacement number）。框架数描述了需要跳过多少框架，置换数表示在该框架里需要跳过几个变量。lexical-address-lookup 将获取存储于相对当前环境偏移的词法地址变量值。如果将 lexical-address-lookup 添加至寄存器机器中，编译器生成指令序列时就可以通过该方法查找变量。与之类似，编译器也可以用 lexical-address-set! 替换 set-variable-value!。
同时，编译器还需要能够辨识变量的词法地址。程序中的词法地址主要根据变量出现在程序中的位置判断。例如，在下列程序中，表达式 <e1> 中的变量 x 的词法地址为 (2, 0)，也就是当前框架向后两个框架中的第一个变量。而 <e1> 中的变量 y 的词法地址为 (0, 0)，变量 c 的词法地址为 (1, 2)。在表达式 <e2> 中，变量 x、y、z 的词法地址分别是 (1, 0)、(1, 1) 和 (0, 2)。
((lambda (x y)
(lambda (a b c d e)
((lambda (y z) <e1>)
<e2>
(+ c d x))))
3
4)编译器使用词法地址的一种方案是需要维护一种称为 编译时环境（compile-time environment） 的数据结构。该数据结构用于追踪运行环境中变量访问操作发生时，变量在框架中的位置变化。如果变量值不需要在编译时运算，则会导致变量没有绑定值。编译时环境将作为 compile 的另一个参数出现，它会被传递至每个代码生成器中。在 lambda 程式体被编译时，compile-lambda-body 将扩展编译时环境，并在扩展环境中添加程式参数，然后编译后的程式体指令将在扩展环境中运行。在 compile-variable 和 compile-assignment 中为了生成合适的词法地址也要使用编译时环境。
直到现在我们还没有解释应该如何在求值器中加载编译器代码。我们假设显示控制求值器已经实现了表示被编译程式的数据结构。现在，我们只需要实现用于编译 Scheme 表达式的 compile-and-go 程式，它将为求值器加载编译后的对象程序，然后在全局环境的条件下启动求值器运行对象程序，并最终输出计算结果，再次开始新一轮的求值器驱动循环。所以我们需要改进求值器，使被解释的表达式和被编译的程式都能够运行。稍后我们将向求值器机器添加一段被编译的程式，然后运算它。
(compile-and-go
'(define (factorial n)
(if (= n 1)
1
(* (factorial (- n 1)) n))))
;;; EC-Eval value:
ok
;;; EC-Eval input:
(factorial 5)
;;; EC-Eval value:
120为了求值器能够处理被编译的程式，我们需要修改 apply-dispatch 的代码，使它能够识别被编译的程式，然后通过转换器直接控制被编译代码的节点。
apply-dispatch
(test (op primitive-procedure?) (reg proc))
(branch (label primitive-apply))
(test (op compound-procedure?) (reg proc))
(branch (label compound-apply))
(test (op compiled-procedure?) (reg proc))
(branch (label compiled-apply))
(goto (label unknown-procedure-type))
compiled-apply
(restore continue)
(assign val (op compiled-procedure-entry) (reg proc))
(goto (reg val))在 compiled-apply 中我们缓存了 continue。回忆一个 apply-dispatch 的处理，continue 是被存入堆栈的顶部的。另一方面，被编译代码的节点标识希望下一步的跳转按 continue 处理，所以continue 必须在编译代码执行前恢复。
除此之外，我们还需要在求值器机器之前加入 branch 指令，如果此时 flag 寄存器已经被设置，便能够使机器进入新的标识节点。
(branch (label external-entry))
read-eval-print-loop
(perform (op initialize-stack))external-entry 预设了求值器机器将以包含进行运算的指令序列地址的 val 寄存器开始，以 (goto (reg continue)) 结束。所以开始时将跳转到 val 中指定的标识节点，不过在此之前会为 continue 赋值，以便执行结束后能够跳转回到 print-result，将 val 的内容输入然后再次开启求值器的驱动循环。
externla-entry
(perform (op initialize-stack))
(assign env (op get-global-environment))
(assign continue (lable print-result))
(goto (reg val))现在，我们可以使用下列程式编译程式定义，然后执行编译结果，最后通过驱动循环测试编译的程式。因为我们希望被编译的代码能够回到 continue 中指定的节点，并将结果存储于 val 中，所以编译表达式时目标寄存器使用 val，linkage 使用 return。为了将编译器产生的代码转换为寄存器机器中可执行的代码，我们需要使用寄存器机器模拟器中的 assemble 程式。随后初始化 val 寄存器，使其指向指令列表的节点，然后设置 flag 寄存器，使求值器能够跳转至 external-entry，然后启动求值器。
(define (compile-and-go expression)
(let ((instructions
(assemble
(statements
(compile expression 'val 'return))
eceval)))
(set! the-global-environment (setup-environment))
(set-register-contents! eceval 'val instructions)
(set-register-contents! eceval 'flag true)
(start eceval)))如果我们已经嵌入了堆栈监控器，在此过程就能查看堆栈的使用情况。
(compile-and-go
'(define (factorial n)
(if (= n 1)
1
(* (factorial (- n 1)) n))))
(total-pushes = 0 maximum-depth = 0)
;;; EC-Eval value:
ok
;;; EC-Eval input:
(factorial 5)
(total-pushes = 31 maximum-depth = 14)
;;; EC-Eval value:
120与只使用解释器的情况比较，计算相同表达式的效率。只使用解释器的时候会进行 144 次堆栈存入操作，堆栈的最大使用尝试为 28。这明显说明了编译对整个运算过程的优化。
现在我们已经对解释和编译两种策略都有了接触。解释器能够将机器升级运行高级程序，而编译器会将高级程序降级为机器语言。我们可以将 Scheme 语言（或者说任何编程语言）看作建立在机器语言之上的抽象集群。解释器对于交互式程序开发和问题排查更加友好，因为程序的每一步执行都可以通过这些抽象管理，因此对于程序员来说也更加智能。编译则能使运行效率提升，因为程序的执行由机器语言管理，所以编译器能够自由优化高级语言的抽象。
解释和编译的不同也将导致语言迁移至新型计算机时的策略不同。假设我们想为一种新型机器实现 Lisp 语言，一种策略是将显示求值器中的指令按新机器的指令进行翻译。另一种策略需要修改编译器，使其生成能在新机器上运行的代码。这种策略只需要对 Lisp 系统进行一次编译就可以在新机器上运行，有所区别的只是编译版本关联的运行库不同。其实还可以更进一步，甚至我们可以编译编译器本身，然后在新机器上编译其他 Lisp 程序。或者编译一个解释器，使其能够在新机器上运行。