5.5  编译

第5.4节的显式控制求值器是一台控制器解释Scheme程序的寄存器机器。在本节中，我们将看到如何在一台控制器不是Scheme解释器的寄存器机器上运行Scheme程序。

显式控制求值器机器是通用的——它能够执行任何可以用Scheme描述的计算过程。求值器的控制器协调使用其数据路径来执行所需的计算。因此，求值器的数据路径是通用的：只要有适当的控制器，它们就足以执行我们想要的任何计算。³³

商业通用计算机是以一组寄存器和操作组织起来的寄存器机器，这些寄存器和操作构成了一套高效便捷的通用数据路径。通用机器的控制器是我们一直在使用的那种寄存器机器语言的解释器。这种语言称为机器的本机语言，或简称为机器语言。用机器语言编写的程序是使用机器数据路径的指令序列。例如，显式控制求值器的指令序列可以被看作通用计算机的机器语言程序，而不是专用解释器机器的控制器。

有两种常见的策略用于弥合高级语言和寄存器机器语言之间的差距。显式控制求值器说明了解释策略。用机器本机语言编写的解释器配置机器以执行用某种语言（称为源语言）编写的程序，该语言可能不同于执行求值的机器的本机语言。源语言的基本过程被实现为用给定机器的本机语言编写的子程序库。要被解释的程序（称为源程序）被表示为一种数据结构。解释器遍历这个数据结构，分析源程序。在此过程中，它通过调用库中适当的基本子程序来模拟源程序的预期行为。

在本节中，我们探索另一种策略：编译。给定源语言和机器的编译器将源程序翻译成用机器本机语言编写的等价程序（称为目标程序）。我们在本节中实现的编译器将用Scheme编写的程序翻译成要使用显式控制求值器机器的数据路径执行的指令序列。³⁴

与解释相比，编译可以极大地提高程序执行的效率，我们将在下面的编译器概述中解释这一点。另一方面，解释器为交互式程序开发和调试提供了更强大的环境，因为正在执行的源程序在运行时可用于检查和修改。此外，由于整个基本过程库都存在，可以在调试期间构建新程序并添加到系统中。

鉴于编译和解释的互补优势，现代程序开发环境采用混合策略。Lisp解释器通常组织成解释过程和编译过程可以相互调用。这使得程序员可以编译那些假定已调试好的程序部分，从而获得编译的效率优势，同时为那些处于交互式开发和调试中的程序部分保留解释执行模式。在第5.5.7节中，在实现了编译器之后，我们将展示如何将其与解释器接口，以产生一个集成的解释器-编译器开发系统。

编译器概述

我们的编译器非常类似于我们的解释器，无论是在结构上还是在它执行的功能上。因此，编译器用于分析表达式的机制将类似于解释器使用的机制。此外，为了便于接口编译和解释代码，我们将设计编译器生成遵守与解释器相同的寄存器使用约定的代码：环境将保持在env寄存器中，参数列表将累积在argl中，要应用的过程将在proc中，过程将在val中返回其结果，过程应返回的位置将保持在continue中。一般来说，编译器将源程序翻译成目标程序，该目标程序执行与解释器在求值相同源程序时基本相同的寄存器操作。

这个描述暗示了实现一个初等编译器的策略：我们以与解释器相同的方式遍历表达式。当遇到解释器在求值表达式时会执行的寄存器指令时，我们不执行该指令，而是将其累积到一个序列中。形成的指令序列将是目标代码。观察编译相对于解释的效率优势。每次解释器求值一个表达式——例如，(f 84 96)——它执行对表达式进行分类的工作（发现这是一个过程应用）和测试操作数列表的结尾（发现有两个操作数）。使用编译器时，表达式仅在编译时生成指令序列时分析一次。编译器产生的目标代码只包含求值运算符和两个操作数、组装参数列表以及将过程（在proc中）应用于参数（在argl中）的指令。

这与我们在第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中得到结果，然后将其移动到proc。

编译器还可以优化对环境的访问。在分析代码后，编译器在许多情况下可以知道特定变量位于哪个框架中，并直接访问该框架，而不是执行lookup-variable-value搜索。我们将在第5.5.6节讨论如何实现这样的变量访问。但在此之前，我们将专注于上述的寄存器和栈优化。编译器还可以执行许多其他优化，例如将基本操作编码为"内联"形式，而不是使用通用的apply机制（见练习5.38）；但我们不会在这里强调这些。我们在本节中的主要目标是在简化（但仍然有趣）的上下文中说明编译过程。

5.5.1  编译器的结构

在第4.1.7节中，我们修改了原始的元循环解释器，将分析与执行分离开来。我们分析每个表达式以产生一个执行过程，该过程以环境为参数并执行所需操作。在我们的编译器中，我们将做基本相同的工作。不过，我们不是产生执行过程，而是生成要由我们的寄存器机器运行的指令序列。

