F#:哪个内存区域是存储的延续:堆栈还是堆？

Question

题

通过遵循连续传递样式(CPS),可以使每个递归函数尾递归.据我所知,你把第一次递归调用后的所有内容都放到一个函数中,然后把它交给同一个调用.因此,递归调用是函数中的最后一个语句,编译器能够进行尾调用优化.这意味着递归被循环替换.没有额外的堆栈帧消耗.

延续是一项功能,它可以完成所有剩下的工作.在我看来,每次递归调用(或循环迭代),延续都在增长.我想知道在执行循环时这个不断增长的指令集存储在内存中的哪个位置.据我所知,只存在两个可以保存动态数据的内存部分:堆栈和堆.我会排除堆栈,因为堆栈帧大小在已经分配时是固定的.它不能保持延续的增长指令集,因此堆剩余.也许堆栈帧包含指向存储连续函数的存储器地址的指针.这个假设是否正确？

例

这里有一个简单的例子.这是一个递归函数,它不是尾递归的:

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

您使用die identity function(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;
    ...]

随着每个循环,延续正在增长一点点:

// 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由堆分配的对象表示.当您执行使用延续传递样式编写的代码时,表示延续的对象树(在堆上)会增长.

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

假设我们有一些非常简单的东西:

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

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

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

因此,如果我的ASCII艺术有意义,我们有3个已分配的对象,这些对象包含继续运行函数体所需的值.也就是说,前一个c值和n当前迭代的值.