从CPS转换看代数效应的编译器实现

代数效应（Algebraic Effects）作为一门源自编程语言研究的特性，正在逐步进入主流开发者的视野。与异常处理相比，它的核心突破在于可恢复性—— 当代码执行到某处需要外部处理时，它并非终止并抛出，而是暂停、等待处理、然后继续。这种机制在概念上类似于 "可恢复的异常"，但其底层实现依赖于编译器层面的 continuation 捕获与控制流重组。

本文从编译器实现的角度，解析代数效应的核心机制，并探讨如何在 JavaScript 这类没有原生支持的语言中通过 CPS 转换与 Generator 实现 polyfill 方案。

核心机制：Continuation 捕获与 Resume 语义

理解代数效应的关键在于理解 continuation。在直接风格（Direct Style）编程中，函数的 "剩余计算" 是隐式的 —— 当函数返回后，调用者继续执行什么由调用者决定。而在代数效应中，这个 "剩余计算" 被显式地捕获为一个可调用的对象。

当代码执行perform EffectName时，运行时会做三件事：

1. 捕获从 perform 位置到最近try/handle块结尾之间的所有代码，打包成一个 continuation
2. 跳转到对应的 handler，将 effect 值和 continuation 一并传递
3. Handler 可以选择调用resume with value来恢复执行，此时 continuation 被调用，程序流回到 perform 位置，并且 perform 表达式的返回值就是 handler 提供的 value

这种机制与异常处理的关键区别在于：异常一旦抛出，调用栈被展开，局部变量销毁，无法回到抛出点；而代数效应保留了完整的执行上下文，handler 可以决定如何继续。

编译器实现：CPS 转换原理

实现代数效应的标准编译技术是将代码转换为Continuation Passing Style（CPS）。CPS 是一种中间表示形式，其核心规则是：

• 每个函数接收一个额外的next参数（continuation）
• 函数不通过return返回结果，而是调用next(result)
• 所有函数调用都处于尾位置（tail position）

以一个简单的加法函数为例，直接风格是：

function add(x, y) {
  return x + y;
}

转换为 CPS 后：

function add(x, y, next) {
  const result = x + y;
  return next(result);
}

对于代数效应的实现，CPS 的价值在于显式化控制流。当代码执行perform effect时，在 CPS 表示中这被转换为：捕获当前的next作为 continuation，然后将其与 effect 一起传递给 handler。Handler 接收到 continuation 后，可以选择立即调用它（resume）、延迟调用（异步 resume）、多次调用（回溯）、或者不调用（中止）。

这种转换使得原本隐式的控制流变成了显式的数据 ——continuation 就是一个普通的函数值，可以被存储、传递、延迟执行。编译器通过这种转换，将语言层面的高级抽象降级为宿主语言（或目标机器码）可以执行的低级操作。

JavaScript Polyfill 方案：Generator 模拟实现

由于 JavaScript 没有原生支持代数效应，社区探索了多种 polyfill 方案，其中最可行的是基于Generator的实现。

Generator 函数天然具备 "暂停 - 恢复" 的能力。当 Generator 执行到yield时，它会暂停并将值传递给调用者；当调用者执行next(value)时，Generator 从暂停点恢复，并且yield表达式的返回值就是传入的 value。这与代数效应的perform/resume语义高度吻合。

一个简化的 polyfill 模式如下：

function* getName(user) {
  let name = user.name;
  if (name === null) {
    name = yield { type: 'ask_name' }; // perform effect
  }
  return name;
}

function runWithHandler(genFn, handler) {
  const gen = genFn();
  
  function step(value) {
    const result = gen.next(value);
    if (result.done) {
      return result.value;
    }
    // 处理effect
    const effect = result.value;
    const resumeValue = handler(effect);
    return step(resumeValue); // resume with
  }
  
  return step();
}

在这个方案中：

• yield扮演了perform的角色，暂停执行并向上传递 effect
• Generator 的next()方法扮演了resume with的角色，恢复执行并注入值
• 中间层的runWithHandler负责路由 effect 到对应的 handler 并管理恢复流程

这种方案的限制在于函数颜色问题：所有可能使用 effect 的函数都必须声明为 Generator 函数，调用它们的方式也与普通函数不同。这与原生代数效应 "无函数颜色" 的理想特性有差距，但在实际工程中是可接受的折衷。

工程实践：何时使用与性能考量

在 JavaScript 生态中，代数效应 polyfill 适合以下场景：

1. 依赖注入与测试隔离 将 IO 操作（文件读写、网络请求、日志记录）抽象为 effect，业务代码只声明 "需要什么" 而不关心 "如何实现"。测试时可以注入 mock handler，无需修改业务代码。

2. 可组合的错误处理 不同于 Promise 的 catch 链，effect handler 可以嵌套组合。外层 handler 可以捕获内层未处理的 effect，或者将内层 effect 重新解释为自己的语义。

3. 异步与同步的统一 如果 handler 选择异步 resume，调用者无需知道这一点 —— 中间函数不需要标记为 async。这解决了 JavaScript 中 async/await 的传染性问题。

性能考量：

• CPS 转换会增加函数调用开销，因为每个函数都需要传递 continuation
• Generator polyfill 在 V8 中有良好优化，但频繁的yield/next循环仍有成本
• 对于 CPU 密集型任务，CPS 可能导致调用栈深度问题（尽管 CPS 调用都是尾调用，但 JavaScript 引擎并非都实现了尾调用优化）

与 React Suspense 的关系

React 的 Suspense 机制在概念上受到代数效应的启发。当组件执行数据读取时，如果数据未就绪，React 会 "暂停" 该组件的渲染，等待数据获取完成后恢复。Dan Abramov 指出，这类似于代数效应的perform/resume语义，只是实现方式受限：React 通过抛出 Promise 并在将来重新渲染来模拟恢复，而非真正的 continuation 捕获。

Hooks 也可以被视为一种受限的 effect handler：useState可以看作perform State，React 作为 handler 提供状态管理。这种视角帮助理解为什么 Hooks 有调用顺序限制 —— 它实际上是隐式的 continuation 管理。

结论

代数效应代表了控制流抽象的一个重要方向。通过 CPS 转换，编译器将 "可恢复的计算" 这一高级概念降级为可执行的代码；通过 Generator polyfill，JavaScript 开发者可以在今天就开始实验这些思想。

虽然原生支持代数效应的语言（如 Eff、Koka、OCaml multicore）仍在发展中，但其核心思想 —— 将控制流显式化、可组合、可拦截 —— 已经在 React 等主流框架中得到了验证。对于编译器开发者而言，掌握 CPS 转换与 continuation 管理是理解现代语言特性的关键；对于应用开发者而言，理解这些概念有助于更好地利用现有框架的抽象能力，并预判语言演进的趋势。

参考来源

1. Dan Abramov, "Algebraic Effects for the Rest of Us", overreacted.io, 2019.
2. Yassine Elouafi, "Algebraic Effects in JavaScript part 1 - continuations and control transfer", GitHub Gist.

compilers