初入编程语言理论

我也问过自己很多次。答案大概是：PLT 是少数几个“你既是规则的制定者，又是规则的囚徒”的领域。你设计一套语言，然后必须接受自己设计出来的一切后果——包括那些你在设计时根本没想到的交互。这种“造物”与“被造物反噬”之间的张力，对我有近乎生理性的吸引力。

另一方面，它是少见的、把“抽象”当作第一公民的工程领域。别的工程把抽象当作工具，PLT 把抽象当作研究对象本身。

语言设计的第一步，往往是决定“我要哪些特性”。这一步很像做排列组合：你希望某些特性之间发生奇妙的化学反应，或者为了专攻某个方向而特意引入某些特性（Rust 的 affine type 与 lifetime、Haskell 的 type class、Lisp 的宏，都属于后者）。把这些特性两两摆到一起，大致会看到五类关系：

• 正交（orthogonal）：彼此独立，可以放心叠加。例如词法作用域与垃圾回收、闭包与模式匹配、泛型与模块系统——它们各自解决不同维度的问题，组合起来几乎不产生额外语义。
• 协同（synergy）：单独看平平无奇，合起来却能涌现出新能力。例如闭包 + GC 让高阶函数变得廉价；type class + 单态化（monomorphization）让“零成本抽象”成为可能；模式匹配 + GADT 让类型安全的结构化求值成为可能；algebraic effects + delimited continuation 让“可恢复的计算”变成一等公民。这类组合是设计语言时最值得追求的东西。
• 冗余 / 重叠（overlapping）：同一个目的有多种相互重叠的表达方式，硬塞在一起就可能让语言出现“两套并行的世界观”。例如 Monad 与 Algebraic Effect Handlers——两者都可用于建模与组织副作用：Monad 通常以库抽象的形式组织计算，algebraic effect handlers 通过处理器解释效果操作；后者既可以作为语言特性，也可以编码成库，两者在语义上有紧密联系；再比如异常与 Result Result / Either Either 、null 与 Option Option 、类与 type class、宏与泛型。冗余本身不致命，但它会让用户不断面对“我该用哪个”的选择疲劳，也会让两套机制的交互成为 bug 温床（毕竟任何一处改动，都得把所有组合重新考虑一遍）。
• 冲突（conflicting）：单独看都很好，放到一起却语义打架，或者直接导致理论上的不可判定。例如子类型（subtyping）与多态、类型推导的组合会增加复杂度，某些具体系统存在不可判定性，但仅凭子类型与记录/列表并不能推出这个结论；MLsub / Simple-sub 就支持子类型、记录和 ML 风格的全局类型推导；类型推导 + ad-hoc 重载会让“最具体实例”的选择变得病态；宏与卫生性（hygiene）如果处理不好，会互相污染作用域；线性类型与“可随意复制”的默认语义天然对立。这类组合往往必须“取舍”而不是“调和”。
• 依赖（dependent）：特性 B 的成立以特性 A 为前提。例如 GADT 模式匹配需要能处理局部类型相等约束的检查规则，实际实现常借助显式标注；高秩多态类型（higher-rank types，不同于 higher-kinded types）在 GHC 等实现中通常需要标注提供多态参数的类型。若希望依赖类型承担可信证明，并保证类型检查中的计算终止，就需要限制相关递归或验证其终止性，但不必要求所有程序都终止。 async async / await await 则需要支持挂起与恢复的机制，状态机变换是常见实现方案之一，也可以借助 CPS、栈式协程或效果处理器。识别真正的依赖关系、区分它们与实现选择，才能排出合理的实现顺序。

（也许还该补上第六类：不可组合（incompatible）——不是“打架”，而是根本不在同一个宇宙里，例如 first-class continuation 与某些 C FFI 的栈约定。）

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

盲点通常不会在纸面上暴露，而是在这些地方被抓出来：

