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.

Comments

  • Anonymous
    December 21, 2007
    The comment has been removed

  • Anonymous
    December 22, 2007
    I'd like to add that CPS can also be used to simulate message-passing systems like Erlang or Scala have in a language without threads, including Javascript.  In that case, you do something like the following Python: receive(lambda msg : print msg) Of course, that only receives one message. To loop, you need to either call more receives in the passed cotinuation or play trickery with specific language features like generators.

  • Anonymous
    December 22, 2007
    As a quick note adding to Peter Thatcher's comment: Indeed, continuations and/or continuation passing style (CPS) can be used to implement concurrency (i.e. implement very lightweight threads) with user-definable schedulers.  By itself, it would be cooperative concurrency. I'd like to expand the UI comment as well.  As you say, the CPS transformation systematically takes "normal" code (called direct style) and turns it "inside-out."  Why do you want your code inside-out?  You don't.  Unfortunately, some interfaces, specifically event-based ones, require it, e.g. many GUI frameworks and web applications.  If the language has support for CallCC, you can write the direct style code and have it transparently work with an event-based GUI framework.  When you first started programming, you might have written a program that reads two numbers from the console and displays the sum.  With continuations, you could write code of that simplicity and have it work for GUIs or web applications (in fact, you could make it so that the exact same code will do all three depending on how you instantiate it.) Continuation passing style is one way to support CallCC if your language doesn't, but unfortunately, continuation passing style is of very limited utility in C#.  CPS transforming your code causes all functions in it to never return.  Since, you can't rely on tail call optimization, this means that the stack will just build and build until it overflows.  You can avoid this to some degree, but only by avoiding many of the sort of things that make CPS and continuations interesting.  One of the things you can still do is the "uninversion" of control described above with regards to event-based systems. (You end up inadvertently implementing tail calls through trampolining.)

  • Anonymous
    December 22, 2007
    Derek & Peter: Fantastic comments. We use CPS to implement cooperative threading in JavaScript in Volta. It is definitely true that a full CPS transform isn't very helpful in C# (to humans), but there are still many areas where it helps to convert portions of code to CPS. As you have probably guessed, my next post will start to show another way (without CallCC) to take advantage of CPS without turning code inside-out.

  • Anonymous
    January 06, 2008
    Great post Wes! Do you mean by "M" the monadic one? Anyway, I hope to see some useful monads in C#, and maybe some syntax help for it from the language who knows...

  • Anonymous
    January 10, 2008
    If the word &quot;continuation&quot; causes eyes to glaze over, then the word &quot;monad&quot; induces

  • Anonymous
    January 21, 2008
    We've been using this for more than 20 years to fake mutithreading on single CPU embedded machine in C.  these environments typically do not have threading and usually have almost no Operating System.

  • Anonymous
    February 01, 2008
    To explain a complex concept in a simple and  very understandable way is a contribution. I really do not understand why other mathematicians explain the simple word in a complicated way. If this page were available earlier, my thesis could have been finished better.

  • Anonymous
    August 11, 2008
    The comment has been removed