Is the continuation + tail trick recursion actually a trading stack for heap space?

Question

This CPS trick in functional programming takes a non-tail-recursive function and rewrites it in a Continued Transfer (CPS) style, thereby trivially making it a tail recursive. There are a lot of questions, for example

• https://lorgonblog.wordpress.com/2008/04/05/catamorphisms-part-one/
• F #: In what area of ​​memory is the continuation stored: stack or heap?
• stack overflow

Take an example

let rec count n = if n = 0 then 0 else 1 + count (n - 1) let rec countCPS n cont = if n = 0 then cont 0 else countCPS (n - 1) (fun ret -> cont (ret + 1)) 

The first version of count will accumulate stack frames in each recursive call, creating a stack overflow with speed n = 60000 on my computer.

The idea behind the CPS trick is that the implementation of countCPS is tail recursive, so the calculation

 let f = countCPS 60000 

It will actually be optimized to work as a loop and work without problems. Instead of stack frames, the continuation that will be executed will accumulate at every step, but it is an honest object on the heap, where memory does not cause problems. As such, the CPS style is said to trade a stack of heap space. But I am skeptical about this.

Here's why: Evaluating the calculation, actually continuing with the sequel, how countCPS 60000 (fun x -> x) hits my stack! Every challenge

 countCPS (n - 1) (fun ret -> cont (ret + 1)) 

generates a new continuation closure from the old one and launches it with a single function application. Therefore, when evaluating countCPS 60000 (fun x -> x) we call a nested sequence of 60000 closures, and even if their data is on the heap, we have functional applications without changes, so again there are stack frames.

Let me dive into the generated code disassembled in C #

For countCPS we get

 public static a countCPS<a>(int n, FSharpFunc<int, a> cont) { while (n != 0) { int arg_1B_0 = n - 1; cont = new Program<a> .countCPS@10 (cont); n = arg_1B_0; } return cont.Invoke(0); } 

There we go, tail recursion is actually optimized. However, the closure class looks like

 internal class countCPS@10 <a> : FSharpFunc<int, a> { public FSharpFunc<int, a> cont; internal countCPS@10 (FSharpFunc<int, a> cont) { this.cont = cont; } public override a Invoke(int ret) { return this.cont.Invoke(ret + 1); } } 

Thus, triggering an external closure will cause .Invoke to close the child, then it will close again and again ... We really have 60,000 nested function calls again.

So, I do not see how the continuation trick is really capable of doing what is advertised.

Now we can claim that this.cont.Invoke again the tail of the call, so it does not need a stack frame. Does .NET do this kind of optimization? What about more complex examples like

 let rec fib_cps nk = match n with | 0 | 1 -> k 1 | n -> fib_cps (n-1) (fun a -> fib_cps (n-2) (fun b -> k (a+b))) 

At the very least, we would have to state why we can optimize the deferred function calls recorded in the sequel.

---

Edit

  interface FSharpFunc<A, B> { B Invoke(A arg); } class Closure<A> : FSharpFunc<int, A> { public FSharpFunc<int, A> cont; public Closure(FSharpFunc<int, A> cont) { this.cont = cont; } public A Invoke(int arg) { return cont.Invoke(arg + 1); } } class Identity<A> : FSharpFunc<A, A> { public A Invoke(A arg) { return arg; } } static void Main(string[] args) { FSharpFunc<int, int> computation = new Identity<int>(); for(int n = 10; n > 0; --n) computation = new Closure<int>(computation); Console.WriteLine(computation.Invoke(0)); } 

To be more precise, we model the closure that creates the stylish CPS function in C #.

Clearly, the data is on the heap. However, evaluating computation.Invoke(0) leads to a cascade of nested Invoke child closures. Just set a breakpoint on Identity.Invoke and look at the stack trace! So, how does the heap precast transaction stack work if it actually makes heavy use of both?

Answer 1

There are several concepts here.

For a tail recursive function, the compiler can optimize it in a loop, and therefore it does not need any stack or heap space. You can rewrite your count function into a simple tail recursive function by writing:

 let rec count acc n = if n = 0 then acc else count (acc + 1) (n - 1) 

This will be compiled into a method with a while that does not make recursive calls.

Usually a continuation is required when the function cannot be written as tail recursive. Then you need to save some state either on the stack or on the heap. Ignoring the fact that fib can be written more efficiently, a naive recursive implementation would be:

 let fib n = if n <= 1 then 1 else (fib (n-1)) + (fib (n-2)) 

This takes up stack space in order to remember what should happen after the first recursive call returns the result (then we need to call another recursive call and add the results). Using extensions, you can turn this into function-allocated heaps:

 let fib n cont = if n <= 1 then cont 1 else fib (n-1) (fun r1 -> fib (n-2) (fun r2 -> cont (r1 + r2)) 

This allocates one continuation (function value) for each recursive call, but it is tail recursive, so it does not exhaust the available stack space.

Answer 2

The hard thing with this question is this:

• He formulated the question of general principles;
• But all the details about how this does not work will inevitably concern implementation details.

Tail rings can be compiled so that a new frame does not stand out on the stack or heap. The object code can simply create a frame of the interlocutor's stack with the same value of the stack pointer and correctly transfer control to its object code procedure.

But I highlighted "can" because it is an option available to the language developer. Not all language implementations optimize all tail calls under any circumstances.

Someone who knows F # will have to comment on the details of your case, but I can answer the question in your headline:

Is the continuation + tail trick recursion actually a trading stack for heap space?

The answer is that it completely depends on your language implementation. And, in particular, implementations that try to optimize tailings on more conventional virtual machines (such as Java VMs) that were not designed for it often provide an incomplete total cost of ownership, with extreme cases not working.