date: 2025-05-01

关于我如何写一个自举编译器的事情

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来做自由变量分析, 下一个pass才做闭包变换，然后下一个pass才限制函数参数。 这是一个很好办法论：如果一个编译步骤太难，就拆开成两个更简单的步骤。

可能有的同学会说，这不是会造成多次遍历，更长编译时间？ 新手嘛，更何况我一个业余，主打一个能work先最重要的精神，不寒碜的。酷炫的东西比如SSA, 输出LLVM IR bitcode, 寄存器分配, 优化可以以后再打算。没有下次

别灰心，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++这种怪物， 自然不会是我考虑范围内。

因此，我选择解析容易的scheme作为我源代码语言。毕竟要自举，scheme自然也是编译器实现的主要语言。 So this is scheme-in-scheme implementation。

科普：编程语言是如何运行的？

首先要澄清一个常见的误解：编程语言源码本身是不能直接执行的，它必须依赖特定的运行平台。

打个比方，CPU其实就是最底层的"解释器"。 当源代码被转换成由0和1组成的机器码时，CPU就会按部就班地完成取指、解码、执行这一系列操作。 从这个角度看，机器码本身也可以说是一种编程语言。 比如同一串机器码在不同CPU架构下可以不同的解读 - 光有机器码是跑不起来的，就像 Jacquard 织布机的打孔卡片，单有卡片可织不出花纹来。

要让一个编程语言源码可以运行起来，我个人通常称之为"实现一门编程语言"(implementing the language)。具体来说有几种常见方式：

这些支持编程语言运行的东西都叫runtime system。

那我问你，python是不是解释型语言?

不是。python官方CPython实习会自动一步完成所有步骤：编译源码输出字节码，然后交给虚拟机解释执行； just python that is it。相比之下，java用户就得先编译javac再java运行。

同个编程语言可以有多种不同实现，LLVM的clang和GCC都是C语言的实现。

所以，要实现一个编程语言，不仅要搞定编译器，运行时系统也要一并考虑。

起手式

源代码语言是scheme, 用scheme实现编译器，编译器目标平台是32bits的x86 CPU。 我编译器会把scheme源代码，变换输出汇编，然后用gcc的汇编器再编译成对应的机器码。开发时间至少一个人月。

开头，我需要写一个简单runtime, 至少可以打印程序结果。 这个runtime也可以作为loader, 里边才调用scheme_entry, 所以编译汇编结果是以scheme_entry作为起始。 比如这样

#include<stdio.h>

extern int scheme_entry();
int main(){
    int val = scheme_entry();
    printf("%d\n", val);
    return 0;
}

第一个编译器是这样的

(define (emit op . args)
  (apply format (cons op args))
  (newline op))

(define (emit-exp op e)
  (cond
    ((integer? e)
     (emit op "mov $~a, %eax" e))
    (else
     (error "emit-exp" "unmatch" e))))

(define (emit-file input-path output-path)
  (system (format "rm -f /tmp/a.s"))
  (let ((exp (read (open-input-file input-path)))
        (op (open-output-file "/tmp/a.s")))
    (emit op ".section .text")
    (emit op ".globl scheme_entry")
    (emit op "scheme_entry:")
    (emit op "push %ebp")
    (emit op "mov %esp, %ebp")
    (emit-exp op exp)
    (emit op "pop %ebp")
    (emit op "ret")
    (close-output-port op)
    (system
      (format "gcc -fomit-frame-pointer -m32 /tmp/a.s runtime.c -o ~a" output-path))))

(emit-file (cadr (command-line)) (caddr (command-line)))

测试架构很简单，用diff或者git diff比较输出结果如下

scheme --script compiler.scm lit.scm lit.out
./lit.out > res.txt
git diff res.txt ans.txt

话说，前端的解析器呢？我可以用原生的read来作弊，以后再写。 现在，我可以无耻地说我已经写了一个能work编译器，虽然只能打印整数。

自举需要什么？

原论文目标完成度只要求可以编译简单解释器。当然一个能work的编译器可以很简单; 刚刚的也算一个。 可以编译简单解释器又可以编译自身的编译器,需要考虑的事情就多了。

自举编译器至少需要支持

  1. separate compilation
  2. foreign function interface
  3. 文件输入输出
  4. 垃圾回收
  5. 尾递归

其他的，workaround应付即可。

separate compilation很重要

Separate compilation非常重要！开发到中期，你必须要设计你编译器可以分别编译，然后再链接的那种。 不然，每一次编译都要编译库然后才是源码，编译时间非常长，更别说测试时间。 我一版测试时间是几分钟。 蛋疼的是原论文没有强调separate compilation的重要性。 再来网上没几个教学实现separate compilation, 只能自己设计一个，不严谨，朴素的那种。

Naively, 我们可以假想我们系统顺序执行一个一个文件。依据这假想，来设计separate compilation。 然而，下个文件需要上个文件的函数，所以需要做“链接”。链接需要做符号解析。 为了链接得以可能，需要记录链接所需要的信息：那些是函数以及入口。

一版是会额外生成一个linker文件。再到二版，输出object files后，利用objcopy注入我定制的链接信息。 要链接编译的时候，我编译器会从每一个object读取链接信息，完成编译。 特点是可以整合几个object files为一个object file。

