协程、生成器与 call/cc 的控制流

· · 科技·工程

上期回顾

光剑系列的第三作！前两篇：

第一篇：Let's build our mathematics by using lambda calculus && church encoding!

第二篇：惰性求值、无穷流与发生的魔法

前言与一个震撼的 demo

在上一篇文章中，我们探讨并实现了惰性求值与无穷流。希望你们还对自然数流印象深刻。

自然数流也可以视为一个不断生成新的自然数的生成器。那么，从这个意义上，我们有更简洁而强大的实现方式。

（还是一贯的 scheme 代码）

(define (nature-gen return)
  (let loop ((i 0))
    (set! return
          (call/cc
            (lambda (state)
              (return (cons state i)))))
    (loop (+ i 1))))

(define nature-numbers

  (let ((k nature-gen))
    (define (tmp-interface)
      (let ((result (call/cc k)))
        (set! k (car result))
        (cdr result)))

  tmp-interface))

这就是一个自然数的生成器！每次调用 nature-numbers，它都会返回一个新的自然数。

> (nature-numbers)
0
> (nature-numbers)
1
> (nature-numbers)
2
> (nature-numbers)
3
> (nature-numbers)
4

正文

上面的代码虽然简短，但是相当晦涩。下面我们将一步步解开它的秘密。

生成器：可以“暂停”的函数

我们在文章开头用那段晦涩的 Scheme 代码创造的东西，用一个更广为人知的术语来说，就是一个 “生成器” (Generator)。

你可以把它想象成一个特殊的函数，它有一种超能力：可以在执行到一半时对自己喊“停！”，然后把一个值“扔”给调用者。当调用者下次再来找它时，它能从上次喊停的地方“满血复活”，继续执行。

其实，这个概念对很多程序员来说并不陌生。Python 中的 yield 关键字就是实现生成器的经典方式，我们开头的 nature-numbers 就等价于下面这段 Python 代码：

def nature_gen():
    i = 0
    while True:
        yield i
        i += 1

回顾我们上一篇文章的无穷流，你会发现它惊人地相似！每次我们从流中取出一个数，计算就会“产出”一个结果，而“剩余的无穷计算”则被巧妙地冻结了。这正是生成器的思想：执行、产出、暂停、等待下一次恢复。

协程：控制权的对等转移

生成器这种“暂停-恢复”的模式，其实是一种更通用、更强大的编程思想的体现，那就是协程 (Coroutine)。

普通函数调用是“主仆”关系：主函数调用子函数，子函数必须执行完毕并返回，控制权才能回到主函数。这就像经理给员工派活，员工必须做完才能交差。

而协程之间是“对等”关系。它们就像两位正在对弈的棋手。你走一步，将控制权（棋盘的使用权）交给我；我走一步，再把控制权交还给你。任何一方都可以主动让出控制权。

看到这里，你应该明白了：生成器，正是一种非对称的协程！ 它在 yield 时将控制权交还给主程序，主程序下次调用时又将控制权还给它，让它从断点处继续。

那么，真正的问题来了：这种“控制权的任意转移”是如何实现的？我们要怎样才能在代码中抓住“控制流”这个看不见摸不着的东西，让它暂停，又让它在未来某个时刻精确地恢复呢？要铸造这柄控制流的光剑，我们需要一种终极材料——续延。

续延：捕获程序的“未来”

想象一下，当程序执行到某个特定点时，我们按下了“暂停”键。此时，“程序接下来要做的所有事情”，就是我们所说的 “续延” (Continuation)。 它就像一个包含了程序未来的“时间胶囊”。比如在这段 C++ 代码中：

int foo(int x) {
    x++;
    x *= 3; // <- 按下暂停键
    x <<= 1;
    return x;
}

在注释标记的那一行，续延就是“把当前 x 的值左移一位，然后返回结果”。它封装了当前计算剩下的所有步骤。 续延，就是协程暂停时需要保存的那个“断点”的精确描述。 如果我们能拿到这个“断点”，并能在之后随时回到这里，协程的实现不就迎刃而解了吗？

call/cc：铸造控制流的魔法棒

在 Scheme 中，call/cc (全称 call-with-current-continuation) 就是这样一个强大的魔法，它能将抽象的“续延”概念物化成一个我们可以操作的实体。 它的作用正如其名：捕获当前的续延，并将它作为一个函数参数，传递给你指定的另一个函数。

(call/cc
  (lambda (k)  ; k 就是被捕获的续延
    (k 3)))

k 就是那个“时间胶囊”，一个代表了“未来”的函数。它和其他函数一样，是一等公民。 当你调用 k 并给它一个参数（例如 (k 3)）时，奇迹发生了：程序会立刻放弃当前的所有计算，瞬移回 call/cc 被调用的那个时间点，并将你给的参数 3 作为整个 call/cc 表达式的返回值。因此，上面表达式的值就是 3。 更神奇的是，这个“时间胶囊”可以被保存起来，反复使用！

