Continuations…frequently referred to by Paul Graham as, to paraphrase,
awesome. With all the reading I've done regarding continuations, I've
never really seen the big deal about them. Turns out its because I
didn't get it. Imagine that… Fortunately for me, I have continued to
read about them and finally had the "ah ha" moment. Reading this
page describing fuctional
programming, the author explains continuations in way that finally made
it click:
A "continuation" is a parameter we may choose to pass to our function
that specifies where the function should return. The description may
be more complicated than it sounds. Take a look at the following code:
int i = add(5, 10);
int j = square(i);
The function add returns 15 to be assigned to i, the place where
add was originally called. After that the value of i is used to
call square. Note that a lazy compiler can't rearrange these lines
of code because the second line depends on successful evaluation of
the first. We can rewrite this code block using Continuation Passing
Style or CPS, where the function add doesn't return to the
original caller but instead returns its result to square.
int j = add(5, 10, square);
In this case add gets another parameter - a function that add must
call with its result upon completion. In this case square is a
continuation of add. In both cases j will equal 225.
So if you redefine your functions to take an optional last parameter
that points to where the function should return to, suddenly you have
some serious flexibility regarding what happens at the end of functions.
The brilliance behind this method is shown a little further in the
article:
Once we convert a program to CPS it becomes clear that every
instruction has some continuation, a function it will call with the
result, which in a regular program would be a place it must return to.
Let's pick any instruction from above code, say add(5, 10). In a
program written in CPS style it's clear what add's continuation is -
it's a function that add calls once it's done. But what is it in a
non-CPS program? We could, of course, convert the program to CPS, but
do we have to? It turns out that we don't. Look carefully at our CPS
conversion. If you try to write a compiler for it and think about it
long enough you'll realize that the CPS version needs no stack! No
function ever "returns" in the traditional sense, it just calls
another function with the result instead. We don't need to push
function arguments on the stack with every call and then pop them
back, we can simply store them in some block of memory and use a jump
instruction instead. We'll never need the original arguments - they'll
never be used again since no function ever returns! So, programs
written in CPS style have no stack but have an extra argument with a
function to call. Programs not written in CPS style have no argument
with a function to call, but have the stack instead. What does the
stack contain? Simply the arguments, and a pointer to memory where the
function should return. Do you see a light bulb? The stack simply
contains continuation information! The pointer to the return
instruction in the stack is essentially the same thing as the function
to call in CPS programs! If you wanted to find out what continuation
for add(5, 10) is, you'd simply have to examine the stack at the
point of its execution!
Continuations are particularly well-suited to web programming because of
the stateless nature of the web. A request for a page could come at
anytime, and what happened before that page request will not matter.
However, this is not always desirable. With continuations, we can
simulate state, even in a stateless environment. For more on that
subject, start with this
article.
An interesting alternative to MVC. This is a whole new paradigm from the
one I was taught in school and I think rightfully so. It is a tough
concept to wrap your mind around at first. Now that I've had the "ah ha"
moment, I look forward to implementing these ideas in my future work.
