I've been browsing all over the web in search of enlightenment about continuations, and it's mind boggling how the simplest of explanations can so utterly confound a JavaScript programmer like myself. This is especially true when most articles explain continuations with code in Scheme or use monads.
Now that I finally think I've understood the essence of continuations I wanted to know whether what I do know is actually the truth. If what I think is true is not actually true, then it's ignorance and not enlightenment.
So, here's what I know:
In almost all languages functions explicitly return values (and control) to their caller. For example:
var sum = add(2, 3);
console.log(sum);
function add(x, y) {
return x + y;
}
Now in a language with first class functions we may pass the control and return value to a callback instead of explicitly returning to the caller:
add(2, 3, function (sum) {
console.log(sum);
});
function add(x, y, cont) {
cont(x + y);
}
Thus instead of returning a value from a function we are continuing with another function. Therefore this function is called a continuation of the first.
So what's the difference between a continuation and a callback?
Best Answer
I believe that continuations are a special case of callbacks. A function may callback any number of functions, any number of times. For example:
However if a function calls back another function as the last thing it does then the second function is called a continuation of the first. For example:
If a function calls another function as the last thing it does then it's called a tail call. Some languages like Scheme perform tail call optimizations. This means that the tail call does not incur the full overhead of a function call. Instead it's implemented as a simple goto (with the stack frame of the calling function replaced by the stack frame of the tail call).
Bonus: Proceeding to continuation passing style. Consider the following program:
Now if every operation (including addition, multiplication, etc.) were written in the form of functions then we would have:
In addition if we weren't allowed to return any values then we would have to use continuations as follows:
This style of programming in which you are not allowed to return values (and hence you must resort to passing continuations around) is called continuation passing style.
There are however two problems with continuation passing style:
The first problem can be easily solved in JavaScript by calling continuations asynchronously. By calling the continuation asynchronously the function returns before the continuation is called. Hence the call stack size doesn't increase:
The second problem is usually solved using a function called
call-with-current-continuation
which is often abbreviated ascallcc
. Unfortunatelycallcc
can't be fully implemented in JavaScript, but we could write a replacement function for most of its use cases:The
callcc
function takes a functionf
and applies it to thecurrent-continuation
(abbreviated ascc
). Thecurrent-continuation
is a continuation function which wraps up the rest of the function body after the call tocallcc
.Consider the body of the function
pythagoras
:The
current-continuation
of the secondcallcc
is:Similarly the
current-continuation
of the firstcallcc
is:Since the
current-continuation
of the firstcallcc
contains anothercallcc
it must be converted to continuation passing style:So essentially
callcc
logically converts the entire function body back to what we started from (and gives those anonymous functions the namecc
). The pythagoras function using this implementation of callcc becomes then:Again you can't implement
callcc
in JavaScript, but you can implement it the continuation passing style in JavaScript as follows:The function
callcc
can be used to implement complex control flow structures such as try-catch blocks, coroutines, generators, fibers, etc.