(define saved-k #f)
(let ((result (+ 1 (call/cc (lambda (k)
  (set! saved-k k) ; 把“时间胶囊”存起来
    5)))))
  (display result) (newline))
;; 第一次执行，call/cc 返回 5，所以 result 是 6，打印 6
;; 现在，如果你在 REPL 中调用 (saved-k 100)
;; 程序会瞬间回到 let 表达式中，仿佛 call/cc 刚刚返回了 100
;; 于是 result 变为 101，并再次打印 101！

这个例子完美地展示了 call/cc 的威力：它不仅能逃出当前的计算，还能让我们在未来任何时候，都能像《命运石之门》一样，一次又一次地回到过去，并带着新的“世界线”参数（返回值）继续执行。

这样的强大工具可以用于构建任意控制流，也包括协程。你可能已经发现了，协程归还控制权时保存状态可以用续延简单实现。更具体地，我们可以直接返回协程内部用 call/cc 捕获的续延！然后再次调用协程时调用那个续延。

庖丁解牛：深入代码的魔法核心

现在，我们手握 call/cc 这柄能任意切割、重塑程序时间线的光剑，是时候回到最初那个令人惊叹的 demo，像一位精准的外科医生一样，剖析其运作的每一个细节了。

整个结构分为两部分：作为“协程引擎”的 nature-gen，以及作为“用户接口”的 nature-numbers。我们将模拟一次完整的“生成-暂停-恢复”流程来理解它们。

第一步：协程引擎 nature-gen 的内部构造

nature-gen 函数是生成器的核心。它的设计精妙之处在于一场“双续延之舞”。

(define (nature-gen return)
  (let loop ((i 0))
    (set! return  ; 3. 更新“出口”，为下次恢复做准备
          (call/cc
            (lambda (state) ; 1. 捕获“内部断点”
              (return (cons state i))))) ; 2. 带着“断点”和值，从“出口”返回
    (loop (+ i 1))))

让我们分解这支舞蹈的三个关键舞步：

  1. state：捕获“内部断点” call/cc 在这里捕获了它所在位置的续延，我们称之为 state。这个 state 就是我们心心念念的“时间胶囊”，它精确地封装了 nature-gen 暂停时的一切：位于 loop 循环内，变量 i 的当前值，以及接下来要执行 (loop (+ i 1)) 这个步骤的“未来”。

  2. return：从指定的“出口”返回 return 参数是什么？它并不是一个普通的变量，而是主调程序（nature-numbers）的续延。可以把它想象成一个传送门，调用 (return ...) 就会立即将控制权和括号里的值一起“传送”回主调程序。 所以 (return (cons state i)) 这行代码的意义是：

    • 将我们刚刚捕获的“内部断点” state 和当前要产出的值 i 打包成一个 cons 对。
    • 通过 return 这个“出口”，将这个包含了“未来”与“现在”的包裹，交还给主调程序。 至此，nature-gen 的一次“生成与暂停”就完成了。

  3. set!：为下一次“恢复”更新出口 set! 语句是整个机制能反复运行的关键。当主调程序下一次要“恢复”协程时，它会提供一个新的“出口续延”。(set! return ...) 的作用就是将 nature-gen 内部记录的 return 更新为这个新的出口。否则，如果下次恢复时还使用旧的 return，程序就会陷入真正的时间循环，回到上一次调用的状态，那将是一场灾难！

第二步：接口 nature-numbers 的封装艺术

如果说 nature-gen 是精密的引擎，那么 nature-numbers 就是驾驶舱，它负责启动引擎、处理引擎返回的状态，并为下一次启动做好准备。

(define nature-numbers
  (let ((k nature-gen)) ; `k` 是状态存储器，初始为引擎本身
    (define (tmp-interface)
      (let ((result (call/cc k))) ; 使用 call/cc 来启动或恢复引擎
        (set! k (car result))     ; 保存引擎返回的新断点
        (cdr result)))            ; 返回生成的值
    tmp-interface))

让我们来追踪 (nature-numbers) 的前两次调用：

就这样，每一次调用 nature-numbers，控制权都在主调程序的续延（return）和生成器的续延（k/state）之间进行一次优雅的交换。k 保存着协程的“过去”，而 call/cc 在调用时则提供了“未来”的去向。这正是协程——控制权的对等转移——最深刻、最本质的实现。一道看似简单的代码，背后却是控制流的绝妙魔法。

展望：光剑出鞘，协程的应用场景

我们已经铸造了这柄名为续延的控制流“光剑”，并用它剖析了协程的内在机理。那么，这件强大的武器在真实的软件世界里，究竟能用来解决哪些棘手的问题呢？

协程最广阔的战场，无疑是异步编程，尤其是处理网络请求、文件读写等 I/O 密集型任务。在传统的同步模型中，程序发起一个网络请求就必须“傻等”结果返回，CPU 在此期间完全被浪费。而协程就像一位技艺高超的厨房总管，他让一个任务去烤箱里“烤蛋糕”（等待网络响应），然后无需原地等待，立刻转身去“切菜”（处理其他计算），当烤箱叮咚作响（I/O 完成）时，他又能无缝地回来，继续完成蛋糕的装饰。这种非阻塞的模式极大地提升了程序的并发能力和资源利用率。今天，无数现代语言中的 async/await 语法，其背后正是协程思想的优雅体现。

除了异步 I/O，协程还在许多领域闪耀着光芒：

总而言之，从我们这个小小的自然数生成器出发，我们窥见的是一种强大的编程范式。协程让我们能够用更符合人类直觉的、线性的方式，去编写本质上非线性的、并发的程序。它将复杂的控制流管理隐藏在优雅的 yield 或 await 之下，让开发者能更专注于业务逻辑本身。

这柄曾经只属于 Scheme、Lisp 等“魔法师”语言的“光剑”，如今已成为现代软件开发中不可或缺的利器。