Home > Uncategorized > Unification of async, await and yield return

Unification of async, await and yield return

The new await facility in the C# 5 CTP is mightly reminiscent of the iterator methods (yield return) added in C# 2. So much so that it is irresistable (to someone like me, anyway) to see if I can reinvent one using the other.

For many years now people have already been implementing something a lot like await using yield return, and I’ve blogged about that before. It’s quite possible to write a simple library such that yield return can play much the same role as await, except for some irritating limitations.

But can we go the other way, and write a library that provides the capability of yield return using only the new await feature?

Short answer: yes.

Long answer: (now read on…)

Firstly, async is a misleading keyword. Methods marked with async are not asynchronous. They’re even more synchronous: they can be stopped and restarted (exactly like iterator methods). Secondly, the await keyword doesn’t wait. When you say:

int x = await Foo();
// do something with x

You’re actually saying something equivalent to:

var foo = Foo();
foo.BeginAwait(() =>
{
  int x = foo.EndAwait();
  // do something with x
});

The object foo can be absolutely anything that has compatible BeginAwait and EndAwait methods. So the new language feature is just a handy way of breaking up your code into pieces so it can be paused and continued.

There is no implementation of an interface (such as IEnumerable) that represents the executing method. The only external representation of the current state is an Action delegate that has been passed to BeginAwait. To execute the next piece of the method, you just call that delegate.

Armed with this knowledge, we can pretend yield return doesn’t exist, and see if we can reinvent it.

For an async method to yield values, it will need an object to pass them to; we need a go-between. From the consumer’s perspective, an iteration is represented by an IEnumerator, so we need the object to implement that interface, but also to allow our async method to pass values into it.

So here’s the first glob of code:

public class YieldEnumerator<TItem> : IEnumerator<TItem>
{
  private Action _continuation;

  private TItem _nextValue;
  private bool _hasNextValue;

  private TItem _current;

  public YieldEnumerator<TItem> GetAwaiter()
  {
    return this;
  }

  public bool BeginAwait(Action continuation)
  {
    Debug.Assert(_continuation == null);
    _continuation = continuation;
    return true;
  }

  public void EndAwait()
  {
    _continuation = null;
  }

I’ve made it implement IEnumerator, but before we get on to that, consider the await methods.

GetAwaiter is something I glossed over before - the compiler actually generates code that calls GetAwaiter to get an object of whatever type you wish, and then it calls the BeginAwait and EndAwait methods on that object. This is a bit of flexibility we don't really need, so we just return this and implement those methods on the same object.

In BeginAwait we stuff the continuation in a field for later use. EndAwait is a little more strange: it doesn't seem to do anything useful. But we'll find some cool uses for it later, don't you worry.

Now, how about the IEnumerator implementation:

public YieldEnumerator<TItem> YieldReturn(TItem value)
{
  if (_hasNextValue)
    throw new InvalidOperationException();

  _nextValue = value;
  _hasNextValue = true;
  return this;
}

public TItem Current
{
  get { return _current; }
}

public bool MoveNext()
{
  if (!_hasNextValue)
  {
    if (_continuation != null)
      _continuation();
  }

  if (!_hasNextValue)
    return false;

  _current = _nextValue;
  _hasNextValue = false;
  return true;
}

To reduce noise, I've ommitted the historical mess of Reset and non-generic IEnumerator.Current. As for Dispose, we will get on to that.

The novel thing here is that YieldReturn method. That is the means by which one of our iterator methods will pass a value to this enumerator. It stores the value in a field. Then it's up to MoveNext to "promote" it to being the current item. If there's nothing to promote, it executes the current stored continuation action, which will execute a bit more of the iterator method.

Of course, before we can use foreach on our sequences, it's not enough to implement IEnumerator. We must also implement IEnumerable, which acts like a factory from which instances of IEnumerator can be generated.

public class YieldEnumerable<TItem> : IEnumerable<TItem>
{
  private readonly Action<YieldEnumerator<TItem> _iteratorMethod;

  public YieldEnumerable(Action<YieldEnumerator<TItem> iteratorMethod)
  {
    _iteratorMethod = iteratorMethod;
  }

