Continuation-Passing Style

There are some technical words that cause quite a stir even amongst geeks.  When someone says the word "continuation", people's eyes glaze over and they seek the first opportunity to change the subject.  The stir is caused because most people don't understand what a continuation is or why someone would want to use one.  This is unfortunate, because they really are rather more simple than they sound.

Defining Continuations

A continuation represents the remainder of a computation given a point in that computation.  For example, suppose that two methods are defined: M and Main.  The method Main invokes M and then writes "Done" to the console.  The method M assigns x the value five, invokes F, increments x, and writes x to the console.

 static void M()
{
    var x = 5;
    F();  // <----------- Point in the computation
    ++x;
    Console.WriteLine(x);
}

static void Main()
{
    M();
    Console.WriteLine("Done");
}

The continuation of the computation at the invocation of F is the remainder of the program execution beginning with incrementing x in the method M.  In this case, the continuation includes incrementing x, writing x, returning to Main, and writing "Done" to the console.

Some languages give programmers explicit access to continuations.  For example, Scheme has a function which calls a function passing a function representing the current continuation.  The function is aptly named call with current continuation or call/cc.  If such a function existed in .NET it might return a T given a delegate that returns a T given a delegate from T to T.

 T CallCC<T>(Func<Func<T,T>, T> f)

Continuations are the functional counterparts of GOTOs both in power and inscrutability.  They can express arbitrary control flow like coroutines and exceptions while bewildering some of the brightest programmers.

Returning Values with Continuations

The simplest use of a continuation is to simulate returning out of a function.  Suppose that .NET had the function CallCC.  If Main calls a function Foo passing the value four and if Foo immediately invokes CallCC with a lambda that binds Return to the continuation at the point of the call to CallCC, then when Return is invoked inside of the lambda with the value four, computation will immediately jump out of the lambda to the point after CallCC but before the return with the value four on the stack.  This happens regardless what of occurs after the invocation of Return inside the lambda.

 static int Foo(int n)
{
    return CallCC<int>(Return =>
        {
            Return(n);
            return n + 1;
        });
}

static void Main()
{
    Foo(4);
}

The result of running the program is therefore four and not five.

All of this demonstrates that returning from a function is equivalent to invoking the continuation defined at the function's call-site.  When a function "returns", it implicitly invokes the continuation of its call-site.

When people explain continuations, they usually discuss stack frames and instruction pointers.  It is easy to see why.  The implicit invocation of the "return" continuation restores the stack frame at the call-site and sets the instruction pointer to the instruction immediately after the call-site.  This is what invoking a continuation does: restore the appropriate stack frame and set the instruction pointer.

Continuation-Passing Style

It is still possible to use continuations if a language does not support a function like call/cc.  A programmer can explicitly construct the continuation of a computation and pass it directly to a function.

To illustrate this transformation, suppose that a function, Identity, is defined that returns the value it is given.

 static T Identity<T>(T value)
{
    return value;
}

The return statement in Identity implicitly invokes the continuation of the call-site causing computation to leave Identity and resume at the point immediately after the invocation of Identity at the call-site.  If Main contains only a call to WriteLine passing the result of the call to Identity, then computation resumes with the call to WriteLine.

 static void Main()
{
    Console.WriteLine(Identity("foo"));
}

However, instead of implicitly invoking Identity's continuation, the programmer can pass the continuation to Identity explicitly.  An extra argument is added to Identity which is a void-returning delegate with one parameter that is the same type as the return type of the former Identity function.

 static void Main()
{
    Identity("foo", s => Console.WriteLine(s));
}

static void Identity<T>(T value, Action<T> k)
{
    k(value);
}

At the call-site, the remainder of the computation has moved into the lambda passed to Identity.  The continuation is explicitly passed.  On the callee's side, the return statement is replaced by the invocation of the continuation parameter, k, with the return value.

This pattern is called continuation-passing style or CPS.

Converting to CPS

Now that we know enough to be dangerous, let's see what we can do.  Consider the typical Max function.

 static int Max(int n, int m)
{
    if (n > m)
        return n;
    else
        return m;
}

To convert this function to CPS, follow these steps:

