Keith Devens .com

I don't entirely understand continuations myself, but I think you have to distinguish between the stack and the heap. The continuation saves the stack, but not the heap. The stack is a set of pointers into code, showing what operations is being executed in each frame. It also contains all the local bindings of each frame. These aren't the objects themselves, just the bindings, so if you have an object that is modified after you've creating a continuation, that object will still appear modified if you restart the continuation.

The heap, in constrast, is where all the actual data is held, where all the objects live. This is not copied, nor can you undo changes to the heap. This must be so, because in all useful programs it is actually impossible to undo changes, as not all changes are reflected in the heap (file writes, network communication, etc).

Ian's comment is spot on. The only thing I would add is that "stack" and "heap" are implementation concepts. In PL theory, the relevant concepts in this case are the lexical environment, and the "store". The lexical environment binds lexical variables to their values (possibly via "locations", depending on the model being used). The "store" is where actual values are stored. These roughly correspond to stack and heap respectively. Lexical closures, and continuations, close over (capture) the current lexical environment, not the store.

The reason it's important to conceptualize this independently of implementation concepts is that the standard stack-based implementations only implement a single, rigid model: that of functions which always return to their caller. If you're implementing systems that create and use continuations, you may not want to be limited by that model. There are many implementation strategies: you can stick to the traditional stack model and copy the relevant portion of the stack whenever a continuation or closure is captured; you can allocate all stack frames on the heap, eschewing the typical C-style stack completely (some ML implementations work like this); and there are many options in between, plus other models, like "Cheney on the MTA", used by Chicken Scheme, which treats the stack as the heap and just keeps pushing stack until it runs out of stack space, at which point it starts a new stack and garbage collects the old one.

So, it's helpful to think about the concepts independently of specific implementation strategies.

What really cleared continuations up for me is:
http://www.ps.uni-sb.de/~duchier/python/continuations.html

At least one implementation, in C, of a functional language, implements continuations by literally copying the C-stack to the heap. In effect it takes a snapshot of the state of the interpreter. Just for the hell of it I implemented the snapshot idea on its own here where I use it to implement something like coroutines in C. I once used those routines to write a Mathematica style algebraic expression pattern matcher with backtracking in C. If asked to implement something like that today in C/C++ I'd probably write code in continuation passing style rather than do a hack like that - but it was kinda fun at the time.

sigfpe,

I'm really interested as to how would you do the backtracking example (that you did using co-routines) using CPS in C/C++ ?

Although I can conceptually understand CPS, I have'nt seen any code in C/C++ . Can you provide an example ?

cheers,
-Krishna