Curiosity is bliss    Archive    Feed    About    Search

Julien Couvreur's programming blog and more

Closures & Continuations

 

For some reason, closures and continuations are a topic that I regularly look into, and every time think I got it. Yet every time I dig into it again, I realize my understanding is still somewhat superficial and discover more.
Sam Ruby just wrote an intro article to continuations. I found it a bit too hand-wavy to be really satisfying, but it made me want to completely get it this time ;-)

I've been re-reading my bookmarks and new pages on the topic, especially in the context of Scheme and Javascript.
Today's post will stay rather general, summarizing what closures and continuations are.
I intend to write a more detailed post some time next week with more specifics of Javascript: closures, data and execution models (but not continuations, as they don't seem to exist in Javascript).

Closures:
When you enter a new function, a new lexical scope is created. Each scope is something like an association table containing the local variables (name and value) and links back to its containing/outer/parent scope. When code needs to lookup an identifier, it will search that lexical environment, by iterating up that chain until it finds it.

A closure is a function object that references a specific inner scope (and thus the chain of its parent scopes too). It is said to "capture" that lexical scope. For example if define and return an inner function, it will reference that local scope.

Here's an example of closure, in Javascript.

> var local = 5;
> var foo = function() { var inner = 1; return local + inner; }
> foo();
6
> var local = 10;
> foo();
11

Because a closure keeps a reference to a specific scope, even as the code exits that scope and starts creating new ones, the chains of lexical scope really build a tree.
Two closures can close over the same scope, thus sharing state as it gets modified. Branches of that tree get "pruned" by the garbage collector, when nothing references them anymore.

Continuations:
There is a second such chain which represents the chain of control (tracking which instruction you're at in a given function). When a function is called or an exception occurs that chain gets involved. For example, when a function is invoked, a new lexical scope is created and a marker is also added to the control chain.

If you take a chain of lexical variable scopes (as found in a closure) and associate it with a chain of control, you could use it these as the context for calling a routine. A continuation is a routine pointer with a lexical scope and a control chain. It captures a context of execution or "place in the code" (stack or stack-frame, lexical scope, and position within the function or method) so that one can return to that location in the code and resume execution from that point forward. Usually the lexical scope, control chain and instruction pointer (what to do next, when you invoke the continuation) are captured together.

All control structures can be implemented with continuations. For example, when you register an exception handler, you capture a continuation; when the exception is thrown that continuation is invoked and you just continue running from the spot in the exception handler (the instruction pointer in the continuation points to the entry of the exception handler).

In comparison, the execution model for C programs only allows a stack that holds both chains of lexical scope and control. Another difference is that that stack is implemented very efficiently, whereas keeping linked lists for the lexical scopes involves heap allocation and garbage collection.

Links:

comments powered by Disqus