主意是这样的

;;; compile to object file
file-1.scm -> emit-obj -> file-1.o -> read-meta -> ((main-entry mian-1) ...)
file-2.scm -> emit-obj -> file-2.o -> read-meta -> ((main-entry mian-1) ...)

;;; when compile to executable
file-1.o -> read-meta -> ((main-entry mian-1) ...)
file-2.o -> read-meta -> ((main-entry mian-1) ...)
-> linking ->
main:
  <init>
  call mian-1
  call mian-2
  <epilogue>
  ret

函数调用

关于各平台函数调用规定，可以参考它们的ABI。 Rui这边https://github.com/rui314/psabi收录很多，可以在那边下载。 32位i386 Sys V函数调用规定压栈传参。 我只依据之前IU compiler的经验和Sys V规定来压栈传参，实现函数调用，又没仔细读论文关于函数调用的实现。

到了尾递归的时候就犯了难。

Sys V的压栈传参是先压参数，过后才压返回地址，再跳转到函数。

尾递归优化需要复制参数到同个位置。

如果没记错，当时运行会时不时抛出segfault, 总之会崩溃。

原来现代操作系统以及编译器实现return address protection,栈上面的返回地址不可改写的。 防止骇客通过改写return address,以便跳转执行他们的malware。 以此衍生各种防御技巧，比如shadow stack。 (类似文章：https://devblogs.microsoft.com/oldnewthing/20241018-00/?p=110385)

实际上，论文已经做好了workaround的铺垫，参数是压在返回地址的后面。 形象的说，在Sys V看来，我们是把参数当成被调用函数的locals, 跳转到“不需要参数”的函数。

IU Compiler的目标平台是64位CPU, 是寄存器传参。其中的workaround就是限制传参数量，多出来打包成tuple, 不压栈。 不过毕竟六个参数还是挺多的。

如何利用FFI来作弊

当你学会实现以及理解了函数调用，foregin function interface也是水到渠成事情， 然后可以开始作弊。

比如，搞不懂x86的div和mod？没问题，在runtime里面用C语言写一个，直接调用这个函数就可以。

比如，不想学posix的文件输入输出？没问题，我直接调用stdio的，就可以了。

比如，不想学make, shell scripting?没问题，我一手system+scheme来写脚本, 跑测试。

make还是值得学一学的。

垃圾回收

追踪式垃圾回收算法核心很简单, 但如何interface就很困难。 作为建议，第一步先实现stack walking(栈回溯), 打印所有栈上面的内存。 过后，才从stack walking函数改写成garbage collector。

实际上你需要帧指针做stack walking。 没有帧指针的栈回溯需要编译器额外支持，我这种菜表示把握不住。 这是原论文没提到的东西，也是Sys V ABI误导的地方。 Sys V ABI说ebp(or frame pointer)帧指针是optional, 不一定需要被实现。 我二版初期尝试不保存帧指针，到了栈回溯犯了难，结果我还是用上帧指针。

赋值是有用的

其中有一个pass是uncover-free, 需要给每个lambda函数标记所需要的自由变量。 目前我编译器这个pass还是会重新构造过AST的。 实然，与其重新构造，uncover-free就地更改lambda所需要的自由变量，就可以避免重新构造的开销。

我的优化就是没什么优化

实际上，我编译器跑测试时间可以跟chez scheme一样快，因为我编译器没做什么优化，可以更快编译完。

为什么要写一个可以自举的编译器

怎么判断你的编程语言可不可以驾驭更复杂的功能？或者你的编译器有没有隐藏很深的bug？

与其想破脑袋写好测试用例，不如来一个更有劲的：自举。用同一门语言写一个"能跑自己"的程序——自循环解释器或者自举编译器。 如果能成功自举，就证明你的编译器完全hold得住复杂功能，毕竟编译器本身就是最复杂的软件之一。自举是一个简单直接又彻底的集成测试。

建议

如果想要入门编程语言设计的同学们，我个人推荐EOPL。

这本书涵盖了编程语言设计的诸多核心技巧： - 树遍历解释器 - 自由变量分析 - 静态域优化 (lexical addressing) - defunctionalize - 类型系统和类型推导 - 续延传递风格(Continuation Passing Style, CPS) - 蹦床(trampoline)

CPS可谓是关键因为该技巧得以让你在不支持尾递归语言(比如python)中实现函数式语言，也是学习垃圾回收前置条件。

比如其中有一些有趣的习题，比如设计以及实现一个基于原型对象的语言(prototype based object, 类似lua, javascript的设计)。

结论

难道不是为了装X

初衷是要弄明白计算机是怎么运行的。

我也好奇如何自己可以从零手搓一个(build something from scratch)。

每一次的掌握都是一种赋能，或许可以暂时逃避未来可以让我攻坚更加的困难课题。

如果我没有先前的经验，接触到IU compiler, 反复炒EOPL的冷饭, 牺牲了无数个解释器POC, 再到后来那篇博客, 单凭论文我很难完成一个可以自举编译器。

后日谈

最近在研究how to compile with continuation, 论文上面的东西我没什么读懂。 而且原著好贵啊，望好心人可以赞助我白漂一本"Compiling with Continuation"。

拓展