Continuation Passing Style Revisited Part Three: Musings about coroutines

Continuation Passing Style Revisited Part Three: Musings about coroutines

Rate This
  • Comments 20

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.

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

  • Calling normal functions from CPS functions is easy; if we had a CPS .net language, calling into other languages would be trivial. But how would you call CPS-style* code from normal code? That is, if I had a method that never returns defined in CPS#:

    public void Foo(int x, Action<int> continuation); // foo is a tricky operator that I don't know how to implement in C#. Luckily, I've got a CPS# foo library which does exactly what I need.

    How would you call it from within C#?

    public void FooCaller(int x) {

       Action<int> continuation = x => { return x from FooCaller; }; // not valid C# in case you didn't notice

       MyCPSLibrary.Foo(x, ???);

    }

    This relates to my question from the other day about how to implement call/cc, since FooCaller is really

    public int FooCaller(int x) {

       return CallWithCurrentContinuation(MyCPSLibrary.Foo, x);

    }

    [ (*) 3 points if you noticed the RAS syndrome there]

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

  • Yeah, well.. Good work, Ben. Someone else mentioned yield! 2 years ago.

    Sorry for the noise.

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

  • @configurator. What calling convention would your hypothetical CPS# language use? From your code snippet it seems to be using standard CLR function calls (is anything else even possible in the CLR?) in which case calls into CPS# are perfectly capable of returning. If its not using the standard function call convention then you shouldn't expect it to be interoperable with C#.

    You then have one of two options for getting the result out:

    a) Using state - write the Action<int> typed continuation so that it stores the result somewhere and then returns. FooCaller can then retrieve the result.

    b) In a more functional style - change your CPS# library so that the type of continuations is Func<int, T>. MyCPSLibrary.Foo would then have to be parameterized by T. You can then instantiate calls into CPS# by your desired answer type, in this case int, and pass in the identity function from the direct-style code.

  • @Daniel: Why would you start a thread only to immediately wait for it? That is equivalent to running the thread code synchronously. If you follow this reasoning to the end, you'll end up with what Petebu called option (a). For example, you could do something like this:

    public int FooCaller(int n) {

       int result;

       MyCPSLibrary.Foo(n, x => { result = x; });

       return result;

    }

  • @Daniel: Why would you start a thread only to immediately wait for it? That is equivalent to running the thread code synchronously. If you follow this reasoning to the end, you'll end up with what Petebu called option (a). For example, you could do something like this:

    public int FooCaller(int n) {

       int result;

       MyCPSLibrary.Foo(n, x => { result = x; });

       return result;

    }

  • You'd do something like this:

    public void FooCaller(int x)

    {

      int result = 0;

      Action<int> continuation = i => { result = i; };

      MyCPSLibrary.Foo(x, continuation);

      return result;

    }

    Or just

    public void FooCaller( int x )

    {

      int result = 0; // must initialize it

      MyCPSLibrary.Foo( x, i => { result = i; } );

      return result;

    }

  • @petebu

    Could you explain

    "b) In a more functional style - change your CPS# library so that the type of continuations is Func<int, T>. MyCPSLibrary.Foo would then have to be parameterized by T. You can then instantiate calls into CPS# by your desired answer type, in this case int, and pass in the identity function from the direct-style code."

    A code sample of usage, for instance?

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

  • @Jonathan Mitchem. Sure. The CPS# library would have to be written so that method signatures look like this:

    public T Foo(int x, Func<int,T> continuation);

    Using the library from direct-style by passing in the identity function:

    public void FooCaller(int x)

    {

     Func<int,int> continuation = i => { return i; };

     return MyCPSLibrary.Foo(x, continuation);

    }

    Notice that the signature using Action<int> is an instance of the above signature. (Well, if you consider Action<int> to stand for Func<int,void>.)

  • To all who replied about saving the return value with an i => result = i continuation, this will work for simple cases only. What if the Foo library is asynchronous and calls the continuation later? What if it calls it twice? What if it does any other sort of weird control flow?

  • There a number of great Coroutine libraries for .NET. Have a look at Caliburn, Jeffrey Richter's PowerThreading library or Servelat Pieces project.

  • @configurator: For years I've always thought of Call/CC as some deep magical thing that I'd never be able to wrap my head around unless I somehow got the opportunity to use CPS in real code. Thank you for, in three lines of code, explaining it in a way I understood...

    "public int FooCaller(int x) {

      return CallWithCurrentContinuation(MyCPSLibrary.Foo, x);

    }"

Page 1 of 2 (20 items) 12