← 返回首页

面向编译器教学的 Nanopass 框架

2026/5/4
编译器SchemeNanopass函数式编程教学

面向编译器教学的 Nanopass 框架

原文: A Nanopass Framework for Compiler Education — Dipanwita Sarkar (Microsoft Corporation), Oscar Waddell (Abstrax, Inc.), R. Kent Dybvig (Indiana University)

本文为翻译稿，仅供学习交流。

摘要

将编译器构造为少量的大型（monolithic）遍，既难以理解，也难以维护。陡峭的学习曲线令人望而生畏，甚至经验丰富的开发者也会发现，修改现有的遍很困难，而且经常引入微妙且顽固的 bug。当开发者是编译器课程的学生时，这些问题尤其令人沮丧。一个有吸引力的替代方案是将编译器构造为多个细粒度遍的集合，每个遍执行一个单一任务。这种结构使编译器的实现与其逻辑组织保持一致，简化了开发、测试和调试。本文描述了构建此类编译器的方法论和工具——一个完整的框架。

1 引言

生产级编译器通常展现出一种单体式（monolithic）结构，其中每个遍执行多项分析、转换和优化。一个有吸引力的替代方案，特别是在教学环境中，是将编译器构造为多个小遍的集合，每个遍执行编译过程中的一小部分。这种”微遍（micropass）“结构使编译器的实现与其逻辑组织保持一致，产生更可读、更可维护的编译器。出现的 bug 更容易隔离到特定任务，添加新功能也更容易，因为新代码不需要嫁接到现有的遍上，也不必挤在单体结构中本应合并的两个逻辑遍之间。

微遍编译器的每个遍执行一个特定的任务来简化、验证、转换、分析或改进代码。

  • 简化遍通过将其输入翻译成更简单的中间语言来降低后续遍的复杂度，例如，将模式匹配构造替换为更原始的代码。
  • 验证遍检查那些不易在文法中表达的编译器不变量，例如，所有绑定变量都是唯一的。
  • 转换遍将底层目标语言不直接支持的抽象显式化，例如，将高阶过程转换为显式分配的闭包。
  • 分析遍从输入程序中收集信息，并将该信息以注解的形式记录到输出程序中，例如，为每个 lambda 表达式标注其自由变量集合。
  • 改进遍试图减少程序的运行时间或资源消耗。

虽然简化和转换遍以某种方式改变了中间语言，但每个验证或改进遍产生与其输入程序相同中间语言的程序，因此我们可以简单地通过不运行相应的遍来选择性地启用或禁用个别检查或优化。验证遍仅在编译器开发期间启用，它们可以帮助识别上游遍中的 bug。禁用优化的能力支持那些用代码质量换取编译速度的编译器开关，在回归测试中也很有用，因为优化可能掩盖其他遍中很少执行部分的 bug。

几年前，我们在高年级和研究生级别的编译器课程中切换到了微遍结构。学生在编写编译器时得到了多种工具的支持：一个带有方便的递归和映射表示法的模式匹配器、用于将每个遍的输出展开为可执行代码的宏、编译器的参考实现、一组（可终止的）测试程序，以及一个驱动程序。驱动程序在测试套件中的每个程序上运行编译器，并评估每个遍的输出以验证它与参考实现产生相同的结果。中间语言程序全部表示为 S-表达式，这简化了编译器遍和驱动程序。

切换到微遍方法论及其支持工具使得我们的学生能够编写更具雄心的编译器。在一个学期的编译器课程中，每个学生构建了一个 50 遍的编译器，从 S-表达式级别到 Sparc 汇编代码，针对图 1 所示的 Scheme 子集。编译器包括几种优化以及一个图着色寄存器分配器。研究生课程的学生实现了几种额外的优化。最近一个学期编译器中包含的遍列在表 1 中。

expr → constant | (quote datum) | var
     | (set! var expr) | (if expr expr) | (if expr expr expr)
     | (begin expr expr*) | (lambda (var*) expr expr*)
     | (let ((var expr)*) expr expr*)
     | (letrec ((var expr)*) expr expr*)
     | (primitive expr*) | (expr expr*)