  public IEnumerator<TItem> GetEnumerator()
  {
    var awaiter = new YieldEnumerator<TItem>();
    _iteratorMethod(awaiter);
    return awaiter;
  }
}

Very simple: to start an iteration, we need an iteratorMethod, and we define that as something accepting a YieldEnumerator. (If the method requires its own additional parameters, we would use an adaptor lambda.)

Believe it or not, we've already got the basics in place. Let's take it for a spin! First, here's an iterator method:

public static async void MyIteratorMethod1(YieldEnumerator<int> e)
{
    Console.WriteLine("A");
    await e.YieldReturn(1);
    Console.WriteLine("B");
    await e.YieldReturn(2);
    Console.WriteLine("C");
    await e.YieldReturn(3);
    Console.WriteLine("D");
}

As noted earlier, we have to pass the enumerator (the go-between) as the first argument, so that it knows where to yield values into. We can now consume the sequence:

foreach (var i in new YieldEnumerable<int>(MyIteratorMethod1))
  Console.WriteLine("Yielded: " + i);

We are rewarded with:

A
Yielded: 1
B
Yielded: 2
C
Yielded: 3
D

But let's not relax just yet. We still haven't implemented Dispose. This is a vitally important part of the IEnumerable contract. Suppose we made a modified version of the iterator method:

public static async void MyIteratorMethod2(YieldEnumerator<int> e)
{
  try
  {
    Console.WriteLine("A");
    await e.YieldReturn(1);
    Console.WriteLine("B");
    await e.YieldReturn(2);
    Console.WriteLine("C");
    await e.YieldReturn(3);
    Console.WriteLine("D");    
  }
  finally
  {
    Console.WriteLine("Running finally");
  }
}

And then we broke out of our foreach loop after the first item:

foreach (var i in new YieldEnumerable<int>(MyIteratorMethod2))
{
  Console.WriteLine("Yielded: " + i);
  break;
}

Even though we don't execute to the end of the iterator method, we still expect the finally block to execute. The signal for that is that behind the scenes, foreach calls Dispose on the IEnumerator. So we need to implement it:

private sealed class AbandonEnumeratorException : Exception { }
private Exception _exception;

public void Dispose()
{
  if (_continuation != null)
  {
    _exception = new AbandonEnumeratorException();

    try
    {
      _continuation();
    }
    catch (AbandonEnumeratorException x)
    {
      Debug.Assert(_exception == null);
    }

    _continuation = null;
  }
}

Cunning or what? We invent a new exception type, totally private to YieldEnumerable so only we can throw it. We store it in a new field, _exception. We then call the current continuation and catch AbandonEnumeratorException. But this means we need that exception to be thrown from inside the continuation. How's that going to happen?

Remember that nearly-empty EndAwait method? It's going to be called at the start of the continuation. So we just need to enhance it:

public void EndAwait()
{
  if (_exception != null)
  {
    var t = _exception;
    _exception = null;
    throw t;
  }

  _continuation = null;  
}

It now checks to see if an exception has been stashed, and throws it (taking care to clear the field to ensure the same exception can't be thrown twice). And now our example with a finally block works.

We've now caught up with C# 2! But why stop there? The standard yield return keyword can push values to a foreach loop... so why can't the body of the loop push values back, and have them "returned" by yield return? That last part is confusing without an example (and may be more confusing with an example):

public static async void MyIteratorMethod3(YieldEnumerator<int, string> e)
{
  Console.WriteLine("A");
  Console.WriteLine(await e.YieldReturn(1));
  Console.WriteLine("B");
  Console.WriteLine(await e.YieldReturn(2));
  Console.WriteLine("C");
  Console.WriteLine(await e.YieldReturn(3));
  Console.WriteLine("D");
}

An extra type parameter has been added to the YieldEnumerator class to indicate the type that we can receive back from the loop. In this example, I'm expecting strings. And so each time I do a YieldReturn, I get back a string and write it to the console.

Now, foreach doesn't provide a way for its loop body to "talk back" to the collection it is iterating through. It's general enough to operate on things other than iterator method sequences. So we need to cook up something more specific:

public static void ForEach<TItem, TResult>(
    Action<YieldEnumerator<TItem, TResult>> iteratorMethod,
    Action<TItem, Action<TResult>> forEach)
{
  IEnumerator<TItem> enumerator = null;

  try
  {
    enumerator = new YieldEnumerable<TItem, TResult>(iteratorMethod).GetEnumerator();
    var enumerator2 = (YieldEnumerator<TItem, TResult>) enumerator;
    while (enumerator.MoveNext())
      forEach(enumerator2.Current, enumerator2.Return);
  }
  finally
  {
    if (enumerator != null)
      enumerator.Dispose();
  }
}

With that we can write a simple demo usage:

int counter = 100;
ForEach(MyIteratorMethod3, (int i, Action<string> loopReturn) =>
{
  Console.WriteLine("Yielded: " + i);
  loopReturn("Counter: " + (counter++));
});

Note how I have to put the types on those lambda parameters: there simply isn't enough information there for the compiler to figure out that i is an int. But no matter. The key point is that we have that loopReturn "keyword" that allows us to publish a value from the loop body, such that it ends up being returned by the YieldReturn inside the iterator method. As you can see from the definition of ForEach, we have a new method called Return in YieldEnumerable.

public void Return(TResult value)
{
    _result = value;
}

It simply stores whatever it is passed. And then we update EndAwait again (it's turning out to be quite useful, isn't it?)

public TResult EndAwait()
{
    if (_exception != null)
    {
        var t = _exception;
        _exception = null;
        throw t;
    }

    _continuation = null;
    return _result;
}

The only change since last time is that it has the return type TResult instead of void, so that it can return the stashed _result. And it now it works:

A
Yielded: 1
Counter: 100
B
Yielded: 2
Counter: 101
C
Yielded: 3
Counter: 102
D

Gimmick or advantageous feature? You decide. The yield keyword in Mozilla's implementation of Javascript can do just this kind of two-way communication.

And that's not all!

There's one more new capability we can take advantage of. As Eric Lippert has explained, a curious fact about C# 2 iterator methods is that if an exception is thrown in the body of the foreach loop, it seems to have the effect of running finally blocks inside the iterator method (which we've already implemented in our reimagined version), and yet the exception cannot be caught inside the iterator method. In fact, you can't even write a try/catch block around a yield return statement.

But no such limitation exists with await. So just to see what it's like (bearing in mind that some things are so disturbing, you wish you could un-see them), supposing we have:

public static async void MyIteratorMethod4(YieldEnumerator<int, string> e)
{
    try
    {
        Console.WriteLine("A");
        Console.WriteLine(await e.YieldReturn(1));
        Console.WriteLine("B");
        Console.WriteLine(await e.YieldReturn(2));
        Console.WriteLine("C");
        Console.WriteLine(await e.YieldReturn(3));
        Console.WriteLine("D");
    }
    catch (IOException x)
    {
        Console.WriteLine(x.Message);
    }
}

In other words, we expect the loop body to take the integer we give it and try to write it to disk. If that fails, we want to handle it in the iterator method. The exception is going to magically travel through a wormhole and pop up where it can be caught. Let's amend our driver code to fail appropriately:

int counter = 100;
ForEach(MyIteratorMethod4, (int i, Action<string> loopReturn) =>
{
    Console.WriteLine("Yielded: " + i);
    loopReturn("Counter: " + (counter++));

    if (counter == 102)
        throw new IOException("Catastrophic disk failure");
});

First we have to make a disgusting, soul-revolting change to ForEach:

public static void ForEach<TItem, TResult>(
    Action<YieldEnumerator<TItem, TResult>> iteratorMethod,
    Action<TItem, Action<TResult>> forEach)
{
  IEnumerator<TItem> enumerator = null;

  try
  {
    enumerator = new YieldEnumerable<TItem, TResult>(iteratorMethod).GetEnumerator();
    var enumerator2 = (YieldEnumerator<TItem, TResult>) enumerator;
    while (enumerator.MoveNext())
    {
      try
      {
        forEach(enumerator2.Current, enumerator2.Return);
      }
      catch (Exception x) // Oh the humanity!
      {
        enumerator2.Throw(x);
      }
    }
  }
  finally
  {
    if (enumerator != null)
      enumerator.Dispose();
  }
}

Look at that... catching the universal Exception base class. If you've read my series of posts on exceptions, you'll know how I feel about this. Dirty and wrong. I want to get into the shower with my clothes on and cry. We'll be catching NullReferenceExceptions, and sometimes a finally block will get executed that throws another exception, thus hiding the original NullReferenceException, which is a horrific thing to be doing. And yet, due to the way the CLR currently works, there's not really a better option if you want to defer exception handling to another context. Exceptions are tied to traditional method-call stacks, which means that, as such stacks are rapidly becoming a late 20th century curiosity, exceptions are due for an upgrade at the runtime level. This is something I will definitely have to bring up when I eventually resume that series of posts.

But let's see this through to the bitter end. Again there's a new method on YieldEnumerator, and it's called Throw, and with crushing inevitability, it stores its argument in a field:

public void Throw(Exception x)
{
    _exception = x;
}

However, rather nicely it's a field we've already added. It's the same one we used to store an AbandonEnumeratorException when we implemented Dispose. The logic to cause it to be thrown in the continuation is already there. Gorgeous!

And the output is:

A
Yielded: 1
Counter: 100
B
Yielded: 2
Catastrophic disk failure

Conclusions

If we'd stopped halfway through this post, we would genuinely have the equivalent of C# 2's iterators, but without this limitation. In the CTP at least, that limitation still exists with standard yield return.

Also in the CTP we cannot say:

foreach (int z in () => { yield return 1;
                          yield return 2; })
{
}

That is, a lambda cannot be an iterator. But with this library-based approach, we can say:

foreach (var i in new YieldEnumerable<int, Void>
                (async e => { await e.YieldReturn(1);
                              await e.YieldReturn(2); }))
{
}

So a lambda can already be an iterator; yes, the wrapping class adds some ugliness, but technically it's possible.

Having gone through this, I'm struck by the enormous overlap between iterator and async methods. I'm not obsessed with orthogonality in languages, but this does seem like two slightly different versions of the same thing. Every widely-used language bears the scars of its evolution; only obscure academic languages remain "tidy", because they're only used to write short examples, not real products. But I wonder if it might be possible, in the time before C# 5 is released, for the language designers to find a way to unify them more, so that C# doesn't have to go forward with two nearly-the-same and rather complex code-transforming features.

It doesn't seem likely though. The new async method transformation is more powerful and has a simpler core, but yield return is already out in the wild and so has to be supported in its current form. Even so, the good news to anyone implementing their own C# 5 compiler is that they only need to implement async, and then they can bolt on yield return with some much simpler syntactic sugar.

Advertisements
  1. configurator
    December 14, 2010 at 7:13 pm

