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 很大时，您可能会遇到 Whosebug 错误：

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

如您所见，它没有遇到 Whosebug 问题：

> 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;
    ...]

随着每一个循环，延续都在一点点增长：

// 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 不会将 code 存储到运行 - 它只存储闭包（代码使用的变量和其他状态）。延续树中每个节点执行的代码总是相同的（并且它的存储方式与普通 .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值

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

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

continuations

f#

问题

例子