选择延续传递样式和记忆化的区别

Question

在撰写函数式语言中关于记忆化和延续传递样式（CPS）函数的示例时，我发现在 Fibonacci 的例子上两者都能用。然而，Fibonacci 并不真正从 CPS 中受益，因为循环仍然必须以指数级运行，而使用记忆化的时间复杂度是仅在第一次为 O(n)，之后每次为 O(1)。

将 CPS 和记忆化结合对 Fibonacci 稍有好处，但是否存在示例，其中 CPS 是防止超出堆栈限制且提高性能的最佳方法，而记忆化不是解决方案？

或：何时选择其中一个或两个的任何指南？

- Abel

---

你能提供一个需要CPS和备忘录化的两种不同解决方案的问题吗？ - Daniel

您可能会觉得以下文章很有趣：使用F#中的延续传递风格和记忆化解决0-1背包问题。 - Phillip Trelford

Answer 1

关于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 变换不太可能大幅提高性能（虽然你的实现和运行时系统的细节可能会使其如此），并且是一个通用的变换，允许避免具有深度调用栈的递归函数的“堆栈溢出”问题。

关于记忆化

Memoization可以用来共享递归函数的子调用。递归函数通常通过将“问题”（“计算斐波那契数列n”等）分解成几个严格更简单的“子问题”（递归子调用），并提供一些基本情况，以便立即解决问题。

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

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

直接递归调用而不使用记忆化将无法观察到这种共享。递归函数的调用结构是一棵树，而不是图，共享子问题（如Fib(n-2)）将被完全访问多次（与从起始节点到子问题节点的路径数一样多）。记忆化通过让一些子调用直接返回“我们已经计算了此节点，这里是结果”来引入共享。对于具有大量共享的问题，这可以导致（无用）计算的显着减少：当引入记忆化时，斐波那契数列的复杂度从指数级降至线性级--请注意，还有其他方法可以编写该函数，而不使用记忆化但使用不同的子调用结构，以获得线性复杂度。

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

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

比较有意义吗？

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

有很多问题不适用于记忆化，因为子问题图结构没有任何共享（它是一棵树）。相反，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]，具有简单的结构：它添加一个整数。不必将其表示为函数fun a -> k (a+1)，而是可以将要添加的整数存储对应于该函数的多个应用程序，使k成为整数而不是函数。

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

这个函数在常量空间中运行，而不是线性空间。通过将尾上下文的表示从函数更改为整数，我们消除了使内存使用线性的分配步骤。

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

肯定还有其他基于相同思想的优化可用（我对这些优化不是专家），即查看涉及的连续体的结构，并以比在堆上分配的函数更高效的形式表示它们。

这与"去功能化"相关，它将延续的表现从函数变为数据结构，而不改变内存消耗（在原始程序中分配闭包时，“去功能化”程序会分配数据节点），但允许在无头递归CPS版本中使用一阶语言（无头递归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

- gasche

---

之前没回复你（在旅行中），但现在终于有时间去仔细研究你详尽的答案了。非常棒且发现得很好。有关图形和树结构以及重新访问节点的解释是一个很好的方式，可以看到这里不同的用例。谢谢！ - Abel

Answer 2

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

我认为最大的情况是当你不谈论计算时，记忆化很棒。相反地，如果你谈论IO或其他操作，CPS的好处在那里，但记忆化不起作用。

关于CPS和记忆化都适用且CPS更好的实例，我不确定，因为我认为它们是不同的功能部件。

最后，在F#中，由于尾递归使整个堆栈溢出问题不再成为问题，CPS有点减弱了。

- Guvante

---

F#并不会自动将每个调用转换为尾调用，因此CPS仍然需要来正确地实现某些函数式设计模式。 - Jack P.

在斐波那契数列的例子中，递归有两个递归返回点，因此无法进行TCO。树遍历算法也是如此。如果没有累加器的阶乘实现也无法进行TCO，因为函数的结果仍然需要在函数返回之前用于计算。事实上，TCO仅适用于有限的递归问题，这时候需要使用CPS来解决。 - Abel

@Jack P. F#会自动将每个尾调用优化为循环吗？我同意将任何一般递归函数转换为尾递归函数并不容易，但是当给定一个尾递归函数时，假设F#将优化递归（前提是打开了适当的编译器设置），这是否不正确？ - Shredderroy

@Shredderroy：并不总是这样，有时它会发出一个call操作，然后是一个tail操作，在这种情况下，就由JIT编译器来优化递归了。 - ildjarn

Tail calls并不一定被优化为循环；它们只是允许JIT编译器在进行尾调用到下一个函数时丢弃当前的堆栈帧。由于没有堆栈溢出的可能性，这意味着一个自我递归（即自身递归）的函数有效地变成了一个循环。F#编译器有时可以进一步将某些自递归函数优化为显式循环——也就是说，tail.call操作被优化掉，而只是使用br操作回到方法体的开头。 - Jack P.

@JackP：我想我并不认为累加器是 CPS。许多尾递归可以简化为它，而与 CPS 相比，你需要包装你的最终操作。 - Guvante