Coroutines and Iterators

The C# 2.0 specification introduces a number of language extensions including generics, anonymous methods, partial types and iterators. In this entry I want to focus on iterators.

Iterators were first introduced in the CLU Language. An iterator is a type of coroutine that yields the elements of a data object, to be used as the sequence of values in a for loop. Here’s an example of an iterator in C# 2.0:

using System.Collections.Generic;

public class Stack: IEnumerable {
T[] items;
int count;

public void Push(T data) {...}

public T Pop() {...}

public IEnumerator GetEnumerator() {

for (int i = count-1; i >= 0; --i) {
yield return items[i];
}
}
}

The presence of the GetEnumerator method makes Stack an enumerable type, allowing instances of Stack to be used in a foreach statement (e.g. foreach (int i in stack) { … }). The caller and enumerator maintain their own states independent of one another. The iterator returns a value to the foreach loop each time it calls yield. And the iterator’s state can be arbitrarily complex. Imagine that the data that the iterator is traversing is a complex tree structure.

One way to visualize how this works is to imagine that the iterator running on a separate thread from the foreach loop. It could use a mutex to notify the foreach loop that another value is available. But threads aren’t needed to implement iterators. Coroutines are cooperative. Yhe iterator does the following: start, find an item, yield to the foreach loop, restart, find next item, yield to the foreach loop. The iterator just needs a separate stack. This is too low-level to implement directly in C# but it has been implemented for .NET using Win32 fibers.

Iterators are a gee-whiz feature that you can usually code some other way but there are times when it certainly would be useful, especially if there’s an efficient implementation. Personally, I’d love to see iterators in Java.