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
Anonymous
October 21, 2010
Is it a sign of possible support of resumable methods in future versions of C#?Anonymous
October 21, 2010
That is insanely cool, Eric. I learn something new every day from you! :)Anonymous
October 21, 2010
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. - EricAnonymous
October 22, 2010
This is making my brain salivate!Anonymous
October 22, 2010
Excellent series so far, as usual - thanks! =)Anonymous
October 22, 2010
The comment has been removedAnonymous
October 22, 2010
The comment has been removedAnonymous
October 22, 2010
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.Anonymous
October 22, 2010
The comment has been removedAnonymous
October 22, 2010
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".Anonymous
October 22, 2010
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.Anonymous
October 22, 2010
The comment has been removedAnonymous
October 22, 2010
@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>)Anonymous
October 22, 2010
The comment has been removedAnonymous
October 22, 2010
The comment has been removedAnonymous
October 22, 2010
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>.Anonymous
October 22, 2010
If Throw only ever calls Action error, why is Action normal even passed in?Anonymous
October 22, 2010
The comment has been removedAnonymous
October 22, 2010
The comment has been removedAnonymous
October 22, 2010
The comment has been removedAnonymous
October 23, 2010
@tobi: How are these two sentences at all related?Anonymous
October 24, 2010
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#?Anonymous
October 24, 2010
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)
- 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).
Anonymous
October 24, 2010
@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.Anonymous
October 24, 2010
@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