过程compile是编译器中的顶层分派。它对应于第4.1.1节的eval过程、第4.1.7节的analyze过程以及第5.4.1节中显式控制求值器的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及其调用的代码生成器除了要编译的表达式外还接受两个参数。一个是目标，指定编译代码应在其中返回表达式值的寄存器。还有一个连接描述符，描述表达式编译产生的代码在完成执行后应如何进行。连接描述符可以要求代码执行以下三种操作之一：

• 继续执行序列中的下一条指令（这由连接描述符下一页指定），

• 从正在编译的过程中返回（这由连接描述符return指定），或

• 跳转到命名的入口点（通过使用指定的标号作为连接描述符来指定）。

例如，编译自求值表达式5，目标为val寄存器，连接为下一页，应产生指令

(assign val (const 5))

用return连接编译相同的表达式应产生指令

(assign val (const 5))
(goto (reg continue))

在第一种情况下，执行将继续执行序列中的下一条指令。在第二种情况下，我们将从过程调用中返回。在这两种情况下，表达式的值将被放入目标val寄存器中。

指令序列和栈使用

每个代码生成器返回一个指令序列，其中包含它为表达式生成的目标代码。复合表达式的代码生成是通过组合来自更简单的组件表达式代码生成器的输出来完成的，就像复合表达式的求值是通过求值组件表达式来完成的一样。

组合指令序列的最简单方法是称为append-instruction-sequences的过程。它以任意数量的要顺序执行的指令序列为参数；它将这些序列追加起来并返回组合后的序列。也就是说，如果<seq₁>和<seq₂>是指令序列，那么求值

(append-instruction-sequences <seq₁> <seq₂>)

产生序列

<seq₁>
<seq₂>

每当可能需要保存寄存器时，编译器的代码生成器会使用preserving，这是一种更微妙的组合指令序列的方法。Preserving接受三个参数：一组寄存器和两个要顺序执行的指令序列。它追加序列的方式是，如果第一个序列的执行需要保留集合中每个寄存器的内容以供第二个序列执行使用，则执行此保留操作。也就是说，如果第一个序列修改了寄存器而第二个序列确实需要该寄存器的原始内容，那么preserving会在第一个序列周围包装一对save和restore，然后再追加序列。否则，preserving简单地返回追加后的指令序列。因此，例如，

(preserving (list <reg₁> <reg₂>) <seq₁> <seq₂>)

根据<seq₁>和<seq₂>如何使用<reg₁>和<reg₂>，产生以下四种指令序列之一：

通过使用preserving组合指令序列，编译器避免了不必要的栈操作。这也将是否生成save和restore指令的细节隔离在preserving过程中，将它们与编写各个代码生成器时产生的关注点分离开来。事实上，代码生成器不会显式产生任何save或restore指令。

原则上，我们可以简单地将指令序列表示为指令列表。然后Append-instruction-sequences可以通过执行普通的列表append来组合指令序列。然而，preserving将成为一个复杂的操作，因为它必须分析每个指令序列以确定该序列如何使用其寄存器。Preserving既低效又复杂，因为它必须分析其每个指令序列参数，即使这些序列本身可能是通过调用preserving构造的，在这种情况下它们的部分可能已经被分析过。为了避免这种重复分析，我们将为每个指令序列关联一些关于其寄存器使用情况的信息。当构造基本指令序列时，我们将显式提供这些信息，而组合指令序列的过程将从与组件序列关联的信息中推导出组合后的序列的寄存器使用信息。

一个指令序列将包含三部分信息：

• 必须在执行序列中的指令之前初始化的寄存器集合（这些寄存器被称为序列需要的），

• 其值被序列中的指令修改的寄存器集合，

• 序列中的实际指令（也称为语句）。

我们将把指令序列表示为其三个部分的列表。因此指令序列的构造函数为

(define (make-instruction-sequence needs modifies statements)
  (list needs modifies statements))

例如，在当前环境中查找变量x的值，将结果赋给val，然后返回的双指令序列，需要寄存器env和continue已经初始化，并修改寄存器val。因此这个序列将被构造为

(make-instruction-sequence '(env 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节中展示。

练习 5.31.  在求值一个过程应用时，显式控制求值器总是在求值运算符前后保存和恢复env寄存器，在每个操作数（最后一个除外）的求值前后保存和恢复env，在每个操作数的求值前后保存和恢复argl，以及在操作数序列的求值前后保存和恢复proc。对于以下每个组合式，指出哪些save和restore操作是多余的，因此可以通过编译器的preserving机制消除：

(f 'x 'y)

((f) 'x 'y)

(f (g 'x) y)

(f (g 'x) 'y)

练习 5.32.  使用preserving机制，编译器在运算符是符号的情况下，将避免在求值组合式的运算符前后保存和恢复env。我们也可以将这些优化构建到求值器中。事实上，第5.4节的显式控制求值器已经通过将无操作数的组合式作为特殊情况处理，执行了类似的优化。

a. 扩展显式控制求值器，使其能够将运算符是符号的组合式识别为一类单独的表达式，并在求值此类表达式时利用这一事实。

b. Alyssa P. Hacker 提出，通过扩展求值器以识别越来越多的特殊情况，我们可以纳入编译器所有的优化，而这将完全消除编译的优势。你认为这个想法如何？

5.5.2  编译表达式

在本节和下一节中，我们将实现compile过程分派到的代码生成器。

编译连接代码

一般来说，每个代码生成器的输出将以由过程compile-linkage生成的指令结束，这些指令实现了所需的连接。如果连接是return，那么我们必须生成指令(goto (reg continue))。这需要continue寄存器，并且不修改任何寄存器。如果连接是下一页，那么我们不需要包含任何额外的指令。否则，连接是一个标号，我们生成一个到该标号的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)))))))

