. 初入编程语言理论

迷上程序语言理论的契机、它的复杂度来源,以及初学者的入门路线.

程序语言理论(PLT)大概是我人生中少有的、能让我持续感兴趣的东西. 它对我的吸引力不太像“一门学问”,更像一种手感: 手里有一套可以自己制定的规则,再设法让这套规则在某个地方真正跑起来. 这篇文章想聊我迷上它的契机、它的难点,以及今天重新入门会走的路线.

1 从简陋的计算器说起

起点是我用 Rust 写的计算器. 它简陋到只有四个运算符,加上括号,能跑. 但当我第一次意识到 1 + 2 * 3 1 + 2 * 3 不该按从左到右解释时, 就撞上了第一堵墙:运算符优先级. 为了越过它,我读了 matklad 的 Simple but Powerful Pratt Parsing, 第一次知道原来“解析”本身是一门可以设计、可以品味的技艺: 每个运算符有自己的结合力,前缀、中缀、后缀各有一套处理方式, 几十行代码就能支撑起可扩展的表达式文法. 那大概是我第一次感受到“抽象”带来的直接快感.

后来我在 JVM 上折腾了一段时间. JVM 对动态语言相当友好:反射、字节码生成(ASM 与 ByteBuddy)、 动态代理、成熟的即时编译(JIT)与垃圾回收(GC),全都现成. 于是我给 Minecraft 服务器写了一些领域特定语言(DSL), 让服主可以用接近自然语言的方式描述规则. 也是从这里开始,我接触了后端优化: 同样的逻辑换个写法,性能有时会差一个数量级; 原因往往藏在 JIT 对这段代码的内联、逃逸分析与去虚拟化之中.

再往后是偶然的连锁反应. 我在尝试对柯里化函数做部分应用时,冒出一个念头: 与其每次调用都重新组合参数,不如在编译期尽量把已知的部分算出来. 顺着这条线,我遇到了部分求值与 Futamura 投影, 又遇到了多阶段编程(如 MetaOCaml 与 LMS), 再往下就是计算作用,以及描述它们的静态作用系统、 建模它们的单子(Monad)、解释它们的代数作用处理器…… 每一样都通向更大的世界,我至今也没走完.

上了大学之后,能自由折腾的时间突然变少了. 大一为了应付作业,我读了 Abelson 与 Sussman 的 Structure and Interpretation of Computer Programs (《计算机程序的构造和解释》,简称 SICP), 然后用 C++ 写了 Scheme 解释器, 那大概是我第一次完整走完“读语法 → 求值 → 打印”这一圈. 这学期我选了一门编程范式的课,又写了半个学期的 Haskell, 大作业是用 Haskell 写解析器组合子,突然就找回了当年那种感觉.

1.1 吸引我的地方

在 PLT 里,你既是规则的制定者,又是规则的囚徒: 设计一套语言之后,必须接受自己设计出来的一切后果, 包括那些在设计时根本没想到的交互. 这种“造物”与“遭造物反噬”之间的张力,对我有很强的吸引力. 别的工程把抽象当作工具,PLT 则把抽象本身当作研究对象.

2 复杂度从哪里来

我设计过不少语言的规格,但几乎每一次都因复杂度过高而作罢: 它增长得比预想的快得多. 好在这两年有了大语言模型,可以帮我填补生产力空洞: 只要把想法讲清楚,就能很快得到能跑的实验原型. 但“能跑”和“设计得对”之间,仍然隔着整个复杂度问题.

2.1 语言特性的组合

语言设计的第一步,往往是决定“我要哪些特性”. 这一步很像做排列组合:你希望某些特性之间发生奇妙的化学反应, 或者为了专攻某个方向而特意引入某些特性, 例如 Rust 的仿射类型与生命周期、Haskell 的类型类、Lisp 的宏. 把这些特性两两摆到一起,大致会看到几类关系.

正交的特性彼此独立,可以放心叠加. 例如词法作用域与垃圾回收、闭包与模式匹配、泛型与模块系统; 它们各自解决不同维度的问题,组合起来几乎不产生额外语义. 协同的特性单独看平平无奇,合起来却能涌现出新能力: 闭包与 GC 让高阶函数变得廉价, 类型类与单态化让“零成本抽象”成为可能, 模式匹配与广义代数数据类型(GADT)支持类型安全的结构化求值, 代数作用与定界续延让“可恢复的计算”成为一等公民. 这类组合是设计语言时最值得追求的东西.

