Continuation Passing Style Revisited, Part One

Continuation Passing Style Revisited, Part One

Rate This
  • Comments 31

Good morning fabulous readers, let me just start by saying that this is going to get really long and really complicated but it will all pay off in the end. I’m also going to be posting on an accelerated schedule, more than my usual two posts per week. (It’ll eventually become clear why I'm doing all of this, he said mysteriously. Remember, suspense is a sign of a quality blog.)

I want to talk quite a bit about a subject that I first discussed briefly a few years back, namely, Continuation Passing Style (henceforth abbreviated CPS), a topic which many people (*) find both confusing and fascinating.

Before going on to read the rest of this series you might want to quickly refresh your memory of my brief introduction to CPS in JScript.

http://blogs.msdn.com/b/ericlippert/archive/tags/continuation+passing+style/

Welcome back. I hope that made sense. The JScript syntax for nested anonymous functions is pretty straightforward and similar to that of C# anonymous methods, so hopefully it was clear even if you don’t normally read JScript. In case you didn’t make it all the way through there, let me sum up:

The traditional style of programming with subroutines provides a programming model that goes like this:

  • make a note of what you were doing and what values your local variables had in some sort of temporary storage, aka "the stack"
  • transfer control to a subroutine until it returns
  • consult your notes; pick up where you left off, now knowing the result of the subroutine if there was one.

CPS is a style of programming in which there are no “subroutines” per se and no “returns”. Instead, the last thing that the current function does is call the next function, passing the result of the current function to the next function. Since no function ever "returns" or does work after it calls the next function, there’s no need to keep track of where you’ve been. It doesn’t matter where you were because you’re never coming back there. In order to ensure that things happen in the desired order, when calling the new function you typically pass a “continuation”, which is itself a function that executes “everything that comes next”.

I showed a way to hack this up in JScript. You make every function take a continuation. New continuations can be built as needed out of nested anonymous functions. Any time that you would have called a subroutine, instead you make a continuation that represents the work you still have yet to do, and logically pass that to the subroutine, so that it can execute it for you. In order to do this without consuming any stack in JScript, you can do this by passing the continuation to some sort of "orchestration" code that keeps track of what has to happen next. The orchestrator just sits there in a loop, dispatching the current continuation with the last-computed result. In languages that do not support CPS natively that’s pretty much the best you can do if you want to do full-on CPS programming without the consumption of stack.

CPS is interesting and useful because it has a lot of nice properties, many of which I did not explain in my first series of articles. I presented CPS solely as a way to deal with the problem of deep recursions; since there are no subroutine calls that ever return, there is no need to consume call stack. But CPS is about much more than just that. In particular, one of the things CPS lets us do is build new control flow primitives into a language by implementing control flow as methods. That might sound crazy, but let’s take a look at a very simple example of how we might build a control flow out of continuations.

Consider for example the ?: conditional operator. It makes a decision about what happens next and therefore is a form of control flow. Suppose we have methods string M(int x), bool B(), int C(), and int D(). We might have this fragment somewhere in our program:

M(B() ? C() : D())

Suppose now that the C# language did not have the ?: operator and you wanted to implement it as a library method call. You can’t just go:

T Conditional<T>(bool b, T consequence, T alternative)
{
  if (b) return consequence; else return alternative;
}

because now the consequence and alternative are evaluated eagerly, instead of lazily. But we could do this:

T Conditional<T>(bool b, Func<T> consequence, Func<T> alternative)
{
  if (b) return consequence(); else return alternative();
}

And now call

M(Conditional(B(), ()=>C(), ()=>D()))

We have our conditional operator implemented as a library method.

Now suppose we wanted to do the conditional operator in CPS because... because we're gluttons for punishment I guess. In CPS we have some continuation; something is going to happen after the call to M. Let’s call that the "current continuation", whatever it is. How we obtain it is not important, just suppose we have it in hand.

We need to rewrite B so that it takes a continuation that accepts a bool. “A continuation that takes a bool” sounds an awful lot like an Action<bool>, so let’s assume that we can rewrite bool B() to be void B(Action<bool>).

What is the continuation of B, the "thing that happens after"? Let’s take it one step at a time.

B(b=>M(Conditional(b, ()=>C(), ()=>D)))

We have B in CPS, but the lambda passed to B is not in CPS because it does two things: calls Conditional, and calls M. To be in CPS it has to call something as the last thing it does. Let’s repeat the analysis we just did for B. M needs to take an int and an Action<string>. C and D need to take Action<int>. What about Conditional? It still needs to lazily evaluate its arguments, but calling those lambdas cannot return a value either; rather, they have to take continuations too:

B(b=>Conditional(b, c=>C(c), c=>D(c), t=>M(t, currentContinuation)))

Conditional now looks like this:

void Conditional<T> (bool condition, Action<Action<T>> consequence, Action<Action<T>> alternative, Action<T> continuation)
{
  if (condition) consequence(continuation) ; else alternative(continuation);
}

Summing up: B executes and passes its bool result to a lambda. That lambda passes b and three different lambdas to Conditional. Conditional decides which of the first two delegates to pass the third delegate - the continuation - to. Suppose it chooses the alternative. The alternative, D, runs and passes its result to the continuation, which is t=>M(currentContinuation, t). M then does its thing with integer t, and invokes whatever the current continuation of the original call was, and we’re done.

There are no more returns. Every method is void. Every delegate is Action. The last thing any method does is invokes another method. We no longer need a call stack because we never need to come back. If we could write a C# compiler that optimized code for this style of programming then none of these methods would consume any call stack beyond their immediate requirements to store locals and temporaries.

And, holy goodness, what a mess we turned that simple operation into. But you see what we did there? I defined a CPS version of the ?: operator as a library method; the fact that the consequence and alternative are lazily evaluated is accomplished by rewriting them as lambdas. The control flow is then accomplished by passing the right continuation to the right method.

But so what? We’ve done nothing here that couldn’t have been done much more easily without continuations. Here’s the interesting bit: continuations are the reification of control flow. So far we’ve only been talking about systems where there is a single continuation being passed around. Since continuations are effectively just delegates, there’s no reason why you can’t be passing around multiple continuations, or stashing them away for later use. By doing so we can construct arbitrarily complex control flows as library methods by keeping track of multiple continuations and deciding which one gets to go next.

Next time: some musings on more complicated control flows.

(*) Including myself.

  • Way to go with the suspense!

    With more FP seeping into C#, my hours sweating over F# will pay off. Bring it on!

    I used CPS recently to create stackoverflow.com/.../3912723.

  • Eric, you keep repeating 'That's probably a coincidence'. How are you not certain it is a coincidence?

    // Ryan

  • Whenever I see CPS I can't help but think about my beginnings when IF-THEN and GOTO were the only control flow mechanisms I knew. I'm anxious to see some CPS code that isn't as hard to understand as the GOTO-laden BASIC code I used to write 25+ years ago.

  • Hi Eric,

    Thanks for this post! Just for my understanding, could I state that 'continuations are to gotos, what delegates are to functions'? So in effect you'd passing goto's around as objects, as a 'first class citizens? And have some language 'training wheels' to fight the downsides of gotos?

    That is a nice way of thinking of it. - Eric

    I once had to write a pretty complicated algorithm to find values in a kind of OLAP datastructure. In the end we had the whole thing written out in a flowchart. we went up the tree in one hierarchy until we were at the root. When that didn't give us the value we had to move to the parent in a second hierarchy and start again on the original member off the first hierarchy.

    In the flowchart, that's a box that says 'SearchObj = SecondHierarchy.Parent' and then an arrow to the top of the flowchart. But doing that with function calls was very akward, because when you eventually found your value, you'd return to all the places where it jumped to the top. So you'd need code there to stop it from searching on.

    When I switched to gotos the whole thing became extremely simple and screaming fast. But that turned into quite a fit because the other programmers just went bezerk at the gotos.

    I personally think that, although old Edsger was right that gotos easily lead to code that is hard to reason about, they actually do hit a sweetspot in certain situatons. Maybe they sould be redeemed just a little.

    Also VERY excited about C# 5 being anounced, can't wait to get my hands on that compiler as a service stuff. That's in there right? Anders kind of promised that..

    It will not, and Anders promised no such thing. Speculations about feature sets of future products are not promises. - Eric

    Combining that with these continuations and the TPL will be pretty awesome...

    Don't get ahead of yourself here. I'm not saying anything about continuations being in any hypothetical, unannounce "C# 5". I'm just doing a few blog posts on a style of programming that I find relevant and interesting, at an accelerated rate, right before the PDC. - Eric

    Thanks!

    Gert-Jan

  • It might be worth noting the Don Syme just posted a pre-print of a conference paper formalizing F#'s async workflows and mentioning in passing how in "...C# versions of an asynchronous language modality, it is natural to support only asynchronous methods, and not asynchronous blocks or expressions".

    Oh, and did I mention that async workflows are both specified and implemented in terms of localized CPS transforms?

    Something in this vein would certainly be at the very top of my list of desirable features for the entirely hypothetical C# 5 that may hypothetically be announced next week.

  • What is the benefit of CPS for a simple, normal developer who develop a small protion of a huge system for years?

  • I guess the transformation of normal code to CPS style code can be done mechanically under some constraints. The code gets turned inside out just like it is the case with enumerators. And like the async keyword... ;-)

  • This is uber-exciting. Anything built-in language support for this would really help many fields at once: async, parallel, observable, microthreaded, and UI programming. Even if no language features come out of it, reusable library methods would be welcomed. This, combined with your immutable collections library, could produce some truly interesting projects.

  • Thank you! Really fascinating article! Continuations are cool to spend some time thinking about.

    F# equivalent is pretty nice too:

    let Conditional<'T> b consequence alternative continuation =
       continuation |> if b then consequence else alternative;;
    B(fun b -> Conditional<int> b (fun c -> C c) (fun c -> D c)
    (fun t -> M t continuation));;

    I had a fun trying to make while-loop continuation styled. Actually, it's not so easy as it looks.

    int i = 0;
    while(i++ < 6)
      Console.WriteLine(i);

    A little more complex

    int i = I();
    while(Incr(i) < Six())
      F(i);

    Loops are not so obvious and my solution's not very beautiful but...

    void While(int i, Action<int, Action<int>> modification,
      Action<int, Action<bool>> action,
      Action<int, Action> continueAction,
      Action afterAction)
    {
    action(i, b => {
      if (b) {
        continueAction(i,
          () => modification(i,
            j => While(j, modification, action, continueAction, afterAction)));
       }
       else
          afterAction();
      });
    }

    And here it is:

    I(i => While(i,
      Incr,
      (j, action) => Six(x => Less(j, x, less => action(less))),
      F,
      myContinuation));

    P.S. maybe you missed a bracket in B(b=>M(Conditional(b, ()=>C(), ()=>D)))?

  • Quick, teach us some ugly CPS assembly language before you unveil some cool new language syntax and transformations, and nobody wants to learn this anymore ;-)

    (hypothetically speaking)

    @Szindbad: their benefit is that people who care can build better frameworks for people who don't, so that they're not that prone to shoot themselves in the foot (we'll do that for you!)

  • I might be committing a sacrilege here, but how is CPS different from GOTO? I mean, really? It is pretty much the same non-returning control transfer to another part of code. The only difference is that CPS call carries some parameters.

    Given that functions evolved from plain goto-controlled code, and considering the today's underlying complexity of the OS and other involved libraries, this is a bit like building an electronic device simulator to create a processor simulation in it, then running actual code there.

    What could be the actual benefit in that? So far, the only practical example involved stack overflow with deep recursions. The tree traversal example (and pretty much any deep recursion) can be rewritten in a way that would use considerably less stack.

  • What's the difference between a Continuation and a Program Counter jmp location?

    Am I correct in thinking nothing if you only have global state? ie the difference is in the closure - and you always close over global state.

  • This is 100% effective for a sequence of sequential operations done in batch processing.

  • Hi,

    I cannot read the link to JScript CPS that is mentioned in the article. Can uou check it?

    regards,

  • Umm, why would ever do THAT? Event driven programming would directly contradict this paradigm, wouldn't it?

Page 2 of 3 (31 items) 123