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 (20)

  1. ShawnHargreaves says:

    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

  2. configurator says:

    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]

  3. Ben says:

    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 ™ or if I'm at least on track so far..

    1: blogs.msdn.com/…/8854601.aspx

  4. Ben says:

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

    Sorry for the noise.

  5. Daniel Ziegler says:

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

  6. petebu says:

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

  7. Joren says:

    @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;

    }

  8. Joren says:

    @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;

    }

  9. Jonathan Mitchem jmitchem@gmail.com says:

    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;

    }

  10. Jonathan Mitchem jmitchem@gmail.com says:

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

  11. Shuggy says:

    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

  12. petebu says:

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

  13. configurator says:

    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?

  14. Yevhen Bobrov says:

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

  15. Stuart says:

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

    }"

  16. Joren says:

    @configurator: Something like this I'm afraid:

    using System.Threading.Tasks;

    public int FooCaller(int n) {

      var tcs = new TaskCompletionSource<int>();

      MyCPSLibrary.Foo(n, tcs.SetResult);

      return tcs.Task.Result;

    }

    Not exactly pretty, but okay.

  17. ShuggyCoUk says:

    @configurator

    Well yeah, if it does something that is not expressible in the implicit stack model then it can't be safely automatically converted to it. Round peg in square hole and all that.

    The asynchronous case can be dealt with with a wait but requires advance warning that this is needed. Multiple calls could only be converted into an IEnumerable if you knew when it had finished, or an IObservable if you didn't (or did for that matter)

    In fact one could argue that simply going with something like the following you can push the decision down to the caller in a reasonable fashion.

    (ObservableSource lifted from Brian's answer to stackoverflow.com/…/implementing-iobservablet-from-scratch I could have used that as a base and implemented the logic within it but for the purposes of the forum post this will do)

    public sealed class CpsAsReturn<T> :  IObserver<T>, IDisposable

    {

    private IDisposable onDispose;

    private List<T> results = new List<T>();

    private bool assertNoMoreResults;

    public CpsAsReturn(IOBservable<T> source)

    {

    this.onDispose = source.Subscribe(this);

    }

    void IObserver<T>.OnNext(T value)

    {

    Debug.Assert(!assertNoMoreResults, "we asserted that we would not accept more results");

    lock (results)

    {

    this.results.Add(value);

    Monitor.PulseAll(results);

    }

    }

    //will block if necessary

    public T RequireSingleResult()

    {

    lock (results)

    {

    while (true)

    {

    if (results.Count == 1)

    {

    this.assertNoMoreResults = true;

    return results[0];

    }

    if (results.Count > 1)

    throw new InvalidOperationException("there are already multiple results");

    Thread.Sleep();

    }

    }

    }

    //will throw if no value yet available

    public T RequireSingleResultImmediately()

    {

    lock (results)

    {

    if (results.Count == 1)

    {

    this.assertNoMoreResults = true;

    return results[0];

    }

    if (results.Count > 1)

    throw new InvalidOperationException("there are already multiple results");

    throw new InvalidOperationException("No result is available");

    }

    }

    //will block if necessary

    public IEnumerable<T> RequireAllResults()

    {

    lock (results)

    {

    while (true)

    {

    if (results.Count > 0)

    {

    this.assertNoMoreResults = true;

    return results;

    }

    Thread.Sleep();

    }

    }

    }

    //will throw if no values yet available

    public IEnumerable<T> RequireAllResultsImmediately()

    {

    lock (results)

    {

    if (results.Count > 0)

    {

    this.assertNoMoreResults = true;

    return results;

    }

    throw new InvalidOperationException("No result is available");

    }

    }

    //will block if no values

    public T GetLatestResult()

    {

    lock (results)

    {

    while (true)

    {

    if (results.Count > 0)

    return results.Last();

    Thread.Sleep();

    }

    }

    }

    public void Dispose()

    {

    if (this.onDispose != null)

    {

    this.onDispose();

    this.onDispose = null;

    }

      }

    }

    public static CpsAsReturn<TResult> ImplicitReturnStyle<T,TResult>(T input, Action<T,Action<TResult>> cps)

    {

    var source = new ObservableSource<TResult>();

    var result = new CpsAsReturn<TResult>(source);

    cps(input, r => { result.Next(r); } );

    return result;

    }

    Extending it to include the ability to timeout, to look at the first/last resutls are all possible.

    The lock is unfortunate, as it is a potential source of dead locks. It's possible you could write it lock free but it would be much more complex (and may not guarantee that If you ever call RequireSingleXxx  that multiple calls to Next() always trigger the assert.

  18. Rob H says:

    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…

  19. Daniel Ziegler says:

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

  20. Paulo Zemek says:

    Why all those new resources are "compiler tricks"?

    Wouldn't it be easier to create a managed fiber (I originally called them StackSavers) and simple allow any method to "yield return" at any point?

    I consider this much better than having explicity enumerators or explicity await, as inner methods will be able to yield return or await without returning a Task or an Enumerator, and without the caller doing that also.