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.

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

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

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

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

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

Page 2 of 2 (20 items) 12