yield, IEnumerator and the iterator pattern in C#

I have been programming in C# for around ten years now. Before that, I worked in C++. My education was games-focused and at the time, C++ was pretty much the only serious option for programming games.

Some poor souls still insisted that C was still the better choice. I thought they were insane at the time; C wasn’t object-oriented! Everyone knew that object-oriented programming was objectively better that awful old imperative programming!

The argument between C and C++ is less clear cut to me these days. I’ve become much more sympathetic to those old C programmers’ views that seemed incomprehensible or old-fashioned to me at the time, and I think it’s safe to say that my relationship with object-oriented programming has become strained.

All that said, C is an awful language for productivity (I await the hate mail) and I think to use it competently requires a level of mastery of the language that requires serious discipline to attain. Can you consistently write your C in a way that is easy to read, type-safe, memory-safe and reusable? I can’t, and I’m not sure I want to invest the time to be able to.

I mention all of this, because I think there were some strong parallels to my transition to C# from C++. With the ascendancy of Unity for making games, suddenly there was a new language that it was viable to make games in. Even if we all knew that C# was terrible for making games; It was so slow! That terrible, unpredictable garbage collector caused unacceptable hangs! C# was a little TOO object-oriented!

It was neat that Unity was trying to break C++’s hold on the industry, but I knew it was only a matter of time before people realized how bad C# was for making games and we’d all switch back to C++.

Well, I suppose it COULD still happen.

Perhaps because of my belief that C# wasn’t here to stay, I resisted learning and using some of the more esoteric features. They seemed frivolous, confusing, and most damning of all, slow. Chief among these was yield and the library that it enables, LINQ.

Looking back however, it was learning these things and related concepts in other languages that set me on a path that somewhat profoundly changed my relationship with problem solving in programming. Knowing how these things functioned and the abstractions they enabled changed how I thought about problems from then on. These changes in my thinking  enabled me to write some of the code in my career that I am most proud of, so I’d like to take the opportunity to try to demystify these concepts a bit, and maybe they’ll help you consider your day to day problems from new angles.

IEnumerator and the iterator pattern

This is the IEnumerator interface:

public interface IEnumerator
{
    bool MoveNext();

    Object Current {
        get;
    }

    void Reset();
}

Do you recognize those methods? It’s entirely possible you’ve never called them, even if you have been programming in C# for years. But you use this interface all the time. If you’ve ever used a foreach loop or called any LINQ methods, you’ve used the IEnumerator interface. Few ever call the methods of that interface directly, and fewer still ever implement the interface, but it is foundational to how C# operates on data structures generally.

IEnumerator is an implementation of the Iterator pattern. This is a pattern that shows up over and over again in programming languages. I’d be willing to bet that if your favorite language has a standard library, somewhere in there exists some version of the iterator pattern.

The power of the iterator pattern is that it allows us to abstract the operation of enumerating(iterating) a collection. Without it, we would have to write completely different code to iterate arrays and lists than we would for dictionaries and linked lists and trees. So long as you can express the iteration through your set in terms of an IEnumerator, anyone can iterate through your collection without needing to know the details of how that iteration occurs.

An example of how we might write an implementation for an array of integers:

struct IntArrayEnumerator : IEnumerator<int>
{
    private readonly int[] array;
    private int currentIndex;

    public IntArrayEnumerator(int[] array)
    {
        this.array = array;
        //Start the enumerator BEFORE the beginning of the array
        currentIndex = -1;
    }

    public bool MoveNext()
    { 
        currentIndex += 1;
        
        // If we are at the end of the array, we return false to indicate that there are no more elements.
        return currentIndex != array.Length;
    }

    public void Reset()
    {
        currentIndex = -1;
    }

    public int Current => array[currentIndex];

    object IEnumerator.Current => Current;

    public void Dispose()
    {
        //IEnumerator is also IDisposable, but we don't need to do anything here.
    }
}

This is pretty simple (if a touch verbose). You might think of it as representing the state of a for loop’s header; we track the index, progression and end condition of the iteration. The power here is that it naturally allows us to express more complex iterations, like through dictionaries or trees using the same interface.

yield, IEnumerator and State Machines

So, what does this have to do with yield? Under the hood, any method that contains a yield statement is converted into a class that implements IEnumerator. So suppose I have the following method:

IEnumerator<int> Numbers()
{
    yield return 10;
    yield return 11;
    yield return 12;
    yield return 13;
    yield return 14;
}

The compiler will sneakily convert this into something resembling this:

IEnumerator<int> Numbers()
{
    return new Numbers_Enumerator();
}

class Numbers_Enumerator : IEnumerator<int>
{
    private int currentState = -1;
    
    public bool MoveNext()
    {
        ++currentState;
        switch (currentState)
        {
            case 0:
                Current = 10;
                return true;
            case 1:
                Current = 11;
                return true;
            case 2:
                Current = 12;
                return true;
            case 3:
                Current = 13;
                return true;
            default:
                Current = 14;
                return false;
        }
    }

    public void Reset()
    {
        throw new InvalidOperationException();
    }

    public int Current { get; private set; }

    object? IEnumerator.Current => Current;

