Continuing on Closures

This is the (long awaited) second part of my tutorial on closures. This part describes how your language's runtime might provide closures. I've assumed that you understand what a closure is, if not, read the first part of this tutorial first.

So by now we know that we can think of a closure as an object: an instance of an automatically generated class. This class has just one method: apply() that executes the body of the closure. The class has one member variable for each variable in the active scope at the time the closure object was constructed.

But local variables are only available to the function that defines them and even then only for the lifetime of that particular function call. How then is it possible for a closure to access these values? To explain that I'm going to briefly go over how functions work, bear with me if this all seems a bit basic.

Sometime back in the 1950's, during the design of ALGOL the concept of the call stack and stack frames were discovered. The call stack is just a list of called functions, implemented as a stack so that as functions return they can be popped off the call stack, leaving the calling function on top. A stack frame is the object that is pushed onto the stack to describe a function. A stack frame contains the line of code to return to when the function returns, the parameters to the functions and the local variables of the function.

Every invocation of a function causes a new stack frame to be created and pushed onto the call stack. Among other things, this makes recursion possible. Early versions of FORTRAN don't support recursion: no call stack.

Your program executes; functions are called; stack frames are constructed; values are calculated; frames are updated; and return values are returned. But every time a function returns its stack frame is destroyed, and the very next function called will completely overwrite the memory where the last stack frame was. So how can a closure always be guaranteed to still be able to access a local variable?

Earlier I referred to a stack frame as an object. In languages like C and Java a stack frame is not an object at all; it's just some conventions for how certain pieces of data are stored. All of which are calculated and laid out ahead of time by the compiler.

But what if the stack frame was an actual object stored with other objects on the heap? What if, instead of a stack, a linked list was used to connect the frames? Hmmm... interesting... The linked list would represent the call stack. Every new stack frame would be constructed with a pointer to the frame of the current function. Like all other objects, these frame objects would be subject to the garbage collector. This prevents a frame from being destroyed until it, and all functions it called, have returned.

Once the runtime provides this implementation of frames and the 'call stack,' a closure can include a pointer to the current frame. When the closure needs access to anything in its containing scope it can now just use this pointer. And as the frame contains a pointer to its calling function, the closure can now work its way back through any scopes it's interested in.

Extra Credit: The ability to work backwards through the scopes of all the functions in the call stack is known as dynamic scope. It's pretty uncommon now, as it's virtually impossible for a human to understand in any kind of complex program. As a result languages that support closures generally provide lexical scoping. In lexical scope the structuring of the program text defines the scopes available to a function; and therefore a closure can only use the local variables of the frame immediately referred to by the closure. But enough on scoping; for more compare early versions of Lisp to Scheme.

Frames as a linked list would not make any difference to your program as the act of reading the data stored in a frame is still hidden by the compiler and runtime.

And that's really all there is to it. Closures can now access local variables that seemed to only exist at the time the function was defined. The reference by a closure to a frame behaves like any other reference: the frame will not be destroyed until the closure is destroyed.

Hmmm... didn't I mention earlier that a frame also contains a line of code to return to? Doesn't that mean that any frame can be safely returned from? Yes, it does. Now, if we move our current line variable into the frame itself we have what's called a continuation. That is, a single frame object describes the current values of all local variables for a function, the next line of code to execute in the function and which function to return to. And that function in turn also has all the same information preserved.

If the language then allowed it, you could pick up that underlying frame object, store it away somewhere and then use it to later on continue execution where it was previously left off. Hence the name: continuation. To pull this off the language needs to provide two features.

Firstly, the ability to get a reference to the frame object for the currently executing function, at the same time halting execution. Secondly, the ability to call that frame object at some later point and have execution pick up exactly where it left off, as if there was no pause.

Continuations as a concept are regarded as 'difficult.' As a result, even though most languages that provide closures could also provide continuations the programmer is not given direct control over them. Some languages do provide this control: Scheme (noticing a patten here?), Ruby and Smalltalk, amongst others.

So what are these good for? Before getting into an example of how continuations can be used, I want to say one thing: powerful language features are always useful. If you're not used to having a feature in a language, the first time someone shows it to you the immediate reaction will be: 'Sounds cool; but what use is something like that?' A fairly normal reaction and simply the result of not having the feature available. Once you've used a language with an 'advanced' feature you'll find all sorts of uses, until eventually you won't be able to imagine coding without it.

Anyway, onto an example. When writing web applications a big problem is the enormous gap between the page displayed in the user's browser and where the server thinks the user is up to. Continuations can make this almost completely disappear. Once the application on the server has prepared a page, instead of winding up the call stack and then returning the page to the user a continuation could be captured. This continuation is stored on the server and a key is sent to the browser to be returned with the other data on the page. Using the key, the continuation is invoked, and execution of the function picks up where it left off.

The code running on the server to handle screens in the application could then look something like the below. The statement yield causes the continuation capturing to occur. And remember, all of this code executes on the server, there is no AJAX or anything like that.

function checkout()
{
  // The following three functions add UI elements to the
  // current page. These are rendered as HTML. 
  displayCartContents();
  addButton(new NextButton());
  addButton(new PrevButton());

  yield; // Continuation is captured, and the page so far
         // is sent down to the user

  // The user has sent a response back to the server
  // The functions payment() and home are similar to
  // this function: they create specific pages.
  if (Page.SelectedButton == Button::NextId)
    payment(); // Display a page to collect payment
  else
    home(); // The user wants to continue shopping
}

As well as this simple server side logic, the user can then explore multiple paths through the application concurrently, with multiple windows and using the 'Back' button with abandon. You, as a programmer and a program, will never become confused. Pretty nice, huh? There is a web server already out there that gives you this: seaside.st

And any language can make these powerful features available simply by implementing the call stack as a garbage-collected, linked list of simple frame objects, instead of a one-dimensional stack of data. Pretty powerful, and remarkably simple. Makes you wonder what other abstractions are lurking behind small implementation decisions.