F#:continuation 存储在哪个内存区域:栈还是堆？

Question

问题

可以通过遵循连续传递样式 (CPS) 使每个递归函数尾部递归。据我了解，您将第一次递归调用后的所有内容都放入函数中，然后将其移交给同一个调用。因此递归调用是函数中的最后一条语句，编译器能够进行尾调用优化。这意味着递归被循环取代。没有消耗额外的堆栈帧。

continuation 是一个函数，它累积所有待完成的工作。在我看来，随着每次递归调用(或循环迭代)，延续性都在增长。我想知道在执行循环时，这组不断增长的指令存储在内存中的什么位置。据我所知，只有两个内存部分可以保存动态数据:堆栈和堆。我会排除堆栈，因为堆栈帧大小在已经分配时是固定的。它不能容纳继续增长的指令集，所以堆被遗留下来。也许堆栈帧包含一个指向存储延续函数的内存地址的指针。这个假设是否正确？

例子

这里我有一个简单的例子。这是一个非尾递归的递归函数:

// bigList: int -> int list
let rec bigList = function
    | 0 -> []
    | n -> 1 :: bigList (n-1)

当参数 n 较小时一切正常:

> bigList 3;;
val it : int list = [1; 1; 1]

但是当 n 很大时，你会得到一个 stackoverflow 错误:

> bigList 170000;;
Stack overflow in unmanaged: IP: 0x2dcdb0, fault addr: 0xbf759ffc
Stack overflow in unmanaged: IP: 0x2dcdb0, fault addr: 0xbf758ffc
...

这基本上是相同的功能，但采用连续传递风格:

// bigListC: int -> (int list -> 'a) -> 'a
let rec bigListC n c =
    match n with 
    | 0 -> c []
    | n -> bigListC (n-1) (fun res -> c (1::res))       

您使用标识函数 (id) 调用该函数:

> bigListC 3 id;;
val it : int list = [1; 1; 1]

如您所见，它不会遇到 stackoverflow 问题:

> bigListC 170000 id;;
val it : int list =
   [1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1;
    1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1;
    1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1;
    1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1;
    ...]

随着每一个循环，continuation 都会增长一点点:

// bigListC 1 id:
> (fun res -> id (1::res)) [];;
val it : int list = [1]

// bigListC 2 id:
> (fun res -> (fun res -> id (1::res)) (1::res)) [];;
val it : int list = [1; 1]

// bigListC 3 id:
> (fun res -> (fun res -> (fun res -> id (1::res)) (1::res)) (1::res)) [];;
val it : int list = [1; 1; 1]

Answer 1

简短的回答是延续由堆分配的对象表示。当您执行使用延续传递样式编写的代码时，表示延续的对象树(在堆上)会增长。

但是，continuation 不存储要运行的代码 - 它只存储闭包(代码使用的变量和其他状态)。延续树中每个节点执行的代码总是相同的(并且它的存储方式与普通 .NET 方法相同)。

假设我们有这样一个非常简单的东西:

let rec factorial n c =
  if n = 0 then c 1
  else factorial (n - 1) (fun r -> c (r * n))

在 factorial 3 id 的 3 次递归步骤之后，c 值将是一个堆分配对象，如下所示:

      +--------+   +--------+   +--------+
      | n = 1  | / | n = 2  | / | n = 3  |
      | c = ----/  | c = ----/  | c = id |
      +--------+   +--------+   +--------+   

因此，如果我的 ASCII 艺术有意义的话，我们有 3 个分配的对象，其中包含继续运行函数体所需的值。即前一个c值和当前迭代的n值。