编译器

https://github.com/taimoon/scheme-compiler 关于一个业余如何另辟蹊径，作弊，逆练功法以及一些心得 前传 实际上，在真正写可以自举的编译器之前，我写了至少两个编译器，以及无数个解释器。 第一次，nand2tetris project写hack处理器汇编器，VM汇编器，Jack编译器。当时我还很懵懂，掌握不到其中的办法论。 第二次，IU Compiler课程学写python优化编译器，包括寄存器分配，尾递归，闭包。 这课程对我影响深远，让我找到适合我这种业余的办法论。 某天，看到某博客的编译器教学， https://generalproblem.net/lets_build_a_compiler/01-starting-out/。 得以让我可以不依赖教学提供的工具，写一个“hello world”式编译器来作为开头。誒，万事开头难啊。 可惜，那位博客并没有更新更多内容，不过博客主要参考Abdulaziz Ghuloum的“An Incremental Approach to Compiler Construction”论文，所以我以同样论文作为我主要参考，继续我的开发。 如果读者对其他语言编译器教学实现有兴趣，但又循序渐进式地实现，可以参考可自举C编译器实现 https://github.com/rui314/chibicc。 那位大大也有相关博客 https://www.sigbus.info/how-i-wrote-a-self-hosting-c-compiler-in-40-days。 办法论 前提提要,前文说到IU Compiler课程对我影响深远是因为… 首先，IU Compiler课程设计继承至Abdulaziz Ghuloum的“An Incremental Approach to Compiler Construction”论文。 核心是incremental, 循序渐进式来学习编译器实现。 你的征程始于一个可以打印整数的编译器。 好了，你已经有了一个编译器，然后一点一点扩展你的编译器。 每一次的提交都要确保之前测试都能通过，还有新测试，以保证你的编译器可以work。 换一种说法就是你会写很多个编译器，厉害吧？给自己鼓掌；听懂，掌声！ 其次，IU Compiler课程采用对新手非常友好的nanopass架构。 在nanopass架构下，编译器会同过多个pass一步一步变换源码直到输出最后汇编，而每一个pass只做非常简单的事情。 比如一个pass来做free variable分析, 下一个pass才做闭包变换，然后下一个pass才限制函数参数。 这是一个很好办法论：如果一个编译步骤太难，就拆开成两个步骤。 可能有的同学会说，这不是会造成多次遍历，更长编译时间？ 新手嘛，更何况我一个业余，主打能work就可以，不寒碜。酷炫的东西比如SSA, 输出LLVM IR, 寄存器分配, 优化可以以后再打算。 不过，别灰心，nanopass被认可的工业优化编译器实现方式。 (详见:A nanopass framework for commercial compiler development) nanopass framework的chez scheme编译是可以非常快哒。传说，chez scheme几秒内就可以完成自身编译。 新手嘛，主打一个能work就好。 Parser generator我又不是很会，pratt parser, parser combinator, 就不明觉厉的感觉。 考虑到什么ambiguous grammar, associativity, precendence, 等等等， 让我手写parser可能会要我的命。 解析难的语言比如有layout syntax的haskell, python, 更不要说C++这种怪物， 自然不会是我考虑范围内。...

我们在上一篇文章中，描述了一个通用的优化技术： 找到时间差，把数据分成已知跟未知，并且用代码表示后者。 但是，这种做法有两个问题： 0 - 你需要费时费力去整这个东东，而且不是所有时候都能刚刚好复用代码。 1 - 如果我们预先不知道应该怎么区分呢？甚至，如果这是动态的呢？假设我们先接受一半的数据，等一会，然后接受另一半，那我们如何用上述的技巧？难不成把所有可能的分法都预先写一遍？ 所以，我们希望把上述技术，staging，自动化掉，使得程序员不再需要去关心之。 我们应该怎么做呢? 我们先从最基本的开始，先决定要操作的语言吧： type expr = | Var of string | Int of int | Add of (expr * expr) | Mult of (expr * expr) 这个语言，简单到了极点，只剩下+跟*两个操作了。别担心，我们会一步步扩展这个语言。 module ENV = Map.Make(String) let rec eval (e : int ENV.t) : expr -> int = function | Var v -> ENV.find v e | Int i -> i | Add (x, y) -> eval e x + eval e y | Mult (x, y) -> eval e x * eval e y 这是一个标准的definitional interpreter实现，中规中矩，并没任何出彩的地方。...

我们先从一个很简单的算法，快速幂，开始看起吧： let rec quick_mod x y m = if y = 0 then 1 else if y mod 2 = 1 then (x * (quick_mod x (y - 1) m) mod m) else quick_mod ((x * x) mod m) (y / 2) m let example_0 = quick_mod 10 1000 3 显而易见，10的n次方除3都会余1： utop # example_0;; - : int = 1 这个算法试图在y很大的时候，算(x^y) mod m。 很明显，这个算法只会进行log y次’*然后mod’的操作 - 我们把这个操作定义为⊕吧。 我们去深入思考一下 - 为什么本来要进行y次⊕，现在，我们只需要进行log y次⊕？...

有趣的CS已经很久没动了。有外因跟内因。 外因是一直在忙，忙着准备OOPSLA的talk，忙着给talk，OOPSLA过后忙着做下一个project，就慢慢把这个忘了 内因是因为知识消耗得差不多了 - 有趣有用而且没基础本科生又能听懂的接近PL的内容。。。实在不怎么多 但是最近要给一些关于Partial Evaluation的talk，所以就随便写点吧。

什么是Tail Call？ Tail Call（尾调用）指，我们调用一个函数后，立刻返回。 def triple(x): # 返回的不是函数 return x * 3 def is_tail_call(x): # 是尾调用，因为我们调用后就返回了 return triple(x) def not_tail_call(x): # 不是尾调用，因为我们调用完还要1 + result return 1 + triple(x) def half_tail_call(x): # 外面的是尾调用，里面的不是 return triple(triple(x)) 在以上例子中，is_tail_call的triple，跟half_tail_call的外面的triple，是tail call。 为什么Tail Call很重要？ 因为Tail Call提供了很好的优化。 假设我们是register machine，return address存在一个register里面，如果我们tail call，我们需要：把argument放对位置，然后goto function就可以了！ 如果是non tail call，我们需要把argument放对位置，保存旧的return address（比如说塞上stack），设定return address为下一行，goto function，把旧的return address restore掉，然后该干啥干啥。 这样，我们额外的多做了一push一pop，space & time overhead一下子上来了，怪不得60~70年代的人不肯用函数。。 当我们递归的时候，不做这个优化导致了big O上的空间差距 - 一个要不停的push stack，一个说，stack是啥？ 另一点是，当递归的时候，argument的位置是对的，‘放对位置’这一步就没有了，于是就成为了一个goto self - 也就是loop。 尾递归优化，其实就是Tail Call Optimization在taill call self下的优化。（见Debunking the ‘Expensive Procedure Call’ Myth, or, Procedure Call Implementations Considered Harmful, or, Lambda: The Ultimate GOTO）...