16

在用函数式语言编写记忆和延续传递风格 (CPS) 函数的示例时，我最终使用了 Fibonacci 示例。然而，斐波那契并没有真正从 CPS 中受益，因为循环仍然必须经常以指数方式运行，而使用记忆化，它第一次只有 O(n)，以后每次只有 O(1)。

将 CPS 和 memoization 结合起来对 Fibonacci 有一点好处，但是有没有例子说明 CPS 是防止你用完堆栈并提高性能的最佳方法，以及 memoization 不是解决方案的地方？

或者：是否有关于何时选择其中一个或两者兼而有之的指导方针？

4

2 回答 2

45

在 CPS 上

虽然 CPS 作为编译器中的中间语言很有用，但在源语言级别上，它主要是一种设备，用于 (1) 编码复杂的控制流（与性能无关）和 (2) 转换非尾调用消耗堆栈空间进入一个持续分配尾调用消耗堆空间。例如，当您编写（未经测试的代码）时

let rec fib = function
  | 0 | 1 -> 1
  | n -> fib (n-1) + fib (n-2)

let rec fib_cps n k = match n with
  | 0 | 1 -> k 1
  | n -> fib_cps (n-1) (fun a -> fib_cps (n-2) (fun b -> k (a+b)))

先前fib (n-2)分配了新堆栈帧的非尾调用变成了尾调用fib (n-2) (fun b -> k (a+b))，尾调用分配闭包fun b -> k (a+b)（在堆上）以将其作为参数传递。

这不会渐近地减少程序的内存使用量（可能会进行一些进一步的特定于域的优化，但那是另一回事了）。您只是在用堆栈空间交换堆空间，这在堆栈空间受到操作系统严重限制的系统上很有趣（对于 ML 的某些实现（例如 SML/NJ）不是这种情况，它们在堆上跟踪它们的调用堆栈而不是使用系统堆栈），并且由于额外的 GC 成本和潜在的局部性降低而可能降低性能。

CPS 转换不太可能大大提高性能（尽管您的实现和运行时系统的细节可能会如此），并且是一种普遍适用的转换，可以避免具有深度调用堆栈的递归函数的“堆栈溢出”。

关于记忆

记忆对于引入递归函数的子调用共享很有用。递归函数通常通过将其分解为几个严格简单的“子问题”（递归子调用）来解决“问题”（“计算斐波那契n”等），其中一些基本情况可以立即解决问题。

对于任何递归函数（或问题的递归公式），您都可以观察到子问题空间的结构。哪些更简单的实例Fib(k)需要Fib(n)返回结果？这些实例又需要哪些更简单的实例？

在一般情况下，这个子问题空间是一个图（出于终止目的通常是非循环的）：有一些节点有几个父节点，它们是几个不同的问题，它们是子问题。例如，Fib(n-2)是Fib(n)和的子问题Fib(n-2)。此图中的节点共享量取决于特定问题/递归函数。在斐波那契的情况下，所有节点都在两个父节点之间共享，因此共享很多。

没有记忆的直接递归调用将无法观察到这种共享。递归函数的调用结构是树，而不是图，共享子问题，例如Fib(n-2)将被完全访问多次（与图中从起始节点到子问题节点的路径一样多）。记忆化通过让一些子调用直接返回“我们已经计算过这个节点，这是结果”来引入共享。对于有很多共享的问题，这可能会导致（无用）计算的显着减少：当引入 memoization 时，Fibonacci 从指数复杂度变为线性复杂度——请注意，还有其他编写函数的方法，不使用 memoization，而是不同的子调用结构，具有线性复杂度。

let rec fib_pair = function
  | 0 -> (1,1)
  | n -> let (u,v) = fib_pair (n-1) in (v,u+v)

使用某种形式的共享（通常通过存储结果的大表）来避免子计算的无用重复的技术在算法界是众所周知的，它被称为动态编程。当您认识到一个问题适合这种处理时（您注意到子问题之间的共享），这可以提供很大的性能优势。