图 1. 一个小巧但具有代表性的 Scheme 子集

表 1. 编译器各遍一览（按执行顺序和周次分组）

周次主题遍
第 1 周：简化verify-scheme¹, rename-var, remove-implicit-begin¹, remove-unquoted-constant, remove-one-armed-if, verify-a1-output¹
第 2 周：赋值转换remove-not, mark-assigned, optimize-letrec², remove-impure-letrec, convert-assigned, verify-a2-output¹
第 3 周：闭包转换optimize-direct-call, remove-anon-lambda, sanitize-binding-forms, uncover-free, convert-closure, optimize-known-call³, uncover-well-known², optimize-free², optimize-self-reference², analyze-closure-size¹, lift-letrec, verify-a3-output¹
第 4 周：规范化introduce-closure-prims, remove-complex-constant, normalize-context, verify-a4-output¹
第 5 周：编码/分配specify-immediate-repn, specify-nonimmediate-repn
第 6 周：UIL 编译器开始verify-uil
第 7 周：标签和临时变量remove-complex-opera*, lift-letrec-body, introduce-return-point, verify-a7-output¹
第 8 周：虚拟寄存器化remove-nonunary-let, uncover-local, the-return-of-set!, flatten-set!, verify-a8-output¹
第 9 周：短暂偏题generate-C-code⁴
第 10 周：寄存器分配准备uncover-call-live², optimize-save-placement², eliminate-redundant-saves², rewrite-saves/restores², impose-calling-convention, reveal-allocation-pointer, verify-a10-output¹
第 11 周：活跃分析uncover-live-1, uncover-frame-conflict, strip-live-1, uncover-frame-move, verify-a11-output¹
第 12 周：调用帧uncover-call-live-spills, assign-frame-1, assign-new-frame, optimize-fp-assignments², verify-a12-output¹
第 13 周：溢出代码finalize-frame-locations, eliminate-frame-var, introduce-unspillables, verify-a13-output¹
第 14 周：寄存器分配uncover-live-2, uncover-register-conflict, verify-unspillables¹, strip-live-2, uncover-register-move, assign-registers, assign-frame-2, finalize-register-locations, analyze-frame-traffic¹, verify-a14-output¹
第 15 周：汇编flatten-program, generate-Sparc-code

注：¹由教师提供。²研究生要求的挑战遍。³实际在第 4 周编写。⁴不包含在最终编译器中。

然而，微遍方法论和工具并非没有问题。遍历和重写抽象语法树的重复代码可能掩盖个别遍所执行的有意义的转换。本质上，每个遍的大量代码可能导致学生”见树不见林”。此外，我们认识到将每个遍输出的文法写出来作为文档的重要性，但文法并没有被强制执行。因此，一个未处理的特定情况很容易落入更通用的情况，导致令人困惑的错误或格式错误的输出，在后续遍中出问题。最后，生成的编译器速度慢，这给学生留下了关于编译器速度及其重要性的错误印象。

为了解决这些问题，我们开发了一种”nanopass（纳遍）“方法论和一种用于编写 nanopass 编译器的领域特定语言。nanopass 编译器与 micropass 编译器有三个不同之处：

  1. 中间语言文法被形式化指定并强制执行；
  2. 每个遍只需包含那些经历有意义转换的形式的遍历代码；
  3. 中间代码更高效地表示为记录（records），尽管与程序员的所有交互仍然通过 S-表达式语法进行。

我们使用”nanopass”这个词来同时表示预期的遍的粒度和实现每个遍所需的源代码量。

本文的其余部分描述了 nanopass 方法和支持工具。第 2 节描述用于构建 nanopass 编译器的工具。第 3 节展示了一组语言和遍定义的示例。第 4 节描述 nanopass 工具的实现。第 5 节讨论相关工作。第 6 节给出我们的结论并讨论未来工作。

2 Nanopass 工具

