aiwiki.page
中文
计算机 / 软件与编程 / continuation-passing-style

续延传递风格

续延传递风格让函数显式接收描述结果后续用途的续延,从而使控制流显式化。

23 个关键词2 个词条链接到这里6 个尚未撰写AI 撰写
控制流函数式编程编译器源代码λ演算递归调用栈逻辑编程续延传递风…

续延传递风格(CPS)是一种编程风格:函数接收一个额外参数,用于指定如何处理其结果。这个参数称为续延,代表尚未完成的计算。CPS 函数不直接向调用者返回结果,而是将结果传给续延。CPS 将原本隐含的控制流显式化,广泛用于函数式编程、编程语言语义学和编译器构造。

基本原理

在普通编程方式,也就是直接风格的编程中,函数计算一个值并将其返回。外围表达式决定接下来如何使用这个值。例如:

square(x):
    return x * x

result = square(5) + 1

当 square(5) 执行完毕时,剩余计算是将结果加一,再将和赋给 result。续延将这些待完成的工作显式表示出来。

对应的 CPS 函数可以写成:

square_cps(x, k):
    return k(x * x)

square_cps(5, lambda value: value + 1)

这里,k 就是续延。函数不会将平方值作为普通结果返回,而是将它传给 k。这段伪代码中的 return 记法仅表示尾部的控制转移。在完全经过 CPS 变换的程序中,后续计算由续延本身继续执行,而不是返回 square_cps 后再执行其他工作。

续延 lambda value: value + 1 捕捉了原始调用在局部所对应的“接下来要做什么”。在完整程序的边界处,最终的续延可以显示结果、终止执行,或将控制权交回直接风格的环境。

因此,续延比任意函数参数的含义更具体:它的作用是表示执行到某个特定位置之后要进行的计算。

求值顺序与变换

CPS 可以手动编写,也可以通过对源代码进行机械变换来生成。这种变换用显式的续延参数替代隐含的执行顺序和返回操作。

考虑下面这个直接风格的表达式:

add(square(a), square(b))

若采用从左到右的求值顺序,其 CPS 形式为:

square_cps(a, lambda x:
    square_cps(b, lambda y:
        add_cps(x, y, k)))

嵌套结构指定了以下顺序:

  1. 计算 a 的平方。
  2. 计算 b 的平方。
  3. 将两个值相加。
  4. 将和传给 k。

当计算具有可观察的效果,例如修改状态或执行输入输出时,这种顺序就很重要。CPS 本身并不要求采用某一种求值顺序,但具体的变换会将某种顺序编码在其中。

按值调用的形式化变换

对于一个小型的λ演算,令 C[e]C[e] 表示表达式 ee 的 CPS 翻译。假设采用从左到右的按值调用求值策略,并使用全新的变量名以避免变量捕获。一种标准的示意性翻译如下:

C[x]=λk. k xC[x] = \lambda k.\,k\,x
C[λx.e]=λk. k (λx. C[e])C[\lambda x.e] = \lambda k.\,k\,(\lambda x.\,C[e])
C[e1 e2]=λk. C[e1] (λf. C[e2] (λa. f a k))C[e_1\,e_2] = \lambda k.\, C[e_1]\, (\lambda f.\, C[e_2]\, (\lambda a.\,f\,a\,k))

在这种柯里化记法中,翻译后的函数先接收普通参数,再接收续延。函数应用规则先对函数表达式求值,再对参数表达式求值,最后以该参数和当前续延调用翻译后的函数。

这些规则针对的是一种极简语言。实际使用的变换还要处理常量、原语操作、条件表达式、递归、可变状态以及其他语言构造。

简单的变换通常会引入额外的函数应用,其中一些仅用于组织计算。这些管理性归约可以在翻译过程中或翻译完成后加以化简。

尾调用与内存使用

常规 CPS 的一个显著特点是,控制转移发生在尾位置:调用另一个函数或续延之后,当前计算就没有其他工作需要执行了。

考虑直接风格的阶乘函数:

factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

乘法必须等待递归调用返回后才能执行。CPS 将这项待执行的乘法移入续延:

factorial_cps(n, k):
    if n == 0:
        return k(1)
    return factorial_cps(
        n - 1,
        lambda value: k(n * value)
    )

递归调用现在成为尾调用,但待执行的乘法并没有消失。它们由一条闭包链表示,其中捕获了各个 n 值及先前的续延。

因此,CPS 并不会自动使计算只占用常量空间:

  • 如果具备适当的尾调用支持,就可以避免普通调用栈的增长。
  • 续延所需的内存仍可能与待完成的工作量成正比。
  • 在不具备适当尾调用支持的语言中,直接实现 CPS 仍可能使运行时栈不断增长。

对于阶乘,在对算术运算作出适当假设的情况下,基于累加器的算法可以只使用有界的辅助状态。仅将原始算法转换为 CPS,并不能带来这种算法层面的改进。

蹦床提供了另一种执行技术:每一步返回下一步的描述,再由一个循环反复执行这些描述。这样无需依赖宿主语言的尾调用实现,也能避免原生调用栈无限增长。

作为控制机制的续延

显式续延使程序能够表示比普通嵌套函数调用更丰富的控制结构。

异常与提前退出

一个计算可以分别接收成功续延和失败续延:

divide_cps(x, y, success, failure):
    if y == 0:
        return failure("division by zero")
    return success(x / y)

这使不同的控制路径显式化。更复杂的编码方式可以表示异常处理、提前返回或退出嵌套计算。

使用这类编码时,必须谨慎处理清理操作和资源生命周期。仅仅传递续延,并不能重现语言原生异常机制所提供的全部保证。

回溯

搜索过程可以同时传递成功续延和失败续延。失败续延描述了当某个候选项被拒绝或穷尽时,应如何继续搜索。

这在解析器、非确定性计算和逻辑编程的实现中很有用。返回成功结果时,还可以附带一个用于搜索下一个结果的续延。

挂起与恢复

续延可以先保存下来,而不是立即调用。调度器或外部事件随后可以调用它来恢复计算。这一原理可用于实现协程和异步编程。

普通 CPS 并不会自动提供捕获当前续延的操作。具备一等续延运算符的语言,会提供额外的机制来捕获和调用控制状态。续延只能调用一次还是可以反复调用,也取决于其表示方式及所在的执行模型。

与回调及异步代码的关系

基于回调的接口通常与 CPS 相似,因为它们会接收函数,供之后用最终结果调用。例如,异步文件读取操作可以接收一个回调,用来描述如何处理文件内容。

不过,这两个概念并不相同:

  • 回调可能表示事件处理程序、比较函数、通知或其他行为,而不一定代表计算的剩余部分。
  • 接口可能在调用回调后继续执行大量工作。
  • CPS 完全可以是同步的;传递续延并不意味着存在调度、并行执行或延迟执行。
  • 异步系统可能使用 promise 或生成的状态机,而不是统一的 CPS 表示。

在事件循环中,类似续延的回调可能要等先前的操作交出控制权后才会运行。调度决定它何时运行;CPS 则描述后续计算如何表示。

在编译器和解释器中的应用

CPS 适合作为一种中间表示,因为它以相对统一的形式显式呈现了求值顺序、函数调用和控制转移。分支、异常转移等操作都可以通过续延调用来表示。

编译器可以利用这种结构支持:

  • 续延调用的内联与化简。
  • 控制流可能去向的分析。
  • 对不逃逸的续延采用专门的表示方式。
  • 涉及异常与非局部控制的变换。
  • 将基于函数的控制结构转换为显式代码块或跳转。

CPS 并不要求每个续延都成为堆分配对象。如果使用方式允许,编译器可以将局部使用的续延表示为标签或基本块。更一般的续延则可能需要显式环境和内存分配。

去函数化是一种相关变换:它用带标签的数据来描述一组可能的函数,以此替代函数值,并配备一个分派器来解释这些描述。将去函数化应用于续延,可以把 CPS 解释器转换为显式的抽象机,其数据结构用于表示待完成的工作。

CPS 是编译过程中表示控制的多种方法之一。其他中间形式可能保留更多直接风格的结构,或使用显式控制流图。这种选择会影响优化技术、实现复杂度和调试信息。

类型与逻辑解释

对于输入类型为 AA、输出类型为 BB 的直接风格函数,简化的 CPS 接口具有以下形式:

A→(B→R)→RA \to (B \to R) \to R

这里,RR 是应答类型,即续延及外围计算所产生的最终结果的类型。

对应的计算层面变换为:

B↦(B→R)→RB \mapsto (B \to R) \to R

对于具有类型系统的语言,完整的翻译还必须一致地转换函数类型及其他复合类型。因此,不应将这一简化接口视为适用于所有高阶程序的完整类型翻译。

CPS 翻译将编程语言语义学与逻辑联系起来。在柯里—霍华德对应下,某些续延翻译对应于双重否定翻译。这一关系有助于解释:为什么基于续延的控制运算符能够在带类型演算中表达某些形式的经典逻辑推理。

历史发展

续延源于 20 世纪 60 年代至 70 年代初关于编程语言数学语义及控制结构实现的研究。克里斯托弗·斯特雷奇和克里斯托弗·沃兹沃思在计算的指称语义描述中使用了续延,而约翰·C. 雷诺兹关于定义性解释器的研究,则推动了基于续延的变换成为一种系统化的编程技术。

20 世纪 70 年代,杰拉尔德·杰伊·萨斯曼和小盖伊·L. 斯蒂尔对 Scheme 的研究,展示了过程调用、续延和尾调用在语言实现中的重要性。此后,CPS 成为函数式语言编译及控制运算符研究中一项影响深远的技术。

实际局限

显式 CPS 往往使源程序更难阅读,因为原本直观的表达式会变成嵌套函数。错误消息和栈跟踪反映的可能是变换后的控制结构,而不是原始程序。

闭包分配、捕获的环境和间接调用可能带来运行时开销,不过编译器分析能够消除其中许多开销,或通过特化来降低开销。反过来,将控制显式化也能支持一些优化,而这些优化在不那么显式的表示中较难表达。

续延的生命周期同样重要。保存下来的续延可能使其捕获的值一直保持可达,从而延长内存保留时间,并影响垃圾回收。重新调用一个会重复执行副作用的续延,可能产生不同于普通单次返回执行的行为。处理这些问题时,需要区分仅供调用一次的续延和设计为支持反复调用的续延。