冗余与重叠出现在同一个目的有多种相互重叠的表达方式时, 硬塞在一起就可能让语言出现“两套并行的世界观”. 例如 Monad 与代数作用处理器都可用于建模与组织副作用: Monad 通常以库抽象的形式组织计算, 代数作用处理器用处理器解释作用操作; 后者既可以作为语言特性,也可以编码成库,两者在语义上有紧密联系. 再如异常与 Result Result / Either Either 、 null null 与 Option Option 、类与类型类、宏与泛型. 冗余本身不致命,但它会让用户不断面对“我该用哪个”的选择疲劳, 也会让两套机制的交互成为缺陷的温床, 因为任何一处改动,都得把所有组合重新考虑一遍.

冲突的特性单独看都很好,放到一起却语义打架,或者直接导致理论上的不可判定. 例如子类型与多态、类型推理的组合会增加复杂度, 某些具体系统存在不可判定性,但仅凭子类型与记录或列表并不能推出这个结论; MLsub 与 Simple-sub 就支持子类型、记录和 ML 风格的全局类型推理. 又如类型推理加特设重载会让“最具体实例”的选择变得病态; 宏如果不满足卫生性,会污染调用处的作用域; 线性类型与“可随意复制”的默认语义天然对立. 面对这类组合,往往只能取舍,难以调和.

依赖指特性 B 的成立以特性 A 为前提. 例如 GADT 模式匹配需要能处理局部类型相等约束的检查规则,实际实现常借助显式标注; 高秩多态类型不同于高阶类型构造子,在 GHC 等实现中通常需要标注提供多态参数的类型. 若希望依值类型承担可信证明,并保证类型检查中的计算终止, 就需要限制相关递归或验证其终止性,但不必要求所有程序都终止. async async 与 await await 则需要支持挂起与恢复的机制: 状态机变换是常见实现方案之一,也可以借助续延传递风格(CPS)、栈式协程或作用处理器. 识别真正的依赖关系、区分它们与实现选择,才能排出合理的实现顺序.

此外还有不可组合的情况:两套机制根本不在同一套假设下, 例如一等续延与某些 C 外部函数接口(FFI)的栈约定.

2.2 交叉点、盲点与处理方式

选好特性只是开始. 真正的复杂度来自交叉点:𝑛 个特性最多有 𝑛( 𝑛−1 )/2 个两两交互, 数量只是二次增长; 如果考虑所有包含至少两个特性的子集,则共有 2 𝑛−𝑛−1 种可能组合, 数量是指数增长的. 组合数量并不等于实际设计复杂度,还要看哪些特性真正发生交互. 你在设计 A 和 B 时都想到了各自的情况, 却没想到 A 的某个角落和 B 的某个角落会撞在一起.

盲点很难在纸面上直接看出来,往往要靠几种实践暴露: 做形式化,写出操作语义,或者在 Coq(现名 Rocq)、Agda、Lean 里做机械化证明,代价最高,也最彻底; 写测试,像 WebAssembly 的规格测试那样用大量程序去撞边界; 亲自自用,拿这门语言写非平凡的程序,乃至自举,把“设计者视角”换成“用户视角”; 或者动手实现原型编译器,让类型检查器和求值器替你发现矛盾.

发现盲点之后,处理手段也集中在几条路上. 可以直接限制,禁止出问题的组合,例如规定“泛型不能作为数组长度”,用报错换一致性; 可以做规约,把一种特性脱糖成另一种,只保留一套语义内核,例如把 for for 脱糖成 while while 、把 async async 脱糖成状态机; 可以分层,把两套机制放到不同的层级,规定谁能看见谁,例如把宏展开限定在编译期,把作用的静态描述与检查放在作用系统里,再由生成的代码或运行时机制实现对应行为; 也可以引入新构造,承认已有特性不够表达,加专门的正交构造来承担交叉点; 还可以限制自动推导,要求必要的类型标注以采用可判定的检查算法;若检查或子类型判定本身不可判定,则标注也未必能解决,必须另行说明限制哪些规则、如何处理无法完成判定的输入.

发现并处理这些盲点,基本上就是 PLT 研究的日常,也是语言设计复杂度的来源.

3 语言设计的抽象

面对迅速增长的复杂度,可以先借抽象把“语言设计”切成几段相对独立的层,再逐层讨论. 我个人习惯分成语法、中间表示、检查系统与运行时四层.

3.1 语法

这一层包含所有与“人怎么写、机器怎么读”有关的设计: 具体语法与抽象语法、运算符优先级与结合性、 缩进与换行规则、语法糖、宏与卫生性、错误恢复.

语法层看起来浅,却很容易积重难返: 随手加的语法糖,可能会让后续所有解析都变得含混. 经验法则是:让语法糖尽量可脱糖; 每引入一种简写,都要能说清楚它脱糖后的核心形式是什么.

