Continuation Passing Style Revisited Part Two: Handwaving about control flow


Last time on Fabulous Adventures: “But we can construct arbitrarily complex control flows by keeping track of multiple continuations and deciding which one gets to go next.

Let’s look at an example of something more complex than a conditional. Consider a simplified version of “try-catch”, where there is no expression to the throw. A throw is simply a non-local goto that goes to the nearest enclosing catch. The traditional way to think about

void Q()
{
  try
  {
    B(A());
  }
  catch
  {
    C();
  }
  D();
}

int A()
{
    throw;
    return 0; // unreachable, but let’s ignore that
}
void B(int x) { whatever }
void C() { whatever }
void D() { whatever }

is “Remember that there is a catch block somewhere near here. Remember what you were doing. Call A(). If it returns normally, remember what you were doing and then call B(), passing the result from A(). If B() returns normally, call D(). If A() or B() do not return normally then look for that catch block you remembered earlier. Call C() and then D().

In the real CLR the code to implement throw is insanely complicated; it has to run around the call stack looking for filters and handlers, and so on. Suppose a language did not have try-catch built in. There’s no way that we could implement all that insane complication as a library method, even if we wanted to. Or is there? Can we make Try() and Throw() methods in a language that supports CPS?

We could start by passing two continuations around to every function that might throw: one “normal” continuation, and one “error” continuation. Let’s suppose that Q can throw. We’ll translate everything into “two continuation” CPS. So we now have:

void A(Action<int> normal, Action error)
{
    Throw(()=>normal(0), error);
}

That should make sense. What does A() do? It calls Throw, and then it returns zero by passing zero to its normal continuation. So the normal continuation of Throw is to pass zero to the normal continuation of A. (As we’ll shortly see, this is irrelevant because Throw by definition does not complete normally. But it’s just another function call, so let’s continue to treat it as one.)

void B(int x, Action normal, Action error) { whatever }
void C(Action normal, Action error) { whatever }
void D(Action normal, Action error) { whatever }

What’s the implementation of Throw? That’s easy! Throw invokes the error continuation and abandons the normal continuation.

void Throw(Action normal, Action error)
{
    error();
}

What’s the implementation of Try? That’s harder. What does try-catch do? It establishes a new error continuation for the try body, but not for the catch body. How are we going to do that? Let me pull this out of thin air, and we’ll see if it works:

void Try(Action<Action, Action> tryBody,
         Action<Action, Action> catchBody,
         Action outerNormal,
         Action outerError)
{
    tryBody(outerNormal, ()=>catchBody(outerNormal, outerError));
}

void Q(Action qNormal, Action qError)
{
    Try (
       /* tryBody      */ (bodyNormal, bodyError)=>A(
       /* normal for A */   x=>B(x, bodyNormal, bodyError),
       /* error for A  */   bodyError),
       /* catchBody    */ C,
       /* outerNormal  */ ()=>D(qNormal, qError),
       /* outerError   */ qError );
}

OK, first off, is this in CPS? Yes. Every method is void returning, every delegate is void returning, and every method or lambda has as its last act a call to some other method.

Is it correct? Let’s walk through it. We call Try and pass a try body, a catch body, a normal continuation and an error continuation.

The Try invokes the try body, which takes two continuations. Try passes outerNormal, which was ()=>D(qNormal, qError), as the normal continuation of the body.

It passes ()=>catchBody(outerNormal, outerError) as the error continuation of the body. So that we’re sure about what that does, let’s expand that out. The catch body was C. Therefore the error continuation of the body will be evaluated as ()=>C(()=>D(qNormal, qError), qError). (Make sure this step makes sense to you.)

What was the try body? It was (bodyNormal, bodyError)=>A(x=>B(x, bodyNormal, bodyError), bodyError). We now know what bodyNormal and bodyError are, so let’s expand those out too. When we expand all this out, the execution of the body will do:

A(
  x=>B(               // A’s normal continuation
    x,                // B’s argument
    ()=>D(            // B’s normal continuation
      qNormal,        // D’s normal continuation
      qError),        // D’s error continuation
    ()=>C(            // B’s error continuation
      ()=>D(          // C’s normal continuation
        qNormal,      // D’s normal continuation
        qError)
,      // D’s error continuation
      qError)),       // C’s error continuation
  ()=>C(              // A’s error continuation
    ()=>D(            // C’s normal continuation
      qNormal,        // D’s normal continuation
     
qError),        // D’s error continuation
    qError))          // C’s error continuation

So, the body invokes A. It immediately invokes Throw, passing some complicated thing as the normal continuation and ()=>C(()=>D(qNormal, qError), qError) as the error continuation.

Throw ignores its normal continuation, abandoning it, and invokes ()=>C(()=>D(qNormal, qError), qError).

What if C (or something it calls) throws? if C throws then control immediately transfers to qError – whatever error handler is in place during the call to Q. What if C completes normally? Its normal continuation is ()=>D(qNormal, qError), so if C completes normally then it invokes D.

What if D then throws? Then it calls qError. If D does not throw then eventually (we hope!) it calls qNormal.