本节描述用于定义新的中间语言和编译器遍的工具。这些工具构成了一个用于编写 nanopass 编译器的领域特定语言，通过 syntax-case 宏系统（Dybvig 等，1993）作为宿主语言 Scheme 的扩展来实现。这种方法提供了对完整宿主语言的访问，用于定义辅助过程和数据结构，这在编写复杂遍（如寄存器分配遍）时特别有用。

2.1 定义中间语言

中间语言定义采用以下形式：

(define-language name { over tspec+ } where production+)

可选的 tspec 声明指定语言的终结符并引入在各种终结符上取值的元变量。每个 tspec 的形式为：

(metavariable+ in terminal)

其中终结符类别在外部声明。元变量 x 的声明隐式指定了形式为 xn 的元变量，其中 n 是数字后缀。每个产生式对应中间语言文法中的一个产生式。

一个产生式将一个非终结符与一个或多个备选形式配对，带有一组可选的元变量。

({ metavariable+ in } nonterminal alternative+)

产生式也可以使用以下语法指定所有备选形式共有的元素：

({ metavariable+ in } (nonterminal common+) alternative+)

共有元素可用于存储注解，例如源信息或分析副产品，这些是中间语言所有子形式共有的。

每个备选形式是一个元变量或带括号的形式，声明一个中间语言构造，后跟一组可选的产生式属性。带括号的形式通常以一个关键字开始，包含子结构，元变量指定每个子形式所属的语言类别。由于带括号的形式通过开头的关键字来消除歧义，最多只有一个备选形式可以是不以关键字开始的带括号形式。这允许中间语言使用自然的 S-表达式语法包含函数应用。每个属性是一个键值对，用于指定相关备选形式的语义、类型和流信息。

图 2 展示了一个简单的语言定义及其对应的文法：

(define-language L0 over
  (b in boolean)
  (n in integer)
  (x in variable)
  where
  (Program Expr)
  (e body in Expr
    b n x
    (if e1 e2 e3)
    (seq c1 e2) => (begin c1 e2)
    (lambda (x ...) body)
    (e0 e1 ...))
  (c in Cmd
    (set! x e)
    (seq c1 c2) => (begin c1 c2)))

对应文法：

Program → Expr
Expr    → boolean | integer | var
        | (if Expr Expr Expr)
        | (seq Cmd Expr)
        | (lambda (var*) Expr)
        | (Expr Expr*)
Cmd     → (set! var Expr)
        | (seq Cmd Cmd)

图 2. 一个简单的语言定义和对应的文法

它定义了元变量 x、b 和 n，分别取值于变量、布尔值和整数，并定义了三组产生式。第一组将 Program 定义为 Expr。第二组定义了取值于 Expr 的元变量 e 和 body，声明 Expr 是布尔值、整数、变量引用、if 表达式、seq 表达式、lambda 表达式或函数应用。第三组定义了取值于 Cmd 的元变量 c，声明 Cmd 是 set! 命令或 seq 命令。

每个中间语言形式的语义可以通过其到宿主语言的自然翻译来隐式指定（如果存在这种翻译的话）。在图 2 中，这种隐式翻译对布尔值、数字、变量引用、lambda、set!、if 和函数应用就足够了。对于 seq 表达式，翻译通过 =>（translates-to）属性显式指定。隐式和显式翻译规则根据宿主语言建立中间语言程序的含义。这有助于理解中间语言程序，并提供了一种机制，在调试编译器时可以验证每个遍的输出是否产生与原始输入程序相同的结果。

2.2 语言继承

连续的中间语言由于中间遍的细粒度特性而通常密切相关。为了允许简洁地指定这些语言，define-language 构造通过 extends 关键字支持一种简单的继承形式，后面必须跟着一个已定义的基础语言的名称：

(define-language name extends base
  { over { mod tspec }+ }
  { where { mod production }+ })

基础语言的终结符和产生式被复制到新语言中，受定义的 over 和 where 部分中的修改影响。每个 mod 要么是 +（添加新的终结符和产生式），要么是 -（移除相应的终结符和产生式）。

以下示例定义了一个从 L0（图 2）派生的新语言 L1，移除了布尔终结符和 Expr 备选形式，并将 Expr 的 if 备选形式替换为 case 备选形式：

