What's the difference between a continuation and a callback?

Question

I believe that continuations are a special case of callbacks. A function may callback any number of functions, any number of times. For example:

var array = [1, 2, 3];

forEach(array, function (element, array, index) {
    array[index] = 2 * element;
});

console.log(array);

function forEach(array, callback) {
    var length = array.length;
    for (var i = 0; i < length; i++)
        callback(array[i], array, i);
}

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:

var array = [1, 2, 3];

forEach(array, function (element, array, index) {
    array[index] = 2 * element;
});

console.log(array);

function forEach(array, callback) {
    var length = array.length;

    // This is the last thing forEach does
    // cont is a continuation of forEach
    cont(0);

    function cont(index) {
        if (index < length) {
            callback(array[index], array, index);
            // This is the last thing cont does
            // cont is a continuation of itself
            cont(++index);
        }
    }
}

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:

console.log(pythagoras(3, 4));

function pythagoras(x, y) {
    return x * x + y * y;
}

Now if every operation (including addition, multiplication, etc.) were written in the form of functions then we would have:

console.log(pythagoras(3, 4));

function pythagoras(x, y) {
    return add(square(x), square(y));
}

function square(x) {
    return multiply(x, x);
}

function multiply(x, y) {
    return x * y;
}

function add(x, y) {
    return x + y;
}

In addition if we weren't allowed to return any values then we would have to use continuations as follows:

pythagoras(3, 4, console.log);

function pythagoras(x, y, cont) {
    square(x, function (x_squared) {
        square(y, function (y_squared) {
            add(x_squared, y_squared, cont);
        });
    });
}

function square(x, cont) {
    multiply(x, x, cont);
}

function multiply(x, y, cont) {
    cont(x * y);
}

function add(x, y, cont) {
    cont(x + y);
}

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:

1. Passing around continuations increases the size of the call stack. Unless you're using a language like Scheme which eliminates tail calls you'll risk running out of stack space.
2. It's a pain to write nested functions.

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:

Function.prototype.async = async;

pythagoras.async(3, 4, console.log);

function pythagoras(x, y, cont) {
    square.async(x, function (x_squared) {
        square.async(y, function (y_squared) {
            add.async(x_squared, y_squared, cont);
        });
    });
}

function square(x, cont) {
    multiply.async(x, x, cont);
}

function multiply(x, y, cont) {
    cont.async(x * y);
}

function add(x, y, cont) {
    cont.async(x + y);
}

function async() {
    setTimeout.bind(null, this, 0).apply(null, arguments);
}

The second problem is usually solved using a function called call-with-current-continuation which is often abbreviated as callcc. Unfortunately callcc can't be fully implemented in JavaScript, but we could write a replacement function for most of its use cases:

pythagoras(3, 4, console.log);

function pythagoras(x, y, cont) {
    var x_squared = callcc(square.bind(null, x));
    var y_squared = callcc(square.bind(null, y));
    add(x_squared, y_squared, cont);
}

function square(x, cont) {
    multiply(x, x, cont);
}

function multiply(x, y, cont) {
    cont(x * y);
}

function add(x, y, cont) {
    cont(x + y);
}

function callcc(f) {
    var cc = function (x) {
        cc = x;
    };

    f(cc);

    return cc;
}

The callcc function takes a function f and applies it to the current-continuation (abbreviated as cc). The current-continuation is a continuation function which wraps up the rest of the function body after the call to callcc.

Consider the body of the function pythagoras:

var x_squared = callcc(square.bind(null, x));
var y_squared = callcc(square.bind(null, y));
add(x_squared, y_squared, cont);

The current-continuation of the second callcc is:

function cc(y_squared) {
    add(x_squared, y_squared, cont);
}

Similarly the current-continuation of the first callcc is:

function cc(x_squared) {
    var y_squared = callcc(square.bind(null, y));
    add(x_squared, y_squared, cont);
}

Since the current-continuation of the first callcc contains another callcc it must be converted to continuation passing style:

function cc(x_squared) {
    square(y, function cc(y_squared) {
        add(x_squared, y_squared, cont);
    });
}

So essentially callcc logically converts the entire function body back to what we started from (and gives those anonymous functions the name cc). The pythagoras function using this implementation of callcc becomes then:

function pythagoras(x, y, cont) {
    callcc(function(cc) {
        square(x, function (x_squared) {
            square(y, function (y_squared) {
                add(x_squared, y_squared, cont);
            });
        });
    });
}

Again you can't implement callcc in JavaScript, but you can implement it the continuation passing style in JavaScript as follows:

Function.prototype.async = async;

pythagoras.async(3, 4, console.log);

