F#:连续存储在哪个存储区中:堆栈还是堆? [英] F#: In which memory area is the continuation stored: stack or heap?

问题描述

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

It is possible to make every recursive function tail recursive by follow the continuation-passing style (CPS). As I understand it you put everything after the first recursive call into a function and hand it over to the same call. Therefore the recursive call is the last statement in the function and the compiler is able to do the tail call optimization. This means that the recursion is replaced by a loop. There are no additional stack frames consumed.

continuation是一个函数，用于累积所有尚待完成的工作.在我看来，每次递归调用(或循环迭代)的持续性都在增长.我想知道执行循环时，这组不断增长的指令存储在内存中的位置.据我所知，只有两个可以存储动态数据的内存部分:堆栈和堆.我会排除堆栈，因为堆栈帧的大小在分配时是固定的.它无法容纳连续的增长指令集，因此留下了堆.也许堆栈帧包含指向存储连续功能的内存地址的指针.这个假设正确吗?

The continuation is a function which accumalates all the work which is left to be done. It seems to me that with every recursive call (or loop iteration) the continuation is growing. I want to know where this growing set of instructions is stored in memory while the loop is executed. As far as I know there are only exist two memory sections which can hold dynamic data: the stack and the heap. I would rule out the stack because the stack frame size is fixed when it is already allocated. It can not hold the growing instruction set of the continuation, so the heap is left over. Maybe the stack frame contains a pointer to a memory address where the continuation function is stored. Is this assumption correct?

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

Here I have a simple example. This is a recursive function which is not tail recursive:

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

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

When the parameter n is small everything is ok:

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

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

But when n is great you can get a stackoverflow error:

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

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

This is basically the same function but in continuation-passing style:

// 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)调用该函数:

You call the function with die identity function (id):

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

如您所见，它不会遭受stackoverflow问题的困扰:

As you can see it does not suffer from the stackoverflow problems:

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

每个循环的持续性都有所增长:

With every loop the continuation is growing a little bit:

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

推荐答案

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

The short answer is that the continuation is represented by a heap-allocated object. As you are executing code written using the continuation passing style, the tree of the objects (on the heap) that represent the continuations grow.

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

However, the continuation does not store the code to run - it just stores the closure (the variables and other state that the code uses). The code executed by each of the nodes in the tree of continuations is always the same (and it is stored in the same way as ordinary .NET methods).

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

Let's say we have something very simple like this:

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值将是堆分配的对象，如下所示:

After 3 recursive steps of factorial 3 id, the c value will be a heap allocated object looking as follows:

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

因此，如果我的ASCII语言有任何意义，我们将分配3个对象，这些对象包含延续要运行函数主体所需的值.也就是说，当前迭代的前一个c值和n值.

So, if my ASCII art makes any sense, we have 3 allocated objects that contain the values that the continuation will need to run the body of the function. That is, the previous c value and the n value of the current iteration.

这篇关于F#:连续存储在哪个存储区中:堆栈还是堆?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！