Continuation 与 call/cc

前言

好久没碰函数式相关的内容了，这篇文章想总结一下我学习函数式编程时对 call/cc 的疑惑与理解。要理解 call/cc 完全离不开 continuation——continuation 是概念，call/cc 是利用这个概念的函数。文章里也会聊一些我认为是理解它们的关键点。

看完这篇你会发现：原来 Java 的异常本质上就是 call/cc。

Continuation

continuation 的字面意思就是”延续”，指当前过程剩下未执行的部分（或者说剩下的流程）。脱离语境讲清楚 continuation 有点难，这里用一个 Python 的例子来类比：

def normal_add(a, b, c):
    s1 = a + b
    s2 = s1 + c
    return s2


def gen_add(a, b, c):
    s1 = a + b
    yield s1
    s2 = s1 + c
    yield s2
    return "done"

对于 gen_add 来说，第一次调用 next 会返回 s1，第二次返回 s2，第三次返回 done。而每一次 yield 之后没有执行的那部分代码，就是当前这一刻的 continuation。

yield 是针对返回的、只能一次性”暂停”的语法，可以看作是 continuation 的一种特殊形态。这样理解的话，continuation 本身其实不算难。

想继续深入 continuation 的话，还可以了解一下 CPS（Continuation-Passing Style）——它是一种和正常顺序流程很不一样的程序组织方式，在一些场景下能让控制流变得更简洁，而且和 call/cc 有直接关联：在 CPS 风格下，由于 continuation 是显式传递的参数，我们可以直接丢弃后续流程，所以不需要 call/cc；而在非 CPS 风格（直接风格）下，我们就需要 call/cc 来实现跳转，从而达到丢弃后续流程的效果。

顺便一提，continuation 是 Scheme 的一等公民（first-class），也就是说你可以把它保存，调用，作为参数。

call/cc

接下来是稍微难理解一些的 call/cc，全称 call-with-current-continuation。如果说 continuation 是描述”剩余流程”的概念，那么 call/cc 就是函数式语言中利用 continuation 来完成流程控制的函数。

call/cc 的作用是什么呢，简单描述：保存当前调用 call/cc 时的 continuation，并在后续被调用并传入值的时候跳转回那个位置，把传入的值替换到 call/cc 对应的位置上。表述有点绕，但有两个关键词：跳转和替换。

再用一个不太准确但直观的描述：“反选”。我们平时只能影响当前流程以及它向下调用的子流程，而不能影响当前流程的调用者；而 call/cc 反过来——它选中的是”当前流程的外侧”，也就是这里返回之后还要执行的那部分流程。

下面贴一段 AI 生成描述更严谨的定义：

把”调用 call/cc 这个表达式所处位置的 continuation”打包成一个一元函数 k；把 k 作为参数传给你写的 lambda；在 lambda 里：

如果你不调用 k，则 lambda 的返回值就是整个 (call/cc ...) 表达式的值（行为像普通函数）；

如果你调用 (k v)，整个程序会”跳回” (call/cc ...) 那个位置，并把 v 当作它的返回值，lambda 中后续的代码全部被丢弃。

来两段 Scheme 代码具体看看：

不调用 k

> (+ 1 (call/cc (lambda (k) 2)))
3

求值过程： (+ 1 (call/cc (lambda (k) 2))) → (+ 1 2) → 3

k 没被用到，(call/cc ...) 的值就是 lambda 的返回值 2。

调用 (k v)

> (+ 1 (call/cc (lambda (k)
                  (+ 2 (k 3)))))
4

求值过程（示意，不严谨）： (+ 1 (call/cc (lambda (k) (+ 2 (k 3))))) → (+ 1 (k 3)) → (+ 1 3) → 4

注意中间 + 2 这一步被整个丢弃了——因为调用 (k 3) 时，控制流直接跳回了 call/cc 所在位置，lambda 中 (k 3) 后面的代码再也不会被执行。

