optimization - 延续+尾递归技巧是否真的用堆栈空间交换堆空间？

Question

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

https://lorgonblog.wordpress.com/2008/04/05/catamorphisms-part-one/

F#: In which memory area is the continuation stored: stack or heap?

why do continuations avoid stackoverflow?

举个例子

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 风格用堆栈空间交换堆空间。但我怀疑它甚至会这样做。

原因如下:通过将延续实际运行为 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);
}

我们走了，尾递归实际上得到了优化。然而，闭包类看起来像

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 s 到子闭包。只需在 Identity.Invoke 上设置一个断点即可并查看堆栈跟踪!那么，如果它实际上大量使用了堆空间，那么内置计算如何用堆栈交换堆空间呢？

Answer 1

这里有很多概念。

对于尾递归函数，编译器可以将其优化为循环，因此不需要任何堆栈或堆空间。您可以重写您的 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))

这需要堆栈空间来记住在第一次递归调用返回结果后需要发生什么(然后我们需要调用另一个递归调用并添加结果)。使用延续，你可以把它变成堆分配的函数:

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

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