(define-language L1 extends L0
  over
  - (b in boolean)
  where
  - (Expr b (if e1 e2 e3))
  + (default in Expr
      (case x (n1 e1) ... default)))

语言 L1 可以作为一个转换遍的输出，该转换遍将与语言相关的细节显式化，以通往一个与语言无关的后端。例如，C 语言将零视为假，而 Scheme 提供了一个代表假的独特布尔常量 #f。这两种语言的条件表达式都可以翻译成 L1 中的 case 表达式，并将与语言相关的假值编码显式化。

语言继承仅仅是一种表示上的便利。为新语言生成一个完整的语言定义，该定义的行为与完全手写出来完全一样。

2.3 定义遍

遍使用一个遍定义构造来指定，该构造命名输入和输出语言，并指定将输入语言形式映射到输出语言形式的转换函数：

(define-pass name input-language -> output-language transform*)

分析遍通常纯粹为了副作用而运行，例如，收集和记录关于变量使用的信息。对于这样的遍，使用特殊的输出语言 void。类似地，当遍遍历 AST 来计算某个更一般的结果（例如目标代码大小的估计）时，使用特殊的输出语言 datum。

每个转换指定转换器的名称、描述转换器输入和输出类型的签名，以及一组实现转换的子句：

(name : nonterminal arg* -> val+
  { (input-pattern { guard } output-expression) }*)

签名的输入部分列出输入语言的一个非终结符，后跟转换器期望的任何附加参数的类型。输出部分列出一个或多个结果类型。除非在输出语言位置指定了 void 或 datum，否则第一个结果类型期望是输出语言非终结符。

每个子句将一个输入模式和一个宿主语言输出表达式配对，共同描述对特定输入语言形式的转换。输入模式使用 S-表达式语法指定，该语法扩展了对应输入语言非终结符产生式中备选形式的语法。子模式由逗号引入，类似于准引用（quasiquote）和反引用（unquote）的方式，表示输入形式中不固定的部分。

模式变量用于输入模式中约束输入 AST 子形式的匹配。它们还建立变量绑定，可在输出表达式中用于引用输入子形式或结构递归的结果。各种子形式可以采用的形式总结如下：

  1. 子模式 ,a 在对应输入子形式是 A 的形式时匹配，并将 a 绑定到匹配的子形式。
  2. 子模式 ,[f : a -> b] 在对应输入子形式是 A 的形式时匹配，将 a 绑定到输入子形式，并将 b 绑定为对 a 调用 f 的结果。如果结果类型不是 B 的形式，则报错。
  3. 子模式 ,[a -> b] 等价于 ,[f : a -> b]，如果 f 是唯一将 A 映射到 B 的转换器。
  4. 子模式 ,[b] 在输入形式被语言定义约束为 A 的形式的上下文中，等价于子模式 ,[a -> b]，只是没有变量绑定到输入子形式。

通常，一个遍只对输入语言的少数几种形式执行非平凡的转换。在这种情况下，两个中间语言密切相关，新语言可以使用语言继承来表达。当两个中间语言可以通过继承关联时，遍定义只需为那些经历有意义变化的形式指定转换器，将其余转换器的实现留给遍展开器（pass expander）。遍展开器通过查询输入和输出语言的定义来完成遍的实现。遍、转换器和中间语言的强类型帮助遍展开器自动完成这些简单转换。遍展开器是保持遍规格简洁的重要工具。中间语言继承和遍展开器共同提供了一种简单而快捷的方式来向编译器添加新的中间语言和相应的遍。

3 示例：赋值转换

赋值转换是一种将赋值变量替换为可变数据结构的变换，使赋值变量的位置变得显式。例如，赋值转换会将程序：

(lambda (a b) (seq (set! a b) a))

转换为以下形式：

