我的消费券

[compiler.scm中的示例编译器是Scheme子集的简单编译器的框架，其结构与eval.scm中的示例解释器非常接近。]

[这不合适，或者首先需要更多介绍性的介绍：]

解释器有一个称为的基本调度例程eval，可以评估任何一种表达式，而编译器有一个名为的基本调度例程，可以对任何一种表达式进行编译compile。像一样eval，compile检查要编译的表达式，并分派给该表达式的适当例程。编译表达式的例程可以递归调用compile来编译子表达式，就像解释性评估程序可以 eval递归调用以评估子表达式一样。

什么是编译器？
[对于早期的内容，这有点多余，但是更具体。我应该把它剪下来吗？]

在回答什么是编译器之前，让我们回头讨论一下解释器。

什么是口译员？
口译员实际上有两件事：

它检查表达式并分派给该表达式的相应代码
它执行程序指定的实际操作
通常，解释器完成的大部分工作都在第一类中-例如，我们的示例解释器花费大量时间检查表达式，以查看它们是自评估还是符号或列表，然后分派到适当的位置。评估那种表达的程序。这种分派与评估表达式的实际工作交错在一起。

解释器的问题之一是，每次遇到表达式时，都会再次对其进行分析。考虑一个类似的表达式，该表达式(+ foo bar)嵌入到一个循环中，可以循环多次。我们的解释器将在循环的每个迭代中遇到此表达式，并且在循环的每个迭代中，它将执行几乎相同的操作：它将检查该表达式并找出它是一个列表，然后调用eval-list，它将进一步对其进行检查以找到它是一个组合（不是特殊形式或宏），然后调用eval-combo。然后eval-combo将 eval递归调用以评估子表达式，并且每次调用eval将检查子表达式并将其分配给适当的专门评估例程。只有这样，我们开始实际计算表达式的值，通过计算子表达式的值+，foo和bar，即查找这些变量的值。

好，那么什么是编译器？
我们宁愿将大部分多余的工作都排除在外，并只检查一次表达式以了解要做什么。然后，每次我们“评估”表达式时，我们都可以做这些事情。对于expression (+ foo bar)，解释器将执行的一组操作（不包括所有分析和分派）：

查找变量栏
     查找变量foo
     查找变量+
     应用
（这里我们假设我们从右到左评估组合的子表达式，而不是从更直观的左到右顺序；这是在Scheme中这样做的合法方法，事实证明，在非常简单的编译器，我们将在稍后说明。）

[也许我应该将其更改为从左到右执行args，但是操作符最后一次，如RScheme。]

对于这样的代码，其中没有任何条件，我们可以很容易地将解释器转换为编译器。我们只是修改了解释器，以使它实际上记录了如果解释表达式将执行的操作，而不是实际评估表达式。对于这些简单的操作（如look-up-variable）的确切工作方式，我有一个模糊的表述 ，但是您应该能够看到它们中的每一个都可以翻译成少量的机器指令。大多数编译器就是这样工作的：他们首先将程序翻译成中间代码表示形式，例如我们的查询变量操作，然后将该表示形式转换为机器指令。（在它们之间可能有一个或多个“优化”中间代码的步骤，并且每个步骤可能以不同的方式表示代码。）

因此，这个简单的编译器只是“假装”要对表达式求值，但是只要它到达实际的操作（例如查找变量或调用过程），它就会简单地记录如果只是解释器就会执行的操作。结果是一系列动作，如果采取的话，将具有与解释表达式相同的作用。

这是另一个例子：