比较有意义吗？

两者似乎大多是相互独立的。

有很多问题是 memoization 不适用的，因为子问题图结构没有任何共享（它是一棵树）。相反，CPS 转换适用于所有递归函数，但它本身并不会带来性能优势（除了由于您使用的特定实现和运行时系统导致的潜在常量因素，尽管它们很可能使代码慢而不是快）。

通过检查非尾部上下文来提高性能

有一些与 CPS 相关的优化技术可以提高递归函数的性能。它们包括在递归调用之后查看“留待完成”的计算（这将变成直接 CPS 样式的函数）并为其找到替代的、更有效的表示，这不会导致系统的闭包分配。考虑例如：

let rec length = function
  | [] -> 0
  | _::t -> 1 + length t

let rec length_cps li k = match li with
  | [] -> k 0
  | _::t -> length_cps t (fun a -> k (a + 1))

您可以注意到非递归调用的上下文，即[_ + 1]具有一个简单的结构：它添加一个整数。与其将 this 表示为一个函数fun a -> k (a+1)，您可以只存储与该函数的多个应用程序相对应的要添加的整数，从而制作k一个整数而不是一个函数。

let rec length_acc li k = match li with
  | [] -> k + 0
  | _::t -> length_acc t (k + 1)

该函数在恒定的而非线性的空间中运行。通过将尾部上下文的表示从函数转换为整数，我们消除了使内存使用线性化的分配步骤。

仔细检查执行添加的顺序会发现它们现在以不同的方向执行：我们首先添加对应于列表开头的 1，而cps版本最后添加它们。这种顺序反转是有效的，因为_ + 1它是一个关联操作（如果您有多个嵌套上下文，foo + 1 + 1 + 1则从内部开始计算它们是有效的，((foo+1)+1)+1或者从外部开始计算它们foo+(1+(1+1))）。上述优化可用于围绕非尾调用的所有此类“关联”上下文。

基于相同的想法当然还有其他可用的优化（我不是此类优化的专家），即查看所涉及的延续的结构并以比在堆上分配的函数更有效的形式表示它们。

这与“去功能化”的转换有关，它将延续的表示从函数更改为数据结构，而不改变内存消耗（当在原始程序中分配闭包时，去功能化程序将分配数据节点），但允许用一阶语言（没有一等函数）表达尾递归 CPS 版本，并且在数据结构和模式匹配比闭包分配和间接调用更有效的系统上更有效。

type length_cont =
  | Linit
  | Lcons of length_cont

let rec length_cps_defun li k = match li with
  | [] -> length_cont_eval 0 k
  | _::t -> length_cps_defun t (Lcons k)
and length_cont_eval acc = function
  | Linit -> acc
  | Lcons k -> length_cont_eval (acc+1) k

let length li = length_cps_defun li Linit

type fib_cont =
  | Finit
  | Fminus1 of int * fib_cont
  | Fminus2 of fib_cont * int

let rec fib_cps_defun n k = match n with
  | 0 | 1 -> fib_cont_eval 1 k
  | n -> fib_cps_defun (n-1) (Fminus1 (n, k))
and fib_cont_eval acc = function
  | Finit -> acc
  | Fminus1 (n, k) -> fib_cps_defun (n-2) (Fminus2 (k, acc))
  | Fminus2 (k, acc') -> fib_cont_eval (acc+acc') k

let fib n = fib_cps_defun n Finit
于 2013-02-09T12:34:54.533 回答
2

CPS 的一个好处是错误处理。如果你需要失败，你只需调用你的失败方法。

我认为最大的情况是当你不谈论计算时，记忆化非常好。如果您谈论的是 IO 或其他操作，那么 CPS 的好处是存在的，但记忆化不起作用。

至于 CPS 和 memoization 都适用并且 CPS 更好的实例，我不确定，因为我认为它们是不同的功能。

最后，CPS 在 F# 中有所减少，因为尾递归已经使整个堆栈溢出问题不再存在。

于 2013-02-08T21:54:29.153 回答