连接代码通过preservingcontinue寄存器追加到指令序列后，因为return连接将需要continue寄存器：如果给定的指令序列修改了continue而连接代码需要它，那么continue将被保存和恢复。

(define (end-with-linkage linkage instruction-sequence)
  (preserving '(continue)
   instruction-sequence
   (compile-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寄存器。

赋值和定义的处理方式与解释器中的处理方式大致相同。我们递归地生成计算要赋给变量的值的代码，然后在其后追加一个双指令序列，该序列实际设置或定义变量并将整个表达式的值（符号ok）赋给目标寄存器。递归编译的目标是val，连接是下一页，这样代码将把结果放入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
     (preserving '(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))))))))

追加的双指令序列需要env和val并修改目标寄存器。注意，虽然我们为这个序列保留了env，但我们没有保留val，因为get-value-code被设计为显式地将其结果放入val以供此序列使用。（事实上，如果我们确实保留了val，我们会引入一个错误，因为这会导致在运行get-value-code后立即恢复val的先前内容。）

编译条件表达式

用给定目标和连接编译的if表达式的代码具有以下形式

 <compilation of predicate, target val, linkage 下一页>
 (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

为了生成这段代码，我们编译谓词、后继和备选，并将生成的代码与测试谓词结果的指令以及新生成的用于标记真分支和假分支以及条件结束的标号结合起来。³⁷在这种代码安排中，如果测试为假，我们必须跳转到真分支之后。唯一的稍微复杂之处在于如何处理真分支的连接。如果条件的连接是return或一个标号，那么真分支和假分支都将使用相同的连接。如果连接是下一页，真分支以跳转到假分支代码之后的条件结束标号处结束。

(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在谓词代码周围被保留，因为它可能被真分支和假分支需要，而continue被保留，因为它可能被这些分支中的连接代码需要。真分支和假分支（它们不会顺序执行）的代码使用第5.5.4节中描述的特殊组合器parallel-instruction-sequences追加。

注意cond是一个派生表达式，因此编译器处理它所需做的就是应用cond->if转换器（来自第4.1.2节）并编译生成的if表达式。

编译序列

序列的编译（来自过程体或显式begin表达式）与它们的求值并行。序列中的每个表达式都被编译——最后一个表达式使用为序列指定的连接，其他表达式使用连接下一页（以执行序列的其余部分）。各个表达式的指令序列被追加起来形成单个指令序列，同时保留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表达式构造过程。lambda表达式的目标代码必须具有以下形式

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

当我们编译lambda表达式时，我们也会生成过程体的代码。尽管过程体在构造过程时不会被执行，但将其插入到lambda代码之后的目标代码中是方便的。如果lambda表达式的连接是一个标号或return，这没问题。但如果连接是下一页，我们需要通过使用一个跳转到插入在过程体之后的标号的连接来跳过过程体的代码。因此目标代码具有以下形式

 <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生成构造过程对象的代码，后面跟着过程体的代码。过程对象将在运行时通过将当前环境（定义点的环境）与编译过程体的入口点（一个新生成的标号）组合来构造。³⁸

(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（第5.5.4节）而不是append-instruction-sequences将过程体追加到lambda表达式代码后，因为过程体不是进入组合序列时将要执行的指令序列的一部分；相反，它之所以在序列中，只是因为那是一个放置它的方便位置。

Compile-lambda-body构造过程体的代码。这段代码以入口点的标号开始。接下来是指令，这些指令将使运行时求值环境切换到用于求值过程体的正确环境——即过程定义环境，扩展以包含形参到调用过程时使用的实参的绑定。之后是构成过程体的表达式序列的代码。该序列以连接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))))

5.5.3  编译组合式

编译过程的本质是过程应用的编译。 用给定目标和连接编译的组合式的代码具有以下形式

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

在求值运算符和操作数期间，可能需要保存和恢复寄存器env、proc和argl。注意，这是编译器中唯一指定非val目标的地方。

所需的代码由compile-application生成。它递归地编译运算符，产生将要应用的过程放入proc的代码，并编译操作数，产生求值应用的各个操作数的代码。操作数的指令序列通过construct-arglist与构造argl中参数列表的代码组合，得到的参数列表代码与过程代码以及执行过程调用的代码（由compile-procedure-call产生）组合。在追加代码序列时，必须在求值运算符前后保留env寄存器（因为求值运算符可能修改env，而求值操作数需要它），并且必须在构造参数列表前后保留proc寄存器（因为求值操作数可能修改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, 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必须在每个操作数求值（第一个除外）前后保留（这样到目前为止累积的参数不会丢失），而env必须在每个操作数求值（最后一个除外）前后保留（供后续的操作数求值使用）。

编译这段参数代码有点棘手，因为第一个要求值的操作数需要特殊处理，并且需要在不同位置保留argl和env。Construct-arglist过程以求值各个操作数的代码为参数。如果根本没有操作数，它简单地发出指令

(assign argl (const ()))

否则，construct-arglist创建用最后一个参数初始化argl的代码，并追加依次求值其余参数并将它们接合到argl的代码。为了从最后一个到第一个处理参数，我们必须反转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))))))

