Debugging lambda in continuations

Question

I'm learning F# (coming from C++/C#) and I just read about continuations as one of the way to avoid stack overflow during recursion. In the beginning it was a bit hard to grasp but then I guess I got used to it and I like the power of this logic. But I'd like to get even more details (and confirm I understood correctly) to possibly make the best use of it so I thought it was time to get in touch with the community.

To make my questions I will use a simple example using recursion, lambda and continuation.

I create a list:

let ml = [1;2;3]

and a function that doubles each element of the list:

let double a = a * 2

then a recursive function that uses a continuantion function (cont) to apply the double function to each element of a list (wlist):

let rec loop cont wlist = 
match wlist with
| [] -> cont []
| x::xs -> loop ( fun acc -> cont (double x::acc) ) xs 

then I get the new list with doubled elements from the old one:

let ml2 = loop id ml 

the loop function could be generalized to accept any mapping function but I want to keep the example simple so I just stick with double function.

Decomposing the code:

The way I understand what I just studied, the calls in the loop function are tail recursive because called in the end of the body, so no need to save info on the stack to restore after the call, and that avoid risk of stack overflow . The cont function is a lambda redifined at each loop, the way i get from code above is decomposed like this:

let loop1 = fun acc -> id(double 1::acc)
let loop2 = fun acc -> id(double 1::(double 2::acc))
let loop3 = fun acc -> id(double 1::(double 2::(double 3::acc)))

in my example after the loop3 the cont function is finally invoked by the pattern match of the empty list:

| [] -> cont []

this translates in calling:

loop3 []

which in turns translates in:

id(double 1::(double 2::(double 3::[])))

then:

id (2::(4::(6::[])))

then:

[2; 4; 6]

which is what the goal I wanted to reach.

Now the questions:

1 - This example is very simple but with more complex lambda it's difficult to figure step by step evolution of a continuation to validate a new algorithm. I tried the vstudio debugger but when I go inspect the continuataion it just tell me that it has been defined at line x of my source code. Thanks, but not very useful, this is not a static lambda, it's redifined at each loop, so what is the current body of the lambda at certain point of the loop? Also i cannot debug-stepinto the lambda. Which tool or trick can give me this info and avoid to figure it with my mind? Should I put printf inside the functions to follow the logic? The risk is if I am working in a hurry on a project (as almost always) I skip this logic because its difficult to validate and debug

2 - The continuation avoid charging the stack and so help avoiding stack overflow, in this example an accumulator value with a growing list could be used but with trees that's not possible. My question is, where the info about the lambda is stored? Is that some sort of new and delete allocation? Is the old lambda at each loop deleted from memory when redifined?

3 - Is there any tool that can show me how the F# is compiled in .net? But not at assembly level, some higher level more readable. I have seen examples that show F# compiled and translated in some sort of C# ( C# and F# lambda expressions code generation) but they don't mention the tools.

Thank you for reading this message, sorry for the lenght.

Answer 1

As for 1, you could always first write your code in a normal stack-allocated way (with risk of stack overflow) and make sure it is correct and just add the continuations later. That way you would make the code in itself correct and just adding the continuations should be a fairly straight-forward procedure afterwards.

As for 2, the intermediate state gets allocated on the heap as opposed to the stack. And since the heap is much larger, you don't get a stack overflow but at worst an out-of-memory. The latter being fairly unlikely, unless you store a massive intermediate state. The lambda is going to be stored as a closure on the heap, whereas a closure in this case would be an object holding the captured values that you already passed into your function.

As for 3, you can look at some decompilers like dotPeek from JetBrains, but you might not find it all that readable code. In F# it is for the most part more useful to think in terms of discriminated unions (DUs), records, tuples and functions as opposed to the classes and objects they are implemented in. Especially if you look at cases that look very similar in F# but have a different meaning, you might get very different C# code, like say: let value = fun () -> 1 as opposed to let func () = 1. They look very similar, but in fact the first one is a constant function value, whereas the latter is a function. In particular, you could do some heavy computation before returning the function value in the first case, but not in the second one. The way, how I like to understand and think about the code is, that I make myself conscious about what part evaluates when.