function pythagoras(x, y, cont) {
    callcc.async(square.bind(null, x), function cc(x_squared) {
        callcc.async(square.bind(null, y), function cc(y_squared) {
            add.async(x_squared, y_squared, cont);
        });
    });
}

function square(x, cont) {
    multiply.async(x, x, cont);
}

function multiply(x, y, cont) {
    cont.async(x * y);
}

function add(x, y, cont) {
    cont.async(x + y);
}

function async() {
    setTimeout.bind(null, this, 0).apply(null, arguments);
}

function callcc(f, cc) {
    f.async(cc);
}

The function callcc can be used to implement complex control flow structures such as try-catch blocks, coroutines, generators, fibers, etc.

Despite the wonderful writeup, I think you're confusing your terminology a bit. For example, you are correct that a tail call happens when the call is the last thing a function needs to execute, but in relation to continuations, a tail call means the function does not modify the continuation that it is called with, only that it updates the value passed to the continuation (if it desires). This is why converting a tail recursive function to CPS is so easy (you just add the continuation as a parameter and call the continuation on the result).

It's also a bit odd to call continuations a special case of callbacks. I can see how they are easily grouped together, but continuations didn't arise from the need to distinguish from a callback. A continuation actually represents the instructions remaining to complete a computation, or the remainder of the computation from this point in time. You can think of a continuation as a hole that needs to be filled in. If I can capture a program's current continuation, then I can go back to exactly how the program was when I captured the continuation. (That sure makes debuggers easier to write.)

In this context, the answer to your question is that a callback is a generic thing that gets called at any point in time specified by some contract provided by the caller [of the callback]. A callback can have as many arguments as it wants and be structured in any way it wants. A continuation, then, is necessarily a one argument procedure that resolves the value passed into it. A continuation must be applied to a single value and the application must happen at the end. When a continuation finishes executing the expression is complete, and, depending on the semantics of the language, side effects may or may not have been generated.

The short answer is that the difference between a continuation and a callback is that after a callback is invoked (and has finished) execution resumes at the point it was invoked, while invoking a continuation causes execution to resume at the point the continuation was created. In other words: a continuation never returns.

Consider the function:

function add(x, y, c) {
    alert("before");
    c(x+y);
    alert("after");
}

(I use Javascript syntax even though Javascript doesn't actually support first-class continuations because this was what you gave your examples in, and it will be more comprehensible to people not familiar with Lisp syntax.)

Now, if we pass it a callback:

add(2, 3, function (sum) {
    alert(sum);
});

then we will see three alerts: "before", "5" and "after".

On the other hand, if we were to pass it a continuation that does the same thing as the callback does, like this:

alert(callcc(function(cc) {
    add(2, 3, cc);
}));

then we would see just two alerts: "before" and "5". Invoking c() inside add() ends the execution of add() and causes callcc() to return; the value returned by callcc() was the valued passed as the argument to c (namely, the sum).

In this sense, even though invoking a continuation looks like a function call, it is in some ways more akin to a return statement or throwing an exception.

In fact, call/cc can be used to add return statements to languages that don't support them. For example, if JavaScript didn't have return statement (instead, like many Lisp languages, just returning the value of the last expression in the function body) but did have call/cc, we could implement return like this:

function find(myArray, target) {
    callcc(function(return) {
        var i;
        for (i = 0; i < myArray.length; i += 1) {
            if(myArray[i] === target) {
                return(i);
            }
        }
        return(undefined); // Not found.
    });
}

Calling return(i) invokes a continuation that terminates the execution of the anonymous function and causes callcc() to return the index i at which target was found in myArray.

(N.B.: there are some ways in which the "return" analogy is a bit simplistic. For example, if a continuation escapes from the function it was created in - by being saved in a global somewhere, say - it is possible that the function that created the continuation can return multiple times even though it was only invoked once.)

Call/cc can similarly be used to implement exception handling (throw and try/catch), loops, and many other contol structures.

To clear up some possible misapprehensions:

• Tail call optimisation is not by any means required in order to support first-class continuations. Consider that even the C language has a (restricted) form of continuations in the form of setjmp(), which creates a continuation, and longjmp(), which invokes one!

  • On the other hand, if you naively try to write your program in continuation passing style without tail call optimisation you are doomed to eventually overflow the stack.

• There is no particular reason a continuation need take only one argument. It's just that argument(s) to the continuation become the return value(s) of call/cc, and call/cc is typically defined as having a single return value, so naturally the continuation must take exactly one. In languages with support for multiple return values (like Common Lisp, Go, or indeed Scheme) it would be entirely possible have continuations that accept multiple values.