应用过程

在求值了组合式的元素之后，编译代码必须将proc中的过程应用于argl中的参数。该代码执行与第4.1.1节元循环求值器中的apply过程或第5.4.1节显式控制求值器中的apply-dispatch入口点基本相同的分派。它检查要应用的过程是基本过程还是编译过程。对于基本过程，它使用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

注意编译分支必须跳过基本分支。因此，如果原始过程调用的连接是下一页，编译分支必须使用一个跳转到插入在基本分支之后的标号的连接。（这类似于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))))

基本分支和编译分支，如同compile-if中的真分支和假分支，使用parallel-instruction-sequences而不是普通的append-instruction-sequences追加，因为它们不会顺序执行。

应用编译过程

处理过程应用的代码是编译器中最微妙的部分，尽管它生成的指令序列非常短。编译过程（由compile-lambda构造）有一个入口点，这是一个标号，指定过程代码开始的位置。该入口点处的代码在val中计算结果，并通过执行指令(goto (reg continue))返回。因此，我们可能期望用给定目标和连接处理编译过程应用的代码（由compile-proc-appl生成）看起来像这样（如果连接是一个标号）

 (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

或者像这样（如果连接是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

这段代码设置continue，使过程将返回到标号proc-return，然后跳转到过程的入口点。Proc-return处的代码将过程的结果从val传送到目标寄存器（如有必要），然后跳转到连接指定的位置。（连接总是return或一个标号，因为compile-procedure-call将编译过程分支的下一页连接替换为after-call标号。）

事实上，如果目标不是val，这正是我们的编译器将生成的代码。³⁹然而，通常目标是val（编译器指定不同寄存器的唯一时候是在将运算符的求值目标定为proc时），所以过程结果被直接放入目标寄存器，不需要返回来复制它的特殊位置。相反，我们通过设置continue来简化代码，使过程直接"返回"到调用者连接指定的位置：

<set up continue for linkage>
(assign val (op compiled-procedure-entry) (reg proc))
(goto (reg val))

如果连接是一个标号，我们设置continue使过程返回到该标号。（也就是说，过程结尾的(goto (reg continue))变得等价于上面proc-return处的(goto (label <linkage>))。）

(assign continue (label <linkage>))
(assign val (op compiled-procedure-entry) (reg proc))
(goto (reg val))

如果连接是return，我们根本不需要设置continue：它已经持有期望的位置。（也就是说，过程结尾的(goto (reg continue))直接到达proc-return处的(goto (reg continue))原本要去的地方。）

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

通过这种return连接的实现，编译器生成尾递归代码。在过程体中作为最后一步调用过程时，进行直接转移，而不在栈上保存任何信息。

假设我们改为按照上面非val目标的方式处理连接为return、目标为val的过程调用情况。这会破坏尾递归。我们的系统仍然会对任何表达式给出相同的值。但是每次调用过程时，我们都会保存continue，并在调用后返回以撤销（无用的）保存。这些额外的保存会在嵌套的过程调用期间累积。⁴⁰

Compile-proc-appl通过考虑四种情况来生成上述过程应用代码，取决于调用的目标是否是val以及连接是否是return。注意，指令序列被声明为修改所有寄存器，因为执行过程体可能以任意方式改变寄存器。⁴¹还要注意，目标为val、连接为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.4  组合指令序列

本节描述指令序列如何被表示和组合的细节。回顾第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-2-sequences一次追加两个。它接受两个指令序列seq1和seq2，并返回指令序列，其语句是seq1的语句后跟seq2的语句，其修改的寄存器是被seq1或seq2修改的寄存器，其需要的寄存器是seq1需要的寄存器以及seq2需要但不被seq1修改的寄存器。（用集合操作术语来说，新的所需寄存器集合是seq1所需寄存器集合与seq2所需寄存器减去seq1修改寄存器的差集的并集。）因此，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-modified 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))

这个过程使用一些用于操作表示为列表的集合的简单操作，类似于第2.3.3节中描述的（无序）集合表示：

(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周围加上适当的save和restore指令，以保护regs中被seq1修改但被seq2需要的寄存器。为了实现这一点，preserving首先创建一个序列，该序列包含所需的save后跟seq1的语句，再后跟所需的restore。这个序列除了需要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被compile-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))))

5.5.5  编译代码示例

既然我们已经看到了编译器的所有元素，让我们检查一个编译代码的示例，看看各个部分如何组合在一起。我们将通过调用compile来编译递归factorial过程的定义：