1.  Change the return type to void

2.  Add an extra argument of type Action<T> where T is the original return type

3.  Replace all return statements with invocations of the new continuation argument passing the expression used in the return statement

Applying these steps to the integer version of Max, the function now returns void, takes an extra parameter, k, of type Action<int> , and invokes k everywhere a return statement appeared.

 static void Max(int n, int m, Action<int> k)
{
    if (n > m)
        k(n);
    else
        k(m);
}

To convert the call-site to CPS:

1.  Remove all of the remaining computation after the call-site

2.  Put the remaining computation in the body of the lambda corresponding to the continuation argument

For example, suppose the user defined a method Main which invokes WriteLine with the result of applying Max to three and four.

static void Main()

{

Console.WriteLine(Max(3, 4));

}

The remaining computation after the invocation of Max is the call to WriteLine.  Therefore, the call to WriteLine is moved into the lambda representing the continuation passed to Max.

static void Main()

{

Max(3, 4, x => Console.WriteLine(x));

}

The steps for converting the call-site skirted the issue of what to do with return statements in the continuation.  For example, suppose there are three methods Main, F, and G where Main calls F and F calls G.   To convert F and G to CPS, follow the same transformation steps as with Max.

 static void Main()
{
    Console.WriteLine(F(1) + 1);
}

static int F(int n)
{
    return G(n + 1) + 1;
}

static int G(int n)
{
    return n + 1;
}

However, what should the transformation do with the return statement in F?  The continuation passed to G should definitely not attempt to return a result because the continuation is a void-returning delegate.

 static void F(int n, Action<int> k)
{
    G(n + 1, x => { return x + 1; });  // error, Action<int> cannot return a value
}

That wouldn't make any sense.  Delegates with void return-types cannot return values.  Furthermore, the code completely ignores k.

Instead, the return statement should be transformed into an invocation of k.

 static void Main()
{
    F(1, x => Console.WriteLine(x + 1));
}

static void F(int n, Action<int> k)
{
    G(n + 1, x => k(x + 1));
}

static void G(int n, Action<int> k)
{
    k(n + 1);
}

This is how functions that use explicit continuations are composed together.

What about recursive functions like Factorial?

 static void Main()
{
    Console.WriteLine(Factorial(5));
}

static int Factorial(int n)
{
    if (n == 0)
        return 1;
    else
        return n * Factorial(n - 1);
}

Recursive functions can be transformed just as easily following the same steps.

 static void Main()
{
    Factorial(5, x => Console.WriteLine(x));
}

static void Factorial(int n, Action<int> k)
{
    if (n == 0)
        k(1);
    else
        Factorial(n - 1, x => k(n * x));
}

CPS turns a program inside-out.  In the process, the programmer may feel that his brain has been turned inside-out as well.

Why CPS?

What exactly can a programmer do with CPS besides showoff at parties?

Compilers use a more thorough CPS transformation to produce an intermediate form amenable to many analyses.  UI frameworks use CPS to keep the UI responsive while allowing nonlinear program interaction.  Web servers use CPS to allow computation to flow asynchronously across pages.

Most programmers have used functions which take a callback.  Often, the callback is the code that is invoked upon completion of the function.  In these cases, the callback is an explicitly-passed continuation.

Asynchronous Calls

Hiding network latency requires asynchronous calls.  In the first technology preview, Volta allows programmers to add asynchronous versions of methods on tier boundaries.

 [RunAtOrigin]
static class C
{
    public static int F(string s)
    {
        return s != null ? s.Length : 0;
    }
}

To make a method asynchronous, define the CPS-equivalent method signature and annotate it with the Async attribute.  Volta will generate the body and modify the call-sites accordingly.

 [Async]
public static void F(string s, Action<int> k);

If the programmer invokes an asynchronous method F, then Volta will launch the invocation on another thread and invoke the continuation upon completion of the call to F.

 C.F("foo", x => Console.WriteLine(x));

Wrapping it Up

Continuations are powerful.  CPS gives programmers a way to use continuations in their day-to-day work.  Perhaps, someday soon we'll discuss how to make CPS more palatable, but we will need to discuss the "M" word first.