Iterator and Interpreter: Two Patterns Built into C# — yield return and Expression Trees

Version note: The code in this post was built and run with C# 14 and .NET 10.

Guess First

Bookstore's catalog service sits behind an API (Application Programming Interface) that returns books page by page. To keep callers from dealing with pages, someone wrote a small helper: it exposes a single IEnumerable<Book> and fetches the pages internally. The catalog has 8 books, the page size is 3, and the first book priced over 40 is in fourth place.

public static IEnumerable<Book> ReadAll(CatalogApi api)
{
    for (int page = 1; ; page++)
    {
        IReadOnlyList<Book> items = api.GetPage(page);
        foreach (Book book in items)
            yield return book;
        if (items.Count < api.PageSize)
            yield break;
    }
}

CatalogApi api = new(all, pageSize: 3);
IEnumerable<Book> books = CatalogReader.ReadAll(api);
Console.WriteLine("Sequence created");
Book? first = books.FirstOrDefault(b => b.Price > 40m);
Console.WriteLine($"First over 40: {first?.Title}");
Console.WriteLine($"Total: {books.Count()}");
Console.WriteLine($"API calls: {api.Calls}");

Every call to GetPage writes a GET line to the console. How many requests do you see before the "Sequence created" line? When the program ends, how many times has the API been called: 3, 4 or 5?

The Iterator Behind a Sequence

The real output:

Sequence created
  GET /books?page=1&size=3
  GET /books?page=2&size=3
First over 40: Introduction to Algorithms
  GET /books?page=1&size=3
  GET /books?page=2&size=3
  GET /books?page=3&size=3
Total: 8
API calls: 5

Calling ReadAll sent no request at all. FirstOrDefault stopped once it found its book on the second page, so the third page was never requested. Count(), however, walked the sequence from the start and fetched the first two pages again. The calling code never saw the page number, the page size or the "is this the last page" check; it only saw books. That is exactly this post's first pattern: Iterator.

GoF (Gang of Four: the 1994 Design Patterns book by Gamma, Helm, Johnson and Vlissides) lists Iterator among the behavioral patterns. Its intent is to give you a way to access the elements of an aggregate object sequentially without exposing its internal representation. The book has four roles: Aggregate (the interface that produces an iterator), ConcreteAggregate (the actual collection), Iterator (the traversal interface) and ConcreteIterator (the object that holds the traversal state). In the book's C++ example the Iterator has four operations: First, Next, IsDone and CurrentItem.

In .NET these four roles map onto the framework's most basic interfaces. IEnumerable<T> is the Aggregate, and its single method GetEnumerator() is the book's CreateIterator. IEnumerator<T> is the Iterator: MoveNext() does the work of both Next and IsDone, and Current is CurrentItem. foreach is the syntax that calls these interfaces for you. The page-reading code above follows the same idea as File.ReadLines in the BCL (Base Class Library): an iterator that reads a file line by line but only exposes an IEnumerable<string>.

A Hand-Written Iterator and One the Compiler Writes

Building the pattern by hand, the way GoF describes it, looks like this:

// GoF roles: Bookshelf = ConcreteAggregate, BookshelfIterator = ConcreteIterator
public sealed class Bookshelf(Book[] books) : IEnumerable<Book>
{
    public IEnumerator<Book> GetEnumerator() => new BookshelfIterator(books);
    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();

    private sealed class BookshelfIterator(Book[] books) : IEnumerator<Book>
    {
        private int _index = -1;

        public Book Current => books[_index];
        object IEnumerator.Current => Current;

        public bool MoveNext() => ++_index < books.Length;
        public void Reset() => _index = -1;
        public void Dispose() { }
    }
}

public sealed class YieldBookshelf(Book[] books) : IEnumerable<Book>
{
    public IEnumerator<Book> GetEnumerator()
    {
        foreach (Book book in books)
            yield return book;
    }

    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
}

Let's get the enumerators of both classes and look at their types, adding the one from List<T> for comparison:

Bookshelf shelf = new(all.Take(3).ToArray());
IEnumerator<Book> it = shelf.GetEnumerator();
while (it.MoveNext())
    Console.WriteLine(it.Current.Title);
Console.WriteLine(it.GetType().Name);