3.2 中间表示

这一层包含从抽象语法树(AST)到字节码之间的所有表示及其转换: 脱糖、A-正规形式(ANF)、CPS、静态单赋值形式(SSA)、 三地址码、闭包转换、单态化、内联、优化遍.

中间表示(IR)的设计与降级流程会深刻影响语言实现: 惰性求值常用延迟块(thunk)或闭包实现,但不要求每一级 IR 都保留显式的节点; 保证尾调用不增长调用栈,需要编译流程与目标平台的配合; 可恢复的作用处理器需要相应的续延或挂起与恢复机制, 而普通的状态修改、I/O 等副作用不需要这样的机制. 许多语言最终卡在从核心语义到低层代码与运行时的转换上,问题并不出在语法或类型系统. IR 正是落实语言语义的桥梁.

3.3 检查系统

“类型系统”只是这一层的一部分,所以我更愿意叫它检查系统. 它负责拒绝那些不该通过的程序,通常在编译期完成,必要时也可以推迟到运行时. 常见的类型系统有 Hindley–Milner(HM)、F 系统、依值类型、线性与仿射类型、精化类型; 实现时可采用双向类型检查,这是一种检查的组织方式,与 F 系统这类演算分类处在不同维度. 作用系统处理作用标注、作用行、作用多态等; Monad 可用于建模作用,代数作用处理器是解释作用操作的机制,两者不等同于静态作用系统, 有处理器的语言也未必静态跟踪作用(例如 OCaml 不静态保证所有作用都得到处理). 此外还有 Rust 那套基于区域与借用的所有权与借用检查、 全函数式编程一脉的终止性与全域性检查, 以及针对纯度、可序列化性、并发安全性等性质的静态检查.

这一层始终在表达力、可推导性、错误信息的可读性与实现复杂度之间取舍,四者很难同时兼顾.

3.4 运行时

这一层包含程序跑起来时的一切: 内存管理(GC、自动引用计数 ARC、区域等)、副作用管理、 求值策略的实现(按值调用、按需调用、按名调用)、并发与并行模型、 FFI、解释执行与 JIT. 提前编译(AOT)是运行前的编译方式,属于编译流程; 它生成的代码仍可能依赖运行时支持. 线性与仿射类型则是静态约束,可以帮助编译器安排资源释放,自身并不充当运行时内存管理算法.

在我看来,这一层最工业化、最繁杂. 入门课程会覆盖其中一些概念,但生产级运行时的工程细节很难在一门课里讲透; 它也是决定一门语言能否落地的重要因素.

4 学校的 PLT 教育

学校里的程序语言教育没有统一的配方: 有的课程偏重编程范式、类型系统与语义,有的偏重编译器实现. 后一类课程常从词法分析与语法分析开始,继续讲语义分析、IR、优化与代码生成. 例如 UNSW 的研究生课程 COMP9102、 Stanford CS143、 CMU 15-411; 此外,还有 Robert Nystrom 的 Crafting Interpreters 这样的实践教程. 这些资料涵盖了目标代码生成之外的诸多环节: CS143 包含类型检查、运行时组织与垃圾回收, 15-411 包含内存管理和运行时组织, Crafting Interpreters 更会带你手写字节码虚拟机、调用栈、闭包与 GC. 编译器课程只是程序语言教育的一部分,不能代表全部本科 PLT 教学.

生产级运行时之所以很难在入门课程里讲透,一方面是因为课时有限,而这些内容涉及大量复杂的工程权衡; 另一方面,确实有不少现成的基础设施可以复用. 把自己的语言编译到 LLVM IR,就能利用它的优化与机器代码生成, 但 LLVM 本身不提供垃圾收集器, 更不自动提供完整的语言运行时; 编译到 WebAssembly(WASM)后,可以交给浏览器或其他引擎执行; 编译到 JVM 字节码,则可以利用成熟的 JIT 与 GC. 如果目标是低成本验证语言设计,优先复用现成后端和宿主运行时比从零手写生产级实现切合实际得多.

至于检查系统,也不能指望选定后端就自动得到. 你可以复用现成的类型系统设计、推导算法或实现框架, 但它仍必须和语言语义严丝合缝,能报出人看得懂的错误, 并在表达力和可推导性之间取舍. 所以类型系统、作用系统这一层仍需要自己学、自己权衡,也是我最想花时间补齐的一块.

5 给初学者的建议

给刚进入 PLT 的新人,我首先建议保持语言实现的低成本. 有现成的工具就用,不要重复造无意义的轮子. 解析器这一块想手写也行,毕竟复杂度没那么高; 但后端还是先复用 LLVM、Cranelift 等工具,或选择 WASM、JVM 字节码这类目标, 别一上来就自己写机器代码后端.

同时,把大目标拆成一组最小语言. 当你想要把 A、B、C、D 这些特性组合到一起、却对每一个都不熟悉时, 先分别实现 A、B、C、D 四个最小语言, 各自只保留支撑该特性的最小核心,然后再尝试把它们合体. 这样每个小语言都能在一两天内跑起来,完成目标带来的满足感可以支撑你继续往下走; 等到把它们合体时,你又会亲手撞上那些交叉点,比在纸上空想直接得多.

5.1 入门路线示例

如果目标是设计一门自己用起来很舒服的编程语言,可以按这样的顺序推进: 先从语法开始,不必急着上手写解析器,先用 ANF 的形式把核心语言的语法与求值规则写清楚;ANF 把求值顺序显式化,让你没法用“反正运行时知道”来糊弄自己. 接着选定 IR,沿着“树遍历解释器 → ANF / CPS → 字节码”的路线先跑通再优化,不必一上来就做 SSA. 类型系统可以从简单类型 λ 演算起步,先把双向类型检查写顺,作用系统留到后面再碰. 最后在后端与宿主运行时上尽量复用成熟的基础设施,同时明确记下仍需自己实现或适配的语言语义与运行时支持.

6 运行时的“草台”方案

语言实现还有一种听起来粗糙、但在工业界广泛应用的做法: 直接编译到某个成熟语言的源码上,即源到源编译. 它可以复用目标语言的工具链,有时也能复用其运行时,但二者有所区别. 例如 Koka 把程序编译成 C 或 JavaScript; TypeScript、CoffeeScript、Elm、PureScript、Reason 与 ReScript 编译到 JavaScript; Nim 编译到 C、C++ 或 JavaScript; Haxe 编译到多种目标语言; Idris 2 借助 Chez Scheme 后端运行; Cython 把 Python 的方言编译到 C. 甚至可以直接生成 Java 源码再交给 javac javac ,虽然不够优雅,却能立刻用上 JVM 的 JIT、GC 以及整个生态.

另一条路是生成中间表示或字节码: 生成 LLVM IR、QBE 的 IL 或 Cranelift 的 CLIF, 或者生成 WASM、JVM 字节码、.NET CIL、Erlang BEAM、Lua 字节码, 交给相应的后端或执行引擎. MLIR 则是支持多种方言与逐层降级的 IR 框架,用来组织这些转换,本身并非现成的运行时.

这里要分清两种复用:复用后端可以减少优化和机器代码生成工作; 复用 JVM、JavaScript 引擎、Chez Scheme 这样的成熟宿主运行时, 可以进一步减少内存管理和执行引擎工作. LLVM、QBE、Cranelift 只是编译器后端,编译到 C 也不自动获得 GC 或作用处理机制. 无论采用哪条路,都能让自己把精力放在语言真正独特的部分,同时专心实现或适配源语言特有的语义.

1关于抽象与分层的边界,可参见 Ray Eldath 的 计算机领域的三个重要思想:抽象,分层和高阶 中“有关分层”一节.

归根结底,PLT 的乐趣在于设计语言,没必要每次都从寄存器分配器写起.

7 延伸阅读

文中出现的英文术语与缩写,可在 术语对照 中检索:

结合力
binding power
部分应用
partial application
部分求值
partial evaluation
多阶段编程
staging
代数作用处理器
algebraic effect handler
定界续延
delimited continuation
一等续延
first-class continuation
高秩多态类型
higher-rank type
高阶类型构造子
higher-kinded type
缩进与换行规则
offside rule
精化类型
refinement type
作用行
effect row
全函数式编程
total functional programming
源到源编译
source-to-source compilation

进一步阅读的材料包括:matklad 的 Simple but Powerful Pratt Parsing 是我接触解析的起点; Robert Nystrom 的 Crafting Interpreters 从树遍历解释器写到字节码虚拟机,是很扎实的入门实践; Harold Abelson 与 Gerald Jay Sussman 的 Structure and Interpretation of Computer Programs (《计算机程序的构造和解释》)堪称抽象的第一课; Benjamin C. Pierce 的 Types and Programming Languages (《类型和程序设计语言》)是类型系统的标准教材. 关于计算作用,可以结合 Daan Leijen 等人的 Koka(把代数作用与 Perceus 引用计数做进真实语言)、 Jeremy Yallop 等人整理的 Effects Bibliography, 以及对照同一种作用在几十种语言或库里写法的 Effects Rosetta Stone.