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

Question

Question

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.

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?

Example

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)

When the parameter n is small everything is ok:

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

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

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

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

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]

Tomas Petricek Tomas Petricek · Accepted Answer · 2015-12-18T20:46:49

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.

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

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

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#: In which memory area is the continuation stored: stack or heap?

Question

Example

1 Answers