用 Swift 搭建一个微型编译器
iunj9154
8年前
<p>对绝大多数开发者来说，尽管我们每天都要与编译器打交道，然而实际上编译器对我们来说仍然像一个神秘的黑盒。在本次 try! Swift 的讲演中，Samuel Giddins 从头搭建了一个全新的微型编译器，用来编译他自制的一门编程语言，从而借此去学习编译器的基本工作机制。他还讲述了 Swift 是如何为复杂问题（例如语义解析、词法分析和代码生成）提供优雅的解决方案的。最后，我们将实现一门全新的编程语言，并完成对它的编译工作！</p> <p>我构建了一门名为「Sipquick」的编程语言，然后我用 Swift 为其搭建了编译器和测试用例。</p> <p>那么这个微型编译器长什么样呢？ 仅仅只有 310 行代码！我并没有去计算 Swift 编译器的代码行数，不过我猜想它起码会超过 100,000 行。所以，相比之下，我的这个编译器的的确确配得上「微型」这一称号。</p> <h3><strong>为啥要编写一个编译器呢？</strong></h3> <ol> <li>编译器是每个开发人员都要每天打交道的玩意儿。因此，我很好奇编译器是如何工作的。 当我运行 Swift 、C 程序或者运行 Clang 的时候会发生什么呢？</li> <li>这是一个很出名的问题领域。现在编译器的种类有成百上千种。您可以去谷歌 「我该如何在编译器当中执行……」 ，您会得到一些比在 Stack Overflow 上更好的答案。您可能会搜索到 推ter 上的推文、博客上的文章以及相关的书籍。</li> <li>这些建议在任何语言当中都是可行的。它本质上是一个将某种文本文件转换为另一种文本文件的程序。</li> <li>我此前从未编写过编译器。不过现在我可以在简历上大书一笔「编译器工程师」。</li> </ol> <p>编译器其实非常简单，就是一函数：</p> <pre> <code class="language-swift">let compiler: (String) -> Data /* 可执行文件 */</code></pre> <p>这个函数接收一个字符串为参数，这个字符串我们称之为 <strong>「源文件」</strong> ，然后输出一个可执行文件。它将我们可以阅读、理解、编写和分析的语言所编写的 <strong>程序</strong> ，转换为另一种机器可以阅读、理解、分析以及执行的语言。</p> <p>那么，我们该如何编写一个编译器呢？下面是一系列众所周知的步骤：</p> <ul> <li> <p>解析源代码</p> </li> <li> <p>词法分析</p> </li> <li> <p>做所谓的「语义分析」。比如说「现在这里有一些 Token，它们是啥意思？在 Swift 当中， Class 这个单词意味着什么呢？」</p> </li> <li> <p>优化</p> </li> <li> <p>生成机器代码</p> </li> </ul> <p>编译器的本质决定了编译器一定是 <strong>高度函数化 (functional)</strong> 的。我构建了一门名为「Sipquick」的编程语言。这是一本书中虚构的一种叫声非常响亮、聒噪的鸟类（译者注：源自 <em>“The Wise Man’s Fear”</em> ，这可能是一种与蜂鸟相关的鸟类）。</p> <ul> <li> <p>这是一门非常简陋的语言，是我专门为本次讲演而发明的。如果我试图为现有的语言编写一个编译器，那么我将不得不实现很多东西，这将会导致我的工作变得困难、复杂。</p> </li> <li> <p>这是一个基于 <em>s-表达式 (s-expressions)</em> 的语言（类似于 Lisp）。所有的内容都包含在括号当中，因此您的编译器必须要能够实现括号自动匹配，这样我们才能够很方便的保证所有的内容都能成功编译。</p> <p>s-表达式：全称是 Symbolic Expression，可以是一个原子量 (atom)，也可以是成对括号组成的列表，例如：(x, y)、x、y 都是一个 <em>s-表达式</em> 。</p> </li> <li> <p>这是一门 <em>动态</em> 语言，因此编译时是没有类型之分的。</p> </li> <li> <p>编译器并不知晓类型，这是一门函数式语言。由于它的本质所致，这使得每个函数都需要接受参数并返回一些东西，这可能会导致语言当中存在某种副作用。</p> </li> </ul> <pre> <code class="language-swift">(def hello name (+ "Hello, " name)) (print (hello "world!"))</code></pre> <p>这就是我们在 Sipquick 当中编写「Hello, world!」的方式。 def 是定义函数的关键字，这个函数的名字为 hello 。它接受一个名为 name 的参数，然后它与一个字符串建立了连接。第二行，我们调用了这个函数并对其进行了输出。</p> <p>首先我们需要搭建一个解析器 (Parser)。它是一个解析器组合器 (Combinator) —— 这里面有一些很有意思的玩意儿，类似于 Monad。不过我很不喜欢那些花里胡哨的运算符——我将其改成了可以即写即读的玩意儿。</p> <p>这是最主要的解析过程：</p> <pre> <code class="language-swift">let schemeParser: Parser<String, [Sexp]> = { return ignoreSecond( sexp(). then(unichar("\n").maybe()). maybeMany(). fmap { $0.map { $0.0 } } .then(dropEndingMetadata().or(empty().andThatsAll()))) }</code></pre> <p>这里我忽略了配置解析器的所有内容，以及一些 <em>s-表达式</em> 的定义。但是我们的基本思路就是需要在一组 <em>s-表达式</em> 当中完成解析操作，然后一旦遇到了文件尾或者遇到了换行标志，那么我们就完成了这一行代码的解析。最后我们会得到一个包含 <em>s-表达式</em> 的数组。</p> <p>这里出现了各种各样的泛型。编译器其实很讨厌泛型的，但是我们可以将我们所获取到的字符串、Token 转换为 <em>s-表达式</em> 。</p> <pre> <code class="language-swift">_.fmap { Sexp.single($0) } _.fmap { Sexp.many($0) } _.fmap { _ in Sexp.none }</code></pre> <p>解析过程中，我们会将所解析的东西转换为 AST (抽象语法树 Abstract Syntax Tree)。我可以分析出「这些是空括号、这些是空的 <em>s-表达式</em> 」，从而让分析过程变得简单。我不必去关注这些字符串在不同的位置意味着什么。这些操作是在 parser.swift 文件当中进行的。</p> <pre> <code class="language-swift">let sema: ([Sexp]) -> [Expression]</code></pre> <p>我们已经完成了解析，现在需要对 Token 进行处理了。但是很多语言当中 Token 都具有不同的特殊意义。 您该如何定义一个函数呢？如何定义一个变量呢？此外还有关键字，这些是运算符吗？不同行之间该如何协同工作呢？</p> <p>这就是所谓的语义分析 (Semantic Analysis)：通过分析这个抽象语法树，然后将其折叠 (collapse) 成 Expression ，从而让编程语言能够进行分析：</p> <pre> <code class="language-swift">struct Expression { init(sexp: Sexp) { switch exp { ... } } }</code></pre> <p>这个初始化语句当中包含了一个臃肿的 switch 语句。我上周都一直在编写这玩意儿。这里我将不会具体描述这段代码，因为我觉得在 Swift 本身的语义分析当中并不会出现这种方式。我们对所要找的东西进行选择，然后将这些类似 Lisp 的 <em>s-表达式</em> 转换为编译器所能够理解的 Expression ，从而理解这个表达式是定义了一个变量，还是定义了一个函数，或者是进行了函数的调用。</p> <p>在绝大多数编译器当中，我们可能会进行检查「这段程序是否正确？它的构造是否正确？」。在类似 Swift 的语言当中，这还意味着我们需要检查 <em>「这个类型是否正确？调用的这个函数的参数数量是否正确？这个函数是否存在？」</em> 。而我们现在编写的这个语言并不需要执行这些操作。此外，我们这个编译器也不会去执行优化操作。</p> <p>讽刺的是， <strong>优化 (Optimization)</strong> 是编译器当中 <strong>最简单的事情之一</strong> ：</p> <pre> <code class="language-swift">let optimizations: Array<[Expression] -> [Expression]></code></pre> <p>优化是指「这里有一些相应的表达式，然后我们需要把它们转换为另一种表达式」。在绝大多数久经风霜的编译器当中，您可能会看到很多的优化流程。在这个流程当中，您将要执行下述操作：</p> <ul> <li>是否有无法访问的代码？如果有就删掉。</li> <li>是否有重复使用的纯函数 (pure function)？如果有，我们可以对值进行计算，然后将结果直接放到重复使用的地方。</li> </ul> <p>这里我一项优化操作都没有做，但是这个操作是编译器执行过程当中最为重要的部分之一，因此人们会在这个步骤花费大量的时间。如果我花了 10 个小时来进行优化，从而可以使代码运行速度加快 1%，那么这就是值得的。因为使用编译器的用户很多，1% 的优化可能意味着可以节省用户成千上万个小时来进行编译。此外，编译器的优化也是学术研究的热点所在，我们需要研究何种转换是既安全又迅速的。</p> <p>代码生成 (Code Generation) 是最后的步骤了，这个时候我已经理解了整个程序的意图。编译器已经知道了整个程序需要执行的操作，但是现在还需要输出电脑能够运行的东西才行：</p> <pre> <code class="language-swift">let codeGen: ([Expression]) -> Data</code></pre> <p>我们用 Expression 数组作为参数，然后将它们转换为可执行文件。</p> <p>什么是可执行文件呢？生成机器代码的工作是交给 Clang 和 LLVM 代劳的。如果您曾经使用过 Babel for JavaScript 的话，那么它本质上是将某种形式的 JavaScript 编译成另一种形式的 JavaScript；它本质上仍然是一种编译过程。</p> <p>我觉得代码生成这个步骤是非常困难的。人们所想出的最简单方法是：导入 LLVM，然后将相关的数据交给 LLVM 来完成，LLVM 当中会有很多的优化操作，并且会生成很棒的机器代码。如果您使用的是类似 C 语言类似的东西的话，那么 LLVM 将会非常好用。因为 LLVM 是专门为 C、C++ 和 Objective-C 的编译器而编写的。</p> <p>这里我所构建的语言是一门非常动态的语言，没有任何类型，我们根本不知道这个变量是一个字符串还是一个整数，也不知道这个函数是否切实存在。我试图将它适配到 LLVM 当中，但是这并未奏效。</p> <p>在第 27 页幻灯片上，这就是理想化的「现代编译器的工作方式」。所有的 LLVM 操作都发生在编译的最后阶段，但是我现在无法这么做。我不得不自行实现最艰难的部分。</p> <p>我将我的这门类似 Lisp 的语言编译为 Ruby。Ruby 是一门动态语言，它有一门很稳定的标准库，这样我就不用去编写诸如「我该如何将这个参数传递给程序？我该如何向屏幕输入内容」此类的内容。</p> <pre> <code class="language-swift">extension Expression { func asRuby() -> String { switch self.type { ... } } }</code></pre> <p>我将代码生成这一步骤基本上作为 Expression 的扩展来实现。我们的做法是「这里有一个表达式，然后我们可以将其转变为 Ruby 来表示」。</p> <p>这个操作是递归进行的。因为我们会有嵌套的表达式存在，比如说函数调用这种形式，我们进行了一次顶层的函数调用，然后可能其参数本身就包含了其他函数调用或者其他的表达式。这个 asRuby() 方法将会对表达式进行转换，然后输出 Ruby 代码，只要您的机器上可以运行 Ruby，那么我们就可以运行我们的程序了。</p> <p>这段代码的要点是：我们要将表达式通过 $0.asRuby() 进行映射，然后将所得到的内容通过换行标志联结在一起，然后在顶部添加一个 Shebang ( #! ) 符号，接着执行 chmod 命令，这样就生成了可执行文件，从而就可以运行了。</p> <p>那么这个步骤是什么样子的呢？</p> <pre> <code class="language-swift">; fibonacci.spq (def fib x (condition (<= x 1) x (+ (fib (- x 1)) (fib (- x 2))))) (print (fib 10))</code></pre> <p>将会转换为：</p> <pre> <code class="language-swift">#!/usr/bin/env ruby def fib(x) if (x.<=(1)) x else (fib((x.-(1))).+(fib((x.-(2))))) end end print(fib(10))</code></pre> <p>这里我们添加了一个定义，定义了第 n 个斐波那契数是什么。Lisp 并不是最具表现力的语言，因为它当中有很多的括号，但是我们可以将其编译为某种看起来很像 Ruby 的玩意儿，这就相对比较友好。如果您实际运行这段代码，会发现它是能够正常工作的。</p> <p>在第 32 页幻灯片上，我列出了整个代码生成的步骤。我知道大家根本看不清，当然我这是故意的。这段代码放在了一个文件当中，非常地紧凑，但是实现起来也比较简单，我还针对 Ruby 做了比较好的转换和优化。</p> <p>它基本上就是对 Expression 执行选择操作，然后挑选出「这是一个函数定义，而这些是参数名称」，然后转换为对应的 Ruby 表达式。</p> <pre> <code class="language-swift">extension Expression { func parenthesize(_ s: String) -> String var isOperatorCall: Bool { get } func asRuby(depth: Int = 0) -> String { switch kind { case .bare: { } case .call: if isOperatorCall { } else { } case .functionDefinition: { } case .empty: { } case .variableDeclaration: { } case .conditional: guard children.count == 3 else { } let conditional = children[0] let positive = children[1] let negative = children[2] { } } } }</code></pre> <p>不过除此之外，之前的语义分析、优化操作都是非常简单的，我们只要实现「将其输出成某个读起来与我们所操作的语言一样的对象」即可。</p> <p>如果我试图将这个语言编译成 Swift 或者 C，那么这将是一个非常困难的操作，因为我该如何判断某个数字是一个整数还是一个浮点数呢？如何判断这是一个字符串还是一个字符呢？我该如何进行栈的分配，如何进行堆的分配？因此，当您试图以传统的编译器的做法来思考这门语言的时候，会发现有很多不匹配的地方。所以，这个步骤完全取决于您所要编译运行的语言特性。</p> <pre> <code class="language-swift">$ cat fibonacci.spq (def fib x (condition (<= x 1) x (+ (fib (- x 1)) (fib (- x 2))))) (puts (fib ([] ARGV 0))) $ sipquick fibonacci.spq fibonacci $ ./fibonacci 10 55</code></pre> <p>我很喜欢这个 .spq 扩展名。您可以编写一个文件，然后将以 spq 结尾。您可以选择它输出的文件是什么，然后您便可以像其他任何一个正常的可执行文件一样，传递参数并运行程序。</p> <p>我只写了集成测试 (integration test)。这些测试主要是编译一个文件，然后进行运行，并验证输出是否符合我的期望。只有通过测试我才知道编译器能够正常工作，因此这需要一个格式良好的程序进行编译和运行，而不是用其他糟糕的例子来验证其稳定性。此外我没有编写任何的单元测试。</p> <p>这是其中的一个测试用例：</p> <pre> <code class="language-swift">(def print_even x (condition (== (% x 2) 0) (print "even") (print "odd"))) (print_even 17) (print_even 12) (print_even -1) (print_even 1) (print_even (* 0 1)) ///// it allows branching 0oddevenoddoddeven</code></pre> <p>基本上我会在顶部添加一个 Sipquick 标志，然后添加五个斜杠，随后写上测试用例的名称、期望的退出代码 (exit code) 以及期望的输出，此外还有测试者的名称。</p> <p>这就是一个标准测试的格式。它拥有一个名称、您所运行的脚本、期望的输出和期望的退出代码。然后您只需要运行这段代码即可，并确保所有的内容都是相等的。然后，找到编译器的路径，或者找到具有所有 spec 文件的路径，找到之后，实例化这些测试用例，运行它们，看看它们是否通过即可。</p> <p>这是我今天早上写的最后一个测试用例：</p> <pre> <code class="language-swift">(def fizzbuzz x (condition (<= x 0) (return "") (condition (== 0 (% x 15)) (+ (fizzbuzz (- x 1)) "fizzbuzz") (condition (== 0 (% x 3)) (+ (fizzbuzz (- x 1)) "fizz") (condition (== 0 (% x 5)) (+ (fizzbuzz (- x 1)) "buzz") (+ (fizzbuzz (- x 1)) (String x))))))) (def fetch_arg position default (condition (!= nil ([] ARGV position)) ([] ARGV position) (return default))) (print (fizzbuzz (fetch_arg 0 100))) ///// it computes fizzbuzz 012fizz4buzzfizz78fizzbuzz11fizz1314fizzbuzz1617fizz19buzzfizz2223fizzbuzz26fizz2 829fizzbuzz3132fizz34buzzfizz3738fizzbuzz41fizz4344fizzbuzz4647fizz49buzzfizz525 3fizzbuzz56fizz5859fizzbuzz6162fizz64buzzfizz6768fizzbuzz71fizz7374fizzbuzz7677f izz79buzzfizz8283fizzbuzz86fizz8889fizzbuzz9192fizz94buzzfizz9798fizzbuzz</code></pre> <p>我试图实现一下 FizzBuzz 程序，而这个测试使得我不得不修复一些编译器当中的错误，从而让这个用例能够正常工作。我不得不花了一段时间弄明白为什么这个用例无法工作，我发现结果是括号并未匹配，因为我的编译器只能够处理一段语句全部位于一行当中的情况，最终我让这个用例成功地通过了。我成功用属于自己的编程语言实现了 FizzBuzz！</p> <ul> <li>我编写的 Swift 代码比较糟糕，此外需要把一些用 struct 的地方改写为 enum ；</li> <li>没有实现优化。Ruby 代码并不是世界上运行最快的代码，我很肯定将我的代码编译为 Ruby 运行会导致运行速度极大地减慢；</li> <li>需要能够在函数域当中定义新变量。函数之类的东西目前并不太理想；</li> <li>没有错误消息。如果没有生成正确的 <em>s-表达式</em> ，程序仅仅只是报告一个致命错误。这使得找出何种原因导致编译失败变得异常困难；</li> <li>没有语义分析错误。您可以使用错误的参数数量来定义函数，还可以使用错误的参数数量来调用函数，此外还可以将某个实际上是函数的东西定义为一个变量，这些操作都仍然可以编译为 Ruby，但是实际上这个做法应该是被禁止的；</li> <li>我将去探索如何直接将代码编译为机器代码，我觉得这将是一件非常有趣的事情。</li> </ul> <p>此外：</p> <ul> <li>没有合适的标准库。我现在正在借用 Ruby 的标准库；</li> <li>注释不起作用（我知道肯定会有朋友希望我构建一个禁止编写注释的编程语言）；</li> <li>没有 Lambda 表达式的概念，如果 Lisp 当中没有 Lambda，那么这会很奇怪的；</li> <li>表达式当中只能包含一个简单的表达式，因此函数体目前必须是纯函数。目前没有办法说打印一个值，然后再调用另一个函数。</li> </ul> <p>首先是： <strong>不要为了一次会议的演讲而真的去动手开写一个编译器！</strong> 这里面的工作量真的太大了。除非你想在自己的职称当中加上一个：编译器工程师。</p> <p>对编译器进行测试是非常必要的，因为我没必要写一个一次性的玩意儿，只在第一次用的时候才工作正常，随后就报废了。</p> <p>Swift 当中进行字符串解析真的是件折磨人的事情。Unicode 大法好，但是这也使得解析源文件之类的事情变得无比的困难。</p> <p>错误消息也是一个很难的事。这看起来很简单，但是要报告 为什么在解析的时候这个地方出现了错误、发生了何种错误真的非常难，此外我该如何表达？「您在这里遗漏了一个右括号？」</p> <p>我所希望使用的 LLVM API 是专门为类型语言设计的，从中我们可以推断出这个变量的类型是 Int32 ，或者这个函数存在函数签名。</p> <p>实现属于自己的编程语言是很有趣的，同时也很有意义。在我的 Github 上，我实现了一个属于自己的编程语言。不过实际上，那些能够实际使用的编程语言远远比我上周所做的那些玩意儿要厉害得多，因为它们是人们花费了大量时间、经历和技术所完成的。因此，后面如果我想抱怨 Swift 不能做什么的时候，我想我可能会更好地理解 Swift 开发人员的心情。因为这玩意儿实在是太难了。</p> <h3> </h3> <p> </p> <p>来自：https://realm.io/cn/news/tryswift-samuel-giddins-building-tiny-compiler-swift-ios/</p> <p> </p>