    Just so you’re clear as to how similar they are, in VB, iterator blocks are new to the version parallel to C# 5, and there they use the same code as async methods. Lucian also told me they’re considering unifying the code for async and iterator blocks in C# because of the similarities, and that has a few pros and cons: it would avoid nearly-duplicate code in the compiler, and it would enable anonymous iterator blocks and iterator blocks/async methods nesting ad infinitum, but there are a few small breaking changes that are probably almost never used (I can’t remember what those are unfortunately).

    But the language features are completely different usage-wise and they shouldn’t be united. Just because they’re similar behind the scenes doesn’t mean that they should use the same keyword; that would cause confusion rather then help make the language clearer.

    • earwicker
      December 16, 2010 at 10:33 am

      I’d like it if they could describe yield return in the C# 5 language spec by means of an expansion into async/await (just as using statement is defined in terms of try/finally, and Linq syntax transforms into method calls).

      I’m hopeful that one day C# will gain a general macro mechanism (in the Scheme sense, not the nasty C/C++ sense) and high-level features will be genuinely implemented in terms of lower-level ones in an open way that we can also use to extend the language, with “compiler addon” components. If this was taken far enough, the core of C# might shrink down to something very simple, augmented by several useful examples of high-level extensions.

      • configurator
        December 16, 2010 at 7:40 pm

