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

Question

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:

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?

Answer 1

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.