(lambda (t b)
  (let ((a (cons t #f)))
    (seq (set-car! a b) (car a))))

赋值转换涉及两个遍。第一个遍 mark-assigned 定位赋值变量（即出现在赋值左侧的变量），并通过在变量记录结构的一个字段中设置标志来标记它们。第二个遍 convert-assigned 将对赋值变量的引用和赋值重写为显式的结构访问或修改。

mark-assigned 遍纯粹为了副作用而运行在语言 L1 的程序上，语言 L1 可以从 L0（图 2）派生而来，添加 let 和 primapp 形式以及终结符 primitive：

(define-language L1 extends L0
  over
  + (pr in primitive)
  where
  + (Expr
      (let ((x e) ...) body)
      (primapp pr e ...))
  + (Command
      (primapp pr e ...)))

由于 convert-assigned 移除了 set! 形式，其输出语言 L2 从其输入语言 L1 派生以反映这一变化：

(define-language L2 extends L1 where - (Command (set! x e)))

两个遍的代码如下：

;; mark-assigned 在语言 L1 的程序上运行为副作用，
;; 通过在记录结构中设置标志来标记每个赋值变量。
(define-pass mark-assigned L1 -> void
  (process-command : Command -> void
    [(set! ,x ,[e])
     (set-variable-assigned! x #t)]))

;; convert-assigned 从语言 L1 的程序生成语言 L2 的程序，
;; 为每个赋值变量创建一个显式位置（pair），
;; 并相应地重写引用和赋值。
(define-pass convert-assigned L1 -> L2
  (process-expr : Expr -> Expr
    [,x (variable-assigned x) `(primapp car ,x)]
    [(lambda (,x ...) ,[body])
     (let-values ([(xi xa xr) (split-vars x)])
       `(lambda (,xi ...)
          (let ((,xa (primapp cons ,xr #f)) ...)
            ,body)))])
  (process-command : Command -> Command
    [(set! ,x ,[e]) `(primapp set-car! ,x ,e)]))

;; split-vars 被 convert-assigned 用于为赋值变量引入临时变量。
(define split-vars
  (lambda (vars)
    (if (null? vars)
        (values '() '() '())
        (let-values ([(ys xas xrs) (split-vars (cdr vars))])
          (if (variable-assigned (car vars))
              (let ([t (make-variable 'tmp)])
                (values (cons t ys) (cons (car vars) xas) (cons t xrs)))
              (values (cons (car vars) ys) xas xrs)))))))

图 3. 赋值转换

第一个遍只需要显式处理一种语言形式：set!。如果输入是 set! 命令，该遍只需在表示赋值变量的记录结构中设置赋值标志，并通过 ,[·] 语法递归处理右侧表达式。

第二个遍显式处理三种形式：变量引用、lambda 表达式和赋值。它将每个赋值变量绑定到一个 pair，其 car 是变量的原始值，将对赋值变量的每个引用替换为对 car 的调用，将每个赋值替换为对 set-car! 的调用。

4 实现

从学生的角度来看，语言定义通过熟悉的 S-表达式语法指定中间语言的结构。学生与中间语言的所有交互都通过这种语法进行。然而在内部，中间语言程序更安全、更高效地表示为记录结构。

中间语言程序在宿主语言中也是可求值的，使用附加到产生式备选形式的翻译属性。为了支持中间语言程序的这些不同视角，通过 define-language 定义的语言隐式定义了以下内容：

  1. 一组表示中间语言程序抽象语法树（AST）的记录类型；
  2. 一个将 S-表达式映射到记录结构的解析器（parser）；
  3. 一个将记录结构映射到 S-表达式的反解析器（unparser）；
  4. 一个将 S-表达式模式映射到记录模式（schema）的部分解析器（partial parser）。

这些产物被打包在一个模块中，可以在需要的地方导入。

4.1 记录类型定义

语言定义自动生成一组记录定义。为基础语言构造一个基记录类型，并为每个非终结符构造一个子类型。每个非终结符的子类型声明该非终结符的共有元素。还为每个备选形式创建一个新的记录类型，作为对应非终结符的子类型。

(define-record L0 ())
(define-record program L0 ())
(define-record expr L0 ())
(define-record command L0 ())
(define-record b.expr expr (b))
(define-record n.expr expr (n))
(define-record x.expr expr (x))
(define-record if.expr expr (e1 e2 e3))
(define-record seq.expr expr (c1 c2))
(define-record lambda.expr expr (xs body))
(define-record app.expr expr (e0 es))
(define-record set!.command command (x e))
(define-record seq.command command (c1 c2))

图 4. 为 L0 生成的记录定义

4.2 解析器

每个语言定义产生一个能够将 S-表达式转换为表示相同抽象语法树的对应记录结构的解析器。第一个输入语言的解析器作为编译器的第一个遍（在词法分析和语法分析之后），提供后续遍所需的记录结构化输入。其他中间语言的解析器通过使获取适合任何给定遍的输入变得容易来简化调试和实验。

4.3 反解析器

反解析器将 AST 记录转换为其对应的宿主语言可执行形式。与解析器一样，这也是一个很好的调试辅助工具，允许学生以宿主语言的形式查看任何遍的输出。它使学生能够跟踪和手动翻译程序，例如在新优化的探索性开发阶段。每种记录类型存储反解析自身实例所需的信息。因此，所有语言共享一个反解析过程。

反解析器还可以将记录结构翻译为其隐含的带括号形式（即没有宿主语言翻译的形式），允许学生美化打印中间语言代码。

4.4 部分解析器

部分解析器用于支持输入模式匹配和输出构造。部分解析器将表示输入模式或输出模板的 S-表达式语法翻译为其对应的记录模式（schema）。记录模式类似于记录结构，只是 S-表达式模式的可变部分被转换为一种特殊的列表表示，稍后用于生成遍的代码。部分解析器产生的结构对学生不可见，但用于生成匹配给定模式和构造所需输出的代码。

4.5 匹配输入

当被调用时，转换器将其第一个参数（必须是 AST）与每个子句的输入模式进行匹配，直到找到匹配。子句按顺序检查，用户指定的子句在遍展开器插入的任何子句之前。此过程持续进行，直到找到某个子句的输入模式与 AST 匹配，并且守卫表达式和模式变量施加的附加约束得到满足。当找到匹配时，执行任何结构递归处理，并评估对应的输出表达式以产生期望结果类型的值。如果没有子句匹配输入，则报错。

4.6 构造输出

当转换器的输入与某个子句的输入模式匹配时，对应的输出表达式在一个将模式变量匹配的子形式绑定到同名程序变量的环境中进行求值。例如，如果表示 (set! y (f 4)) 的输入语言记录匹配模式 (set! ,x ,[e])，则对应的输出表达式在一个将程序变量 x 和 e 分别绑定到表示 y 和处理 (f 4) 结果的记录的环境中求值。当模式变量在输入模式中后面跟着省略号（...）时，对应的程序变量被绑定到匹配的记录列表。

输出模板中可用的记录构造函数由遍定义中指定的输出语言决定。实例化输出模板必须产生一个 AST，表示包含该子句的转换器的输出非终结符的形式。

5 相关工作

我们自动生成的解析器和反解析器类似于 Zephyr 抽象语法定义语言（ASDL）中读写语言特定数据结构的语言特定函数。ASDL 仅关注中间表示，因此不集成定义遍的支持。

TIL 编译器在一系列类型化中间语言上操作（Tarditi 等，1996），允许每个遍的输出被静态类型检查。我们语言定义为每种中间语言产生的反解析器允许我们生成语义等价的宿主语言程序，通过这些程序我们可以类似地验证静态和动态属性，例如通过控制流分析。

Polyglot（Nystrom 等，2003）确保添加新遍或新 AST 节点类型所需的工作与受影响的节点类型或遍的数量成正比，它使用了一些相当复杂的面向对象语法和机制。我们的遍展开器和对语言继承的支持以更少的语法和概念开销达到了同样的目标。

Tm 是一个类似 m4 的宏处理器，接受源代码模板和一组数据结构定义，并生成源代码（van Reeuwijk，1992）。使用 Tm 已经生成了类似于 define-pass 的树遍历器和分析器模板（van Reeuwijk，2003）。这些模板是 define-pass 的低层亲属，define-pass 提供了方便的输入模式语法来匹配嵌套记录结构和输出模板语法来构造嵌套记录结构。

PFC 编译器（Allen & Kennedy，1982）使用宏展开来填充样板转换，而面向对象的 SUIF 系统（Aigner 等，2000a；Aigner 等，2000b）在单一中间语言上操作，允许样板转换被继承。nanopass 方法实现了与这些系统类似的效果，但通过形式化语言定义、在语言定义中包含足够的信息以允许自动转换到宿主语言和从宿主语言转换、以及将遍历算法与中间语言和遍定义分离来扩展了它们。

6 结论

nanopass 方法论支持将编译器分解为许多小片段。这种分解简化了理解每个片段以及整个编译器的任务。不需要将新的分析或转换”硬塞进”现有的单体遍中。该方法论还简化了编译器的测试和调试，因为每个任务可以独立测试，bug 很容易隔离到个别任务。

nanopass 工具使编译器学生能够专注于概念而非实现细节，同时拥有编写一个完整且有实质性的编译器的体验。虽然让学生在前几个遍中写出所有遍历和重写代码以理解过程是有用的，但在后续遍中仅关注有意义转换的能力减少了繁琐和重复代码的数量。代码节省对许多遍来说是显著的。使用我们的旧工具，remove-not 是最小的遍，有 25 行代码；现在是 7 行。类似地，convert-assigned 原来是 55 行，现在是 20 行。另一方面，少数遍的大小无法缩减。例如，代码生成器必须显式处理每个文法元素。

我们的经验表明，细粒度遍在教学环境中效果极好。我们也对使用 nanopass 技术构建生产级编译器感兴趣，在这种情况下，多次遍历代码的开销可能是不可接受的。为了解决这个潜在问题，我们计划开发一个遍组合器（pass combiner），可以在指导下将一组遍融合为单个遍，使用 deforestation 技术（Wadler，1988）来消除重写开销。

致谢

Dan Friedman 建议使用小型、单一用途的遍，并为基于这一原则的早期编译器做出了贡献。Erik Hilsdale 设计并实现了我们用于实现微遍编译器的匹配器。我们的输入模式子模式的灵感来自该匹配器。Jordan Johnson 实现了 nanopass 框架的早期原型。Matthias Felleisen 的评论促成了多处表述上的改进。Dipanwita Sarkar 的资助来自 Microsoft Research University Relations 的赠款。

参考文献

  • Aigner, G., et al. (2000a). An overview of the SUIF2 compiler infrastructure. Tech. rept. Stanford University.
  • Aigner, G., et al. (2000b). The SUIF2 compiler infrastructure. Tech. rept. Stanford University.
  • Allen, J.R., & Kennedy, K. (1982). PFC: A program to convert Fortran to parallel form. Technical Report MASC-TR82-6. Rice University, Houston, TX.
  • Dybvig, R. Kent, Hieb, Robert, & Bruggeman, Carl. (1993). Syntactic abstraction in Scheme. Lisp and Symbolic Computation, 5(4), 295–326.
  • Kelsey, Richard, Clinger, William, & Rees, Jonathan A. (Editors). (1998). Revised⁵ report on the algorithmic language Scheme. SIGPLAN Notices, 33(9), 26–76.
  • Nystrom, N., Clarkson, M., & Myers, A. (2003). Polyglot: An extensible compiler framework for Java. Proceedings of the 12th International Conference on Compiler Construction. LNCS, vol. 2622. Springer-Verlag.
  • Tarditi, D., et al. (1996). TIL: A type-directed optimizing compiler for ML. Proceedings of the ACM SIGPLAN 1996 Conference on Programming Language Design and Implementation.
  • van Reeuwijk, C. (1992). Tm: A code generator for recursive data structures. Software Practice and Experience, 22(10), 899–908.
  • van Reeuwijk, C. (2003). Rapid and robust compiler construction using template-based metacompilation. Proceedings of the 12th International Conference on Compiler Construction. LNCS, vol. 2622. Springer-Verlag.
  • Wadler, P. (1988). Deforestation: Transforming programs to eliminate trees. ESOP ‘88: European Symposium on Programming. LNCS, vol. 300. Springer-Verlag.

📝 文章反馈