        While I like the idea of C# macros, I doubt that would ever happen. They don’t like implementing things that can be too easily abused.

        However, an easy way to create such a macro system would be quite simple: allow delegate parameters to be passed as parameters. For example (I chose the keyword ‘codeblock’ but I’m sure you can come up with something better):

        public static void MyForEach(this IEnumerable items, codeblock Action action);

        would be called as such:

        string[] items = new[] { “a”, “b”, “c” };
        MyForEach(items, string str) {
        Console.WriteLine(str);
        }

        or as such:
        items.MyForEach(string str) {
        Console.WriteLine(str);
        }

        For a more complicated example

        public static void Try(codeblock Action action, params codeblock Action Catch[] where E: Exception, codeblock Action Finally);

        FileStream fs = null;
        Try {
        fs = OpenFile;
        DoSomething();
        } Catch (IOException ex) {
        Console.WriteLine(“I couldn’t write the file”);
        } Catch (Exception ex) {
        Console.WriteLine(“Unexcepted exception: ” + ex.ToString());
        } Finally {
        if (fs != null) {
        fs.Close();
        }
        }

  2. Dax
    December 22, 2010 at 12:15 am

    Seems like we’re just due for a new language. Something<-C# (unless you hate MS)<-Java<-C++<-C. C# is wonderful, but lots of inherited problems going all the way back to MulticastDelegate. F# is almost it, man I hate that OCaml syntax. Clojure too parenthetical, and who wants to debug Java exceptions in a Lisp program? And I think type-safety is still a level 1 reqt so no on Python and Ruby. Haskell too confusing. I haven't been following much, but maybe Go can get somewhere. Though the wikipedia article seems to imply it is falling in relevance.

