编程中的绝妙创意：生成器和延续

在这篇文章中，我将总结我从尝试更深入地理解编程中的两个重要概念中学到的东西：Python 的生成器和 Scheme 的延续。目的不是教授 Python 或 Scheme 编程。相反，我想要做的是证明生成器是一个更强大的构造的特例 - 延续。延续允许程序员发明新的控制结构，它是构建迭代器、生成器、协同程序和许多其他有用结构的基础。我发现从更深入和更广泛的延续角度理解生成器的工作原理非常有用。延续在编程语言理论中已经很成熟（它是在 70 年代引入的），但它的使用还没有成为主流。但是，我怀疑在云计算和大数据时代，惰性求值变得越来越重要，延续会变得更加突出，就像函数式编程中的许多其他概念一样。我认为值得你花时间在你的周边视觉中为这个概念保留一个位置。对于那些不熟悉 Scheme 的人：Scheme 是最古老的编程语言之一：LISP 的一种相对现代的方言。 Scheme 是一种极简但极富表现力的语言，这使其成为试验高级编程概念的理想工具。这就是为什么 Scheme 经常被用作教授计算机科学的工具，以及编程语言研究人员的游乐场。延续并不是 Scheme 独有的，但 Scheme 是第一种将延续视为一流实体的语言，从而使它们易于操作。这是探索延续的最自然的场所。在 Python 中，生成器主要用于使复杂的循环更易于编写和维护。这就是为什么它们是迭代器的特殊情况。在像 c 这样的传统语言中，for 循环如下所示： 第一行指定要迭代的数字序列。第二行是我们想用这些数字做什么。使用 Python 中的生成器，我们可以像下面给出的示例一样编写这种类型的循环。在其中，我们使用 squared_ints() 生成器一个一个地产生一个平方整数序列，然后使用 sum_of_squares() 函数将它们累加，直到总和大于程序员指定的界限： def squared_ints()： ''' Infinite generator Return i^2 for i = 1, 2, ... ''' i = 1 while True: yield i *i # 正是这个 yield 使这个函数成为一个 generator i += 1 def sum_of_squares( bound): ''' 返回大于界限的平方整数的最小总和 ''' g = squared_ints() s = 0 for i in g: # 迭代生成器 gs += i # 如果 s >bound，则累积总和 s : # 如果 s 大于 n 则退出循环 return s squared-ints() 的定义看起来像一个常规函数，但是 yield 关键字的存在使它成为一个生成生成器的函数 [1]。在生成器 g 上使用 next() 函数，我们可以看到数字是一一生成的。生成器与 Python 中的循环配合得很好。在 sum_of_squares() 中可以看到一个例子，我们用 for 循环迭代生成器。