(compile
 '(define (factorial n)
    (if (= n 1)
        1
        (* (factorial (- n 1)) n)))
 'val
 'next)

我们已经指定应将define表达式的值放入val寄存器。我们不关心编译代码在执行define之后做什么，因此我们选择下一页作为连接描述符是任意的。

Compile确定该表达式是一个定义，因此它调用compile-definition来编译计算要赋的值的代码（目标为val），然后是安装定义的代码，再后是将define的值（即符号ok）放入目标寄存器的代码，最后是连接代码。在计算值的过程中保留Env，因为安装定义需要它。由于连接是下一页，在这种情况下没有连接代码。因此，编译代码的骨架是

  <save env if modified by code to compute value>
  <compilation of definition value, target val, linkage 下一页>
  <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的指令。然后序列跳过在此处插入的编译过程代码。过程代码本身首先通过一个将形参n绑定到过程参数的框架来扩展过程的定义环境。然后是实际的过程体。由于这段为变量值的代码不修改env寄存器，上面显示的可选的save和restore不会被生成。（entry2处的过程代码此时不会被执行，因此它对env的使用是无关的。）因此，编译代码的骨架变为

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

过程体总是（由compile-lambda-body）作为目标为val、连接为return的序列编译。本例中的序列由单个if表达式组成：

(if (= n 1)
    1
    (* (factorial (- n 1)) n))

Compile-if生成首先计算谓词（目标为val）的代码，然后检查结果，如果谓词为假则分支跳过真分支。Env和continue在谓词代码周围被保留，因为它们可能被if表达式的其余部分需要。由于if表达式是构成过程体的序列中的最后一个表达式（也是唯一的表达式），其目标为val，连接为return，因此真分支和假分支都以目标val和连接return编译。（也就是说，条件表达式的值，即由任一分支计算的值，就是该过程的值。）

  <save continue, env if modified by predicate and needed by branches>
  <compilation of predicate, target val, linkage 下一页>
  <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

真分支（常量1）编译为（目标val和连接return）

  (assign val (const 1))
  (goto (reg continue))

假分支的代码是另一个过程调用，其中过程是符号*的值，参数是n和另一个过程调用（对factorial的调用）的结果。这些调用每个都设置proc和argl及其自己的基本分支和编译分支。图5.17展示了factorial过程定义的完整编译。注意上面显示的谓词周围可能的continue和env的save和restore实际上被生成了，因为这些寄存器被谓词中的过程调用修改，并且被分支中的过程调用和return连接需要。

练习 5.33.  考虑下面阶乘过程的定义，它与上面给出的定义略有不同：

(define (factorial-alt n)
  (if (= n 1)
      1
      (* n (factorial-alt (- n 1)))))

编译这个过程，并将生成的代码与为factorial生成的代码进行比较。解释你发现的任何差异。哪个程序比另一个执行效率更高？

练习 5.34.  编译迭代阶乘过程

(define (factorial n)
  (define (iter product counter)
    (if (> counter n)
        product
        (iter (* counter product)
              (+ counter 1))))
  (iter 1 1))

注解生成的代码，展示factorial的迭代版本和递归版本的代码之间的本质区别，即一个过程会消耗栈空间而另一个会在常量栈空间中运行。

练习 5.35.  什么表达式被编译产生了图5.18中所示的代码？

练习 5.36.  我们的编译器为组合式的操作数产生的求值顺序是什么？是从左到右、从右到左，还是其他顺序？这个顺序在编译器的何处确定？修改编译器使其产生某种其他的求值顺序。（参见第5.4.1节关于显式控制求值器求值顺序的讨论。）改变操作数求值的顺序如何影响构造参数列表的代码的效率？

练习 5.37.  理解编译器用于优化栈使用的preserving机制的一种方式是，看看如果我们不使用这个想法会产生什么额外的操作。修改preserving使其总是生成save和restore操作。编译一些简单的表达式，识别生成的不必要的栈操作。将代码与保持preserving机制完整时生成的代码进行比较。

练习 5.38.  我们的编译器在避免不必要的栈操作方面很聪明，但在编译对语言基本过程的调用时，就机器提供的基本操作而言，一点也不聪明。例如，考虑为了计算(+ a 1)编译了多少代码：代码在argl中设置参数列表，将基本加法过程（通过在环境中查找符号+找到）放入proc，并测试该过程是基本过程还是复合过程。编译器总是生成执行测试的代码，以及基本分支和复合分支的代码（其中只有一个会被执行）。我们没有显示实现基本过程的那部分控制器，但我们假定这些指令使用了机器数据路径中的基本算术操作。考虑如果编译器能够开代码基本过程——也就是说，如果它能生成直接使用这些基本机器操作的代码——那么会生成少得多的代码。表达式(+ a 1)可能被编译成像这样简单的东西 ⁴³

(assign val (op lookup-variable-value) (const a) (reg env))
(assign val (op +) (reg val) (const 1))

在本练习中，我们将扩展编译器以支持选定基本过程的开代码。对于对这些基本过程的调用，将生成专用代码，而不是通用过程应用代码。为了支持这一点，我们将用特殊的参数寄存器arg1和arg2来增强我们的机器。机器的基本算术操作将从arg1和arg2获取输入。结果可以放入val、arg1或arg2。

