一个简单的模式编译器(1997)

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

我们用来开始编译的主要例程是Compile-Procedure，它以表达式、编译时环境、编译时连续和文字列表作为参数。它返回过程的中间代码和更新后的文字列表。

我们获取中间代码，并将其传递给生成可执行代码对象的过程中间代码&>；可执行代码。(这可以通过将中间代码指令序列翻译成等价的汇编语言指令序列，并通过汇编器来运行。在进行程序集之前，它可以通过一个或多个优化阶段运行中间代码。

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

现在，我们可以将适当的运行时环境和模板交给Make-Closure，并为该过程返回一个可调用的闭包。

当我们编译lambda表达式时，我们必须生成在运行时创建闭包的代码。一种非常天真的方式是生成代码，该代码将在运行时调用编译器将lambda表达式编译成过程，外加一个小代码在运行时环境中创建该对象的闭包。

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

因此，编译器为lambda过程生成代码和模板；在运行时，lambda表达式的实际代码只是在堆上做一个闭包，并初始化它的环境指针和模板指针。这段代码将从环境寄存器获取环境指针(并将其放入新闭包的环境字段中)；模板指针将是指向lambda过程的模板的指针。

为了允许这个小代码序列快速获取要关闭的过程的模板，编译器在执行lambda表达式的过程的模板中存储了一个指向该模板的指针。例如，如果在编译过程foo时遇到lambdaexpression，编译器将编译lambda过程并将其模板存储在foo的模板中。(在编译foo时，它只是将指向新lambda过程的指针记录为另一个文字。然后，它将像其他文字一样出现在foo'；的模板中。)。

因此，为生成的代码看起来像...。(ENVT-REG-GET)；复制ENVT的原语。雷吉。到取值堆栈(推送)(FETCH-TEXAL 15)；抓取lambda过程的模板指针(推送)(Make-Close)；将使用这些值创建闭包的代码...。

真正的诀窍在于编译lambda过程，并将其模板填充到包含lambda表达式的过程的模板中。编译器只是调用自己来生成代码和模板，然后将模板保存在文字库中，生成类似上面的代码来引用正确的文字。

我们在上面已经说过，我们可以通过将顶级表达式全部转换为lambda表达式来处理它们，这将在调用时产生计算这些表达式的效果。

在处理顶级定义时，这有点棘手，因为顶级定义不能以显而易见的方式嵌套在lambdaexpression中--它们只会变成局部定义。

因此，我们必须特别对待他们。我们使用一个特殊的过程ENVERENCE-DEFINE！，它在顶级环境上运行，并允许我们创建顶级绑定。这不是标准的Scheme过程--它是编译器可以调用的特殊过程，但普通的可移植Scheme代码不能直接使用。

因此，read-eval-print-循环将识别顶级定义并对其进行特殊处理。当它遇到一个时，初始值表达式将被包装为lambda并进行编译，并将结果转换为代码、模板和闭包。(闭包被赋予运行时顶层环境指针。)。

将调用闭包以获得初始值表达式和环境定义的结果！将用于创建和初始化TopLevel变量。

(这一开始可能会导致作用域问题：如果绑定直到初始值表达式编译后才创建，编译器将看不到绑定。但是回想一下，如果我们编译一个使用未定义变量的表达式，我们假设它是一个TopLevel变量，并为其创建一个绑定对象，然后将该对象标记为无效。如果绑定已经通过正向引用以这种方式创建，则环境定义！将只用真实值覆盖标记。)。

当然，如果顶层定义使用过程定义语法，则在执行上述消息传递和编译之前，有必要将其传递到lambda表达式中。

为了支持垃圾收集(就像Scheme所要求的那样)，编译器和垃圾收集器之间必须达成某种协议，以便收集器可以找到运行程序可能找到的指针，并确保程序可以从它们到达的所有对象都得到保留。

实现这一点的一种常见方法(在RScheme和Scheme-48中使用)是拥有一组固定的寄存器(可能还有一个eval堆栈)，这些寄存器保存收集器需要知道的所有根值，并保证无论何时发生垃圾收集，所有指针都是可以识别的。任何给定的寄存器都必须知道从不包含指针，始终包含指针，或包含可解码的自标识(标记)值，以查看它们是否重新指向。(#**$$}{##**$$}。

例如，在我们已经详细描述过的简单编译系统中，值寄存器和EVAL堆栈只包含正常的Schem值：可以检查它们是否重新指向的标记值。另一方面，模板和过程中的指针可能总是包含原始指针，因为它们只能指向一种东西，而标签会减慢一些东西的速度。

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

这在单线程系统中很简单；GC只保留一些空间，这样它就不会在安全点之间耗尽内存。如果分配需要使用此储备，则会设置一个标志，以便在下一个安全点进行GC。

通常的技巧是确保每个过程调用和向后分支都是安全点。这确保程序(或线程)周期性地到达安全点，

这在多线程系统中有点棘手--您必须确保在安全点挂起线程，以便在另一个线程强制GC而另一个线程挂起的情况下挂起线程。

有些系统不使用安全点，实际上使代码中的每个点都成为收集的安全点。它们确保无论GC发生在哪里(或者线程在GC发生之前挂起在哪里)，都会有足够的信息，以便收集器可以找到它需要找到的所有指针。

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

其他编译器允许更多地使用奇数表示法和更灵活地使用寄存器，因此可以在运行时计算出值。例如，根据寄存器在那里分配了一个变量，可以假定寄存器保存非指针，但编译器标记的代码中的位置除外。

到目前为止，我们描述的系统生成的代码相当慢，一个主要的罪魁祸首是持续保存和过程调用的频率。即使是非常小的、经常执行的过程，如eq？、car、cdr和+，也需要几个if指令来调用，再需要几个指令才能返回，如果是非尾部调用，还需要另外几个指令来保存延续。这比传统语言(如C或Pascal；)中类似操作的成本要低得多。在这些语言中，这些简单的小操作没有调用一流过程的特性。

有时需要牺牲一些像Scheme这样的语言的纯洁性和优雅，并牺牲降低的灵活性来换取更好的性能。要做到这一点，一种方法是声明常用的小过程不可重定义，并允许编译器内联编译这些操作，而不是作为过程调用。在一些系统中，这只适用于编译器理解的内置过程，但在另一些系统中，编译器足够智能，可以根据需要内联用户定义的过程。

在某些Scheme系统中，您可以将过程声明为可内联，或者使用编译器标志，表示您承诺不会重新定义最有价值内联的常见小过程。这意味着你不能马上改变像+这样的东西的定义，但是你很少想要这样做。一种常见的权衡是在程序开发期间避免内联除最频繁调用的过程之外的任何过程，一旦程序完成，就用大量内联重新编译。这使您可以灵活地在调试过程中动态修改过程定义，同时在清楚哪些过程在正常操作中不会被定义后，即可获得最大速度。

一些高科技编译器在安全的情况下使用先进的技术来做大量的内联，而不会大大降低灵活性，也不需要用户提供大量的声明。

自编译器积极地内联代码，并自动重新编译因更改过程定义而失效的代码。(这个编译器是针对语言本身的，而不是Scheme，但是类似的技术也可以应用于Scheme。)。

目前正在开发的一些编译器有一种特殊的模式来编译已完成的程序，该模式不会与读取-求值-打印循环一起使用。这样的编译器利用了这样一个事实，即如果它可以查看整个程序(而不是让用户交互地键入部分)，它就可以告诉您哪些变量可能在运行时被修改。(只要在运行时没有调用eval，编译器就可以知道该程序的所有代码在编译时都存在；可以在运行时创建新的闭包，但不能完全创建新的过程。)。在全局确定程序中没有可以更改过程定义的代码之后，可以自由地将该过程的代码内联到其调用方。

Scheme(或其他动态类型语言)的朴素实现的另一个关键性能问题是，在传统的静态类型语言中，基本操作通常比它们的执行速度慢。例如，Scheme过程+必须检查其参数的类型，并(取决于这些类型)执行几个可能的代码序列中的任何一个以将两个数字相加。通常，单是格子头一项就比实际加法的成本高出好几倍。

降低此成本的一种方法是扩展Scheme以允许用户声明某些变量的类型。编译器可能能够使用该信息来编译已知类型的值的运算的快速版本。(如果公共操作是内联的，这一点尤其正确--编译器可以选择内联适当的版本，而不是更通用的代码。)。

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

声明和推理的组合可以很好地工作。例如，如果用户已将变量a声明为<；整数>；类型，则编译器可以判断(+a22)是一个表达式，它的参数是整数(因此那里不需要运行时类型测试)，并且其结果是整数，这可以消除使用该值的表达式进行类型检查的需要。

有可能采用更激进的方案来降低动态类型检查的频率。例如，自编译器积极地内联和转换代码，以便将多个动态类型检查折叠为单个动态类型检查。

例如，它很可能是一个好主意，使用更多的寄存器，或者没有一个求值堆栈，或者不经常使用它。OurSimple抽象机要求参数在取值堆栈上传递，这意味着每个参数至少存储到内存中一次，并在使用参数时从内存加载回。大多数现代机器都有几个硬件寄存器，可以用来传递参数，还有更多的硬件寄存器可以用来保存中间值的计算。

如果我们有更多的寄存器可用于参数传递，我们只需将参数值留在这些已知的寄存器中，程序就可以预期它们在那里。在许多情况下，可以通过将结果保留在适当的参数传递寄存器中的方式来计算参数值，而不必将其从其他地方复制到那里。类似地，在许多情况下，过程可以将它们的参数留在参数传递寄存器中并在那里使用它们，而不需要将它们实际复制到堆上的绑定环境中。(即使只有几个寄存器可以专门用于此，它也将占所传递参数的绝大部分，因为大多数过程调用都是针对接受1到3个参数的过程。)。

类似地，在许多情况下，通过计算子表达式生成的临时值可以保留在寄存器中，然后由另一个表达式使用，而无需推送和弹出eval堆栈。

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

使用更多寄存器可能会使编译器和运行时系统更加复杂。如果保存延续时变量在寄存器中，则它们的值必须保存在延续中并在过程返回时恢复。这要求编译器跟踪哪些寄存器在哪些点上正在使用，并生成适当的代码。它还使编译代码和垃圾收集器之间的接口变得复杂；垃圾收集器必须能够找到存储在寄存器中的所有指针值，这样才能找到所有可访问的对象。因此，编译器必须记录足够的信息，以便在垃圾收集时可以找到所有指针值。(或者，编译器可以记录信息的安全近似值，并要求收集器保守地了解什么是什么。)。

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

聪明的Scheme编译器可以通过分析程序并注意到许多闭包是以刻板的方式使用的，并且对它们的调用可以比幼稚的实现更便宜地实现，从而消除了大部分开销。类似地，对表达式的分析可能会显示大多数绑定环境可能会被闭包捕获，因此不需要在垃圾收集堆上进行分配。绑定可以与临时值一起保存在连续中，或者可以使用更传统的堆栈，或者(最好的)，绑定可以是寄存器分配的。

语言级闭包的一个不需要完全通用的朴素实现的简单示例是由出现在组合的函数位置的lambda表达式创建的闭包：(回想一下，这样的构造通常是由实现绑定构造的宏生成的，比如let-在本例中，我们可以从lambda表达式出现在函数位置的事实看出，闭包可以转义，并可以对其进行任何奇怪的处理。也就是说，不会将指向闭包的指针赋给变量绑定，不会传递给过程调用，也不会插入到数据结构中。很明显，这个闭包唯一可能发生的事情是它将被调用，然后指向它的指针将被丢弃，即不会被传递到其他任何地方。因此，关闭将在其执行后立即变得很大。

因此，智能编译器将认识到，实际上所做的一切就是绑定它的变量并执行它的主体；它将省略创建闭包的代码，而只编译成等价的代码--在本例中，它将为let表达式生成明显的代码。