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.