编译器必须能够在源程序中识别开代码基本过程的应用。我们将增强compile过程中的分派，除了它目前识别的保留字（特殊形式）之外，还能识别这些基本过程的名称。⁴⁴ 对于每个特殊形式，我们的编译器都有一个代码生成器。在本练习中，我们将为开代码基本过程构建一组代码生成器。

a.  与特殊形式不同，开代码基本过程都需要操作数被求值。编写一个供所有开代码生成器使用的代码生成器spread-arguments。Spread-arguments应接受一个操作数列表，并将给定的操作数编译到连续的参数寄存器中。注意，操作数可能包含对开代码基本过程的调用，因此在操作数求值期间必须保留参数寄存器。

b.  对于每个基本过程=、*、-和+，编写一个代码生成器，它接受具有该运算符的组合式，以及目标和连接描述符，并生成将参数展开到寄存器中，然后对给定目标以给定连接执行操作的代码。你只需要处理具有两个操作数的表达式。让compile分派到这些代码生成器。

c.  在你的新编译器上尝试factorial示例。将生成的代码与没有开代码时产生的结果进行比较。

d.  扩展你的+和*的代码生成器，使其能够处理具有任意数量操作数的表达式。具有两个以上操作数的表达式必须编译成一系列操作，每个操作只有两个输入。

5.5.6  词法寻址

编译器执行的最常见优化之一是变量查找的优化。我们的编译器，迄今为止我们实现的，生成使用求值器机器的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)

每次lookup-variable-value搜索x时，它必须确定符号x既不eq?于y或z（在第一个框架中），也不eq?于a、b、c、d或e（在第二个框架中）。我们暂且假设程序不使用define——变量仅通过lambda绑定。由于我们的语言是词法作用域的，任何表达式的运行时环境都将具有与该表达式出现的程序的词法结构相平行的结构。⁴⁵ 因此，编译器在分析上述表达式时可以知道，每次应用该过程时，(* x y z)中的变量x将位于当前框架向外两层处的框架中，并且是该框架中的第一个变量。

我们可以利用这一事实，发明一种新的变量查找操作lexical-address-lookup，它接受一个环境和一个由两个数字组成的词法地址作为参数：一个框架编号，指定要跳过多少个框架，以及一个位移编号，指定在该框架中跳过多少个变量。Lexical-address-lookup将产生存储在该词法地址处的变量值（相对于当前环境）。如果我们将lexical-address-lookup操作添加到我们的机器中，就可以使编译器生成使用此操作而非lookup-variable-value来引用变量的代码。类似地，我们的编译代码可以使用新的lexical-address-set!操作来代替set-variable-value!。

为了生成这样的代码，编译器必须能够确定它即将编译引用的变量的词法地址。程序中变量的词法地址取决于代码中的位置。例如，在下面的程序中，表达式<e1>中x的地址是(2,0)——向后退两个框架，且是该框架中的第一个变量。在那一点上，y的地址是(0,0)，c的地址是(1,2)。在表达式<e2>中，x的地址是(1,0)，y的地址是(1,1)，c的地址是(0,2)。

((lambda (x y)
   (lambda (a b c d e)
     ((lambda (y z) <e1>)
      <e2>
      (+ c d x))))
 3
 4)

编译器产生使用词法寻址的代码的一种方式是维护一个称为编译时环境的数据结构。它跟踪当执行特定变量访问操作时，运行时环境中哪些变量将在哪些框架的哪些位置。编译时环境是一个框架列表，每个框架包含一个变量列表。（当然，变量不会绑定值，因为在编译时不计算值。）编译时环境成为compile的额外参数，并传递给每个代码生成器。对compile的顶层调用使用空的编译时环境。当编译lambda体时，compile-lambda-body通过包含过程参数的框架扩展编译时环境，因此构成体的序列使用那个扩展后的环境进行编译。在编译的每个点，compile-variable和compile-assignment使用编译时环境来生成适当的词法地址。

练习5.39到5.43描述了如何完成这个词法寻址策略的概要，以便将词法查找合并到编译器中。练习5.44描述了编译时环境的另一个用途。

练习 5.39.  编写一个实现新查找操作的过程lexical-address-lookup。它应该接受两个参数——一个词法地址和一个运行时环境——并返回存储在指定词法地址处的变量值。如果变量的值是符号*unassigned*，Lexical-address-lookup应发出错误信号。⁴⁶还要编写一个过程lexical-address-set!，实现改变指定词法地址处变量值的操作。

练习 5.40.  修改编译器以维护如上所述的编译时环境。也就是说，向compile和各种代码生成器添加一个编译时环境参数，并在compile-lambda-body中扩展它。

练习 5.41.  编写一个过程find-variable，它以变量和编译时环境为参数，返回变量相对于该环境的词法地址。例如，在上面显示的程序片段中，编译表达式<e1>期间的编译时环境是((y z) (a b c d e) (x y))。Find-variable应产生

