Continuation Passing Style Revisited Part Three: Musings about coroutines
Last time I sketched briefly how one might implement interesting control flows like try-catch using continuations; as we saw, the actual implementations of Try and Throw are trivial once you have CPS. I'm sure that you could extend that work to implement try-catch-finally. Or, another basic exercise when learning about CPS you might try is to implement coroutines.
What’s a coroutine? Excellent question!
Cast your mind back to the days of cooperative multitasking in Windows 3. The idea of cooperative multitasking is the operating system would allow a process to run, and the process would decide when to pause itself and allow another process to run. If a process got an infinite loop then it could starve all the other processes of processor time indefinitely. Programs had to be carefully designed so that they did not take up a lot of cycles before yielding control back to the OS, which would then choose the next process to run.
Of course, nowadays we have non-cooperative multitasking built into the operating system at both the process and thread level. The operating system, not the process, decides when a particular thread in a particular process needs to pause. This means that programs do not have to be written specially to be nice to other programs; they can just be written the straightforward way without worrying that other processes will starve. However, it means that the operating system has to be able to rapidly grab all the state in the CPU that is relevant to a particular thread, save it for later, and restore it so that the thread picks up where it left off without ever being the wiser. (In fact, the operating system is essentially storing the continuation of the thread!)
Coroutines are a programming language concept very similar to cooperative multitasking at the OS level. A coroutine is a method that runs for a little while, and then decides to be nice, pause itself, and allow some other coroutine to run. When some other coroutine returns the favour, the first one picks up exactly where it left off. One imagines any number of systems that could make use of this technique:
Stack<Pancakes> pancakes = new Stack<Pancakes>();
coroutine MakePancakes(Chef chef)
{
while(true)
{
while (chef.IsAwake)
pancakes.Push(chef.MakePancake());
yield;
}
}
coroutine EatPancakes(Child child)
{
while(true)
{
while (child.IsHungry && pancakes.Count != 0)
child.Eat(pancakes.Pop());
yield;
}
}
This is way better than mutual recursion. Clearly you don't want to be calling "MakePancakes()" and "EatPancakes()" in there because (1) that makes for an infinite recursion, and (2) there might be multiple chefs and multiple children who get turns in different orders. Rather, you want to say "I'm done working on this task for now. Someone else can run, but I need to pick up right here when it is my turn again". Since this is cooperative single-threaded multitasking, no two coroutines ever run at the same time, or ever are suspended halfway through an operation. There's no "thread safety" problems with two routines sharing the same global pancake stack.
The tricky bit is, of course, how to achieve "pick up right here when it is my turn again." In Windows you can use fibers to implement coroutines, because basically that's all a fiber is: a "lightweight" thread that decides when it yields control to another fiber, instead of allowing the OS to decide. But let’s ignore that. Suppose we didn’t have fibers(*) but we did have continuations.
From what you know about continuations thus far it should be clear that coroutines can be implemented quite easily in any programming language that supports CPS. It is particularly easy if you can get a little help from whatever code is orchestrating the invocation of the next continuation, but not strictly necessary. When it is time to yield control, you just tell the orchestrator “I am a coroutine who is yielding now. Here is my current continuation. Please put it at the end of a queue. Go run whatever coroutine’s continuation is on the top of the queue.” If everyone cooperates then each coroutine with pending work runs for a little while and then gives the next guy a turn. (And of course, when the coroutine completes, if it does, then it simply never puts a continuation on the queue and it vanishes.) Since "everything I need to do next" is precisely what a continuation is defined as, we've already solved the problem of figuring out how to pick up where we left off.
As you’ve no doubt just realized, if you didn't know it already, the “yield return” statement in C# is a weak form of coroutine. When you hit a “yield return”, conceptually the enumerator stores away its continuation – that is, enough information to know how to pick up where it left off. It then yields control back to its caller, which decides when to call MoveNext() again and pick up where the iterator block left off. The iterator block and the caller have to cooperate; the iterator block promises to give the next item back in a timely manner, and the caller promises to call either MoveNext() or Dispose() to allow the iterator to either run its next piece of work or clean up after itself.
Of course, as I noted last year, iterator blocks are not really implemented in "pure" Continuation Passing Style the way I've presented it thus far. We do not actually transform the entire method and every function call in it into CPS and build a lambda for “the stuff that comes next”. Because we are limiting ourselves to implementing coroutine-like data flow solely for the purpose of building an implementation of IEnumerator, we don’t have to pull the big hammer that is CPS out of our toolbox. We build a much simpler system, a state machine that keeps track of where it was, plus a closure that keeps track of what all the local variable values were. But in theory we could have written iterator blocks as coroutines, and we could have written coroutines by building them out of continuations. The “yield return” statement gives a fairly complex control flow, but we can build any complex control flow out of continuations.
At this time it might be a good idea to read Raymond’s articles on how iterators are actually implemented in C#, and, optionally, the rest of my articles on some of the consequences of those design decisions. Familiarity with that subject will be necessary presently. (Remember, foreshadowing is a sign of a quality blog.)
Next time: if Continuation Passing Style is so awesome then why don’t we all use this technique every day?
(*) Or that we didn’t want to pay the price of a million bytes of stack space reserved by default for each fiber. Fibers aren't actually as lightweight as one might like.
Comments
Anonymous
October 25, 2010
Speaking of C# iterators as coroutines, this article describes how they can be used to build simple state machines, similar to how many game programmers use coroutines in Lua: blogs.msdn.com/.../iterator-state-machines.aspxAnonymous
October 25, 2010
The comment has been removedAnonymous
October 25, 2010
Eric, on Raymond's series[1] you commented "To return to the subject at hand... We could fix the issue Raymond alludes to by implementing a new syntax which allows you to "yield foreach CountTo100()". The compiler could generate efficient code which does not run into the problem. We could make this work even with complex iterators on recursive data structures." I know I'm late to the party and I might miss something completely obvious here - but isn't that what F# did afterward then? I'm a bit rusty, but I thought that the F# "yield!" solves the same issue, i.e. yielding a sequence (which again might be lazily evaluated) instead of being limited to single value yield returns. Would love to get a heads up if I'm already lost reading the prerequisites for the Big Thing (tm) or if I'm at least on track so far.. 1: blogs.msdn.com/.../8854601.aspxAnonymous
October 25, 2010
Yeah, well.. Good work, Ben. Someone else mentioned yield! 2 years ago. Sorry for the noise.Anonymous
October 25, 2010
@configurator: I'm pretty sure there is no better solution than to use another thread to run the CPS function. Then, the continuation function that is passed in could simply store the result somewhere and wake up the original thread. However, this is ugly and quite inefficient since it uses two threads (and two million-byte stacks), only one of which is actually doing work.Anonymous
October 25, 2010
The comment has been removedAnonymous
October 25, 2010
The comment has been removedAnonymous
October 25, 2010
The comment has been removedAnonymous
October 25, 2010
The comment has been removedAnonymous
October 25, 2010
The comment has been removedAnonymous
October 25, 2010
Or generalised to: public static TResult ImplicitReturnStyle<T,TResult>(T input, Action<T,Action<TResult>> cps) { TResult result = default(TResult); cps(input, r => { result = r; } ); return result; } If you didn't like the allocation of the delegate everytime you could do something less pleasant to read/maintain but possible more efficient with ThreadStaticAnonymous
October 26, 2010
The comment has been removedAnonymous
October 26, 2010
The comment has been removedAnonymous
October 26, 2010
There a number of great Coroutine libraries for .NET. Have a look at Caliburn, Jeffrey Richter's PowerThreading library or Servelat Pieces project.Anonymous
October 26, 2010
The comment has been removedAnonymous
October 26, 2010
The comment has been removedAnonymous
October 26, 2010
The comment has been removedAnonymous
October 28, 2010
On a lighter note, I can't stop thinking about how awesome a global pancake stack would be. Perhaps they could be dispensed via the CD tray...Anonymous
October 29, 2010
@Joren: At first I thought that I was being stupid when I suggested using a thread, but now I realize that the threading solution, while still not able to handle weird cases like returning twice, is somewhat better than just waiting for the CPS method to do a normal return. What if the CPS method returns control immediately, then calls the continuation function 5 seconds later? This is a very realistic scenario and only works if you actually wait for the continuation to be called.Anonymous
March 29, 2012
The comment has been removed