« October 2010 | Main | October 2011 »

1 posts from November 2010

November 02, 2010

Building Iterators Using Asynchronous Methods

The asynchronous methods feature was recently announced for the next version of C# and made available as a CTP release. The feature was very much anticipated as Luca Bolognese previously mentioned it in PDC 2009 and a similar feature, asynchronous workflows, already exists in F#.

Asynchronous methods is based on the same state machine mechanism as used in iterators.  There were also independent efforts by Jeffrey Richter and Tomáš Petříček to simplify asynchronous programming using iterators last year.

I spoke to a C# PM earlier this year in a Dev Lab, cautioning him to not merely transplant the iterator machinery over to asynchronous programming, but to generalize the approach enough to accommodate unforeseen, nontraditional use cases. In particular, I had in mind backtracking scenarios that are quite useful for AI.

I am here to demonstrate the ability to construct iterator methods, not through existing syntax, but through a new approach based on asynchronous methods. The following snippet of code constructs a method that returns an enumerable using this approach.

    public static IEnumerable Range(int start, int end)
    {
        return new Iterator(async (yielder) =>
        {
            for (int i = start; i <= end; i++)
                await yielder.Yield(i);
        });
    }

The Iterator class accepts an asynchronous method. The yielder is a parameter of type Yielder, that has basically one useful method, Yield(object obj), whose intended use is to replace “yield return.”

Aside from demonstrating the potential of asynchronous methods, this new approach also has some advantages over existing iterators:

1) The ability to yield elements from asynchronous functions, called from the top-level down simply by passing the yielder parameter with each call (or capturing via anonymous methods). The called functions, though, must return a Task rather than a “void,” because void functions are “fire-and-forget” and not tied to call chain via the Awaiter pattern.

2) Much more efficient “bottom-up” enumeration with nested iterators. Each time an element is enumerated, a call made directly to function frame deepest in the “stack,” skipping all parent frames. This is possible because because the frames are stored in heap.

3) This approach can be generalized to produce asynchronous collections (IAsyncEnumerable) which is not expected to be possible with the traditional iterator syntax.

Below is the source for the full implementation of the reusable classes Iterator and Yielder:

class Asynchrony
{
    public class Iterator : IEnumerable
    {
        Action<Yielder> _asyncIterator;

        public Iterator(Action<Yielder> action)
        {
            _asyncIterator = action;
        }

        public IEnumerator GetEnumerator()
        {
            var y = new Yielder();
            y.BeginAwait(() => _asyncIterator(y));
            return y;
        }

        public class Yielder : IEnumerator
        {
            #region Variables
            private Action _action;
            private object _current;
            #endregion

            #region Methods
            public Yielder Yield(object obj)
            {
                _current = obj;
                return this;
            }
            #endregion


            #region Awaiter Interface
            public Yielder GetAwaiter()
            {
                return this;
            }

            public bool BeginAwait(Action action)
            {
                _action = action;
                return true;
            }

            public void EndAwait()
            {
            }
            #endregion

            #region IEnumerable Interface
            void IEnumerator.Reset()
            {
                throw new NotSupportedException();
            }

            object IEnumerator.Current
            {
                get { return _current; }
            }

            bool IEnumerator.MoveNext()
            {
                var action = _action;
                _action = null;
                if (action != null)
                    action();
                return _action != null; // !_task.IsCompleted
            }
            #endregion
        }
    }

    static void Main(string[] args)
    {
        foreach (var i in Range(1, 10))
            Console.WriteLine(i);
        Console.ReadLine();
    }  
}