(find-variable 'c '((y z) (a b c d e) (x y)))
(1 2)

(find-variable 'x '((y z) (a b c d e) (x y)))
(2 0)

(find-variable 'w '((y z) (a b c d e) (x y)))
not-found

练习 5.42.  使用练习5.41中的find-variable，重写compile-variable和compile-assignment以输出词法地址指令。在find-variable返回not-found的情况下（即变量不在编译时环境中），你应该让代码生成器像以前一样使用求值器操作来搜索绑定。（在编译时找不到的变量唯一可能的位置是全局环境，它是运行时环境的一部分，但不是编译时环境的一部分。⁴⁷因此，如果你愿意，可以让求值器操作直接在全局环境中查找，这可以通过操作(op get-global-environment)获得，而不是让它们搜索env中的整个运行时环境。）在一些简单的情况下测试修改后的编译器，比如本节开头的嵌套lambda组合式。

练习 5.43.  我们在第4.1.6节中论证了用于块结构的内部定义不应被视为"真正的"define。相反，过程体应被解释为，好像被定义的内部变量被安装为普通的lambda变量，并使用set!初始化为其正确的值。第4.1.6节和练习4.16展示了如何通过扫描出内部定义来修改元循环解释器以实现这一点。修改编译器以在编译过程体之前执行相同的转换。

练习 5.44.  在本节中，我们专注于使用编译时环境来产生词法地址。但编译时环境还有其他用途。例如，在练习5.38中，我们通过开代码基本过程来提高编译代码的效率。我们的实现将开代码过程的名称视为保留字。如果程序要重新绑定这样的名称，练习5.38中描述的机制仍然会将其作为基本过程进行开代码，忽略新的绑定。例如，考虑以下过程

(lambda (+ * a b x y)
  (+ (* a x) (* b y)))

它计算x和y的线性组合。我们可以用参数+matrix、*matrix和四个矩阵调用它，但开代码编译器仍然会将(+ (* a x) (* b y))中的+和*开代码为基本+和*。修改开代码编译器以查询编译时环境，以便为涉及基本过程名称的表达式编译正确的代码。（只要程序不对这些名称使用define或set!，代码就能正确工作。）

5.5.7  将编译代码接口到求值器

我们还没有解释如何将编译代码加载到求值器机器中或如何运行它。我们将假设显式控制求值器机器已按照第5.4.4节中的定义，并具有脚注38中指定的额外操作。我们将实现一个过程compile-and-go，它编译一个Scheme表达式，将产生的目标代码加载到求值器机器中，并使机器在求值器全局环境中运行代码，打印结果，并进入求值器的驱动循环。我们还将修改求值器，使得解释表达式可以调用编译过程和解释过程。然后我们可以将一个编译过程放入机器中，并使用求值器调用它：

(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

为了允许求值器处理编译过程（例如，求值上面调用factorial），我们需要修改apply-dispatch（第5.4.1节）处的代码，使其识别编译过程（区别于复合过程或基本过程）并直接将控制转移到编译代码的入口点：⁴⁸

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。

为了使我们能够在启动求值器机器时运行一些编译代码，我们在求值器机器的开头添加一条branch指令，如果设置了flag寄存器，该指令使机器转到新的入口点。⁴⁹

  (branch (label external-entry))      ; branches if flag is set
read-eval-print-loop
  (perform (op initialize-stack))
  ...

External-entry假定机器启动时val包含一个指令序列的位置，该指令序列将结果放入val并以(goto (reg continue))结束。从这个入口点开始，跳转到val指定的位置，但首先赋值continue，使得执行将返回到print-result，它打印val中的值，然后转到求值器read-eval-print循环的开头。⁵⁰

external-entry
  (perform (op initialize-stack))
  (assign env (op get-global-environment))
  (assign continue (label print-result))
  (goto (reg val))

现在我们可以使用以下过程来编译过程定义、执行编译代码，并运行read-eval-print循环，这样我们可以尝试该过程。因为我们希望编译代码返回到continue中的位置，其结果在val中，所以我们以目标val和连接return编译表达式。为了将编译器产生的目标代码转换为求值器寄存器机器的可执行指令，我们使用寄存器机器模拟器中的assemble过程（第5.2.2节）。然后我们初始化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)))

如果我们已经设置了栈监控，如同第5.4.4节末尾那样，我们可以检查编译代码的栈使用情况：