它要解决什么问题

那么 call/cc 究竟是为了解决什么问题呢？

考虑这样一个场景：在一段很长的流程中，某种特殊情况下我们需要中途跳出。如果不使用 call/cc，我们就必须让外层流程对这种”中途跳出”的情况层层做处理（一级一级把信号往上传）；而使用 call/cc，可以直接一步跳到目标位置。

此外，call/cc 还能用来实现协程（单线程模拟多任务、任务暂停与恢复）、生成器（类似 Python 的 yield，随着调用不断产出值）等等——它能实现控制流抽象的多种功能。

例子：求列表乘积

举个乘法的 Scheme 例子。需求是：求列表元素之积，遇到非数字返回 'error，遇到 0 直接返回 0（避免无谓地把后面的乘法都做完）。

使用 call/cc：

(define (product-with-cc lst)
  (call/cc
   (lambda (return)              ; return 是"逃逸续延"
     (let loop ((lst lst))
       (cond
         ((null? lst) 1)
         ((not (number? (car lst)))
          (return 'error))        ; 直接跳出整个 call/cc，返回 'error
         ((= (car lst) 0)
          (return 0))              ; 直接跳出，无需展开调用栈
         (else
          (* (car lst) (loop (cdr lst)))))))))

不使用 call/cc：

(define (product-without-cc lst)
  (cond
    ((null? lst) 1)
    ((not (number? (car lst))) 'error)
    ((= (car lst) 0) 0)
    (else
     (let ((rest (product-without-cc (cdr lst))))
       (if (eq? rest 'error)
           'error
           (* (car lst) rest))))))

可以看到，不使用 call/cc 时，我们必须显式向上传播 'error，递归的每一层都要多一次判断。在更复杂的流程里，这种”层层判断、层层透传”的代码会越积越多，每种异常情况都需要单独处理一遍。

其他语言中的类似控制

看到”向上传播 'error”这个场景，可能不少 Java Bros 已经想到异常了。我们来一个简单对比：

static int k(int v) {
    throw new Continuation(v);
}

public static void main(String[] args) {
    int innerResult;

    try {
        int kRet = k(3);
        innerResult = 2 + kRet;
    } catch (Continuation c) {
        innerResult = c.value;
    }

    int result = 1 + innerResult;
    System.out.println(result);
}

真相大白了——原来异常就是 call/cc 啊！准确地说，Java 的异常系统可以看作函数式里 call/cc 的一种受限特例：它只能向上跳（escape），不能像完整的 call/cc 那样把 continuation 保存下来反复调用。这种 call/cc 特例被 Java 做成了语言的基础特性，实用、流行、被广泛使用。

但这是有代价的：所有函数都需要额外思考”这里要不要处理异常”。有些语言就不愿意承担这个代价，宁愿保持函数的简洁单纯，比如 Go，引来的争议与战斗这里也无须赘述（不过 Go 又支持 goto，我也搞不清设计者是什么想法）。

总结

call/cc 就像一个爹，生出了好多儿子：Rust，JavaScript 的 async/awit，Python 的 yield，Java 的 Exception 等等，也能感觉出这些语法对于各自的语言来说并不是那么的”原生“，他们是新介绍的关键字，只针对这一种用法。

call/cc 就像是控制流的“原子”，而上述语法是为了安全性和性能（捕获完整堆栈开销极大）对原子进行的封装。如果你拥有完全体的 call/cc，你可以自己实现上述所有语法，但反之则不行，即使勉强实现也很别扭。

还没玩够想再深挖一下可以看看 call/cc 经典的阴阳问题，如下：

(let* [(yin ((lambda (foo) (newline) foo)
             (call/cc (lambda (bar) bar))))
       (yang ((lambda (foo) (display "*") foo)
              (call/cc (lambda (bar) bar))))]
  (yin yang))

continuation 与 call/cc