（让[[x 22）
      （y 15））
   （+ x（* xy）））
假设我们的中间代码表示形式是表示操作及其操作数的一系列列表，那么我们的简单编译器将生成的代码为：

（字面意思是22）
  （字面量为15）
  （绑定xy）
  （查找变量y）
  （查找变量x）
  （查找变量*）
  （致电程序）
  （查找变量x）
  （致电程序）
  （解除绑定）
稍后，我们将更具体地讨论有关在查找值时将值临时存储在何处的信息，并进行各种调整以使将中间代码转换为更短和更快的机器指令序列成为可能。现在，请注意我们可以将这些中间代码操作的序列串在一起，如果仅将它们转换成一些机器指令，我们就可以将这些机器指令序列串在一起并得到更大的序列，然后执行该序列来评估整个表情。我们可以根据需要执行任意多次，并且所有表达式分析和分派都已经完成-每次执行时唯一要做的工作就是实际绑定变量，查找值，调用过程以及以此类推。

编译条件表达式（如）并不难if。当我们编译一个时if，我们需要为条件表达式，结果表达式和替代表达式生成代码。（“条件”是在条件为真时执行的代码，“条件”是在条件为假时执行的代码。）然后，我们需要将这些表达式的代码与一些条件分支适当地串在一起：

<条件代码>
   （如果为假，则分支“其他操作标签”）
   <结果代码>
   （无条件分支“结束标签”）
“其他动作标签”
   <替代代码>
“结束标签”
此处的标签实际上将转换为它们所标签的代码的地址，并且分支将被这些地址填充。（我们必须谨慎地对if我们编译的每个标签使用一对唯一的新标签，或类似的其他技巧，以便我们可以嵌套if表达式并使它们的标签保持直线。）

（从该表示形式生成机器代码的一种方法是，将每个语句转换为简短的汇编指令序列，并将每个标签转换为汇编标签，如图所示将它们串在一起。然后可以将汇编代码组装为机器代码。）

请注意，对于if，编译器的控制结构实际上比解释器的控制结构简单。解释器将评估条件表达式，然后在运行时决定是评估后续表达式（“ then”）还是替代表达式（“ else”）。编译器将始终编译所有三个子表达式，并根据条件表达式代码计算出的运行时值，将它们与将在运行时进行确定的条件分支一起串起来。

这是一个稍微复杂的示例：

（让[[x 15））
   （如果x
       （让[[y（* 2 x）））
          （+ xy））
       #t））
转换为中间代码，大致类似于：

（字面量为15）
   （绑定x）
   （查找变量x）
   （如果为假，则分支“ else22”）
   （查找变量x）
   （字面意思2）
   （查找变量*）
   （致电程序）
   （绑定y）; 创建并输入绑定y的envt
   （查找变量y）
   （查找变量x）
   （查找变量+）
   （致电程序）
   （解除绑定）; 绑定y的退出环境
   （分支“ end22”）
 “ else22”
   （字面意思是#t）
 “ end22”          
实际上，我们生成的代码有一些小问题，但这与可行的中间表示非常接近。

编译器生成什么？
[讨论机器代码，解释性虚拟机等。

编译器的基本结构
编译器的主要功能是compile，它为表达式生成中间代码，并且可以递归调用自身以为子表达式生成代码。

要求compile传递它一个表达和一些簿记信息，我们将在后面讨论。编译返回中间代码，以及一些簿记信息的更新版本。

要开始此过程，需要对顶层表单（例如您在read-compile-run-print循环中键入的表单或顶层过程的定义）进行一些按摩，然后生成它们的中间代码。然后，将中间代码转换为实际的可执行代码，并将其打包为可以调用的闭包。

我们将在稍后讨论这些问题，这些问题包括按摩顶级表单并生成可执行的闭包。目前，主要要了解的是递归生成嵌套表达式的中间代码。

这是编译器的主要调度例程，与解释器类似eval：

（定义（编译expr ct-envt文字状态ct-cont）
   （cond（（symbol？expr）
          （编译符号expr ct-envt文字状态ct-cont））
         （（对？expr）
          （编译列表expr ct-envt文字状态ct-cont））
         （（自我评估？expr）
          （编译自我评估exp ct-envt文字状态ct-cont））
         （#t
          （语法错误“非法表达形式” expr））））
现在，忽略大多数关于的参数compile，我们将在后面解释。需要注意的主要事情是它看起来很像 eval。

[ 等等等等等等...]

[在某处，重要的是要找出eval的相互递归和在解释器中的应用以及编译器的工作方式之间的区别。Eval在本地重复发生，但是只是生成适用于应用的代码...编译器的控制结构实际上比解释器更简单，因为这些毛茸茸的东西仅在运行时发生...]

数据表示，呼叫约定等
在尝试更详细地了解编译器本身之前，可能最好先具体了解一下数据的表示形式，过程调用的工作方式以及寄存器的使用方式。也就是说，您必须了解编译器为其编译的“抽象机”。

抽象机是低级操作和对象的抽象。编译器首先将代码从源语言编译为该较低层的表示形式，然后将“抽象机器语言”转换为实际的可执行代码。（可执行代码可以是直接在硬件上运行的机器代码，也可以是由快速解释器解释的解释性可执行代码，例如字节码。）

您可以认为抽象机更像是汇编器，而不是解释器，但可能比大多数汇编器更聪明。

我将描述一组使事物具体化的特定功能；这不是RScheme，Scheme-48或我所知道的任何其他特定系统的工作方式，但是除了它的简单性之外，没有什么不寻常的地方。

在充实示例编译器的过程中，让我们假设系统以这种方式工作：

我们有一些重要的寄存器以定型方式使用，例如，用于保存指向当前绑定环境的指针。
我们有一个评估堆栈，用于在评估嵌套表达式时存储中间值。
我们使用延续链来表示调用者及其调用者等的保存状态，以便可以在过程返回后恢复它们。
抽象机的寄存器可以代表硬件寄存器，或仅代表以这些原型化方式使用的存储位置。（例如，如果编译为C，则寄存器可能是C全局变量，并且C编译器可能会或可能不会让您指定应将变量放入硬件寄存器中。）

寄存器
我们假设编译器生成的代码可以使用几个重要的寄存器：

的VALUE寄存器，其中的表达叶子的值，以便它能够通过一个封闭表达式中使用。在过程的情况下，这是过程返回时为调用方保留值的地方。调用过程时也使用值寄存器。
该ENVT寄存器包含指向当前正在执行代码的环境的指针。
的CONT寄存器，它保存一个指针到呼叫者保存延续的链。
该TEMPLATE寄存器包含指向与当前正在执行的过程相关联的特殊数据结构的指针，以及
该PC程序计数器寄存器，它说这指示我们目前正在执行。（如果我们要编译为普通的机器代码，则这是为此目的内置在CPU中的一个特殊寄存器，我们几乎像其他任何代码一样使用它。如果我们要编译为解释性的可执行代码，则可能是解释器中的变量。）
评估堆栈（或简称为评估堆栈）
评估堆栈用于保存已通过评估子表达式计算但尚未使用或绑定的值。

在(+ foo 22)计算表达式时，将计算三个值。计算每个值时，它将保留在VALUE寄存器中。我们从右到左求值，并在评估PUSH完每个参数之后，对eval堆栈执行操作，该操作将值寄存器中的值复制到eval堆栈中。当我们到达第一个子表达式（应该返回一个函数调用的子表达式）时，我们将值保留在值寄存器中，因为这是我们将闭包指针放置在过程调用中的位置。

评估堆栈用于两个主要目的：

存储嵌套表达式的中间值，以及
将参数传递给过程。
评估堆栈不用于保存暂停过程的中间值或局部变量-与传统的C或Pascal实现中的激活堆栈不同。在任何给定时间，评估堆栈中的值只是为当前执行过程存储的中间值。暂停过程的中间值会根据需要保存在继续链中。

当我们调用过程时，评估堆栈上唯一的值就是该过程的参数。在调用之前，调用方使用的任何其他值都将从eval堆栈移到一个延续中。

延续链
延续链是一种数据结构，它在传统编程语言的实现中大致充当了激活堆栈的角色。连续链是部分连续的链接列表 ，每个部分都是存储过程保存状态的记录。

当一个过程执行一个非尾过程调用时，它将重要的状态信息打包为部分延续。该记录将保存环境，模板，PC和延续寄存器的值以及评估堆栈上的所有临时值。

一旦调用者以部分连续的形式保存了其状态，则被调用者可以使用重要的寄存器和评估堆栈来执行其所需的任何操作。（这称为调用方保存寄存器使用约定，因为过程的调用方必须保存恢复时所需的任何值。）

请记住，连续性是在垃圾回收堆上分配的，并且是不可变的-一旦创建了连续性，我们就永远不会对其进行修改。当我们从已保存的部分连续中恢复时，我们会将部分连续中的值复制到寄存器和eval堆栈中，但这并不会修改部分连续本身，它仍然位于堆上。这对于能够实现“当前通话”很重要：这就是使我们可以从同一连续中恢复任意次的原因。

环境环境
编译器假定绑定环境是一 帧框架，每个框架都是作为变量绑定的插槽向量。每个框架还具有一个静态链接或作用域链接 字段，该字段指向表示下一个词法包围环境的框架。

顶级环境专门表示为将名称映射到绑定的哈希表。我们将使用哈希表而不是我们在简单解释器中使用的关联列表，因为如果您有很多绑定，它们会更快。用于顶层环境的绑定对象与解释器中的绑定对象几乎相同：一个带有两个重要槽的小向量：一个用于其名称的槽和一个用于实际值字段的槽。

本地环境被从顶层环境表示非常不同：每个帧是时隙的矢量，并且不没有 存储所述绑定的名称。事实证明，仅在编译时才需要名称，因此实际上不必将其存储在运行时环境中。（事实证明，编译器能够完成大部分工作，以便在编译时查找顶级变量，因此哈希表的速度对于我们的运行时速度而言并不重要。）

闭包表示和调用
我们系统中的闭包用具有两个字段的对象表示：指向闭包捕获的环境的指针，以及指向称为template的对象的指针，该对象又包含指向该过程代码的指针。

当我们评估以下表达式时

（让（（foo 22）
      （第15条））
   （lambda（...）
       ...））
我们将创建一个环境框架来保存foo和bar的绑定，并将它们分别初始化为22和15。该环境框架将具有一个范围链接，该链接指向进入时我们在其中执行的环境let。在此环境中，我们将创建一个闭合。闭包将保存指向新环境的指针，以及指向表示要关闭的匿名过程的模板对象的指针。该模板将具有指向实际可执行代码的指针。所有这些都将是堆分配的对象，在我们的实现中，我们将为每个头字段提供一个标题字段，以显示该对象是什么类型的对象：

<以至于 帧
                                           用于封闭
                                              范围>
                                               
                                                ^
                                                |
                                + ---------- + |
                                | 环保 fr。| |
                        ，------> + ========== + |
                       /范围| + ---- + ---- +       
     + ---------- + / + ---------- +
     | 封闭| / foo | 22 |
     + ========== + / + ---------- +
envt | + ---- +-'栏| 15 |
     + ---------- + + ---------- +     
proc | + ---- +-。    
     + ---------- + \ + ---------- +   
                     \ | 模板| + ---------- +
                      `---> + ========== + | 代码
                      代码 + ---- + -----> + ========== +
                           + ---------- + |可执行|
                           | | +的代码+
                           + ---------- + |程序|
                           | | + +
                           + ---------- + | ... |
                           | ... | + ---------- +
                           + ---------- +
模板对象不仅保存指向实际代码的指针，还保存编译器可以在编译时计算或查找的任何其他方便的值，并且这些值应在运行时可用于过程。我们稍后再讨论。

当我们想将过程应用于某些参数值时，我们将参数值放在eval堆栈上，并在VALUE寄存器中指向要调用的闭包的指针。然后，我们执行执行调用的简短指令序列：

从闭包中提取环境指针，并将其放入环境寄存器中。（这基本上只是使用值寄存器作为基础的索引加载。）
从闭包中提取模板指针，并将其放在模板寄存器中。（这基本上只是使用值寄存器作为基础的另一个索引加载。）
从模板中提取代码指针，并将其放入程序计数器寄存器，即跳转到该代码。（这基本上只是使用模板寄存器作为基址并跳转到该地址的另一个索引加载。）
因此，在中间表示中用于“应用”操作的实际机器代码只是少数执行此操作的指令-定型小指令序列，该序列解构闭包并在开始执行过程之前将适当的值放入寄存器中。

因为这是过程调用约定的工作方式，所以我们知道，当我们开始为过程执行代码时，环境寄存器将指向正确的环境（定义过程的位置），而模板寄存器将指向用于以下操作的模板：该过程。通过以模板寄存器为基数进行索引加载，可以在编译时获取编译器存储在模板中的所有值。

考虑以下过程：

（定义（foo xy）
   （列出'bar xy））
在这里，过程需要文字栏-foo中必须有一些代码以某种方式获取指向符号栏的指针。这就是模板对象的用途。编译此过程时，编译器将累积此类文字的列表，并且在创建该过程的模板对象时，所有这些值都将存储在其中。当编译器生成代码以获取符号时bar，它仅查看符号在文字列表中的位置（并因此查看其在模板对象中的偏移量），并生成代码以进行索引加载以在运行时从模板获取该值。

延续
应用过程不会保存呼叫者的状态
请记住，当我们做一个过程调用，我们也没有必要保存调用者的状态。对于非尾部调用，编译器必须生成代码以保存调用者的状态以及实际调用的代码。对于尾部呼叫，无需保存状态。因此，实际上并没有一个单独的“过程调用”操作可以保存调用者的状态并调用被调用者。有两个单独的操作，save-continuation和 apply。

如上所述，执行过程应用的代码序列假定指向要调用的闭包的指针在VALUE寄存器中。该过程返回时将其值保留在该寄存器中。

继续保存
save-continuation 是将当前执行过程的状态保存为部分延续的操作，并将其推入延续链。

推入延续时，将所有值保存在eval堆栈上非常重要，除了要调用的过程的参数外。因此，对于组合（过程调用）表达式生成代码时，代码保存呼叫者的状态并没有只是实际的代码之前来调用过程。这将从eval堆栈中删除该过程的参数。取而代之的是，继续保存恰好在生成将传递给过程的参数值的代码之前：

（保存-继续<label>）; 在计算参数之前保存所有其他内容
  <计算参数>
    ...
  <计算arg1>
  <计算被叫方>
  （应用）
<标签>
这样，在调用过程时，调用的参数（以及其他所有参数）将位于eval堆栈上，并且当过程返回时，它将把部分继续的其他值恢复到eval堆栈上。

对于调用过程的嵌套表达式，这种保存和调用代码的分离看起来特别有趣，但这是很有意义的。

save-continuation接受一个参数，该参数是恢复继续执行时要执行的代码的地址。该地址保存在部分延续中，恢复延续时，将跳转到（放入 PC寄存器）。

一个例子
现在我们有了一个更详细的想法，寄存器，评估堆栈和延续如何工作，下面是一个示例：

（+（-ab）（/ cd））
编译为中间代码，例如：

（推送继续“ resume23”）；保存续以致电+
  （按继续“ resume24”）；保存续以致电-
  （lookup-variable d）; 将d的值转换为值reg
  （推） ; 将d推入eval堆栈
  （lookup-variable c）; 将c的值转换为值reg
  （推） ; 在评估堆栈上推入c的值
  （lookup-variable /）; 抬头 /
  （应用）；呼叫/，在查询后值reg
  （推）                 
“ resume24” 
  （按继续“ resume25”）；将续保存为-，包括。（/ cd）的值
  （查找变量b）；得到b的值
  （推） 
  （查找变量a）；得到一个的价值
  （推）
  （lookup-variable-）; 获得-
  （应用）；致电-
  （推） ; 将返回的值推入已还原的e堆栈顶部     
“ resume25”
  （lookup-variable +）; 查找+
  （应用）；尾声+
“ resume23”  
注意事项：

在第一个之后apply，被调用的例程（或其直接或间接尾调用）将最终使过程返回，并弹出我们推送的最新延续，恢复当时在eval堆栈上的所有内容，并在label1恢复执行。[糟糕...解决此问题]
在第二次应用之后，被调用的例程最终将（直接或间接地）返回过程，这将弹出我们推送的第二个继续，将子表达式的已计算值恢复(/ c d)到eval堆栈。
我们(+ (- a b) (/ c d)) 为要在尾巴位置使用的表达式生成了代码。最终调用+之前，此代码不会保存延续。如果要在非尾巴位置使用该表达式，则必须生成稍有不同的代码，这将保存将在此表达式后恢复的继续。
生成唯一标签
[这去哪里？]

像一样compile-if，compile-combo根据需要生成标签，以便能够命名调用后应在其处恢复执行的代码-在其生成的代码中，它将标签放在要恢复的中间代码指令之前，并将相同的标签放置在对save-continuation应该在那里恢复。

很容易为程序中的每个可恢复点生成唯一的标签。我们只是保留到目前为止已使用过的标签的计数器，然后创建一个新标签，将代表该数字的数字附加到字符串"resume"，以便得到 "resume1"，"resume2"等等。

我们可以编写一个Scheme过程，generate-label该过程保留一个计数器，当给定一个字符串作为参数时，将返回一个新字符串，该字符串具有相同的字符以及代表计数器中数字的数字。这样，我们可以使用以"else"和开头的标签"end"来标记if表达式的分支目标 ，并使用"resume"以开头的标签代表继续保存的恢复点。这使得我们生成的中间代码相当容易理解，同时确保标签仍然是唯一的，并且在将中间代码翻译成机器语言时易于用作汇编标签。

有关环境表示的更多信息
为了使我们的系统获得合理的性能，我们将顶层环境与本地变量绑定环境区别对待。我们将使用一个涉及词法作用域的技巧来预先计算在查找局部变量绑定中完成的大部分工作，并使用另一种技巧来快速查找顶级变量。

如前所述，每个局部变量绑定轮廓（例如，由let或通过将args绑定到过程引入的绑定）在运行时表示为带有每个变量插槽的框架，并带有指向该变量的作用域链接。代表封闭轮廓的框架。

顶级环境可能很大，我们希望能够以特殊方式访问它。我们将其表示为将符号（变量名）映射到其顶级绑定的哈希表。绑定本身将被表示为对象，其主要功能是拥有一个保存变量当前值的字段。为简单起见，我们还将使它们具有自识别性：不仅将名称用作哈希表中的键，而且绑定对象将包含指向其名称和值的指针。

请记住，这种表示只是一种方便。顶级环境可以表示为任何类型的表（例如，关联列表），但是即使有成千上万个顶级变量，我们也希望它能够以相当快的速度进行访问。（我们将使用一种特殊的技巧在运行时使对顶级变量绑定的正常访问非常快，但我们也希望在编译时使它们具有相当快的访问速度，哈希表对此非常有用。）

假设我们在顶级评估以下表达式，以定义和初始化几个变量：

（定义队列“ fubar”）

（定义（双x）（+ xx））
除了已经存在的内容之外， 这还将通过添加quux和的绑定来修改顶层环境 double：

+ ------------------------------------------------- ------------------ +
   | |
   | |
  \ | / |
   + ------------------ + |
   | 顶级环境 | |
   + ================= + + ---------- + |
   | 缺点 * ---- + --------> | 装订 |
   + -------- + --------- + + ========== + |
   | | | 价值| * ---- + ------> <关闭cons> |
        。。+ ---------- + |
        。。名称| 缺点 |
        。。+ ---------- + |
                                                                       |
   | | | + ---------- + |
   + -------- + --------- + | 装订 |
   | quux | * ---- + --------> + ========== + |
   + -------- + --------- +值| * ---- + ------>“ fubar” |
   | | | + ---------- + |
        。。名称| quux | |
        。。+ ---------- + |
        。。|
                                                                       |
   | | | + ---------- + |
   + -------- + --------- + | 装订 + ---------- + |
   | 双| * ---- + --------> + ========== + | 封闭| |
   + -------- + --------- +值| * ---- + ---------> + ========== + |   
   | | | + ---------- + envt | * ---- + ----- +
        。。名称| 双| + ---------- +
        。。+ ---------- + proc | * ---- + ---> ...
        。。+ ---------- +
需要注意的几件事：

哈希表本身的表示可能并不是真正的简单的名称/值对数组，但是我不想用溢出桶和其他东西弄乱图片。
原则上，我们不需要指向单独的绑定对象的指针。我们可以使用名称-值对的value字段保存实际变量值，直接将绑定的值存储在表中。（毕竟，绑定实际上只是带有名称的位置，用于保存值。）对于我们的实现而言，拥有包含值的单独对象会很方便。
图片中符号名称的出现实际上将是指向符号对象的指针，而字符串"fubar"也实际上将是对象本身。像往常一样，我们有选择地缩写图形表示，以免造成混乱。
我们将顶级绑定对象称为对象，但它们不是Scheme对象-标准Scheme无法为您提供任何指向其中之一的指针并从语言内部进行操作的方法。从意义上说，这些“对象”是对象，它们是在堆上分配的，并由编译器和已编译的代码通过指针引用，但它们不是“第一类”。（Scheme语言的扩展版本可能使let您从语言内部了解它们，但这不是标准的。）
文字编译代码
当编译器为文字编译代码时，例如'fooor "foo"或22以下表达式），

（列出'foo“ foo” 22）
它注意到在运行时表达式将需要哪些文字，并确保这些文字将出现在过程模板中。它保留了要编译的过程所需的文字列表，并在为该过程编译代码后，使用该列表来构造与代码一起使用的模板。

如果foo是遇到的第一个文字，则可以将其首先放入列表中，并在模板中（在代码指针之后）分配第一个空闲插槽。 "foo"可能会分配第二个插槽，依此类推。在语言实现的术语中，模板充当文字框架，并保留指向过程代码的指针。

在模板上给字面量分配位置之后，编译器可以生成一个或两个指令，这些指令可以通过使用模板的地址，添加该插槽的偏移量并从结果地址加载来从模板中获取值。由于模板地址保证在TEMPLATE 寄存器中，因此这可能只是一条索引加载指令。在伪C中，它可能类似于：

值寄存器= *（模板寄存器+偏移量）
其中offset是由编译器计算的，因此可能是将值加载到值寄存器的load指令的立即操作数。

请注意，这里我们利用了编译器在我们的系统中运行并生成仅是我们系统中的数据的代码这一事实。这些代码将在同一堆中运行，因此编译器可以只计算值并将它们放入模板中，并且它们将一直存在直到执行该代码为止。（如果您想生成将被加载到另一个系统中并在其中执行的代码，则生活会稍微复杂一些。）

[现在我们应该解释，literal-stateto 的参数 compile是到目前为止在编译过程时看到的文字列表。的返回值compile是包含已更新的中间代码literal-state。]

顶级变量引用的编译代码
由于词汇作用域，编译器很容易分辨出对顶级变量绑定的引用与对局部变量的引用之间的区别。稍后我们将详细讨论，但是现在仅假设编译器在生成用于变量引用的代码时知道其区别。

当编译器为顶级变量生成代码时，通常可以在为其生成代码的环境中查找该变量的绑定-定义该变量的表达式已经执行，因此绑定已经存在。

因此，编译器可以在编译时进行实际查找，例如，哈希到实现顶级环境的哈希表中，并获得指向将在运行时引用的实际绑定对象的指针。

为了快速引用该对象，编译器可以简单地将此指针放在正在编译的过程的模板中，就好像它是文字值一样。

要弄清楚这里发生了什么：编译器无法查找变量的 值，因为直到运行时引用变量的那一刻，它才能知道。（在执行代码之前，其他一些代码段可能会运行并更改存储在绑定中的值。）但是绑定本身的标识是已知的，并且可以保存在文字框架中。

实际上，它比这稍微复杂一点。在定义变量本身之前，可以在过程定义中使用变量。（这称为“前向引用”。）要解决此问题，编译器将进行“欺骗”，然后在实际遇到变量的定义之前，在顶级环境中创建绑定对象及其条目。在语言级别，该变量尚未绑定或没有值，但是我们继续创建唯一的绑定对象，并将其用于编译其他表达式。为了进行错误检查，我们在绑定中添加了一个特殊值以指示该绑定还不是“真实的” —我们引用了一些我们认为“不是真实的值”的对象，以便我们可以检测到a的使用没有真正绑定的变量。

（在为最大安全性和早期错误检查而设计的系统中，我们可以确保对顶级变量的每个引用都将检查该值，并在发现错误时发出信号。如果我们不太关心早期错误检查，我们可以等到有人尝试使用这样的值时，例如，通过将其添加到某个值或采用该car值，然后我们依靠语言的常规类型检查来告诉我们在操作发生时出了点问题。）

现在考虑编译类似

（定义（make-foo-list）
   （列出'foo“ foo”））
编译器将积累该过程所需的顶级绑定和文字的列表，即字符串"foo"，symbol foo和symbol的 顶级绑定list。这些将被放置在该过程的模板中，在代码指针之后的第一个，第二个和第三个插槽中。为此过程生成的代码（假设从右到左求值）将类似于：

（字面量为1）；从模板插槽1获取字符串“ foo”
  （推） ; 将其推入评估堆栈
  （字面意思2）；从模板插槽2获取符号foo
  （推） ; 将其推入评估堆栈
  （字面量为3）；从模板插槽3获取列表的顶级绑定
  （tl-bdg-get）; 从绑定中提取价值
  （应用）；（尾部）通话清单
当然，请注意，我们现在使中间代码表示更加具体了-我们使用插槽号作为fetch-literal的参数，并且我们从值寄存器中的顶级绑定对象明确获取了顶级变量的值。 。为了在绑定中设置值，我们将使用不同的中间代码指令，t-l-bdg-set! （t-l-binding-set!希望值寄存器保存指向顶级绑定对象的指针；它将提取绑定的值，并将该值保留在值寄存器中。 ）

[现在我们可以解释更多有关立即数状态的信息-我们积累了在程序运行时必须可访问的立即值和顶级变量绑定的列表。]

到现在为止，您应该非常清楚如何将中间表示中的每个小操作转换为一些汇编语言说明。

[需要图片吗？]

使用词法作用域预先计算局部变量查找
我们实际上无法在编译时以顶级绑定的方式查找局部变量绑定-在编译创建和使用它们的表达式时，局部变量绑定尚不存在。（考虑到以下事实：每次您输入let或调用绑定参数的过程时，都会创建一个新的绑定环境框架。在这种环境中执行的代码每次运行时都会在环境寄存器中看到一个不同的绑定环境框架。）

我们可以做的是利用词法作用域来预先计算环境中变量的大部分搜索。

考虑执行此过程：

（lambda（xy）
     （让（（（<some-expression>
           （b <some-expression>））
        （列出清单））
当我们计算对的调用的参数时list，很明显，第一个和第二个变量（a和b）将位于第一个绑定环境框架的第一个和第二个插槽中，直接由ENVT寄存器指向。这是所创建的环境 let。第三个和第四个变量（x和y）将在下一个环境框架中，由第一个的作用域链接指向。

编译器可以在编译对其的引用时计算每个变量绑定的词法地址，即相对位置从环境寄存器开始的变量。词法地址包含两个部分：要找到正确的框架而跳过的环境框架的数量，以及该框架中绑定的偏移量。在上面的示例中，词法地址为：

a：0.1
   b：0.2
   x：1,1
   y：1,2
（我们使用以下约定：帧号从零开始，但是插槽号似乎从1开始，因为范围链接位于插槽0中。）

引用a生成的代码可以简单地是一个索引加载指令，使用环境寄存器加上一个偏移量来获取第一个变量绑定槽中的值。在伪C中，这类似于

value_register = *（envt_register +偏移量）
其中偏移量可能是4（字节）以索引超出范围链接插槽的位置。稍微抽象一点，它的词法地址是[什么？]

引用变量的代码y将涉及一个间接级别-首先必须从第一个环境帧中提取作用域链接指针，然后可将其用于索引加载以获取第二个值。第二帧：

value_register = *（envt_register）; 获取第二个envt帧的ptr
  value_register = *（envt_register +偏移量）
其中偏移量可能是8（字节），以通过作用域链接和的绑定建立索引x。

给定该方案，访问局部变量所花费的时间与介于正在编译的表达式和定义了引用变量的环境之间的环境帧的数量成比例。这通常相当快，有两个原因：

词汇嵌套的深度通常很小，它对应于程序中绑定表达式的嵌套，通常在1到3之间，很少会超过5左右。
在运行时执行的大多数引用都是对当前作用域中的变量的引用，或者是对它的下一级或二级引用。（考虑对内部循环中的变量的引用，这些循环构成了大多数程序中执行最频繁的代码。）
由于这些原因，大多数对局部变量的引用将采用一到五个指令。对于第一近似，可以将参考局部变量的时间视为一个小的常数。（稍微时髦的编译器可以通过使用更多的寄存器并在寄存器中保留许多值而不是从eval堆栈中推入和弹出这些值来减少这种情况，但这是比我们在此要解决的更高级的技术。）

词汇寻址和编译时环境
对于编译器而言，计算词汇地址非常容易。它需要做的就是维护一个称为编译时环境的数据结构，该数据结构记录运行时环境的结构。

每次编译器编译一个创建新绑定的表达式时，它都会扩展编译时环境以反映对环境结构的更改，并且当编译将在该环境中执行的表达式时，它将新的编译时环境交给递归调用compile将编译该表达式。

例如，当编译a时let，编译器将分派给 compile-let的类似物eval-let，以完成四件事：

编译用于初始值表达式的代码。该代码在之外的环境中执行let，因此 compile-let在进行递归调用compile以生成初始值代码时会给出使用环境。
生成代码以创建绑定环境并使用这些值初始化它。
用新框架扩展了编译时环境，这反映了事实let将在包含新绑定的新范围内执行。
调用compile-sequence编译的主体，并向其let传递新的编译时环境。
就像编译器的整体递归结构非常类似于解释器的递归结构一样，编译时环境的作用与解释器中环境的作用非常相似。

当解释器（编译器）评估（编译）在与其父表达式相同的环境中执行的子表达式时，它将递归调用与给定的环境进行递归。当解释器（编译器）在新环境中评估（编译）表达式时，它将递归调用交给新（编译时）环境。

编译过程中任何时候的编译时环境的结构都将反映将在其中执行代码的运行时环境的结构。但是，与解释器对环境的表示不同，编译时环境不包含实际的绑定-不能，也不需要。

实际上，我们将解释器的环境分为两个具有并行结构的部分。在解释器的环境是持有名称绑定对的框架链的情况下，编译器将其分成两个框架链：运行时环境（其框架具有实际的绑定）和编译时环境（其框架具有相应的名称）。

考虑表达

（让[[x 1]
      （y 2））
   （让[[foo 3]
         （第4条）
      （列出foo bar xy）））
在哪里 (list a b x y)编译或执行时，解释系统的环境如左下方所示，而编译系统的环境如右所示：

解释编译编译
                                （编译时间）（运行时间）
                    / \ / \ / \
                     | | |
 + --------------- + | + ---------- + | + ---------- + |
 | 环保 框架| | | ctefr。| | | 环保 fr。| |
 + =============== + / + ========== + / + ========== + /
 | + ---- +-'| + ---- +-'| + ---- +-'
 + ------- + ------- + + ---------- + + ---------- +
 | x | 1 | | x | | 1 |
 + ------- + ------- + + ---------- + + ---------- +
 | y | 2 | | y | | 2 |
 + ------- + ------- + + ---------- + + ---------- +
                  _ _ _
                 | \ | \ | \
                   \
                    \
 + --------------- + | + ---------- + | + ---------- + |
 | 环保 框架| | | ctefr。| | | 环保 fr。| |
 + =============== + / + ========== + / + ========== + /
 | + ---- +-'| + ---- +-'| + ---- +-'
 + ------- + ------- + + ---------- + + ---------- +
 | foo | 3 | | foo | | 3 |
 + --------------- + + ---------- + + ---------- +
 | 酒吧 4 | | 酒吧 | 4 |
 + ------- + ------- + + ---------- + + ---------- +
请注意，编译时环境与运行时环境之间存在多对一的关系：a let或lambda 表达式仅编译一次，并且创建了相应的环境框架并将其传递给编译子表达式的递归调用。但是，该代码可以执行多次，并且每次都会创建运行时环境框架，以便可以在该环境中执行用于子表达式的代码。

一个详细的例子
逐步介绍一下表达式的编译

（让[[x 1234）
      （y 3456））
   （让[[foo z]）
      （+（-富x）
         （+ bar y））））
如下。（我们假定此表达式出现在顶层。）

由于我们正在编译顶级表达式，因此我们在与顶级环境相对应的编译时环境中对其进行编译。顶级环境受到特殊对待，因为它们不是像本地绑定环境那样动态创建的。顶级编译时环境和相应的运行时环境之间存在一对一的关系。我们将顶层编译时环境表示为一种特殊的环境框架，它实际上只是持有指向顶层运行时环境的指针，以便可以查询顶层变量。

因此，我们从顶层环境开始，我们将其描述为[top-level]；我们将compile其与表达式一起进行编译。 compile是分析表达式的主要调度；在这种情况下，它会对其进行分析，然后（通过compile-list和compile-special-form）将其分派 到compile-let用于编译let表达式的专用过程。

compile-let编译的初始值表达式x 和y使用compile-multi，后者又调用compile 递归; 它们是在（顶层）环境中编译的，因为没有创建新的环境，所以仅将其传递。不过，在这种情况下，这并不重要，因为它们只是文字。（此时，值1234和3456被添加到文字列表中。）然后compile-let生成绑定x和的代码 y。

到目前为止，生成的代码如下：

（字面意思＃1）; 取1234
  （推） ; 将其推入评估堆栈
  （fetch-literal＃2）; 提取3456
  （推） ; 将其推入评估堆栈
  （绑定2）; 绑定2个变量（x和y），w / values组成评估堆栈
文字列表包含1234和3456。

compile-let然后调用compile-sequence编译的身体let，但首先它创建了一个新的编译时环境，代表一个事实，即体序列将在之后的新的运行环境执行x，并y已绑定。这个环境的结构是

[xy]-> [顶层]
（这是我们为编译时环境绘制箱形和箭头数据结构的新的简洁方法。我对绘制ascii艺术感到厌倦。）

compile-sequence调用compile递归计算表达式的序列; 在这种情况下，体内只有一个表情。

对compile调度的递归调用（再次通过 compile-list和compile-special-form进行compile-let，以编译内部let。

compile-let使用编译初始值表达式 compile-multi。 compile-multi调用compile 递归来编译列表中的一个表情，符号 z。（同样，只是传递了相同的环境，因为我们还没有创建新的环境。）

现在，递归调用compile调度到compile-symbol，z在编译时环境中查找符号的绑定信息。第一帧（包含x和y）中没有绑定，因此搜索转到第二帧（即顶级环境），并返回顶级绑定。这将导致调度到 compile-toplevel-var-ref，从而将的顶级绑定添加z到文字列表中，并生成代码以从模板中获取它并在运行时提取其值。

然后compile-let生成代码以将获取的值绑定为局部变量foo。

到目前为止生成的代码是：

（字面量为1）；取1234
  （推）
  （字面意思2）；提取3456
  （推）
  （绑定2）; 绑定2个值（x和y）
  （字面量为3）；获取（z的）顶级绑定
  （tl-bdg-get）; 从（z的）绑定中获取价值
  （推）
  （绑定1）; 绑定一个变量（foo）
和文字列表包含1234，3456以及结合z。现在compile-let创建一个新的编译时环境，以表示内部创建的环境let；它的结构是

[foo]-> [xy]-> [toplevel]
并将其传递compile-sequence给编译let的主体。 compile-sequence调用compile递归一次，移交它的新环境，编译一个身体表达， (+ (- foo x) (+ bar y))。

递归调用compile（到compile-list）的调度程序，通过 compile-combo递归调用 compile3次，以生成子表达式的代码 (+ bar y)，(- foo x)和+。由于没有新的绑定被创建，因此递归调用被赋予相同的环境。

递归调用调用(+ bar y)同样分派给 compile-combo和编译y，bar以及+。这些调用中的每一个都调度到，compile-symbol并且在编译时环境中查找变量。查找的y 返回的词法地址为1,2，因此生成的中间代码为

（本地变量ref 1 2）
bar的查找找不到任何本地绑定，并返回顶级绑定，因此该绑定被添加到文字列表中，中间代码为

（文字查询4）
  （tl-bdg-get）
同样，查找 +找不到任何本地绑定并返回顶级绑定，因此将绑定添加到文字列表中，并且中间代码为

（文字查询4）
  （tl-bdg-get）
现在compile-combo对它的调用已编译(+ bar y)可以将这三个片段串在一起以获得

（保存继续“ resume26”）；保存通话状态
  （local-var-ref 1 2）; 查找y
  （推）
  （文字查询4）；获取（栏的）顶级绑定
  （tl-bdg-get）; 从bdg获得价值（以bar为单位）
  （推）
  （文字查询5）；获取（+）的顶级绑定
  （tl-bdg-get）; 从绑定中获得价值（+）
  （应用）；致电+
“ resume26”                    
然后返回。注意，对于参数子表达式， compile-combo插入(push)es以将值保存在eval堆栈中。对于第一个（函数位置）子表达式，它将值保留在值寄存器中，这是期望的值（按apply）。

递归compile-combo编译的调用与的调用(- foo x) 非常相似(+ bar y)，主要区别是foo和x都被发现是局部变量并进行了适当的编译，结果是顺序

（保存继续“ resume27”）；保存呼叫状态-
  （local-var-ref 1 2）; 查找x
  （推）
  （local-var-ref 0 1）; 查找foo
  （推）
  （文字查询4）；获取（-的）顶级绑定
  （tl-bdg-get）; 从（的-）绑定中获得价值
  （应用）；致电-
“ resume27”
编译符号的递归调用直接+前进到compile-symbol，查找+并发现它是顶级变量；绑定已经在文字列表中，因此生成的代码为：

（文字查询5）；获取（+）的顶级绑定
  （tl-bdg-get）; 从绑定中获得价值（+）
并将其返回到的外部调用compile combo。然后，它可以将外部+表达式的代码串在一起，将a save-continuation放在前面，然后将a 放在后面apply 。此代码返回到的内部调用compile-let，该内部调用将 其附加到其代码中，并返回到的外部调用compile-let，该外部调用返回整个代码序列

（字面量为1）；取1234
  （推）
  （字面意思2）；提取3456
  （推）
  （绑定2）; 绑定2个值（x和y）
  （字面量为3）；获取（z的）顶级绑定
  （tl-bdg-get）; 从（z的）绑定中获取价值
  （推）
  （绑定1）; 绑定一个变量（foo）
  （保存继续“ resume26”）；保存通话状态
  （local-var-ref 1 2）; 查找y
  （推）
  （文字查询4）；获取（栏的）顶级绑定
  （tl-bdg-get）; 从bdg获得价值（以bar为单位）
  （推）
  （文字查询5）；获取（+）的顶级绑定
  （tl-bdg-get）; 从绑定中获得价值（+）
  （应用）；致电+
“ resume26”
  （保存继续“ resume27”）；保存呼叫状态-
  （local-var-ref 1 2）; 查找x
  （推）
  （local-var-ref 0 1）; 查找foo
  （推）
  （文字查询4）；获取（-的）顶级绑定
  （tl-bdg-get）; 从（的-）绑定中获得价值
  （应用）；致电-
“ resume27”
  （文字查询5）；获取（+）的顶级绑定
  （tl-bdg-get）; 从绑定中获得价值（+）
  （应用）；（尾巴）通话+
使用编译时连续性保留尾递归
在描述编译器的工作原理时，我们刚才谈到的一件非常重要的事情是何时确切地保存延续性，何时不保存延续性。如果被调用者必须返回并恢复调用者的执行，则在调用过程之前保存连续性很重要。这对于尾部调用不是必需的，并且实际上Scheme要求not为尾部调用保存连续性-如果我们在碰巧实现循环的尾部调用之前保存连续性，则可能会导致不必要的连续性无限堆积。

另一个重要的问题是何时应该执行退货。如果过程以尾部调用结束，则假定被叫方将返回。但是最终，某些事情实际上必须返回，并将控制权传回给它的调用者（或其调用者的调用者……）。当过程的尾部表达式不是另一个过程调用时（例如，返回变量或文字的值），就会发生这种情况。

我们应该何时保存延续？
一般规则是，如果过程调用是过程执行的最后一件事，则不应保存任何继续操作-我们可以跳入被调用方，并且由于未保存我们的状态，因此被调用方的返回将恢复我们的调用方。为了做到这一点，我们只需要跟踪正在“尾部位置”编译的表达式。

在程序中

（λ[x）
   （如果（foo x）
       （bar（加倍x））
       （巴兹））
的if表达是在尾部位置，因为如果的值将作为程序的值被返回。条件表达式(foo x)不在尾部，因为执行完条件后，控制必须返回到此过程，以便可以执行结果表达式(bar (quux x))或替代表达式(baz)。

请注意，结果表达式和替代表达式都位于尾部位置；无论执行哪个，这将是此过程的最后一件事，而计算出的值将是此过程的结果。

另一方面，如果将过程修改为始终返回#f，则这些表达式都不位于尾部位置。

（λ[x）
   （如果（foo x）
       （bar（加倍x））
       （巴兹））
   ＃F）                                                  
这是因为现在表达式#f位于尾部位置，而不是if表达式；无论if是否执行，控制都必须返回此过程，以便#f可以返回该值。

请注意，用于计算组合参数（过程调用）的值永远不会位于结尾位置，在计算它们之后，控制必须始终返回，以便可以应用该过程。当然，组合本身可能是一个尾部调用，在这种情况下，一旦计算了参数，就可能发生应用并且控制可能永远不会返回。

为了获得这种权利，所有必要的是，每次递归编译都应该知道被编译的代码是否将在尾部使用；为此，我们使用了编译时延续。（请不要害怕，它比编译时环境简单。实际上，它只是传递给递归调用的标志compile，有时会一直关闭。）请记住，尾巴位于尾巴位置，但非尾部子表达式不是。因此，在嵌套的情况下，if外部if位于尾部位置，只有结果的结果和替代项位于结果的尾部，例如，在

（lambda（）
   （如果（如果（a）
           （b）
           （C））
       （如果（d）
           （e）
           （F））
       （如果（g）
           （H）
           （一世）））
尾部调用是(e)，(f)，(h)，和(i)。第一个内部调用if必须返回，因为返回的值必须由外部使用if。在两个内IFS的条件表达式的调用也必须返回，因为值必须被用来告诉其中的替代和随后的使用。

对于每种基本类型的表达式，如果整体表达式为：我们可以判断哪些子表达式应视为尾部：

对于一个序列，只有最后一个子表达式可以是尾巴-其余的是非尾巴。
对于let，绑定的初始值表达式永远不会是尾巴，主体只是一个序列，其最后一个子表达式可以是尾巴。
如果是这样，结果和替代方案可以是尾巴，但条件永远不能。
对于程序，身体是始终处于尾部位置的序列。
当我们在尾部位置编译某些东西时，我们通过compile 一个标志，这样说。将检查该标志，并在适当时将其传递给子表达式以编译所讨论的子表达式的类型。

例如，如果compile-sequence递给一个标志说应编译为尾部位置的标志，则compile在对其最后一个子表达式进行递归调用时，它将通过尾部标志。但是，对于其他子表达式，它将始终传递非尾标，因为它们必须始终返回以执行序列中的下一个表达式。

同样，compile-if在调用compile其结果子表达式和替代子表达式时，将传递给它的任何标志，但在编译其条件表达式时则从不传递。

compile-combo 在对其子表达式调用compile时，它将始终传递一个非尾标志，但在评估所有子表达式之前，将检查给出的标志以判断是否应保存延续。

compile-lambda将始终在非尾部位置编译主体表达式，但最后一个总是在尾部位置编译。（简单来说，compile-lambda只需将整个身体移到compile-sequence带有尾标的位置即可。）

compile-let，始终在非尾部位置编译其初始值表达式，而其主体表达式则像一个序列。（为简单起见，它只是将整个身体交给compile-sequence，不管给出了什么标志。）

编制退货
如上所述，当除过程调用之外的其他表达式是过程的尾部时，它必须附带一个返回值。也就是说，过程的每个尾部都必须是apply（将调用将返回的内容，可能是由于尾部调用而间接返回）或a return。

编译器可以通过确保在生成表达式图的叶子的中间代码的任何地方（例如in compile-variable-ref和compile-literal）来处理此问题，我们将检查编译时延续标志以查看表达式是否出现在尾部位置。如果是这样，我们不仅执行简单的操作而不是将值保留在值寄存器中，还执行return 一系列指令-一系列指令，这些指令将从链的第一个部分继续中获取值，并将其恢复到寄存器和评估堆栈中，以恢复暂停的过程。我们有一个特殊的中间代码指令代表该序列，称为return。

请考虑以下过程：

（lambda（abc）
   （如果（如果一个
           （b）
           C）
       d
       （e）））
编译其主体时，我们将分派compile-sequence 并递归调用compile以编译if尾部位置。它以递归方式调用compile来编译如果在非尾位置，这又递归嵌套调用 compile来编译a，(b)并c在非尾位置。

请注意，这a是一个叶子表达式，由于它处于非尾部位置，因此可以将其值保留在值寄存器中。后续代码（对false和条件分支的测试是inner代码的一部分if）将在那里期望该值，所以很好。

该表达式(b)不在尾部位置，因为它从内部继承了非尾部位置if，因此必须在调用之前保存一个延续b。当b返回时，它的价值将在值寄存器和执行将继续在这是部分分支if。

类似地，表达式c处于非尾部位置（它也从内部if继承）；它可以将其值保留在值寄存器中，以便随后的代码可以找到它。（在这种情况下，它是内部的返回值if，并通过外部if的false和条件分支测试进行测试。）

表达d是不同的。它处于尾部位置，并且是一片叶子（不是呼出声）。它不能只是将它的值保留在寄存器中，因为这是过程的结尾。因此，必须return在其上标记一个序列。

该表达式(e)只是一个尾部调用，它可以调用 e而无需保存延续。无论e调用如何，它都可以做任何想做的事情，并且可能最终某些东西会在值寄存器中留下并弹出调用者的延续。

为上述过程生成的代码是：

（绑定3）; 绑定参数（a，b和c）
  （local-var-ref 0 1）; 得到一个的价值
  （推）
  （错误分支“ else32”）；比较，也许与其他内部
  （保存继续“ resume33”）
  （local-var-ref 0 2）; 得到b的值
  （应用）；叫b
“ resume33”
  （分支结束）
“ else32”
  （local-var-ref 0 3）; 得到c的值
“ end32”
  （假分支else1）; 比较并可能超越其他
  （字面量为1）；获取d的顶级绑定
  （tl-var-get）; 从绑定中获得d的值
  （返回）；并退还
  （分支end1）
“ else31”
  （字面意思2）；获取e的顶级绑定
  （tl-var-get）; 从绑定中获得e的值
  （应用）；然后叫它
“ end31”
（请注意，当我们为外部else生成代码时，我们生成了一个永远都不会被采用的分支。 compile-if 为代码的末尾生成了一个标签，因此在执行此操作之后，将在。之后的任何代码恢复控制if。在这种情况下if，结果将总是在遇到分支之前执行返回操作。稍微聪明一点的编译器可能会识别这种情况，并消除分支。）

编译顶级表达式
前面我们说过，编译器主要使用递归为嵌套表达式生成中间代码。但是，为了使此功能有用，必须将顶级表达式的中间代码在某些时候转换为实际的可执行代码并打包，以便可以对其进行调用。

假设我们通过read-eval-print循环与我们的系统交互，其中eval实际上是通过编译表达式并执行生成的编译代码来实现的。

为了使实现起来容易，如果编译器不必为其生成代码并能够实际调用的顶级表达式种类繁多，那就很好了。特别是，如果可以将不同类型的表达式转换为相同类型的表达式，将非常方便。执行此操作的简单方法是将所有不同类型的可执行表达式转换为生成过程的表达式，然后调用这些过程。

如果我们输入

（让[[x 2））
  （+ xx））
对于rep循环，rep循环可以简单地将其包装在一个过程表达式中进行编译，然后将其打包为可执行文件，然后对其进行调用。实际上，read-eval-print循环会将其转换为

（lambda（）
   （让[[x 2））
      （+ xx））
在编译之前，并调用生成的闭包以执行它。

同样，像

（设置！foo quux）
和

（如果bar baz）
可以包装成

（lambda（）（set！foo quux））
和

（lambda（）（如果bar baz））
现在，当我们开始编译时，我们只需要处理一种事情-整个过程，当我们返回生成的代码并将其打包以运行它时，我们将始终处理整个代码。程序。这使得创建实际的闭包调用变得容易。

我们开始编译的主要例程是compile-procedure，它使用一个表达式，一个编译时环境，一个编译时延续和一个文字列表作为参数。它为该过程返回中间代码和更新的文字列表。

我们采用中间代码，并将其交给 intermediate-code->executable-code生成可执行代码对象的过程。（这可以通过将中间代码指令序列转换为等效的汇编语言指令序列，然后通过汇编器运行。在进行汇编之前，它可以通过一个或多个优化阶段来运行中间代码。

我们获取生成的可执行代码和文字列表，并将它们make-template交给创建模板对象。

现在，我们可以将适当的运行时环境和模板make-closure移交给该过程，并取回该过程的可调用闭包。

lambda在程序内部编译表达式
编译lambda表达式时，我们必须生成在运行时创建闭包的代码。一个非常幼稚的方法是生成在运行时调用编译器以将lambda表达式编译为过程的代码，再加上一些代码在运行时环境中创建该对象的闭包。

幸运的是，这不是必需的，并且编译器可以在编译时完成所有实际的编译-因为lambda表达式的代码 每次执行时都是相同的，并且由于词法范围保证了它将始终在环境中执行具有相同的结构，只需要一个版本的代码，并且可以在该过程的所有闭包之间共享它。模板也可以共享。

因此，编译器会为该lambda 过程生成代码和模板。在运行时，lambda表达式的实际代码仅对堆进行关闭，并初始化其环境指针和模板指针。该代码将从环境寄存器中获取环境指针（并将其放置在新闭包的环境字段中）；模板指针将成为该lambda过程模板的上标器。

为了使这个小代码序列能够快速获取要关闭的过程的模板，编译器将指向该模板的指针存储在执行lambda表达式的过程的模板中。例如，如果lambda 在编译过程时遇到表达式foo，则编译器将编译该lambda过程并将其模板存储在的模板中foo。（编译时foo，它只是将指向新lambda过程模板的指针记录为另一个文字。然后，它将foo像其他文字一样以模板结尾。）

所以生成的代码

...
   （λ[x）
      （...））
   ...
好像

...
   （envt-reg-get）; 复制环境的原始文件。reg。到评估堆栈上
   （推）
   （字面量为15）；抓取lambda proc的模板指针
   （推）
   （关闭）；将使用这些值创建闭包的代码
   ...
真正的诀窍在于编译lambda过程并将其模板填充到包含lambda表达式的过程模板中。编译器只是调用自身来生成代码和模板，然后将模板保存在文字列表中，并生成上述代码以引用正确的文字。

编译顶级定义
上面我们说过，我们可以通过将所有顶级表达式都变成lambda表达式来处理顶级表达式，这将具有在调用这些表达式时对其求值的效果。

在处理顶级定义时，这有点棘手，因为顶级定义不能以明显的方式嵌套在lambda表达式中-它们只是成为局部定义。

因此，我们必须对其进行特殊对待。我们使用一个特殊的过程，environment-define!该过程 在顶层环境中运行，并允许我们创建顶层绑定。这不是标准的Scheme过程，它是编译器可以生成调用的特殊过程，但是普通的便携式Scheme代码不能直接使用。

因此，read-eval-print-loop将识别顶级定义并对其进行特殊处理。当遇到一个时，初始值表达式将被包装为a lambda并进行编译，结果将转换为代码，模板和闭包。（为闭包提供了运行时顶级环境指针。）

将调用该闭包以获取初始值表达式的结果，environment-define!并将其用于创建和初始化顶级变量。

（这乍看起来可能会引起范围界定问题：如果在编译初始值表达式之后才创建绑定，则编译器将看不到该绑定。但是请记住，如果我们编译使用未定义变量的表达式，我们假设它是一个顶级变量，并为其创建一个绑定对象，并将该对象标记为无效。如果绑定已通过这种方式由正向引用创建，environment-define!则将用真实值覆盖标记。）

当然，如果顶级定义使用过程定义语法，则lambda在进行上述按摩和编译之前，有必要将其整理为表达式。

与运行时系统接口
为了支持垃圾收集（Scheme要求），编译器和垃圾收集器之间必须达成某种协议，以便收集器可以找到正在运行的程序可能找到的指针，并确保程序可以找到所有对象。从他们的到达被保留。

一种常用的方法（用于RScheme和Scheme-48）是拥有一组固定的寄存器（可能还有一个eval堆栈），这些寄存器保存着收集器需要知道的所有根值，并确保每当有垃圾时发生收集时，所有指针都可以这样识别。必须知道任何给定的寄存器从不包含指针，始终包含指针或包含可识别以识别其是否为指针的自标识（标记）值。

例如，在我们已经详细描述的简单编译系统中，VALUE寄存器和EVAL堆栈仅包含正常的Scheme值：可以检查标记的值以查看它们是否为指针。另一方面，指针和模板和过程可能始终包含原始指针，因为它们只能指向一种事物，而标记会使某些事物变慢。

可能还有其他一些寄存器，它们总是包含非指针。

垃圾收集
安全点
许多系统（如RScheme和Scheme-48）确保仅当程序位于定义明确的“安全点”时，而不是代码中的任意点时，才发生垃圾收集。为了安全起见，已知所有指针值都是可识别的。在安全点之间，代码可以使用GC无法正确识别的值。（例如，通常只包含标记值的寄存器可能会短暂保存原始指针。）

在单线程系统中，这很容易。GC只是保留了一些空间，因此在安全点之间它永远不会耗尽内存。如果分配要求使用此储备金，则会设置一个标志，以便GC将在下一个安全点发生。

通常的技巧是确保每个过程调用和反向分支都是安全的。这样可以确保程序（或线程）定期到达安全点，

在多线程系统中，这有些棘手-您必须确保在安全点挂起线程，以便在挂起另一个线程时，如果另一个线程强制GC。

随时提供GC
某些系统不使用安全点，实际上会使代码中的每个点成为收集的安全点。它们确保无论发生GC的位置（或发生GC之前挂起线程的位置），都将有足够的信息在周围，以便收集器可以找到它需要查找的所有指针。

一些编译器通过限制使用寄存器和生成代码的方式来做到这一点。（例如，Orbit编译器仅使用某些寄存器来保存指针，而仅使用某些其他寄存器来保存非指针。此外，寄存器中的所有指针都必须直接指向对象的开头；数组索引不能转换为任意ponter算法通过优化的编译器。）

其他编译器允许更多使用奇数表示形式和更灵活地使用寄存器，以便可以在运行时确定值。例如，基于寄存器已在其中分配了变量的情况，可以假定一个寄存器将非指针保存在编译器标记的代码点之外。

中断
先进的编译器和运行时系统技术
内联小程序
到目前为止，我们所描述的系统生成的代码相当慢，而造成这种情况的主要原因是持续保存和过程调用的频率。即使是很小的，经常执行的过程（如eq？，car，cdr和+），也需要少数几个if指令来调用，而另外几个则要返回，如果是非尾部调用，则需要另外几个来保存延续。这比使用常规语言（如C或Pascal）进行类似操作的成本要慢得多。在这些语言中，这些简单的小“操作”没有调用一流过程的语义。

有时，需要舍弃诸如Scheme之类的语言的某些纯净和优雅，并牺牲灵活性降低以提高性能。一种实现方法是，将经常使用的小程序声明not为可重定义，并允许编译器以内联方式而不是作为过程调用来编译这些操作。在某些系统中，这仅适用于编译器可以理解的内置过程，但在其他系统中，编译器足够智能，可以直接内联用户定义的过程。

在某些Scheme系统中，您可以声明过程是不可插入的，或使用表明您保证不会重新定义对内联最有价值的通用小过程的编译器标志。这意味着您无法即时更改类似+的定义，但是却很少想要这样做。常见的折衷方法是避免在程序开发过程中内联除最常调用的过程之外的任何过程，并且一旦程序完成，请使用大量内联进行重新编译。这使您可以灵活地在调试过程中随时修改过程定义，同时可以很容易地以最快的速度清楚地知道在正常操作中不会重新定义哪些过程。

一些高科技的编译器在安全的情况下使用先进的技术进行很多内联，而又不会大大降低灵活性或要求用户提供很多声明。

Self编译器积极地内联代码，并自动重新编译因更改过程定义而无效的代码。（此编译器用于“自我”而不是“方案”语言，但是类似的技术也可以应用于“方案”。）

当前正在开发的某些编译器具有一种特殊模式，用于编译已完成的程序，而该模式不会与read-eval-print循环一起使用。这样的编译器利用了以下事实：如果它可以查看整个程序（而不是让用户以交互方式键入部分），那么它可以告诉您哪些变量可以在运行时进行修改。（只要在运行时不调用eval，编译器就可以告知该程序的所有代码都在编译时存在；可以在运行时创建新的闭包，但不能创建全新的过程。）如果确定程序中没有代码可以更改过程的定义，则可以将该过程的代码内联到其调用方中。

类型声明和类型分析
Scheme（或其他动态类型的语言）的幼稚实现的另一个关键性能问题是，相对于在常规静态类型的语言中执行基本操作而言，基本操作通常较慢。例如，Scheme过程+必须检查其参数的类型，并（取决于那些类型）执行几个可能的代码序列中的任何一个以加两个数字。通常，仅检查开销就比实际添加的开销大几倍。

降低成本的一种方法是通过扩展Scheme以允许用户声明某些变量的类型。编译器可能能够使用此信息来为已知类型的值编译操作的快速版本。（如果内联常用操作，则尤其如此-编译器可以选择内联相应的版本，而不是更通用的代码。）

减少类型检查成本的另一种方法是让系统自动推断某些表达式的类型。例如，考虑表达式(+ a 22)。由于22是文字，其类型在编译时已知。如果编译器可以内联该 +过程，则它至少可以忽略该参数的类型检查。

声明和推断的结合可以很好地工作。例如，如果用户已将变量a声明为type <integer>，则编译器可以判断出这(+ a 22)是一个表达式，其参数为整数（因此无需在运行时进行类型测试） ，其结果为整数，这可以消除需要通过使用该值的表达式进行类型检查。

更主动的方案可以减少动态类型检查的频率。例如，Self编译器积极地内联和转换代码，以便可以将多个动态类型检查折叠为一个。

使用更多的硬件寄存器
[等等等等]

例如，使用更多的寄存器，或者没有评估堆栈，或者不经常使用评估堆栈是一个好主意。我们的简单抽象机要求将参数传递给eval堆栈，这意味着每个参数至少要在内存中存储一次，并在使用参数时从内存中加载回来。大多数现代机器都有几个硬件寄存器可用于传递参数，还有更多硬件寄存器可用于保存计算的中间值。

如果我们还有更多的寄存器可用于传递参数，则可以将参数值保留在那些已知的寄存器中，而过程可能会期望它们在那里。在许多情况下，可以通过以下方式计算参数值：将结果保留在适当的参数传递寄存器中，而不必从其他地方复制该值。同样，在许多情况下，过程可以将其参数保留在传递参数的寄存器中，并在其中使用它们，而无需实际将其复制到堆上的绑定环境中。（即使只有几个寄存器可用于此目的，它也将解释所传递的绝大多数参数，因为大多数过程调用都针对采用一到三个参数的过程。）

同样，在许多情况下，可以将通过评估子表达式生成的临时值保留在寄存器中，然后由另一个表达式使用，而无需压入和弹出评估堆栈。

这可能是一个巨大的性能胜利-对寄存器中已有的参数和临时值进行操作要快得多，而不是一直将它们复制到内存中和从内存中复制出来。

使用更多的寄存器会使编译器和运行时系统更复杂。如果在保存连续性时变量在寄存器中，则必须将其值保存在连续性中并在过程返回时恢复。这就要求编译器跟踪哪些点在使用哪些寄存器，并生成适当的代码。它还使编译后的代码与垃圾回收器之间的接口变得复杂。垃圾收集器必须能够找到存储在寄存器中的所有指针值，以便它可以找到所有可访问的对象。因此，编译器必须记录足够的信息，以便可以在垃圾回收时找到所有指针值。（或者，编译器可能会记录信息的安全近似值，并要求收集器对哪些内容进行保守的猜测。

封闭分析
Scheme的简单实现的性能问题之一是，在一般情况下，必须在垃圾回收堆上分配变量绑定，并且过程调用必须通过指向闭包的指针进行。这通常比不必支持的常规编程语言的通常实现要慢得多lambda。在堆上分配闭包和环境主要是很慢的，因为创建和访问变量绑定比在堆栈或寄存器中分配变量要慢。

一个智能的Scheme编译器可以通过分析程序并注意到许多闭包以定型方式使用，从而摆脱了大部分此类开销，并且与天真的实现相比，对它们的调用可以更便宜地实现。类似地，对表达式的分析可能会发现大多数绑定环境不可能被闭包捕获，因此不需要在垃圾回收堆上分配。绑定可以与临时值一起连续保存，或者可以使用更常规的堆栈，或者（最好），可以将寄存器进行寄存器分配。

一个不需要完全通用的天真的实现的语言级闭包的简单示例是由lambda表达式创建的闭包，该表达式出现在组合的函数位置：

（（λ（x）
    （+ xx））  
 2））
（回想一下，这样的结构通常是由宏生成的，这些宏实现了类似let---的 绑定结构

（让（（x 2）
   （+ xx））
在这种情况下，我们可以从lambda表达式出现在函数位置这一事实中得知，闭包无法“转义”，并且对其进行了任何奇怪的处理。也就是说，没有将指向闭包的指针分配给变量绑定，没有传递给过程调用或没有插入到数据结构中。显然，此关闭可能发生的唯一事情是将调用它，然后指向它的指针将被“丢弃”，即未传递到其他任何地方。因此，关闭将在执行后立即变为垃圾。

因此，一个聪明的编译器将认识到闭包真正所做的就是绑定其变量并执行其主体。它会省略创建闭包的代码，而只是编译为等效的代码-在这种情况下，它将为let表达式生成明显的代码。

（有些编译器总是将let和letrec转换为 lambda组合，并依靠其优化器来识别不必要lambda的并删除它们。这似乎是倒过来的，但这很好，因为无论lambda组合是转换后的结果，相同的优化都有效一个let或macroexpanding用户定义的宏，或由用户或任何直接写入。更复杂的优化，更简单，用户可以编写宏和程序，并期望编译整理了这一切，并产生高效的代码）

闭包和环境分析的另一个简单案例是绑定范围，在其范围内没有创建任何闭包。假设我们的编译器内联调用car，eq?以及cdr和考虑表达式

（让[[x（car a））
   （如果（eq？（汽车x）目标）
       （汽车（cdr x））
       ＃F））
在这种情况下，的主体let可以编译成完全内联的代码，很明显，没有可能的执行路径可以创建捕获的闭包x。 x 因此，可以在整个生命周期内将其分配到寄存器中，从而使此代码更快。

[单独的部分？在这里找出结构...]

实际上，由于存在副作用和，这些分析中的一些比看起来复杂得多call/cc。

[尚未谈论call/cc！]

考虑一下表达式，我们不假设任何内联

（让[[x（car a）））
   （如果（eq？（汽车x）目标）
       （汽车（cdr x））
       （设置！x（foo））））
乍一看来，由于lambda表达式中没有，x因此可以在寄存器中分配它，并在每次调用之间以连续方式保存。（例如，在调用时car，我们可以只保存x延续中的值，并在car返回时恢复它的值，对吗？）不幸的是，如果我们没有任何car无法以怪异方式重新定义的保证，则可能该调用将是将（直接或间接）调用的过程call/cc，并捕获可用于多次返回该过程的连续性。在这种情况下，我们不能确定不会返回此代码并进行修改x。如果这样做了，那么每次返回到该环境时，我们应该看到的最新值x。如果of的值x在堆上的普通绑定环境中，则将发生这种情况，但如果它的值在连续保存的寄存器中，则不会发生这种情况。回想一下，当我们恢复连续性时，我们只是将值复制到寄存器中。如果我们多次恢复相同的延续，我们将继续复制相同值的x退出。

为了实现这一点，我们必须确保对进行任何分配x，然后所有引用x都要通过指向堆分配的绑定的指针。然后，当我们保存一个延续时，我们将该指针保存到的绑定x，而不是的绑定状态（值）x。每次设置或读取的值时x，我们都会通过此间接访问相同的绑定，并看到最新的值。

因此，高科技方案编译器会跟踪set!作用域中任何位置的变量，并确保在堆上分配这些变量的绑定。

在Scheme中，将迭代编码为递归是一种常见的习惯用法。用于不同循环结构的宏通常会letrec使用尾调用lambda表达式编译为。

尽管这是一个表达各种迭代模式的非常强大的框架，但是幼稚的实现速度很慢。在大多数情况下，以这种方式创建的循环实际上只是用作循环，因此希望减少闭包创建和调用的开销。例如，考虑一个名为letlike

（让循环（（x 0））
   <身体>
   （如果（<x 10）
       （循环（+ x 1））））
变成了

（让（（循环（lambda x）
               <身体>
               （如果（<x 10）
                   （循环（+ x 1））））））
   （循环0）
我们可以看一下该表达式，如果loop<body>表达式中没有对变量的引用 ，则可以告诉我们可以将其编译为循环。

此处的分析仅比允许我们优化由lambda 组合函数位置中的表达式产生的闭包的分析复杂。

编译时let，我们可以跟踪每个let变量，并查看它是否曾经用作除尾部调用过程名称之外的其他任何方法-如果从未分配loop的值，并且从未调用过它，那么我们知道循环的“调用”实际上并不需要完全是成熟的闭包调用。我们可以内联循环主体的代码，并在直接跳转到该代码时编译这些调用。

思维食品-调用是否为尾部调用是否重要，如果我们仅将它们视为对已知地址的过程调用，然后继续并使用正确的标签保存延续？

为循环注册分配的循环变量
Notice that register closure analysis is particularly important for loop control variables and variables for little let's inside loops. Because Scheme requires that a loop variable be bound again (to fresh memory) at each iteration of a loop, actually allocating them on the heap is expensive. If it can be determined that the variable is dead at the end of the loop, however, then the variable can be re-bound at each iteration by simply re-using the same register. (We're binding the name to a particular piece of memory--the register--over and over again, and it just happens that these conceptual rebindings incur no runtime cost.)

With good closure analysis, loop conversion, and register allocation, a Scheme compiler can compile "normal" loops into code that's just as efficient as any compiler's.

常规优化
除了上述优化之外，常规的编译器优化还可用于优化诸如Scheme之类的语言。

就像在FORTRAN或C编译器中一样，数据流分析和控制流分析可以使编译器简化中间代码并生成更好的机器代码。

堆栈缓存
内联和闭包分析可以大大减少Scheme实现中的堆分配量。在堆上分配所有绑定环境和连续性可能会使分配率比正常数据结构（如对和向量）的分配率高一个数量级。使用简单的编译器和垃圾收集器，这可以大大增加垃圾收集的成本。尽管连续性和环境的分配率很高，但在任何给定时间它们通常都相对较少生存-它们中的绝大多数被非常非常短暂地使用，然后变成垃圾。

内联过程调用可能会大大减少连续性的分配，并且闭包分析可以允许大多数绑定分配在寄存器中而不是堆中。

尽管如此，还是希望保留大多数连续性和环境，使其不成为普通的垃圾收集堆。

A stack cache是用于连续性和/或绑定环境的初始分配的内存区域（或不连续的内存块池），期望它们中的大多数会很快消失。堆栈缓存会缓存部分延续链；之所以称为堆栈缓存，是因为它的行为基本上类似于堆栈。堆栈缓存可用于连续性，而环境仍分配在堆上，或者可使用更复杂的设计来防止大多数环境也进入堆中。

在大多数情况下，堆栈高速缓存被视为堆栈，因为连续性像堆栈一样被推送和弹出。call/cc但是，当通过捕获连续性时，会先将连续性链移动到堆中，以便可以按通常的方式保留它。通常这是一个不错的折衷，因为call/cc 通常不会经常执行该操作，并且堆栈缓存在大多数情况下都可以像堆栈一样工作。通过弹出堆栈缓存，可以非常快地收回大部分连续内容，而一小部分则将移出普通堆。

缓存绑定环境有些棘手，但是基本原理是相同的。大多数环境都是在堆栈缓存中创建的，并且仅在必要时（即在堆上创建闭包时）才移至垃圾回收堆。在那一刻，环境被移动到堆中，一次移动一帧，直到到达堆中已经存在的一帧。（执行此操作的代码必须确保不会将环境两次复制到堆中，从而破坏了在其范围内创建的内部环境对外部环境的共享。）

鉴于编译器在关闭分析方面做得相当好，因此尚不清楚环境对堆栈缓存的期望程度。在环境中使用堆栈缓存会使闭包的创建速度变慢，如果通过闭包分析和寄存器分配已消除了大多数短暂的环境，则可能不值得。

关于堆栈缓存一般是否值得，还是世代垃圾收集器是否将有效地处理大量短期数据，也存在一些争议。

有趣的一点是，堆栈高速缓存确实是一种分代垃圾回收方案，它利用了特定种类数据的通常较短的生存期。（当环境和连续性移至正常堆时，可以将其视为将对象从一代移到下一代。由于连续链和绑定环境的构造型结构，这种特殊的一代比普通的一代方案便宜。 ）

与不使用堆栈缓存的分代GC相比，堆栈缓存由于很小而可以减少非常频繁使用的内存量。（堆栈高速缓存可能只有几千字节，但是世代GC的最年轻一代可能是数百千字节或兆字节。）对于某些高速缓存体系结构，频繁重复使用如此大的区域会导致严重的高速缓存未命中罚款。（对于其他一些体系结构，遗漏仍然会发生，但是成本却低得令人惊讶。我相信堆栈缓存仍然是一个好主意，因为它们从没有造成太大的伤害，有时可能会有所帮助。）

Scheme-48具有一个堆栈缓存，可缓存连续性和绑定环境。RScheme具有仅用于继续的堆栈缓存，并且依赖于编译器来编译掉绑定环境的大多数堆分配。（这目前可能还没有达到应有的效果—编译器需要更多的测试和改进，才能生成非常好的代码。）

一个简单的方案编译器