Take a step back. What if we remove the Throw so that A doesn’t throw? What if it just passes zero to its normal continuation? Well, the normal continuation of A listed above is a call to B, so this passes zero to B. And as you can see from that, if B throws then it transfers control to C, and if B does not throw then it transfers control to D.

And there you go. We just implemented try-catch and throw as methods. Moreover, we implemented them both as single line methods. Apparently try-catch-throw is not very hard after all!

You see what I mean about CPS being the reification of control flow? A continuation is an object that represents what happens next, and that’s what control flow is all about: determining what happens next. Any conceivable control flow can be represented in CPS.

Any conceivable control flow is rather a lot. This works because all possible control flows are simply fancy wrappers around a conditional “goto”. “if” statements are gotos, loops are gotos, subroutine calls are gotos, returns are gotos, exceptions are gotos, they’re all gotos. With continuations the non-local branching nature of any particular flavor of goto is completely irrelevant. You can implement some quite exotic control flows with CPS. Resumable exceptions, conditionals that evaluate both branches in parallel, yield return, coroutines. Heck, you can write programs that run forwards and then run themselves again backwards if you really want to. If it’s a kind of control flow, then you can do it with CPS.

Next time: handwaving about coroutines.

 

 

Comments (25)

  1. OmariO says:

    Is it a sign of possible support of resumable methods in future versions of C#?

  2. James Dunne says:

    That is insanely cool, Eric. I learn something new every day from you! :)

  3. RichB says:

    How can you evaluate branches in parallel if each branch is side-effecting?

    Very carefully. – Eric

    I suppose a CPS language could also enforce a purely functional approach and then you'd need to get state monads in there to do things like IO.

    Yep. – Eric

  4. Samuel Jack says:

    This is making my brain salivate!

  5. Erik says:

    Excellent series so far, as usual – thanks! =)

  6. Stefan Wenig says:

    banging my head right now…

    shouldn't int A() and void B (int x) in CPS be

    void A(Action<int> normal, Action error)
    void B(int x, Action normal, Action error)

    Yes; there was a typo. Thanks! – Eric

  7. Stefan Wenig says:

    So we just need to

    a) turn A and B inside out to make it more readable, just like you did with extension methods for LINQ: Where(…).Select(…) instead of Select(Where(…), …) – in fact, a callcc extension method could do that on lambdas, if it weren't for the ugly cast to Action<….>:

    Extensions.ToAction((int x) => B(x, bodyNormal, bodyError)).CallCC (A, bodyError)

    b) get rid of the explicit passing-around of normal and error continuations. maybe along the lines of SelectMany-monads, using amplified types or some such?

    almost feels like there's just a little syntax missing so we could build this ourselves 😉

    a more general way to do monads (from/select kinda sucks, maybe some Haskell-like "do"), variadic generics (plee-ease!), implicitly typed lambdas…

    or am I totally wrong here? enough. my brain tries to escape my head.

  8. configurator says:

    The CLR's code for handling try and catch is indeed insanely complicated. But that's by choice. You didn't have to use the call stack for that – even if you're in a world with a call stack. You could have another stack for catches, but that has its own flaws – whether its dynamically or statically allocated. Using an extra method for error handling is exactly convertible to using a second stack for error handling. My point that CPS is just a different way to look at normal evaluation still stands. You said yesterday "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". Even if they're the same data structure it still holds – the continuation simply holds the closure in that case. And the continuation could hold the catch pointer. If we implemented it this way:

    class Continuation<T> {

      Action<T> action;

      Closed-over variables; // (can't really be represented in C#)

    }

    class CatchContinuation<T> : Continuation<T> {

      Action<Exception> catchAction;

    }

    Then the error handler would be pretty simple.

    in Continuation: {

     public virtual void Catch(Exception ex) {

       action.Catch(ex);

     }

    }

    in CatchContinuation: {

     public override void Catch(Exception ex) {

       catchAction(ex);

     }

    }

    And there you have it, a single stack, with all continuations, closed variables, and catch clauses. Perhaps you can call it a "Call stack". The only major feature, and that's the important one, is that the stack is dynamically allocated. This is what makes CPS so beautiful – even though CPS isn't strictly necessary for that.

  9. Gabe says:

    Sure, it was easy to write the Try method, but only because you shifted the burden of exception handling onto every other function. If you already had the B, C, and D methods working without exception handling and decided to add it, you had to change every line in your program to support the new error continuations.

  10. Jacob says:

    It's important that the continuation passing style versions of B, C and D call their normal continuation. It might be helpful to add the call to normal(); after "whatever".

  11. George Spofford says:

    Looking forward to more. On some complex projects (database query processors) I have wished I could reify method call frames (the locals of a method, or at least an attributed subset). I recognize that's a hard problem to solve in the compiler.

  12. Jason says:

    Can't wait for coroutines next! I'm surprised that (the not-so-ideal) keyword variable names haven't been mentioned yet:

    void Foo(Action<int> @return, Action<Exception> @throw, Action @finally)

    {

       if (bar) @throw(new BarException());

       else @return(0);  

       @finally();

    }

  13. configurator says:

    @Gabe: Only if the parameter was action an Action<T> and not, say, a Continuation<T> (a hypothetic type implicitly convertible from lambdas and Action<T>)

  14. configurator says:

    @Jason:

    That finally() is kinda broken; it happens too late. It should happen before return so that would be

    void Foo(Action<int> @return, Action<Exception> @throw, Action @finally)

    {

      @finally();

      if (bar) @throw(new BarException());

      else @return(0);  

    }

    But then it needs to know which was the inner one – the finally or the throw.

    Finally doesn't need to be a separate method though. It can just be attached to the given actions, e.g.

    void Finally<T>(Action<Action<T>> action, Action @finally, Action<T> @return, Action<Exception> @throw) {

     @action(p => { @finally(); @return(p); },

                    ex => { @finally(); @throw(ex); });

    }

  15. jader3rd says:

    I'm not sold on having a catchBody and a outerError. From the little cogs spinning in my head I think it would be cleaner if they were the same thing. An error occured at this point, handle it, or pass it along.

  16. LBushkin says:

    CPS is indeed awesomeness wrapped in rainbows. Async programming especially benefits from CPS – problems like animation, async-IO, and fork/join can be cleanly expressed in CPS. By chance, have you seen the Reactive extensions? They already provide a limited form of CPS for operations on Observable<T>.

  17. Robert Davis says:

    If Throw only ever calls Action error, why is Action normal even passed in?

  18. Data says:

    Jason, let's imagine a situation with a nested analog of tyr-finally – what do you think about the @finally invokation?

    void Foo2(Action<int> @return, Action<Exception> @throw, Action @finally) {

       Foo(i => Console.WriteLine("Foo result: " + i),

           e => { Console.WriteLine("Foo throws exc"); @throw(new BarException()); },

           () => Console.WriteLine("Foo's finally"););

       @finally();

    }

    Foo2(null, e => Console.WriteLine("Foo2 throws exc"), () => Console.WriteLine("Foo2's finally"));

    We'll get

    Foo throws exc  

    Foo2 throws exc

    Foo's finally

    Foo2's finally

    instead of

    Foo throws exc

    Foo's finally

    Foo2 throws exc

    Foo2's finally

    >"you can write programs that run forwards and then run themselves again backwards if you really want to."

    Bingo! There's no impossible in this world!

  19. Aaron says:

    What (if any) implications would an exclusively CPS program have for things like CPU branch-prediction and speculative execution?

  20. tobi says:

    Aaron, the overhead of creating all the delegates and closure instances (every local on the stack now goes to the heap) will be devastating (10x). Thats why f# mixes normal code with async code seamlessly, even in an async block. You can decide to have statements execute immediately or async by appending a "!".

  21. configurator says:

    @tobi: How are these two sentences at all related?

  22. Benjol says:

    Hm, wondering if it's going to be a new keyword, new type, or just a new operator?

    Could it just be as simple as using ! like F#?

  23. Shuggy says:

    I would imagine a (hypothetical) new operator would be tricky.

    There aren't that many left to use (f# had ! because it does negation through not) and even if one is made available through context sensitivity this is often something language designers are loath to do (it can complicate the parser and is a latent source of complications down the road) especially on punctuation since it explicitly encourages terse code.

    It's worth noting that on (my English) keyboard the only punctuation available not already used in c# is '£' and '$' and perhaps the "M$FT" moniker would be too tiresome to be worth it 😉 (1)

    I would postulate that 'yield' would be a candidate for use in such a scenario since it is already in use as a 'magic happens here' word, and thus should be relatively low additional overhead for the parser, syntax highlighter and crucially the user.

    It has the advantage of also being pretty meaningful in the way it would (hypothetically) be used.

    It would make using generators and cps together either more complex/confusing/impractical but I think it likely that such usage would simply be disallowed (as the compiler transforms involved are unlikely to play nice together).

    As to (yet more hypothetical) keywords for immutability I would imagine that readonly would continue to be used if the semantics remained the same. const is available but if its behaviour differed significantly from the C++ usage I think that might cause confusion…

    I would guess that the internal changes to the compiler to allow it's exposure to the rest of the world have lead to it significantly increasing in its capabilities (there's nothing like exposing something to force you to smooth those rough edges that were previously tolerated) so I suspect that many minus points that previously applied to changes no longer apply and that the design team are able to base their decisions on the user impact to a much greater degree so some of the above may not apply.

    (Hypothetically)

    1. I do wonder if $ is being reserved as a "OMG this feature is so awesome we have to have it" once only deal. If the c heritage means it is simply avoided or if it's inherent not always present on international keyboards (I suspect the latter).

  24. configurator says:

    @Shuggy: Const is so different from its C++ usage it's not even related. In fact, I'd say readonly is much closer to C++ const than C# const is.

  25. Shuggy says:

    @configurator

    I was assuming an 'upgrading' of const usage beyond the simple 'compile time known literal' to be used to indicate the immutability of a variable or a type rather than a value and that the resulting (probable) similarity in some areas and disparity in others make that unappealing