Continuation Passing Style Revisited, Part One


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.

Comments (31)

  1. chakrit says:

    Nice article, exactly what I've been trying to do with my lib … and I'm rewriting it into an even better CPS system save for a bug I've mailed you about.

    That aside, I'm looking forward to your "pay off in the end" πŸ™‚

  2. configurator says:

    You sound excited. So am I! CPS is very useful, although painful if not built-in to the language. I was wondering how to implement call/cc in .net…

  3. Will says:

    "I'm going to start this series of posts about a possible new language feature a week before PDC and post unusually quickly, but you won't be able to guess why"

    The timing is probably a coincidence. – Eric

  4. configurator says:

    I'd like to note that continuations can be referred to as a stack – each continuation would have its continuation contained within. While it can't be statically allocated like the 'normal' stack, it's still very much a stack. Let's look at it a bit differently:

    A register machine I've just invented has two styles: "Normal", and CPS. In Normal style, the calling convention is: Push the return address onto the stack, push all function parameters, and jump to the function's location. To return, the function will pop the return address and jump to that. In CPS style, you don't push a return address; instead, the first parameter is the continuation. So, you push a continuation onto the stack, push all function parameters, and jump to the function's location. To return, the function will pop the return address and jump to that.

    Wait a second! They're exactly the same! If the original stack wasn't statically allocated but a dynamic stack instead, there would be no difference at all.

    I'm ignoring a lot here (e.g. closed variables), but the idea that they are two representations of the same thing still holds. Doesn't it?

  5. configurator says:

    Or is that exactly what you meant when you said continuations are the reification of control flow?

    You are spot on. A few additional thoughts. First off, note that there is no need for the call stack and the local variable stack to be the same data structure. That local data and return addresses share a structure in x86 architectures is in my opinion a design flaw that leads to security problems like buffer overruns smashing the return address. If they are logically or actually separate data structures then the call stack is essentially a list of nested continuations and the data stack is essentially a set of closures. Continuation passing style just makes those things explicit first class entities that can be manipulated programmatically.

    But continuations are more powerful than a call stack; with continuations you can run them in any order, do non-local gotos, resume where you left off after an exception, whatever you want. Those things are a lot harder to do with a call stack. – Eric

  6. Luke Sandberg says:

    This is somewhat like how control flow operators are implements in smalltalk.  for example bool is an abstract object which has a method called 'ifTrue: ablock ifFalse: aBlock'  where blocks are essentially Actions. and there are similar constructs for 'while' which is essentially a method on the Func<bool> class.  Though it still uses 'returns' for control flow.

    I think there would be some value in refactoring these new control flow operators as extension methods on their controlling statements.

  7. don says:

    eagerly awaiting the unveiling of the mystery …

  8. Samuel Jack says:

    Are we allowed to speculate where this is going?

    I'm guessing that you're leading up to an announcement at PDC 2010 about resumable methods being part of C# 5 (first trailed at PDC 2009 – blog.functionalfun.net/…/future-directions-for-c-and-visual.html).

    Am I close?

     

    You are allowed to speculate as much as you like. Speculate away! I will ignore your speculations and neither confirm nor deny the existence of any unannounced hypothetical "C# 5" product or any feature that it hypothetically might or might not implement. – Eric

  9. Jon Skeet says:

    Nice. Are there any points for guessing the mystery reason? πŸ˜‰

    When you wrote: "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."

    … how would that tie in with languages which don't explicitly have CPS support per se, but *do* perform tail-call optimization in a guaranteed fashion? (Would F# be such a language? Or would you consider F# to have CPS support?)

    Oh, and I *must* try to get reification and homoiconicity into the same sentence in a non-trivial way some time. I don't think $5 is enough for those words…

  10. configurator says:

    Wait a second… Is this to do with next week's announcement of C# 5?

    Any of Eric's musings on hypothetical unannounced products like a hypothetical "C# 5" would be "for entertainment purposes only". – Eric

  11. Daniel Earwicker says:

    Another excellent topic, and in real-world JS almost all library functions and huge swathes of application code are written in CPS, so it is in danger of becoming the most commonly used style of programming in the world!

    jQuery apps are full of little chains like:

     button.click(function() {

         button.animate({ opacity: 0 }, function() {

             button.animate({ opacity: 100 });

         });

     });

    The continuation is stashed somewhere, and later woken up so it can continue happily, for any of a number of reasons: a button was clicked, a timer completed, a download is done, an animation finished…

    I personally find it a joy to use. It makes UI development a breeze.

  12. Mark Knell says:

    Gaa. Some of us working stiffs don't have the time to give your sagas the attention they deserve. Not that I'm suggesting you do anything different.

    What I need is a way to add you to my Netflix queue.  

  13. jader3rd says:

    The closest thing this reminds me of is the TPL ContinueWith() methods. If a language was contructed to be CPS based, I could see it being easier for a system to auto break up serial code into parallel code.

  14. Dmitry Zaslavsky says:

    Wasn't async stuff already previewed last PDC? It will need such a feature.

    That's probably a coincidence too. – Eric

  15. DRBlaise says:

    I am very excited about this topic.  I decided to write the TreeDepth JScript code from the previous postings in C#.  It came out pretty well I thought:

    public static class BinaryTreeExtension

    {

       public static int TreeDepth<T>(this IBinaryTree<T> tree)

       {  //use CPS logic

           int depth = 0;

           Action<dynamic> contFunc = curDepth => depth = curDepth;

           Continue(TreeDepth<T>, new { Tree = tree, ContFunc = contFunc });

           Run();

           return depth;

       }

       static void TreeDepth<T>(dynamic args)

       {

           IBinaryTree<T> tree = args.Tree;

           Action<dynamic> contFunc = args.ContFunc;

           if (tree == null)

               Continue(contFunc, 0);

           else

           {

               Action<dynamic> afterLeft = leftDepth =>

               {

                   Action<dynamic> afterRight = rightDepth =>

                   {

                       Continue(contFunc, 1 + Math.Max(leftDepth, rightDepth));

                   };

                   Continue(TreeDepth<T>, new { Tree = tree.Right, ContFunc = afterRight });

               };

               Continue(TreeDepth<T>, new { Tree = tree.Left, ContFunc = afterLeft });

           }

       }

       static dynamic continueFunction = null;

       static void Continue(Action<dynamic> function, dynamic args)

       {

           continueFunction = new { Function = function, Args = args };

       }

       static void Run()

       {

           while (continueFunction != null)

           {

               Action<dynamic> curFunction = continueFunction.Function;

               dynamic curArgs = continueFunction.Args;

               continueFunction = null;

               curFunction(curArgs);

           }

       }

    }

  16. Benjol says:

    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.

  17. Ryan Heath says:

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

    // Ryan

  18. Gabe says:

    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.

  19. Gert-Jan van der Kamp says:

    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

  20. Blake Coverett says:

    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.

  21. Szindbad says:

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

  22. tobi says:

    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… πŸ˜‰

  23. Jason says:

    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.

  24. Data says:

    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)))?

  25. Stefan Wenig says:

    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!)

  26. Stanislav Pugach says:

    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.

  27. RichB says:

    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.

  28. Greg says:

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

  29. itzhak Kasovitch says:

    Hi,

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

    regards,

  30. Confusious says:

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

  31. rvp says:

    Eric, does not look like the link is taking me to a correct page

    blogs.msdn.com/…/continuation+passing+style