date: 2024-11-28

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

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

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

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

要澄清一个误解或科普一个常识，编程语言源码本身不能运行，需要依附某个平台来运行。 打个比方，可以把CPU看作是终极解释器，源码是0和1的机器码数组，然后CPU会提取, 解码, 执行。 在这层面，机器码本身可以看作是编程语言，但是单纯的机器码本身是不能运行的。 如同Jacquard织布机的打孔卡本身也不能织出相应花纹的布。

为了可以让源码运行，我一般管这叫实现这个编程语言。(implementation of a language)

让源码可以运行至少有几个办法。 编译源码相应的机器码，然后让CPU执行。 其次，用机器码写一个解释器，可以直接执行源码的那种。 当然，你也可以颅内计算lambda calculus, 那你就是那个解释器。

这些支持编程语言运行的东西都叫runtime system。 So, programming language + supported platform + system = programming language system。这也是为什么chez scheme的介绍是

Chez Scheme is both a programming language and an implementation of that language, with supporting tools and documentation.

利用以上的知识,请问python是不是解释型语言?

不全然是。如同java, lua, python官方实现会编译python源码去bytecode,然后有专门的虚拟机解释执行。 区别在于python执行是会自动编译然后直接执行。 也能看到同个编程语言可以有多种不同实现，LLVM的clang和GCC都是C语言的实现。

所以要理解一个程序的行为，也需要理解其运行时系统的行为，包括链接，加载。同样，设计和实现一个编程语言，同时也要实现运行时系统。

起手式

源代码语言是scheme, 用scheme实现编译器，编译器目标平台是32位的i386 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一样快，因为我编译器没做什么优化，可以更快编译完。

建议

如果想要入门编程语言设计，我强烈推荐EOPL。

EOPL特色是以解释器来研究语言语义，实现，设计。 其次，EOPL涵盖很多重要技巧：树遍历解释器，自由变量分析, lexical addressing, defunctionalize, 类型系统，类型推导，CPS, 蹦床。

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

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

我类型系统启蒙是出之于EOPL。实际上，TAPL类型论课本也推荐前置知识可以学习EOPL。 TAPL书上的各种解释器，在我学了EOPL后, 我可以更加得心应手，直接手撸一个类型系统来实验。

结论

为什么写一个自举的编译器?

难道不是为了装X

初衷是想要了解计算机如何运行。

我也好奇如何自己可以从零手搓一个(build something from scratch), 也好奇以前人们如何bootstrap他们的实现。 就是想要了解一下一种奇怪魔法：先有鸡，还是先有蛋的魔法

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

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

可以自举的编译器需要更高完成度，也是对实现编译器的一种integration testing。如果能自举，代表编译器功能足以应付更复杂功能。

最主要是享受创造的乐趣。

后日谈

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

拓展