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.

https://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

• Anonymous
  October 20, 2010
  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" :)

• Anonymous
  October 20, 2010
  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...

• Anonymous
  October 20, 2010
  "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

• Anonymous
  October 20, 2010
  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?

• Anonymous
  October 20, 2010
  The comment has been removed

• Anonymous
  October 21, 2010
  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.

• Anonymous
  October 21, 2010
  eagerly awaiting the unveiling of the mystery ...

• Anonymous
  October 21, 2010
  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

• Anonymous
  October 21, 2010
  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...

• Anonymous
  October 21, 2010
  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

• Anonymous
  October 21, 2010
  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.

• Anonymous
  October 21, 2010
  The comment has been removed

• Anonymous
  October 21, 2010
  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.

• Anonymous
  October 21, 2010
  Wasn't async stuff already previewed last PDC? It will need such a feature. That's probably a coincidence too. - Eric

• Anonymous
  October 21, 2010
  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);        }    } }

• Anonymous
  October 21, 2010
  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.

• Anonymous
  October 21, 2010
  Eric, you keep repeating 'That's probably a coincidence'. How are you not certain it is a coincidence? // Ryan

• Anonymous
  October 21, 2010
  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.

• Anonymous
  October 21, 2010
  The comment has been removed

• Anonymous
  October 21, 2010
  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.

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

• Anonymous
  October 21, 2010
  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... ;-)

• Anonymous
  October 21, 2010
  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.

• Anonymous
  October 22, 2010
  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)))?

• Anonymous
  October 22, 2010
  The comment has been removed

• Anonymous
  October 24, 2010
  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.

• Anonymous
  October 28, 2010
  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.

• Anonymous
  October 29, 2010
  This is 100% effective for a sequence of sequential operations done in batch processing.

• Anonymous
  November 02, 2010
  Hi, I cannot read the link to JScript CPS that is mentioned in the article. Can uou check it? regards,

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

• Anonymous
  April 12, 2011
  Eric, does not look like the link is taking me to a correct page blogs.msdn.com/.../continuation+passing+style