    public void Dispose()
    {
    }
}

(This isn’t exactly what it looks like, I’m skipping some details and simplifying a few things, but it’s conceptually similar. If you’d like a more in depth overview of the actual mechanics, might I recommend you read this article by the incomparable Jon Skeet)

A slightly more interesting example:

IEnumerator<int> NumberRange(int min, int max)
{
    for (int i = min; i <= max; ++i)
    {
        yield return i;
    }
}

This function would get converted to something like this (Again, this is how a human might write it, not the compiler):

IEnumerator<int> NumberRange(int min, int max)
{
    return new NumberRange_Enumerator(min, max);
}

class NumberRange_Enumerator : IEnumerator<int>
{
    private int currentState = 0;

    public NumberRange_Enumerator(int min, int max)
    {
        i = min;
        this.max = max;
    }

    private int max;
    private int i;
    
    public bool MoveNext()
    {
        switch (currentState)
        {
            case 0:
                Current = i;
                ++i;
                if (i > max)
                {
                    ++currentState;
                    return false;
                }
                return true;
            default:
                return false;
        }
    }

    public void Reset()
    {
        throw new NotImplementedException();
    }

    public int Current { get; private set; }

    object? IEnumerator.Current => Current;

    public void Dispose()
    {
    }
}

One thing that might stand out to you is the use of the switch statement in the MoveNext function. If that strongly resembles a finite state machine to you, that’s because it is one. In fact, you might even think of methods that contain yield as a compact way of writing state machines. We’ll explore this more in later articles.

Take a moment to consider these classes for a bit. There are some interesting and powerful properties:

1. They abstract the iteration of collections. This was their primary goal, and it’s good that they accomplish this.
2. They can be lazy. This is a subtle, useful (and sometimes dangerous) property. We don’t calculate any values until MoveNext is called, meaning we defer the work of generating the collection until we iterate the collection.
3. They can abstract the collection itself. If I call var range = NumberRange(0, 10000); how much memory is allocated? If I created all the numbers between 0 and 10,000 in an int array it would be somewhere around 40,000 bytes, the NumberRange_Enumerator is probably less than 20 bytes (knowing the size of reference types in C# is hard). This means that we can work with collections that don’t explicitly exist in memory and are generated on demand.
4. We can exploit ‘side effects‘ of the iteration to create more exotic control structures, like Unity’s coroutines.

IEnumerator and LINQ

IEnumerator and yield are the primary enablers of the LINQ library. LINQ is a library for dealing with collections that allows us to express transformations of those collections functionally. Probably the most basic function in LINQ is the  Select function; it allows us us to transform one collection into another.

Say we have a bunch of user objects we want display the usernames for, and we’ve been tasked for writing the method GetUserNames :

class User
{
    public string Username;
}

void ShowNames(IEnumerable<User> users)
{
    var names = GetUserNames(users);

    foreach(string name in names)
    {
         Console.WriteLine($"User: {name}");
    }
}

IEnumerable<string> GetUserNames(IEnumerable<User> users)
{
    //Convert from user to name
}

We could write it in an imperative style:

IEnumerable<string> GetUserNames(IEnumerable<User> users)
{
    List<string> names = new List<string>();
    foreach (User user in users)
    {
        names.Add(user.Username);
    }
    return names;
}

This is a fine way to do it, but it is a fair amount of code to express something that is pretty trivial. Here’s the same basic solution using Linq:

IEnumerable<string> GetUserNames(IEnumerable<User> users)
{
    return users.Select(user=>user.Username);
}

Here we are supplying a function to be run on each element in users and returning a list that contains each of those items.

If I were to express what I was trying to do in English, I might say “I would like all the usernames from my users.”

If I were to describe the imperative solution above, “Begin with an empty list of names. Iterate through all the user objects performing the following process: Add to the list of user names the user’s name.”

If I were to describe the Linq solution: “Given a set of users, select from each their username.”

Comparing those three descriptions, we can see that the imperative description is very concerned with how we are performing the operation, and what we are trying to do takes a bit more effort to work out. The Linq solution is almost entirely concerned with the what, but tells us almost nothing about the how.

Arguably the Linq version is closer to most people’s conceptual map of the problem. We tend to want to think more about the final outcomes of our functions, rather than how they got there, notice how the description of the Linq solution looks a lot more like the plain English description. This isn’t to say we aren’t ever concerned with the how, but I’d argue that the vast majority of the time we’re really much more interested in expressing collection manipulations as a series of whats rather than a complicated bit of how.

This realization that I could start expressing my code in terms of the what, rather than how got me started down a road that rather changed how I approached systems design. The best summation of this sort of thinking I’ve come across can be found here:
Boundaries (I strongly recommend all of Gary’s videos, a subscription is well worth the cost.)

I’ve written a handy cheat sheet for linq operations here.

Learning the Details

If you want to challenge yourself a bit and learn more about how to use yield, it can be a great exercise to write the definitions for a few Linq operations. How would you write:

1. Select?
2. Where?
3. Reverse? (this one is sneaky)
4. SelectMany?

If you do this exercise, send me your solutions at jason.yegge@thephilosophyofcode.com. I’d love to see them!