continuation + tail递归技巧是否真的为堆空间交换堆栈空间？

Question

在函数式编程中有这种CPS技巧,它采用非尾递归函数并在连续传递样式(CPS)中重写它,从而使其尾递归.很多问题实际上涵盖了这一点,比如

• https://lorgonblog.wordpress.com/2008/04/05/catamorphisms-part-one/
• F#:哪个内存区域是存储的延续:堆栈还是堆？
• 为什么延续避免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)嵌套Invokes 级联到子闭包的结果.只需打开一个断点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))

这需要堆栈空间来记住第一次递归调用返回结果后需要发生的事情(然后我们需要调用另一个递归调用并添加结果).使用continuation,您可以将其转换为堆分配的函数:

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

这为每个递归调用分配一个continuation(函数值),但它是尾递归的,所以它不会耗尽可用的堆栈空间.