Fun for Fun

我发起了一个从 0 开始制作编程语言的项目 fun for fun. 该项目使用 OCaml 实现了一个编译器(称为 ff 编译器), 可以把一个 OCaml 的子集编译到可以 C++ 源程序 (生成程序只用到了 C 的语法), 该 C++ 程序可以被进一步编译为可执行文件.

为什么又一个编译器教程

为什么又又又一个关于编程语言实现的教程?

并不是已有的教学项目不够好/不足够, 现在高质量的编译器教程非常多(可以直接看最后一节看我的推荐目录). 之所以发起一个新的编译器教学项目, 主要有以下几方面的原因:

实现一个编译器真的很有趣: 我最开始是只是对 OCaml 的类型系统(主要是模块系统)的检查很感兴趣, 只是想着实现一个类型系统以加深一下自己的理解. 在完成类型系统的实现后, 每次只是想再往后再走一小步, “不知不觉"就完成了一个到 C++ 的后端, 正如这个项目名称 Fun for Fun, 这件事情太有趣了使我一有时间就忍不住不做;
向前辈学习: 现在的高质量编译器教学项目确实很多, 这些优秀的教程已经帮助我少走了很多弯路. 作为一个已经从前辈们的教学项目受益良多的人, 我认为不仅有必要学习他们传播的知识, 还有必要学习他们无私共享的精神, 我希望能通过文字说明和代码演示展示我对知识的理解和学习的过程, 让未来的学习者也能少走一些弯路;
与人沟通对理解深刻的知识是很有帮助: 知识的理解, 从最 看懂书本/论文上的介绍 到 能在实践中根据需要运用自如, 是需要一个过程的, 对于一些比较深刻的知识, 这甚至可能是一个长期的过程. 通过给别人讲解, 可以帮助我站在多个角度重新思考问题, 从而加深我对知识的理解, 让我离事物的"本质"更进一步.

首先要推荐的是已经被很多人推荐过的 SICP (Abelson and Sussman 1996). 这本书的前半部分尝试教会读者: 如何在程序中建立抽象, 如何基于已有的抽象建立新的抽象. 后半部分介绍了在编程语言实现中常见的抽象.

抽象是这本书的主题(我一连说了 3 个抽象), 一方面也暗示了这本书描述的内容十分的抽象(即使书里有演示代码), 另一方面也暗示了建立可靠&可组合的抽象对实现编程语言的重要性.

我很庆幸当时听了知乎人的建议, 在"生涯早期"就学习了这本书, 如果有时间, 我希望我能重读一遍.

注: 如果你和我一样在第一次看书时无法理解书上的内容, 公开课视频也许会有帮助, 因为公开课中的学生也许和我们有着一样的问题, 他们有可能会在课上帮我们把问题提出来.

todo

语言常见的两种实现模式: 编译和解释(Language and Interpreters). 对于编译实现, 很多人推荐学习龙书来学习, 但是我在费力的理解了书上的定义以后仍然云里雾里, 不知道实现一个编译器到底应该干嘛, 没能通过这本书学会编译原理.

TIoFPL 这本书给了我答案: 编译其实就是一个函数, 把一个语言的源程序映射至另一个语言.

一个函数式编程语言的实现贯穿着整本书, 这本书把这个足够复杂的函数式编程语言映射到足够底层的语言(X86 汇编).

最关键的是, 书中几乎看不到龙书里那样复杂的算法描述, 而是用很多个简单的函数来描述语言之间的映射, 每个函数做的事情都很少, 因此很容易验证它们正确性. 这些函数环环相扣地组合到一起变成一个大的函数, 这个大函数可以把源语言映射到目标语言, 整个过程相当精彩.

之前的书都没有解析将解析(parsing)的内容, 有人说如果对 parsing 感兴趣可以看龙书, 我认为但是龙书的严谨程度和清晰程度都不如这本计算理论导引, 龙书parsing相关章节中的结论很多, 但是结论的证明是很少的, 取代证明的是大量的算法, 例子和演示.

我更喜欢计算理论导引的讲解方式: 只有少量的结论, 但是这些结论都通过严谨的推导得出. 而这些证明有的时候可以成为理解问题的关键.