让我们回顾一下到目前为止我们取得的成就。在 c 风格的循环中，序列的生成和消耗是紧密耦合的。然而，在上面的 Python 代码中，它们被分解为两个独立的实体。由于生成器可以构建在其他生成器上，因此您可以将复杂的生成器进一步分解为更简单的生成器链。这使得复杂的循环更加模块化和可重用，因此更易于编写和维护。另一个改进是生成器代码没有对序列的长度设置限制。理论上是无限的。生成的序列的实际长度由消耗该序列的代码决定。这意味着生成器代码可以尽可能通用，将计算效率留给消费者。在生成序列中的下一个项目的计算成本很高的情况下，这种“懒惰”是非常可取的。所有这一切都可以通过一个关键字收益实现！这很神奇，不是吗？发生的情况是，每次调用 yield 时，函数的状态都会被冻结，并且控制流连同生成的值一起交给调用者 [2]。下一次调用生成器时，控制流返回到生成器的冻结状态。对于复杂的行为来说，多么简单而优雅的语法！这就像魔术。然而，我的一部分（也许是我的理论家）对编程语言中的神奇行为感到不舒服。 yield 如何从函数定义中创建生成器（即生成器类的对象）？为什么在语言的其他地方没有发现这种魔法？为什么不能在函数外调用 yield？此外，生成器提供了一些用于制作协程的工具——并发编程中的一个主题。货币与迭代有什么关系？由于所有这些行为似乎都以一种特别的方式与产量相关联，我倾向于按照惯用的方式编写生成器，遵循熟记的配方而不考虑幕后的重型机械。我总是有一种唠叨的感觉，有一个我看不到的更大的图景。那时我意识到我以前曾在不同的上下文中阅读过类似的想法。当我在大学学习编程时，我有一份 Springer 和 Friedman 所著的 Scheme 和编程艺术。有一章是关于“延续”这个神秘概念的，在那里讨论了所有这些东西。我跳过了整章，因为我无法理解延续有什么好处。也许是时候重新审视这个话题了。在我们继续讨论延续之前，请放心，Scheme 中提供了 Python 风格的生成器。它们不是语言本身的一部分，但是通过准标准库（即 SRFI-158）中的 make-coroutine-generator 函数，前面讨论的 squared-ints 生成器可以在 Scheme 中编写为：（定义 squared- ints ;;; squared-ints 是一个函数 (lambda)，它生成一个生成器 ( lambda() ( make-coroutine-generator ( lambda ( yield) ( let loop (( i 1)) ) ;;; 定义递归函数“循环”它增加了 i，从 1 ( yield ( * ii)) ( loop ( + i 1)))))))(define g (squared-ints)) 开始；;;制作一个生成器，将其赋值给“g” 这看起来不像 Python 代码那么优雅，但逻辑几乎相同 [3]。这里的不同之处在于，Scheme 中的 yield 不是嵌入到解释器中的保留关键字。相反，产生控制的机制是通过操纵“延续”来实现的——这是语言的基本构建块，表示待执行的计算步骤。事实上，make-coroutine-generator 只是一个由大约 10 行代码组成的常规 Scheme 函数。它可以由任何有能力的 Scheme 程序员实现，无需太多工作。这怎么可能？神奇的是在 make-coroutine-generator 中使用 call/cc（代表“当前继续调用”）。请注意，此代码中没有任何内容涉及特殊的类或关键字。 make-coroutine-generator、yield 和 g 都只不过是常规函数。这就是为什么我们通过像函数一样调用它来请求下一个值：

