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.

  • 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" :)

  • 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...

  • "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

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

  • 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

  • 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.

  • eagerly awaiting the unveiling of the mystery ...

  • 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

  • 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...

  • 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

  • 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.

  • 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.  

  • 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.

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

    That's probably a coincidence too. - Eric

  • 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);

           }

       }

    }

Page 1 of 3 (31 items) 123