编写 Cyclone Scheme 编译器（2017）

# 编写 Cyclone Scheme 编译器 来源：https://justinethier.github.io/cyclone/docs/Writing-the-Cyclone-Scheme-Compiler-Revised-2017 ## 2017 年修订版 ###### 作者 Justin Ethier (https://github.com/justinethier) 本文从高层次介绍了 Cyclone 的各个组成部分以及它们的编写过程。这是对原始文章 (https://justinethier.github.io/cyclone/docs/Writing-the-Cyclone-Scheme-Compiler.html) 的修订版，原文写于一年多前的 2015 年 8 月，当时编译器已经可以自举，但新的垃圾收集器还未编写。自那时以来已经过去了不少时间，因此我认为有必要把这一年半中发生的一切记录下来。 在开始之前，我要向 Scheme 社区的所有贡献者表示**感谢**。Cyclone 基于社区对 Scheme 语言的最新修订版本，并且在可能的情况下复用或重新利用了现有代码，而不是从零开始。本文末尾列出了一些有用的在线资源。没有这些高质量的 Scheme 资源，Cyclone 项目是不可能完成的。 ## 目录 - 概述 (https://justinethier.github.io/cyclone/docs/Writing-the-Cyclone-Scheme-Compiler-Revised-2017#overview) - 源码到源码的变换 (https://justinethier.github.io/cyclone/docs/Writing-the-Cyclone-Scheme-Compiler-Revised-2017#source-to-source-transformations)- 只做许多小遍历 (https://justinethier.github.io/cyclone/docs/Writing-the-Cyclone-Scheme-Compiler-Revised-2017#just-make-many-small-passes) - 宏展开 (https://justinethier.github.io/cyclone/docs/Writing-the-Cyclone-Scheme-Compiler-Revised-2017#macro-expansion) - CPS 转换 (https://justinethier.github.io/cyclone/docs/Writing-the-Cyclone-Scheme-Compiler-Revised-2017#cps-conversion) - CPS 优化 (https://justinethier.github.io/cyclone/docs/Writing-the-Cyclone-Scheme-Compiler-Revised-2017#cps-optimizations) - 闭包转换 (https://justinethier.github.io/cyclone/docs/Writing-the-Cyclone-Scheme-Compiler-Revised-2017#closure-conversion) - C 代码生成 (https://justinethier.github.io/cyclone/docs/Writing-the-Cyclone-Scheme-Compiler-Revised-2017#c-code-generation) - 原生编译 (https://justinethier.github.io/cyclone/docs/Writing-the-Cyclone-Scheme-Compiler-Revised-2017#native-compilation) - 垃圾收集器 (https://justinethier.github.io/cyclone/docs/Writing-the-Cyclone-Scheme-Compiler-Revised-2017#garbage-collector)- 背景：MTA 上的 Cheney 算法 (https://justinethier.github.io/cyclone/docs/Writing-the-Cyclone-Scheme-Compiler-Revised-2017#background-cheney-on-the-mta) - Cyclone 的混合收集器 (https://justinethier.github.io/cyclone/docs/Writing-the-Cyclone-Scheme-Compiler-Revised-2017#cyclones-hybrid-collector) - 主垃圾收集算法 (https://justinethier.github.io/cyclone/docs/Writing-the-Cyclone-Scheme-Compiler-Revised-2017#major-garbage-collection-algorithm) - 新收集器的开发 (https://justinethier.github.io/cyclone/docs/Writing-the-Cyclone-Scheme-Compiler-Revised-2017#developing-the-new-collector) - 堆数据结构 (https://justinethier.github.io/cyclone/docs/Writing-the-Cyclone-Scheme-Compiler-Revised-2017#heap-data-structures) - C 运行时 (https://justinethier.github.io/cyclone/docs/Writing-the-Cyclone-Scheme-Compiler-Revised-2017#c-runtime)- 数据类型 (https://justinethier.github.io/cyclone/docs/Writing-the-Cyclone-Scheme-Compiler-Revised-2017#data-types) - 线程数据参数 (https://justinethier.github.io/cyclone/docs/Writing-the-Cyclone-Scheme-Compiler-Revised-2017#thread-data-parameter) - 调用历史 (https://justinethier.github.io/cyclone/docs/Writing-the-Cyclone-Scheme-Compiler-Revised-2017#call-history) - 异常处理 (https://justinethier.github.io/cyclone/docs/Writing-the-Cyclone-Scheme-Compiler-Revised-2017#exception-handling) - Scheme 库 (https://justinethier.github.io/cyclone/docs/Writing-the-Cyclone-Scheme-Compiler-Revised-2017#scheme-libraries)- 原生线程支持 (https://justinethier.github.io/cyclone/docs/Writing-the-Cyclone-Scheme-Compiler-Revised-2017#native-thread-support) - Reader（读取器）(https://justinethier.github.io/cyclone/docs/Writing-the-Cyclone-Scheme-Compiler-Revised-2017#reader) - 解释器 (https://justinethier.github.io/cyclone/docs/Writing-the-Cyclone-Scheme-Compiler-Revised-2017#interpreter) - 编译器内部机制 (https://justinethier.github.io/cyclone/docs/Writing-the-Cyclone-Scheme-Compiler-Revised-2017#compiler-internals) - Scheme 标准 (https://justinethier.github.io/cyclone/docs/Writing-the-Cyclone-Scheme-Compiler-Revised-2017#scheme-standards) - 基准测试 (https://justinethier.github.io/cyclone/docs/Writing-the-Cyclone-Scheme-Compiler-Revised-2017#benchmarks) - 未来计划 (https://justinethier.github.io/cyclone/docs/Writing-the-Cyclone-Scheme-Compiler-Revised-2017#future) - 结语 (https://justinethier.github.io/cyclone/docs/Writing-the-Cyclone-Scheme-Compiler-Revised-2017#conclusion) - 术语 (https://justinethier.github.io/cyclone/docs/Writing-the-Cyclone-Scheme-Compiler-Revised-2017#terms) - 参考资料 (https://justinethier.github.io/cyclone/docs/Writing-the-Cyclone-Scheme-Compiler-Revised-2017#references) ## 概述 Cyclone 的架构与其他现代编译器类似： Cyclone 编译器流程图 首先，命令行收到一个包含 Scheme 代码的输入文件，由 Cyclone 的解析器将其加载为抽象语法树（AST）。接下来，对 AST 执行一系列源码到源码的变换，以展开宏、进行优化，并使代码更易于编译成 C。这些中间表示（IR）可以以可读格式打印出来，以便于调试。最终的 AST 被输出为一个 `.c` 文件，然后调用 C 编译器以生成最终的可执行文件或目标文件。 程序与所需的 Scheme 库以及 Cyclone 运行时库链接在一起，以生成可执行文件： 编译后可执行文件中各文件链接关系图 ## 源码到源码的变换 ### 概述 Cyclone 的主要灵感来源于 Marc Feeley 的《90 分钟 Scheme 到 C 编译器》（http://churchturing.org/y/90-min-scc.pdf）（另见 video 1 (https://www.youtube.com/watch?v=HIr9eO1kB8g)、video 2 (https://www.youtube.com/watch?v=TxOM9Y5YrCs) 以及 code (https://github.com/justinethier/nugget/tree/master/90-min-scc)）。在 90 分钟内，Feeley 演示了如何通过源码到源码的变换将 Scheme 编译为 C 代码，其中包括闭包转换和续延传递风格（CPS）转换。 如演示中所述，编译到 C 的一些困难在于： > Scheme 有而 C 没有的东西——尾调用（也即尾递归优化）、一等续延、不定长作用域的闭包、自动内存管理（即垃圾收集 GC）。 > 这意味着——无法将（全部）Scheme 调用直接翻译成 C 调用；必须自行实现续延；必须自行实现闭包；必须组织好代码以支持 GC。其余的部分都很简单！ 为了克服这些困难，使用一系列源码到源码的变换，来移除 C 不提供的强大特性、添加 C 代码所需的构造，并为生成 C 做准备而对代码进行重组和重标记。最终的代码可以直接编译成 C。Cyclone 还包含许多其他中间变换，包括： - 宏展开 - 全局变量的处理 - Alpha 转换 (https://wiki.haskell.org/Alpha_conversion) - CPS 转换 (https://en.wikipedia.org/wiki/Continuation-passing_style) - 闭包转换 (http://matt.might.net/articles/closure-conversion/) 90 分钟编译器最终将代码编译为单个函数，并使用跳转来支持续延。这种方式对于生产级编译器来说限制太大，因此没有采用这一部分。 ### 只做许多小遍历 为了使 Cyclone 更易于维护，每种变换都各自单独作为一个遍历（pass）来实现。这使得 Cyclone 的代码尽可能简单，并将依赖关系降到最低，从而减少一个变换的修改破坏另一个变换代码的可能性。 在内部，Cyclone 将正在编译的代码表示为由普通 Scheme 对象构成的 AST。由于 Scheme 使用 S 表达式 (https://en.wikipedia.org/wiki/S-expression) 同时表示代码和数据，我们的编译器（通常）不需要像许多其他语言那样使用自定义抽象数据类型来存储代码。 大多数变换遵循类似的模式：递归地检查表达式。下面是一个简短的例子，展示了代码的结构： `` (define (search exp) (cond ((const? exp) '()) ((prim? exp) '()) ((quote? exp) '()) ((ref? exp) (if bound-only? '() (list exp))) ((lambda? exp) (difference (reduce union (map search (lambda->exp exp)) '()) (lambda-formals->list exp))) ((if-syntax? exp) (union (search (if->condition exp)) (union (search (if->then exp)) (search (if->else exp))))) ((define? exp) (union (list (define->var exp)) (search (define->exp exp)))) ((define-c? exp) (list (define->var exp))) ((set!? exp) (union (list (set!->var exp)) (search (set!->exp exp)))) ((app? exp) (reduce union (map search exp) '())) (else (error "unknown expression: " exp)))) `` Nanopass 框架 (https://github.com/nanopass/nanopass-framework-scheme) 正是为了让编写「对代码执行许多小遍历」的编译器变得更加容易而创建的。不幸的是，Nanopass 本身是用 R6RS 编写的，因此无法用于这个项目。 ### 宏展开 宏展开是最早的变换之一。编译器所认识的所有宏都会作为函数加载到宏环境中，然后对代码进行一次遍历。当编译器发现一个宏时，就调用该宏来展开代码。随后编译器会再次检查展开后的代码，以防宏展开后又产生另一个宏。 在最底层，Cyclone 的显式重命名（ER）宏 (http://wiki.call-cc.org/explicit-renaming-macros) 提供了一个简单、底层的宏系统，除了 `eval` 之外几乎不需要什么别的东西。来自 Chibi Scheme (https://github.com/ashinn/chibi-scheme) 的许多 ER 宏被用来实现 Cyclone 的内置宏。 Cyclone 还支持 Scheme 报告中高层的 `syntax-rules` 系统。`syntax-rules` 是作为一个巨大的 ER 宏实现的，该宏从 Chibi Scheme 移植而来 (https://github.com/justinethier/cyclone/blob/v0.3.3/scheme/base.sld#L1242)。 作为一个简单的例子，下面的 `let` 宏： `` (let ((square (lambda (x) (* x x)))) (write (+ (square 10) 1))) `` 会被展开为： `` (((lambda (square) (write (+ (square 10) 1))) (lambda (x) (* x x)))) `` ### CPS 转换 转换为续延传递风格（CPS）会使续延在编译后的代码中显式出现。这是让 Scheme 代码简化到足以用 C 来表示的关键一步。正如我们后面会看到的，运行时的垃圾收集器也要求代码处于 CPS 形式。 基本思路是：每个表达式都会产生一个值，该值由表达式的续延所消费。续延将使用函数来表示。所有代码都必须被改写为接受一个新的续延参数 `k`，该参数会以表达式的结果被调用。例如，考虑之前的 `let` 例子： `` (((lambda (square) (write (+ (square 10) 1))) (lambda (x) (* x x)))) `` 其 CPS 形式的代码变为： `` ((lambda (r) ((lambda (square) (square (lambda (r) ((lambda (r) (write r)) (+ r 1))) 10)) r)) (lambda (k x) (k (* x x)))) `` ### CPS 优化 CPS 转换生成的代码太多，对于像原始函数（primitive）这样可以直接返回结果、而无需调用续延的函数来说效率低下。因此我们需要对它进行优化，使编译器实用可行。例如，上面的 CPS 代码可以简化为： `` ((lambda (k x) (k (* x x))) (lambda (r) (write (+ r 1))) 10) ``` 最有效的优化之一是对原始函数的内联。也就是说，有些运行时函数可以直接调用，因此不需要外层的 `lambda` 来求值它们。这可以大大减少生成的代码量。 还会使用一个收缩（contraction）阶段来消除其他不必要的 `lambda`。还有一些其他的杂项优化，比如常量折叠，即当参数是常量时在编译期求值某些原始函数。 为了更高效地识别优化机会，Cyclone 首先会对代码做一遍处理，构建起一个基于哈希表的分析数据库（DB），记录各种属性。这与 CHICKEN 采用的策略相同，只是每个编译器记录的属性不同。该 DB 包含一张记录表，为每个变量（以符号为索引）和每个函数（以唯一 ID 为索引）都有一条条目。 为了支持分析 DB，此阶段使用自定义的 AST 来表示函数，这样每个函数都可以被标记上一个唯一的标识号。优化完成后，这些 lambda 会被转换回普通的 S 表达式。 ### 闭包转换 传递给嵌套函数的自由变量必须被捕获到闭包中，以便在运行时引用。闭包转换会根据需要修改 lambda 定义，以创建新的闭包。它还会把对自由变量的引用替换为从当前闭包中查找。 Cyclone 使用扁平闭包（flat closure）：包含单个函数引用和一个自由变量向量的对象。这是一种比环境（environment）更高效的表示方式，因为读取任何自由变量都只需要一次向量查找。 可变变量（被 `set!` 修改的变量）不能直接由扁平闭包支持，因此在闭包转换之前的单独编译遍历中，必须将它们添加到一个 pair（称为“单元”，cell）中。 Cyclone 的闭包转换基于 Marc Feeley 的 90 分钟 Scheme->C 编译器以及 Matt Might 的 Scheme->C 编译器中的代码。 ### C 代码生成 编译器的代码生成阶段会对变换后的 Scheme 代码做一次遍历，并将 C 代码输出到当前输出端口（通常是一个 `.c` 文件）。 在此阶段，C 代码有时会被暂存以备后用，而不是直接输出。例如，在编译向量字面量或一系列函数参数时，生成的代码会以字符串列表的形式返回，将变量声明与生成函数“主体”中的 C 代码区分开来。 C 代码的生成方式经过精心设计，使得一个 Scheme 库（`.sld` 文件）会被编译成一个 C 模块。库中导出的函数和变量在生成的代码中会成为 C 全局变量。 ### 原生编译 此时会调用 C 编译器，为 Scheme 模块生成机器码，并在编译 Scheme 程序时创建可执行文件。 ## 垃圾收集器 ### 背景：MTA 上的 Cheney 算法 我们采用了基于 Henry Baker 论文《CONS 不应对其参数调用 CONS，第二部分：MTA 上的 Cheney 算法》（https://github.com/justinethier/cyclone/raw/master/docs/research-papers/CheneyMTA.pdf）的运行时，因为它允许生成快速的代码，并且满足 Scheme 运行时的所有基本要求：尾调用、垃圾收集和续延。 Baker 解释了它的工作原理： > 我们建议通过将 Scheme 转换为续延传递风格（CPS）来编译它，然后将所得的 lambda 表达式编译为单独的 C 函数。参数作为普通的 C 参数传递，函数调用也遵循普通的……