Scheme 生成器的美妙之处在于该库没有引入新的实体类，因此生成器可以与语言的其余部分无缝集成。简单地说，continuation 是一系列待执行的计算步骤。例如，0 + 1 + 2 在 Scheme 中表示为 (+ 2 (+ 1 0))。从0的角度来看，会发生的事情是将1加到它，然后将2加到结果中。因此，在此上下文中 0 的延续是这两个加法。 Scheme 的美妙之处在于延续不是一个奇特的构造。相反，它只是一个程序员可以轻松操作的函数。在这个例子中，延续就是 (lambda (x) (+ 2 (+ 1 x)))。它等价于 Python 中的 lambda x: x + 1 + 2。在 Scheme 中，我们可以使用一个名为 call-with-current-continuation（或简称 call/cc）的函数来捕获当前的 continuation，然后将其传递给不同的函数，该函数有时称为接收器。大多数编程语言没有这个结构，所以需要一点时间来适应它。考虑这个简单的接收器，它只是将延续存储在全局变量“c”中。 (定义 c #f) ;;;最初，全局变量 c 不存储任何内容（定义 store-continuation ;;; 定义一个函数 store-continuation ( lambda ( cc) ;;; 它接收一个 continuation ( set! c cc) ;;; 将它存储到全局变量 c 0 )) ;;;并返回 0 我们现在可以使用它来捕获 (+ 2 (+ 1 0)) 中 0 的延续： > c ;; c #f 中没有存储任何内容 > ( + 2 ( + 1 ( call/cc store-continuation))) 3 > c # <procedure ( continuation . results1887) >

(+2 (+ 1 (call/cc store-continuation))) 的返回值并不重要。重要的是，在call/cc调用之后，c变量存储了一个函数，就是我们捕获的continuation！我们看不到代码，因为它被编译了，但是我们可以验证它是有效的(lambda (x) (+2 (+ 1 x)))，因为当我们用一个数字调用c时，返回值是输入加 3。让我们使用 call/cc 做一些有用的事情。我们用它来实现Scheme中Python函数sum_of_squares()的逻辑。和以前一样，我们在循环中迭代生成器，累加总和，当总和大于某个界限时停止。 (define sum-of-squares ( lambda ( bound) ;;define (sum-of-squares bound) ( call/cc ( lambda ( break) ;; 定义一个接收者：首先捕获到break ( let (( g ( squared-ints))) ;; 使生成器 g ( let loop (( s 0)) ;; 定义递归函数（loop s），其中 s 是累加值（ let (( new-s ( + s ( g )))) ;; 计算新的累加值 ( if ( > new-s bound) ;; 如果新累加值大于 bound ( break new-s) ;; 退出循环 (loop new-s))) )))))));;否则，使用新的累积值继续循环 > (sum-of-squares 100) 140 在平方和函数执行任何操作之前，我使用 call/cc 来捕获延续，并将其分配给变量 break。请注意，在 Scheme 的语法中，这是函数的最后一步。因此，无论在何处调用，调用break都会立即存在有返回值的函数。在这个简单的示例中，这似乎并不太令人印象深刻，但这意味着如果您必须使用大型且深度嵌套的数据结构（例如，树或图），您可以优雅地进行编程递归，但能够在满足某些条件时立即放弃递归。这可以大大减少不必要的计算。有人将 call/cc 称为函数式语言的 GOTO 语句，但更好的表征是它是程序员创建核心语言中不存在的新控制结构的通用机制。使用 call/cc，可以构建所有形式的控制，包括异常、回溯和协程。由于不涉及魔法，如果您不喜欢它们的行为方式，您可以创建这些结构的自定义版本。还可以发明特定于问题域的新型控制结构。例如，在 Web 编程中，continuation 已被用于控制服务器应用程序的逻辑（请参阅此处）。请注意，我编写了上面的程序来反映 Python 代码的逻辑。有更好的方法可以在不使用递归或调用/cc 的情况下实现相同的目标。例如，在下面的例子中，我使用生成器库创建了第二个无限生成器 acc 来累加 gen 生成器中元素的总和，然后使用 generator-find 函数获取 acc 中第一个大于边界。这是链接迭代器以制作更复杂迭代器的示例。 ( 定义平方和 ( lambda ( bound) ( let* (( gen ( squared-ints) ) ) ;; 创建一个生成器 gen ( acc ( make-unfold-generator ;; 创建第二个生成器 acc ( lambda ( s) #f) ;; 无停止条件，使 acc 成为无限生成器 ( lambda ( s) s) ( lambda ( s) ( + s ( gen))) ;; 从 gen 0))) 累积下一个值 ;; 从0 ( generator-find ;; 在 acc 生成器中找到第一个大于 bound 的值 ( lambda ( s) ( > s bound)) acc))))

在上一节中，我们使用 call/cc 来中断迭代生成器的循环。让我们用 call/cc 来实现生成器本身。为了实现它，我们需要一种机制来让步——在函数正常结束之前退出它。我们已经看到它是如何完成的。现在，我们需要一种机制，可以在函数产生后恢复函数。不难看出我们需要两个延续。 (define squared-ints ( lambda () ( let* (( break #f) ;;; 将存储一个继续以中断函数 ( resume #f) ;;; 将存储一个继续以在屈服后恢复 ( yield ; ) ;; 定义函数 "yield" ( lambda ( value) ( call/cc ;;; 捕获当前的延续 ( lambda ( r) ( set!resume r) ;;; 将它存储在 "resume" ( break value))) ))) ;;; 和 break out ( lambda () ;;; 将返回一个函数（一个闭包）（ call/cc ;;; 捕获当前的延续...（ lambda ( cc) ( set!break cc) ; ;; ...并将其存储在“break”中（如果 resume ;;; 如果此生成器之前已被调用...（ resume '()) ;;; ... 恢复它（ let loop (( i 1) ) ;;; 否则，循环 i=1, 2, 3, 4... ( yield ( * ii)) ;;; 产生 i 的平方 ( loop ( + i 1))))))))) )(define g ( squared-ints)) > ( g) 1 > ( g) 4 > ( g) 9 我从 Vasilij Schneidermann 对 SRFI-158 库的实现中稍微修改了这段代码（完整源代码见这里）。对于那些不是专业 Scheme 程序员的人来说，这看起来有点吓人，但逻辑非常简单：对于循环中的每个数字 i，首先将计算的未来存储到一个名为 resume 的内部变量中，然后将 break 继续调用为我们之前已经完成了存在的功能。下一次调用生成器时，调用 resume continuation，它将前进到循环中的下一个数字。请注意，在上面的代码中，我们将生成器作为没有参数的函数返回。我们可以轻松地向函数添加一个参数，以便在迭代开始后将消息发送到生成器。例如，我们可以修改代码，使得 (g 'reset) 将重置迭代。由于生成器只是 Scheme 中的函数，因此可以通过常规函数调用自然地与生成器进行通信。在 Python 中，您也可以向生成器发送消息，但它需要使用 yield 关键字的特殊语法和生成器类的 .send() 方法。同样，在 Python 中使用生成器是惯用的，在幕后发生了很多事情。我本来打算详细介绍协程，因为 Python 的生成器教程和 Scheme 的延续教程都倾向于以协程结尾（多有趣！）。但是，我决定反对这个想法，因为它会使讨论脱轨到一个不同的领域。但是非常简单，Python 中的 yield 通常被表示为编写生成器的简化方法，但它所做的，暂停函数的执行并具有恢复它的能力，是一个比迭代更通用的概念。它使一个例程可以做少量工作，然后将控制权交给另一个例程，从而允许它们并发运行。这使数据能够由例程网络处理，而不必将其组织为线性管道。它比迭代更灵活、更强大。换句话说，虽然生成器用于迭代，但产量不一定是。 Scheme中的故事要简单得多。由于 Scheme 中的实体不是按类分层组织的，因此您不会有使用主要为迭代而设计的类来实现协程的尴尬。在 Scheme 中，协程和生成器只是以不同方式操作延续的普通函数。

我写这篇文章主要是为了总结我学到的新东西。我也把它作为艺术欣赏的练习。很多人喜欢谈论他们为什么喜欢一首歌、一部电视节目或一部小说。我希望看到更多的文字来阐明为什么一个想法是优雅的、强大的或聪明的。 Scheme 是一种极简主义的不寻常语言。它的设计者希望它具有高度的表现力（意味着可以简洁地表达复杂的逻辑），同时又尽可能简单。这只能通过在少数强大的想法上构建语言来实现。一个强大的想法的范围并不窄。一个强大的想法对自己保持真实，但是当它与其他强大的想法结合使用时，就会出现新的功能。这就是表现力的来源。表达这种魔力的一种诗意方式（由于约翰麦卡锡）是它几乎感觉语言是被发现而不是被发明的。一旦掌握了它，就很难想象如何以任何其他方式设计一种语言，因为如果没有其他组件，每个组件似乎都是不完整的。我显然是这种哲学的粉丝。然而，我对强大的想法更难掌握这一事实并不视而不见。续集很难理解，也很难写。在上完大学编程课这么多年后，我仍然在考虑延续这一事实应该告诉你一些关于达到纯粹 lambda 启蒙的幸福状态所需的奉献水平。这让我想到了 Python。正如我之前所说，我的极简主义者被发电机背后隐藏的机械所困扰。但是使用 yield 关键字，任何人都可以在 10 分钟内学习习语并开始使用生成器。它可能不像 continuation 那样强大，但它足够强大，可以很好地与循环融合，使复杂的循环更容易编写。这是一个美丽的想法。最后，我不得不回到Scheme。 Python 生成器的美妙之处在于，yield 是强大思想的最小接口。您可能对 Scheme 的延续和宏有同样的看法。通过 call/cc 和define-macro，程序员可以访问解释器的机制，从而消除了编程和元编程之间的界限。关于这个主题已经写了很多，所以我不会在这里重复（参见这里），但解析（可通过宏访问）和执行控制（可通过 call/cc 访问）基本上是解释器所做的。我对解释器的 API 如此之少感到惊讶。那个好漂亮。 [1] 在函数定义中使用 yield 并不是在 Python 中构建生成器的唯一方法。请查阅有关生成器的任何一般教程。 [2] 更准确地说，yield 在函数中创建了一个生成器，它在定义中出现 yield 的地方暂停执行。这个特征更难阅读，所以我会写得好像 yield 实际上做了屈服。语法的目的是创造这种错觉。 [3] 请注意，递归是 Scheme 编写循环的首选方式。创建生成器不是必需的。由于这是尾递归的一种形式，Scheme 解释器会自动将递归转换为循环。