Andy Keep - 编写 Nanopass 编译器

Andy Keep - Writing a Nanopass Compiler

频道:ClojureTV · 时长:40:47 · 发布:2014-01-06 · 播放:28724

在 YouTube 观看

简介

Andy Keep 在 Clojure/Conj 大会上关于编写 nanopass 编译器的演讲,该编译器由许多单一任务的 pass 构建,并具有形式化定义的中间语言。它涵盖了该框架在印第安纳大学编译器教学课程中的起源。

HN 为什么推荐

与编译器构建资源一起被引用,作为 Chez Scheme 中使用的 nanopass 方法的首选演讲。

Andrew Keep 有一个关于这种方法的精彩演讲 [2]。 — HN, 2018

函数式编程 · 编译器、解释器与程序分析

中文字幕节选

[掌声] 非常感谢,嗯,我是 Andy Keep,跟随 我办公室伙伴 Will Bird 的传统,我,我今天不会展示任何 Clojure 代码 抱歉,但我会展示一些 Scheme 代码,所以,嗯 所以,你知道,我想一开始就说,我是 Andy Keep,我喜欢编译器,我喜欢 编写编译器,用编译器做各种事情,我只是觉得这非常有趣 所以我想先讲一点编译器历史,嗯,只是为了谈谈 nanopass 这个想法的概念是什么,它的起源是什么,嗯,所以我们过去 编写编译器时只是用少数几个遍,嗯,为了方便这里我只 展示了三个遍,大多数那些编译器有更多遍,但也不会 多太多,早期的编译器之所以这样写,是因为嗯,每个 单独的遍都有一些工作需要完成,但机器上没有足够的 资源来在单个遍中完成所有这些,事实上 机器上甚至没有足够的资源来把所有这些东西存储在内存中 每个遍实际上会读入嗯程序的一种表示,把它写到 文件系统,下一个遍会读入它并写到文件系统,所以 你可以理解为什么他们想要尽量减少编译器中的遍数 尤其是在文件系统是磁带驱动器或纸带的时候,所以你 知道,这不是一个很好的设计,嗯,或者说不是一个很好的空间来做这些 事情,但计算机变得更好了,然后我们可以做同样的少数几个遍 并且可以把所有东西都保存在内存中,那还挺不错的,但人们 继续以这种方式编写他们的编译器,我的意思是也有一些例外 有些东西是用很多遍写的,但大多数情况下还是保持这样 有时我们甚至从不把它写到文件系统,我们只是直接运行它 嗯,你知道,那挺酷的,这有点像你在 Scheme 或 Clojure 或 Haskell 或 ML 或任何你 最喜欢的 REPL 中的情况,嗯,稍微谈谈我参与过的那个编译器 一个遍做了闭包转换、循环识别,嗯,它开始了我们的嗯处理 它处理了多返回值、外部可调用处理、外部函数 处理、直接调用优化,然后闭包优化开始于一个 遍,然后在下一个遍中继续,让这一切变得有点 棘手的是,如果我正在积极地开发我的编译器,我想添加一个 新的优化,而这个新优化必须在一个任务之后但在 另一个任务之前发生,而这两个任务都由同一个遍执行,那么现在我就 有点麻烦了,因为我必须找到一种方法把它编织到现有的 路径中,而不破坏已经在那里的任何东西,所以那相当棘手 所以我们想要做的是,我们想要把这些东西分解成 一堆小的遍,其中每一个遍只是执行某个 单一任务,然后以那种方式运行它们,所以正如我所说,我喜欢 编译器,嗯,但我特别喜欢 nanopass 编译器,我花了一些时间 研究这些东西,所以只是给你们一点关于 nanopass 东西来自哪里的背景,嗯,这一切都源于印第安纳大学的编译器课程,嗯 或者至少它的一些起源在那里,嗯,所以我的导师 Kent Dybvig,他当时在 印第安纳,我想他当时去休假了,Dan Friedman 教这门课 他真的想要嗯摆脱这种教授遍的方式,这些大的

HN 上的讨论

编译器有各种形状和大小。有些是单遍的,如Turbo Pascal。它们在解析时直接生成机器码(没有AST!)。Niklaus Wirth(Pascal/Modula/Oberon的人)写了一本遵循这种方法的书[1]。有些是多遍的,如Chez Scheme。它们有许多简单的遍,称为“nanopass”。Andrew Keep有一个关于这种方法的精彩演讲[2]。在实践中,今天大多数编译器是多遍的,尽管可能没有Chez那么多。如果我们看Rust,它们从AST -> HIR -> MIR -> LLVM IR -> 机器码[3]。从LLVM到机器码可能还有更多事情发生,但我知识不够,无法评论。我认为这里的权衡很清楚:更少的遍 -> 更短的编译时间,更多的遍 -> 生成的代码更快,编译器更模块化。Martin Odersky(Scala的人)有一篇论文试图兼得两者之长[4]。 [1] [LINK]… — undecidabot, 2018-04
另见,Andy Keep的论文[1]和他在Clojure/Conj 2013的演讲[2]。我认为nanopass架构特别适合由LLM实现的编译器,因为它们非常擅长执行小而定义明确的工作。我很想看到Anthropic再次尝试他们的C编译器实验,但建立在Nanopass框架之上。我最近一直在研究向Langkit添加Nanopass支持,这将允许用Ada、Java、Python或其他几种语言编写Nanopass编译器[3]。 [1]: [LINK] [2]: [VIDEO] [3]: [LINK] — LiamPowell, 2026-04
许多人建议编译器实现的资源,我个人会从原型设计语言本身开始,考虑它的类型系统和运行时属性。类型系统有很多可能性,从静态到动态以及介于两者之间的一切,像线性类型、代数类型等概念。运行时属性包括内存模型(垃圾回收,是或否)。所有这些都取决于你语言的目的。 第二部分是选择一个运行平台(这样你只需要编写编译器前端)。有许多伟大的技术可以托管语言,但我在这里提倡两个特定的: * [LINK](向@love2code致敬) * [LINK] ZetaVM是动态类型和/或JIT编译语言(如Python或JavaScript)的绝佳目标。LLVM用于许多低级/接近硬件的语言,如C、C++、Rust等。两者都不必是你的最终目标,你的编译器前端可以稍后移动到另一个平台,如JVM。 最后一部分,实现你的编译器前端。这涉及词法分析/解析源代码,如果需要则进行类型检查,并生成目标的中间表示。我个人更喜欢使用解析器… — vengarioth, 2017-09
这是Chez Scheme增量式编译器(像40多个Scheme编译器)这一杰作的前期工作吗?我的意思是,思科收购了它,可能是为了向我们所有人隐藏它。它一定有价值。[VIDEO] [LINK] [LINK] — 616c, 2016-12

相关视频