Implementing iterator blocks in C++ (part 1)

Recently I had to port some C# code to C++. The C# code was making a limited use of the .NET framework, so, most of the porting turned out to be fairly simple. (I only had to pay attention to the difference between value and reference types and to fix small issues with uninitialized data members, where the code relied on the default initialization in C#).

But part of the code was also using some of the features of C# 3.0: implicit types, lambda expressions, iterator blocks and LINQ. Some of this code is not difficult to port to C++, if we target the new C++11 standard. For example C# ‘var’ maps to C++ ‘auto’; C# lambda expressions can be translated into C++ lambdas.

But there is nothing in C++ that matches the elegance of IEnumerable<T> sequences and LINQ, so for the problem at hand I just ended up rewriting the LINQ-based code using STL containers and algorithms. That worked fine, but let me wonder: is there a way to implement C# iterators in C++, and, consequently, to have something similar to LINQ-to-objects in unmanaged code?

The answer is… kind of. In this short series of posts I’ll try to present a possible solution, based on co-routines implemented with Win32 Fibers.

Caveats

A few caveats: this is really just an experiment, a proof of concept, a toy project. The best way to deal with algorithms and containers in C++ is certainly to use the STL. I found that using Fibers has many drawbacks in Windows and makes it very difficult to write correct code. Also, the absence of a garbage collector makes things much trickier, as we will see.

But still, I think that emulating the behavior of C# iterator in C++ is a very interesting exercise, and a great way to learn how LINQ actually works. In many ways it also made me appreciate even more the simplicity and elegance of C#. It’s not the destination, but the journey.

C# iterator blocks

Iterators are objects that allow you to traverse a sequence of elements. Iterators in .NET are the basis of the foreach statement and of the LINQ-to-Objects framework. A very good introduction to iterators, iterator blocks and data pipelines can be found here, or in John Skeet’s “C# In Depth”.

To summarize, the iterator pattern in .NET is encapsulated in the IEnumerable/IEnumerator interfaces, which are defined as follows:

public interface IEnumerable : IEnumerable {
     IEnumerator GetEnumerator();
}

public interface IEnumerator : IEnumerator, IDisposable {
     void Reset();
     bool MoveNext();
     T Current { get; }

     void Dispose();
}

An object that wants to enumerate a sequence of data will implement the IEnumerable interface. Data consumers ask the IEnumerable for an IEnumerator calling GetEnumerator(), and then iterate over the sequence calling MoveNext and getting the Current property. MoveNext returns false when there is no more data to return.

A foreach statement is transformed by the C# compiler in code like this:

IEnumerator it = source.GetEnumerator();

while (it.MoveNext()) {
     int value = it.Current;
     // use ‘value’
}

Note that the Reset() method is never called.

C#2.0 added support for iterator blocks, with the yield keyword. An iterator block is a function that contains the yield keyword and returns an IEnumerable interface. For example, this function returns the sequence of the first 10 Fibonacci numbers:

class Test
{
     public static IEnumerable Fibonacci()
     {
         long a = 0;
         long b = 1;
         yield return a;
         yield return b;
         for (int i = 2; i < 10; i++)
         {
             long tmp = a + b;
             a = b;
             b = tmp;
             yield return b;
         }
     }
}

Coroutines

It is interesting to understand how the function returns the sequence of numbers. A function like this is completely different from normal methods of a class. When normal methods are invoked, execution begins at the beginning and once the method exits, it is finished; an instance of a method only returns once. In the case of iterators, instead, the execution is paused each time a value is yielded. Therefore, C# iterators behave like coroutines.

More precisely, coroutines can be defined as generalized subroutines with the following three properties:

· Local data to a coroutine persists between successive calls.

· Execution is suspended at the point where control leaves a coroutine (perhaps to allow another coroutine to produce something for it). When control reenters the coroutine, execution is resumed at the point where it previously left off.

· Control can be passed from one coroutine to another, causing the current coroutine to suspend its execution and transfer control to the new coroutine.

C# iterators can be considered like a basic form of coroutines. In this article Joe Duffy explains how they can be used to implement a kind of co-routine scheduler, which can be used to schedule lightweight tasks for simulated concurrent execution.

State machine

However, C# iterators are not really coroutines. They are implemented by the C# compiler by generating the code of a state machine. More precisely, for a function like the one above, the compiler generates a class that represents the closure for the block of code in the function, and that exposes both the IEnumerable and the IEnumerator interfaces. The effect of this compiler magic is that an instance of this iterator function will suspend (or “yield” itself and can be resumed at well-defined points.

The core of the implementation is in the MoveNext method: this is where the state machine is carefully crafted to produce the sequence of values according to the sequence of yield statements. When a yield statement is met the method MoveNext exits returning the corresponding value and the state machine keeps track of the exact state of the iterator in that point. When MoveNext is called again, afterwards, the state machine restarts the execution from the instruction that follows the last issued yield.

This implementation has one drawback: it is possible to yield only from one stack frame deep. The C# compiler state-machine can only generate the code required to transform one function, but obviously cannot do that for the entire stack. Real coroutines can yield from an arbitrarily nested call stack, and have that entire stack restored when they are resumed.

For example, C# iterators cannot be used to easily implement in-order traversal of a binary tree. The following code implements a recursive iterator. It works, but with poor performance: if the tree has N nodes, it builds O(N) temporary iterator objects, which is not ideal.

class TreeNode<T>
{
    public TreeNode<T> left;
    public TreeNode<T> right;
    public T value;

    public static IEnumerable<T> InOrder(TreeNode<T> t)
    {
        if (t != null)
        {
            foreach (var i in InOrder(t.left)) { yield return i; }
            yield return t.value;
            foreach (var i in InOrder(t.right)) { yield return i; }
        }
    }
}

// build tree
TreeNode<int> root = new TreeNode<int> { … };

// in-order traversal
var query = TreeNode<int>.InOrder(root);
foreach (int i in query) {
     Console.WriteLine("{0}", i); // only the root node will be printed!
}

We’ll see how this limitation can be overcome with an implementation of coroutines based on Fibers.

I will not delve into more implementation details, since a very detailed explanation can be found here and here. Also, it can be very interesting to look at the generated code using the Reflector  tool.

Next…

In the next posts we’ll see a possible way to reproduce in C++ the behavior of C# iterators (deferred execution, lazy evaluation, “yield” semantic and so on) using Win32 Fibers. And we’ll use iterators as the base for reimplementing LINQ-style queries in C++.

Of course, I can’t think of a way to reproduce the declarative query syntax in C++, with keywords like from, where, select. But we should be able to write code like the following, with expressions defined as the pipe of query operators:

auto source = IEnumerable::Range(0, 10);

auto it = source->Where([](int val) { return ((val % 2) == 0); })
                ->Select([](int val) -> double { return (val * val); }));

foreach(it, [](double& val){
     printf("%.2f\n", val);
});