(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

将此示例与使用同一过程的解释版本求值(factorial 5)进行比较，后者显示在第5.4.4节末尾。解释版本需要144次压栈和最大栈深度28。这说明了我们的编译策略所带来的优化。

解释与编译

有了本节中的程序，我们现在可以试验解释和编译的替代执行策略。⁵¹解释器将机器提升到用户程序的层次；编译器将用户程序降低到机器语言的层次。我们可以将Scheme语言（或任何编程语言）视为建立在机器语言之上的一族连贯的抽象。解释器适合交互式程序开发和调试，因为程序执行的步骤是按照这些抽象组织的，因此对程序员来说更容易理解。编译代码可以执行得更快，因为程序执行的步骤是按照机器语言组织的，并且编译器可以自由地进行跨越更高级抽象的优化。⁵²

解释和编译的替代方案也导致了将语言移植到新计算机的不同策略。假设我们希望为新机器实现Lisp。一种策略是从第5.4节的显式控制求值器开始，将其指令翻译成新机器的指令。另一种不同的策略是从编译器开始，修改代码生成器使其为新机器生成代码。第二种策略允许我们首先使用运行在原始Lisp系统上的编译器编译任何Lisp程序，并将其与运行时库的编译版本链接，从而在新机器上运行该程序。⁵³更好的是，我们可以编译编译器本身，并在新机器上运行它以编译其他Lisp程序。⁵⁴或者，我们可以编译第4.1节中的一个解释器，以产生一个在新机器上运行的解释器。

练习 5.45.  通过比较编译代码使用的栈操作与求值器用于相同计算使用的栈操作，我们可以确定编译器在速度（减少栈操作总数）和空间（减少最大栈深度）方面优化栈使用的程度。将此优化的栈使用与同一计算的专用机器的性能进行比较，可以给出编译器质量的一些指示。

a. 练习5.27要求你确定求值器使用上面给出的递归阶乘过程计算n!所需的压栈次数和最大栈深度作为n的函数。练习5.14要求你对图5.11中所示的专用阶乘机器进行相同的测量。现在使用编译的factorial过程执行相同的分析。

取编译版本中压栈次数与解释版本中压栈次数的比率，并对最大栈深度做同样的操作。由于用于计算n!的操作次数和栈深度在n中是线性的，这些比率在n变大时应趋近于常数。这些常数是什么？类似地，找出专用机器中的栈使用与解释版本中使用的比率。

将专用代码与解释代码的比率与编译代码与解释代码的比率进行比较。你会发现专用机器比编译代码好得多，因为手工定制的控制器代码应该比我们初级的通用编译器产生的代码好得多。

b. 你能提出帮助编译器生成更接近手工定制版本性能的代码的改进吗？

练习 5.46.  执行类似于练习5.45中的分析，以确定编译树递归Fibonacci过程的有效性

(define (fib n)
  (if (< n 2)
      n
      (+ (fib (- n 1)) (fib (- n 2)))))

与使用图5.12的专用Fibonacci机器的有效性进行比较。（关于解释性能的测量，见练习5.29。）对于Fibonacci，使用的时间资源在n中不是线性的；因此栈操作的比率不会趋近于独立于n的极限值。

练习 5.47.  本节描述了如何修改显式控制求值器，使解释代码可以调用编译过程。请展示如何修改编译器，使编译过程不仅能调用基本过程和编译过程，还能调用解释过程。这需要修改compile-procedure-call以处理复合（解释）过程的情况。确保处理所有与compile-proc-appl中相同的target和linkage组合。为了执行实际的过程应用，代码需要跳转到求值器的compound-apply入口点。该标号不能直接在目标代码中引用（因为汇编器要求它汇编的所有代码中引用的标号都必须在其中定义），因此我们将向求值器机器添加一个名为compapp的寄存器来保存这个入口点，并添加一条初始化指令：

  (assign compapp (label compound-apply))
  (branch (label external-entry))      ; branches if flag is set
read-eval-print-loop
  ...

要测试你的代码，首先定义一个调用过程g的过程f。使用compile-and-go编译f的定义并启动求值器。然后，在求值器中输入，定义g并尝试调用f。

练习 5.48.  本节实现的compile-and-go接口很不方便，因为编译器只能被调用一次（在求值器机器启动时）。通过提供一个可以从显式控制求值器内部调用的compile-and-run基本过程来增强编译器-解释器接口，如下所示：

;;; EC-Eval input:
(compile-and-run
 '(define (factorial n)
    (if (= n 1)
        1
        (* (factorial (- n 1)) n))))
;;; EC-Eval value:
ok
;;; EC-Eval input:
(factorial 5)
;;; EC-Eval value:
120

练习 5.49.  作为使用显式控制求值器的读-求值-打印循环的替代方案，设计一个执行读-编译-执行-打印循环的寄存器机器。也就是说，该机器应该运行一个循环，读取表达式、编译它、汇编并执行生成的代码，然后打印结果。在我们的模拟设置中这很容易运行，因为我们可以安排将过程compile和assemble作为"寄存器机器操作"调用。

练习 5.50.  使用编译器编译第4.1节的元循环求值器，并使用寄存器机器模拟器运行该程序。（要一次编译多个定义，可以将定义打包在begin中。）生成的解释器由于多层次的解释将运行得非常慢，但使所有细节都工作是一个有教学意义的练习。

练习 5.51.  通过将第5.4节的显式控制求值器翻译成C语言，开发一个Scheme的初等实现（用C语言或你选择的其他低级语言）。为了运行这段代码，你还需要提供适当的存储分配例程和其他运行时支持。

练习 5.52.  作为练习5.51的对比，修改编译器使其将Scheme过程编译成C指令序列。编译第4.1节的元循环求值器，以产生一个用C编写的Scheme解释器。