    Hmm, I think there needs to be more of an FVM. JVM and CLR are optimized to OOP but permit FP on them. I think the inverse is going to be the way of the future. A functional VM, a functional rewrite of the System.Core libraries, and all will be right with the world.

    • configurator
      December 22, 2010 at 12:40 am

      If you look at the CLR design you won’t see a lot of by-design OO bias. Perhaps the implementation is optimized for OOP, but the interface (i.e. CIL) is simple and powerful – it is a powerful stack based VM, and that’s really all there is to it.

      Of course, it has ways to call methods on objects (be them instance or static methods), but the difference between a call to an instance method on type T and a call to a static method with first parameter of type T is non-existent. And that’s the same way you invoke functions (delegates) – callvirt its Invoke method and you’re done.

      If your problem is that all code must be contained in a class, then think of a (insert-functional-language-name) module or file as a static class and you’ve got that solved.

      If your problem is that all code must be contained in a method, then remember you’ve got a static initializer – any external code can go there.

      It’s really the compiler’s job to compile a functional language into units that the CLR can understand, and I don’t think the fact that you’re forced to separate your code into modules means that you’re OO-biased.

      • Hendry Luk
        February 9, 2012 at 1:59 am

        The fact that it is stack based, doesnt that mean an OO-bias? It’s a huge show-stopper to be a platform for functional language. They implement a workaround in place for F# (tailcall optimization), but it’s just a workaround for a problem inheritted from its OO root.

      • earwicker
        February 9, 2012 at 11:38 am

        Stacks aren’t specific to OO languages. There are many non-OO languages with inherent function invocation stacks (C, Pascal), and there are “stackless” variants of some OO languages (e.g. Python).

        In IL the stack is not a language design concern – it’s a JIT implementation concern. All widely used CPUs, such as x86 and ARM, have specific registers for tracking the stack, and a defined stack frame layout. Operating system APIs are exposed via functions that must be called (sometimes re-entrantly) via the stack.

        So to make it possible to implement an “efficient” language that can work with operating systems, it makes sense to include the same kind of concept in IL. This doesn’t rule out the possibility of layering something more high-level on top if this, and one day it may be that most languages take that approach.

        The same goes for the flat memory space addressable by pointers, which is how memory is exposed to processes. Hence IL includes that concept, even though most of the time high-level languages will avoid exposing it directly to their users (e.g. in C# you must use unsafe).

      • Hendry Luk
        February 9, 2012 at 11:36 pm

        Yes, stacks are not specific to OO languages, but they are inappropriate (or inefficient) for functional language where infinite recursions are common

      • Hendry Luk
        February 9, 2012 at 11:42 pm

        Was just trying to say that C, pascal, and python are not relevant examples since they are never designed to be functional languages

  3. January 26, 2012 at 12:47 am

    Does this work nicely with the call stack as well? Are there any tail call issues? I haven’t thought about it enough, but it seems that may be a reason doing try/catch in iterator blocks is “difficult”.

    • earwicker
      January 29, 2012 at 9:19 pm

      It works fine with the call stack – today I put up an update with complete source code (with lots of comments), compatible with the VS 11 preview, so try stepping through it to see how it works (as always with elaborate compiler-generated code, Resharper helps a lot too). Try/catch in iterator blocks is perfectly doable technically.

  1. January 29, 2012 at 1:21 pm
  2. June 9, 2014 at 2:06 am
  3. February 1, 2015 at 11:43 pm

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: