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.