• 形式化：写 operational semantics，或者在 Coq / Agda / Lean 里做机械化证明——代价最高，也最彻底；
• 测试：写一个足够大的测试套件或一致性测试（像 WebAssembly 的 spec tests 那样），用大量程序去撞边界；
• 自用：拿这门语言写一个非平凡的程序，最理想的是自举，把“设计者视角”换成“用户视角”；
• 实现：先写一个原型编译器，让类型检查器和求值器去替你发现矛盾。

发现盲点之后，处理手段大致也就那么几种：

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

“该怎么发现盲点、该怎么处理盲点”，基本上就是 PLT 研究的日常，也是语言设计复杂度的真正来源。

所有与“人怎么写、机器怎么读”有关的设计：具体语法与抽象语法、运算符优先级与结合性、缩进/换行规则（offside rule）、语法糖、宏与卫生性、错误恢复。

这一层看起来最“浅”，其实最容易积重难返：一个随手加的语法糖，可能会让后续所有解析都变得含混。经验法则是——让语法糖尽量可脱糖：每引入一个甜美的写法，都要能说清楚它脱糖后的核心形式是什么。

从 AST 到字节码之间的所有表示及其转换：脱糖、ANF、CPS、SSA、三地址码、闭包转换、单态化、内联、优化遍。

IR 的设计与 lowering 流程会深刻影响语言实现：惰性求值常用 thunk / 闭包实现，但不要求每一级 IR 都保留显式的 thunk 节点；保证尾调用不增长调用栈，需要编译流程与目标平台的配合；可恢复的效果处理器需要相应的 continuation 或挂起与恢复机制，而普通的状态修改、I/O 等副作用不需要这样的机制。很多语言最终卡住，不是因为语法或类型系统，而是因为从核心语义到低层代码与运行时的转换没有打通。总之一句话：IR 是落实语言语义的重要桥梁。

（也许该换个名字，因为“类型系统”只是它的一部分。）

它负责拒绝那些不该发生的程序——通常是在编译期，必要时也可以推迟到运行时：

• 类型系统：HM、System F、依赖类型、线性/仿射类型、refinement types；实现时可采用双向类型检查（bidirectional type checking），它是一种检查的组织方式，而不是与 System F 同层级的分类；
• 效果系统：效果注解、effect rows、效果多态等；Monad 可用于建模效果，algebraic effect handlers 是解释效果操作的机制，两者不等同于静态效果系统。有 handlers 的语言也未必静态跟踪效果，例如 OCaml 不静态保证所有效果都被处理；
• 所有权/借用检查：Rust 那一套 region + borrow 的静态分析；
• 终止性/全域性检查：total functional programming 这一脉；
• 其它静态性质：纯度、可序列化性、并发安全性……

这一层的关键词是“取舍”：表达力、可推导性、错误信息的可读性、实现复杂度，四者几乎不可能同时最优。

程序跑起来时的一切：内存管理（GC / ARC / region 等）、副作用管理、求值策略的实现（call-by-value / need / name）、并发与并行模型、FFI、解释执行与 JIT。AOT 是运行前的编译方式，属于编译流程；它生成的代码仍可能依赖运行时支持。线性/仿射类型则是静态约束，可以帮助编译器安排资源释放，但不是运行时内存管理算法。

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

如果让我给自己规划一条路线，大概是这样的——目标是设计一门自己用起来很舒服的编程语言：

• 从语法开始：不要急着直接上手写 parser，先用 ANF 的形式把核心语言的语法与求值规则写清楚。（ANF 的好处是把求值顺序显式化，让你没法用“反正运行时知道”来糊弄自己。）
• 选一个 IR：树遍历解释器 → ANF / CPS → 字节码，是最经典的递进路线。先跑通，再优化，不要一上来就 SSA。
• 选一个类型系统：建议从 simply typed lambda calculus 起步，先把 bidirectional type checking 写顺，再考虑 effect 系统——effect 系统可以先不碰。
• 把成熟的基础设施用起来：这一点后面单独说。优先复用后端与宿主运行时，同时明确列出仍需自己实现或适配的语言语义和运行时支持。