YieldBookshelf shelf2 = new(all.Take(3).ToArray());
Console.WriteLine(shelf2.GetEnumerator().GetType().Name);
Console.WriteLine(new List<Book>().GetEnumerator().GetType());

Dune
Emma
The Hobbit
BookshelfIterator
<GetEnumerator>d__2
System.Collections.Generic.List`1+Enumerator[Bookstore.Catalog.Book]

<GetEnumerator>d__2 is a class we never wrote. When it sees yield return, the compiler turns the method body into a hidden class that implements IEnumerator<T>; it keeps track of where it stopped in a state field and resumes from there on every MoveNext(). So in C# you almost never write a ConcreteIterator by hand; the compiler does. The List<T> enumerator, on the other hand, is a struct: because foreach is pattern-based syntax that looks for a GetEnumerator() method rather than the interface, the BCL returns allocation-free struct enumerators for its commonly used collections.

GoF discusses two more distinctions. The first is external versus internal iterators: does the client drive the traversal (foreach, MoveNext) or does the collection (List<T>.ForEach(Action<T>))? The book finds external iterators more flexible, because tasks such as walking two collections side by side are only possible with them; LINQ's (Language Integrated Query) Zip works that way. The second is the robust iterator: what happens if the collection changes during traversal?

List<Book> cart = all.Take(4).ToList();
try
{
    foreach (Book b in cart)
        if (b.Price < 15m)
            cart.Remove(b);
}
catch (InvalidOperationException ex)
{
    Console.WriteLine(ex.Message);
}
cart.RemoveAll(b => b.Price < 15m);
Console.WriteLine(string.Join(", ", cart.Select(b => b.Title)));

Collection was modified; enumeration operation may not execute.
Dune, The Hobbit, Introduction to Algorithms

List<T> bumps a version counter on every change, and its enumerator checks that counter on every MoveNext(). .NET does not choose to be "robust" here; it chooses to fail fast and loudly, throwing as soon as it notices the change. Our Bookshelf has no such check; if the array changes, the iterator silently reads the new value. When you write your own iterator, that decision is yours too.

Reading a Paged API with IAsyncEnumerable

A real catalog API answers over the network, so fetching a page is an asynchronous operation. Since C# 8 the async form of an iterator is part of the language too:

public static async IAsyncEnumerable<Book> ReadAllAsync(
    AsyncCatalogApi api, [EnumeratorCancellation] CancellationToken ct = default)
{
    for (int page = 1; ; page++)
    {
        IReadOnlyList<Book> items = await api.GetPageAsync(page, ct);
        foreach (Book book in items)
            yield return book;
        if (items.Count < api.PageSize)
            yield break;
    }
}

AsyncCatalogApi api = new(all, pageSize: 3);
await foreach (Book b in CatalogReader.ReadAllAsync(api).Where(b => b.Category == "IT").Take(2))
    Console.WriteLine($"{b.Title} ({b.Price})");
Console.WriteLine($"API calls: {api.Calls}");

using CancellationTokenSource cts = new();
try
{
    await foreach (Book b in CatalogReader.ReadAllAsync(api).WithCancellation(cts.Token))
    {
        Console.WriteLine(b.Title);
        if (b.Title == "Emma")
            cts.Cancel();
    }
}
catch (OperationCanceledException)
{
    Console.WriteLine("Cancelled");
}

  GET /books?page=1&size=3
  GET /books?page=2&size=3
Introduction to Algorithms (95)
Clean Code (42)
API calls: 2
  GET /books?page=1&size=3
Dune
Emma
The Hobbit
Cancelled

In .NET 10 the LINQ operators for IAsyncEnumerable<T> ship with the framework; we installed no extra package for Where and Take. Once the first two books were found on the second page, the iterator stopped and the third page was never requested. The second loop has a detail worth noticing: we asked for cancellation at "Emma", yet "The Hobbit" was still printed. The token is only checked at await points, that is, at the next GetPageAsync call; the remaining elements of the page already in hand are still returned. If cancellation must be immediate, call ct.ThrowIfCancellationRequested() before yield return. The [EnumeratorCancellation] attribute and what await foreach does behind the scenes are covered in detail in the C# Async series post "C# IAsyncEnumerable, await foreach and Async Dispose".

The Only Reason to Write Your Own Iterator

The common mistake in Bookstore is not writing too few iterators but too many. Wrapping a List<OrderItem> you already have in an OrderItemIterator brings none of the pattern's benefits. The problem with the Order class is usually the opposite: it exposes its internal list as is.

// Bad: the representation leaks, anyone can modify the list
public sealed class Order
{
    public List<OrderItem> Items { get; } = [];
}

// Good: only a read-only view outside, changes go through Order's methods
public sealed class Order
{
    private readonly List<OrderItem> _items = [];
    public IReadOnlyList<OrderItem> Items => _items;

    public void AddItem(OrderItem item) => _items.Add(item);
}

The real justification for the Iterator pattern is that the traversal itself carries knowledge: paging, walking a tree depth-first, reading a file line by line, producing an infinite or expensive sequence only as far as needed. In those cases a few lines written with yield return free the caller from that detail entirely. If the collection is already in memory, the right tool is not writing an iterator but choosing the right interface: IReadOnlyList<T>, IReadOnlyCollection<T> or IEnumerable<T>. The details of that choice are in the Collections series post "C# Collection Interfaces: IEnumerable, ICollection, IList and yield return".

Interpreter: A Small Rule Language

The second pattern is built into C# in a different way. According to GoF, Interpreter's intent is this: given a language, define a representation for its grammar and write an interpreter that uses that representation to interpret sentences in the language. The roles: AbstractExpression (the common Interpret operation), TerminalExpression (the leaves of the grammar), NonterminalExpression (nodes that combine rules) and Context (the information needed during interpretation). In short, an AST (Abstract Syntax Tree) where every node evaluates itself.

Bookstore's marketing team wants to define promotion rules without changing code, for example "total > 100 AND (category = 'IT' OR items >= 3)". The grammar is small and fixed, exactly the kind Interpreter likes. First the AST:

// Context: the order information the rule is evaluated against
public sealed record OrderFacts(decimal Total, string Category, int Items);

// AbstractExpression
public abstract record Rule
{
    public abstract bool Evaluate(OrderFacts order);
}

// TerminalExpression
public sealed record Comparison(string Field, string Operator, object Value) : Rule
{
    public override bool Evaluate(OrderFacts order) => (Field, Value) switch
    {
        ("total", decimal v) => Compare(order.Total.CompareTo(v)),
        ("items", decimal v) => Compare(((decimal)order.Items).CompareTo(v)),
        ("category", string v) => Compare(string.CompareOrdinal(order.Category, v)),
        _ => throw new InvalidOperationException($"Cannot compare {Field} with {Value}"),
    };

    private bool Compare(int c) => Operator switch
    {
        "=" => c == 0,
        "!=" => c != 0,
        ">" => c > 0,
        ">=" => c >= 0,
        "<" => c < 0,
        "<=" => c <= 0,
        _ => throw new InvalidOperationException($"Unknown operator {Operator}"),
    };
}

// NonterminalExpressions
public sealed record And(Rule Left, Rule Right) : Rule
{
    public override bool Evaluate(OrderFacts order) => Left.Evaluate(order) && Right.Evaluate(order);
}

public sealed record Or(Rule Left, Rule Right) : Rule
{
    public override bool Evaluate(OrderFacts order) => Left.Evaluate(order) || Right.Evaluate(order);
}

GoF does not count the parser that turns text into a tree as part of the pattern; Interpreter assumes the tree is already in hand. We still wrote a small recursive descent parser, because that is where most security decisions are made:

// Grammar: rule := and ("OR" and)* ;  and := primary ("AND" primary)* ;
//          primary := "(" rule ")" | field op literal
private Rule ParsePrimary()
{
    if (Peek == "(")
    {
        Next();
        Rule inner = ParseOr();
        if (Next() != ")")
            throw new RuleParseException("Expected ')'");
        return inner;
    }

    string field = Next().ToLowerInvariant();
    if (!Fields.Contains(field))
        throw new RuleParseException($"Unknown field '{field}'");
    string op = Next();
    if (!Operators.Contains(op))
        throw new RuleParseException($"Unknown operator '{op}'");
    string literal = Next();
    object value = literal.StartsWith('\'')
        ? literal.Trim('\'')
        : decimal.TryParse(literal, System.Globalization.CultureInfo.InvariantCulture, out decimal d)
            ? d
            : throw new RuleParseException($"Bad literal '{literal}'");
    return new Comparison(field, op, value);
}

ParseOr and ParseAnd are each a while loop of the same shape; AND binding tighter than OR comes from these two levels of the grammar. Let's parse the rule and apply it to four orders:

Rule rule = RuleParser.Parse("total > 100 AND (category = 'IT' OR items >= 3)");
Console.WriteLine(rule);

OrderFacts[] orders =
[
    new(Total: 150m, Category: "IT", Items: 1),
    new(Total: 120m, Category: "Fiction", Items: 4),
    new(Total: 120m, Category: "Fiction", Items: 2),
    new(Total: 80m, Category: "IT", Items: 5),
];
foreach (OrderFacts o in orders)
    Console.WriteLine($"{o} -> {rule.Evaluate(o)}");

And { Left = Comparison { Field = total, Operator = >, Value = 100 }, Right = Or { Left = Comparison { Field = category, Operator = =, Value = IT }, Right = Comparison { Field = items, Operator = >=, Value = 3 } } }
OrderFacts { Total = 150, Category = IT, Items = 1 } -> True
OrderFacts { Total = 120, Category = Fiction, Items = 4 } -> True
OrderFacts { Total = 120, Category = Fiction, Items = 2 } -> False
OrderFacts { Total = 80, Category = IT, Items = 5 } -> False

The compiler-generated ToString() of records shows the AST as it is: an And at the root, an Or on its right branch. The parentheses vanished from the text but live on in the shape of the tree.

Expression Trees: Compiling Instead of Interpreting

Interpreter's known weakness is speed: the tree is walked from the top on every evaluation, with a virtual call and a switch at every node. If you convert the same AST once into an Expression<Func<OrderFacts, bool>> and compile it, the rule becomes a delegate that runs as fast as a hand-written lambda:

// Instead of interpreting the same AST, we turn it into an expression tree and compile it
private static Expression Build(Rule rule, ParameterExpression o) => rule switch
{
    And a => Expression.AndAlso(Build(a.Left, o), Build(a.Right, o)),
    Or x => Expression.OrElse(Build(x.Left, o), Build(x.Right, o)),
    Comparison c => BuildComparison(c, o),
    _ => throw new NotSupportedException(rule.GetType().Name),
};

Expression<Func<OrderFacts, bool>> lambda = RuleCompiler.ToExpression(rule);
Console.WriteLine(lambda);
Func<OrderFacts, bool> compiled = lambda.Compile();
Console.WriteLine(string.Join(", ", orders.Select(compiled)));

o => ((o.Total > 100) AndAlso ((o.Category == "IT") OrElse (Convert(o.Items, Decimal) >= 3)))
True, True, False, False

The results match the interpreter exactly. There is something interesting here: System.Linq.Expressions is itself an Interpreter. Expression is the abstract base class, ConstantExpression and ParameterExpression are terminals, and BinaryExpression nodes are nonterminals. And the same tree can be interpreted in two ways: Compile() turns it into IL (Intermediate Language), while Entity Framework Core (EF Core) translates the same tree into SQL (Structured Query Language) when it is passed to IQueryable<T>.Where. That is why going from your AST to an expression tree is valuable when you want promotion rules to run as database filters. Expression trees themselves are covered in the C# Advanced series post "Expression Trees in C#: Holding a Lambda as Data, and the Bridge to EF Core".

Regex Is an Interpreter Too

There is another interpreter you use every day. Regex first parses the pattern you give it into a tree, then either interprets that tree or turns it into code. We can see which one it does by reading the internal factory field through reflection (an internal detail, only for curiosity):

FieldInfo factory = typeof(Regex).GetField("factory", BindingFlags.NonPublic | BindingFlags.Instance)!;
Regex interpreted = new(@"^\d{3}-\d{10}$");
Regex compiled = new(@"^\d{3}-\d{10}$", RegexOptions.Compiled);
Regex generated = Patterns.Isbn();
Console.WriteLine(factory.GetValue(interpreted)?.GetType().Name);
Console.WriteLine(factory.GetValue(compiled)?.GetType().Name);
Console.WriteLine(factory.GetValue(generated)?.GetType().Name);

static partial class Patterns
{
    [GeneratedRegex(@"^\d{3}-\d{10}$")]
    public static partial Regex Isbn();
}

RegexInterpreterFactory
CompiledRegexRunnerFactory
RunnerFactory

A default Regex runs with RegexInterpreter, which interprets the tree; that is GoF's Interpreter exactly. RegexOptions.Compiled turns the same tree into IL at runtime, and the [GeneratedRegex] source generator produces readable C# code at build time. The "interpret first, compile if needed" journey we took with our rule language is the same one the .NET team took with Regex.

Common Pitfalls

Writing an Interpreter for a large grammar. GoF itself says the pattern suits simple grammars and that the class hierarchy becomes unmanageable for grammars with many rules. If your rule language is growing function calls, variables and precedence levels, stop writing the parser by hand and move to a parser generator such as ANTLR (ANother Tool for Language Recognition) or a parser combinator library. Better still, ask whether you really need a new language: a JSON (JavaScript Object Notation) rule definition or a form screen is often enough.

Turning user input directly into a dynamic expression. Our parser knows only three field names and six operators; everything not on the list is rejected:

total > 100 AND password = 'x' -> Unknown field 'password'
total >> 100 -> Bad literal '>'
total > 100 OR -> Unexpected end of rule

General-purpose solutions that resolve property and method names from text via reflection open a serious hole if they don't set that boundary. In versions of the System.Linq.Dynamic.Core library before 1.3.0, a vulnerability was found where an untrusted string passed to Where or OrderBy could call methods on object types and execute code; its CVE (Common Vulnerabilities and Exposures) entry is CVE-2023-32571, with a CVSS (Common Vulnerability Scoring System) score of 9.8. The rule: text a user typed must never turn directly into a type or member name; the allowlist must be yours. The general picture of injection is in the OWASP (Open Worldwide Application Security Project) Top 10 series post "OWASP A05: Injection (1) — SQL Injection and Command Injection".

Walking an iterator twice. In the opening example Count() fetched all the pages again. If you will use a lazy sequence more than once, materialize it once with ToList(); know that every traversal has a cost, and that it is the consumer, not the author of the iterator, who forgets it. This is measured in the LINQ series post "LINQ Deferred Execution: When Does a Query Run? IEnumerable and IQueryable".

Putting argument validation inside the iterator. The body of a method containing yield return does not run at all until the first MoveNext(), and neither does its ArgumentNullException. The technique for separating validation from the lazy part is in the LINQ series post "Writing Your Own LINQ Operator: Extension Methods and yield return".

When Not to Use It

For Iterator: if what you have is already an in-memory collection, don't write your own iterator class; return the right read-only interface. Using yield to walk a small list you have already copied is unnecessary too; return _items; is enough. For Interpreter: if there are few rules and they rarely change, writing them as plain C# code or a handful of Func<OrderFacts, bool> delegates is much cheaper than designing a language and carrying the parser, the error messages, versioning and security. Interpreter only pays for itself when non-developers write the rules and those rules change without waiting for a deploy. Before reaching for it, consider the Specification pattern, a lighter way to combine rules; it is in this series' post "Code-Level Patterns Beyond GoF: Null Object, Specification, Result and Pipeline".

A Small Experiment

★☆☆ In the opening example, materialize books with ToList() and see how far the number of API calls drops. Why does the same change cost FirstOrDefault its advantage of stopping early?

★★☆ Write an IEnumerable<Category> Descendants() iterator that walks the category tree (Fiction → Fantasy → Epic Fantasy and so on) depth-first. Notice that the first version, using recursive yield, creates a new iterator object at every level, and write a second version with an explicit Stack<T>.

★★★ Add a NOT operator and the category IN ('IT', 'Fiction') syntax to the rule language. Extend both Evaluate and RuleCompiler for the new nodes, and write a small loop that checks both paths give the same result for every order.

Both patterns in this post hid the inside of a structure from the outside. The next post deals with the opposite: objects that know each other too well. What happens when the coupon, shipping and order total components on the checkout screen call each other directly, how does GoF's Mediator solve it, and is MediatR really this pattern?