continuation + tail recursion 技巧实际上是用栈 space 换取堆 space 吗？

Question

函数式编程中有一个 CPS 技巧，它采用非尾递归函数并以连续传递样式 (CPS) 重写它，从而使它成为尾递归。很多问题实际上都涵盖了这一点，比如

https://lorgonblog.wordpress.com/2008/04/05/catamorphisms-part-one/
why do continuations avoid Whosebug?

举个例子

let rec count n = 
    if n = 0
      then 0
      else 1 + count (n - 1)

let rec countCPS n cont =
    if n = 0
      then cont 0
      else countCPS (n - 1) (fun ret -> cont (ret + 1))

count 的第一个版本将在每次递归调用中累积堆栈帧，在我的计算机上大约 n = 60000 处产生堆栈溢出。

CPS 技巧的思想是 countCPS 实现是尾递归的，因此计算

let f = countCPS 60000

实际上将优化为运行作为一个循环并且可以正常工作。不是堆栈帧，而是运行的延续将在每一步中累积，但这是内存不会导致问题的堆上的诚实对象。 所以说 CPS 风格是用栈 space 换取堆 space。但我怀疑它是否真的这样做了。

原因如下：通过实际运行将延续作为 countCPS 60000 (fun x -> x) 来评估计算，这让我的筹码大打折扣！每次调用

countCPS (n - 1) (fun ret -> cont (ret + 1))

从旧闭包生成一个新的延续闭包，运行它涉及一个函数应用程序。所以在计算 countCPS 60000 (fun x -> x) 时，我们调用了 60000 个闭包的嵌套序列，即使它们的数据在堆上，我们仍然有函数应用程序，所以又出现了堆栈帧。

让我们深入研究生成的代码，反汇编成 C#

对于countCPS，我们得到

public static a countCPS<a>(int n, FSharpFunc<int, a> cont)
{
    while (n != 0)
    {
        int arg_1B_0 = n - 1;
        cont = new Program<a>.countCPS@10(cont);
        n = arg_1B_0;
    }
    return cont.Invoke(0);
}

好了，尾递归实际上已经被优化掉了。但是，闭包 class 看起来像

internal class countCPS@10<a> : FSharpFunc<int, a>
{
    public FSharpFunc<int, a> cont;

    internal countCPS@10(FSharpFunc<int, a> cont)
    {
        this.cont = cont;
    }

    public override a Invoke(int ret)
    {
        return this.cont.Invoke(ret + 1);
    }
}

所以运行最外层的闭包会导致它 .Invoke 它的子闭包，然后它的子闭包一次又一次... 我们真的有 60000 次嵌套函数调用再次.

所以我不明白延续技巧实际上是如何做到所宣传的。

现在我们可以争辩说 this.cont.Invoke 又是一种尾调用，因此它不需要堆栈帧。 .NET 是否执行这种优化？更复杂的例子，比如

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)))

至少我们不得不争论为什么我们可以优化掉延续中捕获的嵌套函数调用。

编辑

    interface FSharpFunc<A, B>
    {
        B Invoke(A arg);
    }

    class Closure<A> : FSharpFunc<int, A>
    {
        public FSharpFunc<int, A> cont;

        public Closure(FSharpFunc<int, A> cont)
        {
            this.cont = cont;
        }

        public A Invoke(int arg)
        {
            return cont.Invoke(arg + 1);
        }
    }

    class Identity<A> : FSharpFunc<A, A>
    {
        public A Invoke(A arg)
        {
            return arg;
        }
    }
    static void Main(string[] args)
    {
        FSharpFunc<int, int> computation = new Identity<int>();

        for(int n = 10; n > 0; --n)
            computation = new Closure<int>(computation);

        Console.WriteLine(computation.Invoke(0));
    }

更准确地说，我们对 CPS 样式函数在 C# 中构建的闭包进行建模。

显然，数据位于堆上。但是，评估 computation.Invoke(0) 会导致嵌套的 Invoke 级联到子闭包。只需在 Identity.Invoke 上放置一个断点并查看堆栈跟踪！那么，如果实际上大量使用两者，那么构建计算如何为堆交换堆栈 space？

Answer 1

这里有很多概念。

对于尾递归函数，编译器可以将其优化为循环，因此不需要任何堆栈或堆space。您可以通过以下方式将 count 函数重写为简单的尾递归函数：

let rec count acc n = 
   if n = 0
      then acc
      else count (acc + 1) (n - 1)

这将被编译成一个带有 while 循环的方法，不会进行递归调用。

当函数不能写成尾递归时，通常需要延续。然后，您需要在堆栈上或堆上保留一些状态。忽略 fib 可以更有效地编写这一事实，朴素的递归实现将是：

let fib n = 
  if n <= 1 then 1
  else (fib (n-1)) + (fib (n-2))

这需要stack space记住第一次递归调用后需要发生什么returns结果（然后我们需要调用另一个递归调用并添加结果）。使用延续，你可以把它变成堆分配的函数：

let fib n cont = 
  if n <= 1 then cont 1
  else fib (n-1) (fun r1 -> 
         fib (n-2) (fun r2 -> cont (r1 + r2))

这为每个递归调用分配一个延续（函数值），但它是尾递归的，因此不会耗尽可用堆栈 space。

Answer 2

这个问题的棘手之处在于：

它被设计成一个关于一般原则；
但所有关于它似乎不起作用的细节都不可避免地会涉及到实施细节。

尾调用可以编译，这样就不会在堆栈或堆上分配新帧。 object 代码可以简单地创建具有相同堆栈指针值的被调用者的堆栈帧 in-place 并无条件地将控制权转移到它的 object 代码例程。

但我将 "can" 加粗了，因为这是语言实现者可用的选项。并非所有语言实现都能在所有情况下优化所有尾部调用。

了解 F# 的人将不得不对您的案例细节发表评论，但我可以回答您提交标题中的问题：

Does the continuation + tail recursion trick actually trade stack space for heap space?

答案是完全取决于你的语言实现。特别是，尝试在并非为其设计的更传统的 VM（如 Java VM）上提供 tail-call 优化的实现通常提供不完整的 TCO，边缘情况不起作用。

continuation + tail recursion 技巧实际上是用栈 space 换取堆 space 吗？

Does the continuation + tail recursion trick actually trade stack space for heap space?

optimization

f#

functional-programming

tail-recursion

continuations

编辑