12/22/2010 When shouldn’t you write ref this?

Last time, we saw that the this parameter to an instance method in a struct is passed by reference, allowing the method to re-assign this or pass it as a ref parameter.

Due to limitations in the CLR, the this parameter to an iterator method is not a reference to the caller’s struct, and is instead a copy of the value.  Quoting the spec (§7.6.7)

• When this is used in a primary-expression within an instance method or instance accessor of a struct, it is classified as a variable. The type of the variable is the instance type (§10.3.1) of the struct within which the usage occurs.
  • If the method or accessor is not an iterator (§10.14), the this variable represents the struct for which the method or accessor was invoked, and behaves exactly the same as a ref parameter of the struct type.
  • If the method or accessor is an iterator, the this variable represents a copy of the struct for which the method or accessor was invoked, and behaves exactly the same as a value parameter of the struct type.

To explain why, you’ll need to understand how iterators are compiled.  As Jon Skeet explains, an iterator method is compiled into a nested class that implements IEnumerable, with the original code transformed into a state machine.  This nested class has fields to store the method’s parameters (which includes this for instance methods) so that the iterator code can use them. 

This is why iterators cannot take ref parameters; the CLR cannot store a reference (as opposed to a reference type) in a field.  Therefore, the this parameter is passed to iterator methods by value, not by reference.
This is also why anonymous methods in structs cannot use this; anonymous methods are also compiled to methods in separate classes and so cannot inherit the ref parameter.

This means that if you change the Mutate method from before into an iterator, the code will still compile (!), but the calling method will not see the changes.

static void Main() {
    Mutable m = new Mutable();
    m.MutateWrong().ToArray();    //Force the iterator to execute
    Console.WriteLine("In Main(): " + m.Value);
}

struct Mutable {
    public int Value;
    
    public IEnumerable<int> MutateWrong() {
        this = new Mutable();
        MutateStruct(ref this); 
        Console.WriteLine("Inside MutateWrong(): " + Value);
        yield break;
    }
}
static void MutateStruct(ref Mutable m) { 
    m.Value++; 
}

This code prints

Inside MutateWrong(): 1
In Main(): 0

In summary, don’t mutate structs in iterators (or at all, if you can help it).
I don’t know why this isn’t a compiler error.

12/16/2010 Nested Iterators, part 2

In part 1, we discussed the simple approach to making a nested iterator.  However, we fell short of a completely lazy nested iterator.

In simple cases, we can make an separate iterator method for the subsequence:

IEnumerable<IEnumerable<int>> FullyLazy() {
    for(int i = 0; i < 10; i++) 
        yield return Inner(i);
}
IEnumerable<int> Inner(int i) {
    for(int j = 0; j < 10; j++)
        yield return i * 10 + j;
}

Note that this is actually smaller than the single-method implementation!

This seems to work very well; the inner iterator code for a particular subsequence will not execute at all unless that subsequence is actually enumerated.

However, this approach falls short in practice.  To see why, consider a real-world example.
Here is a fully lazy implementation of a Partition method, which converts a sequence into a 2D “jagged IEnumerable” where each subsequence (partition) contains n elements.

class Ref<T> { 
    public Ref(T value) { Value = value; } 
    public T Value { get; set; } 
}

public static IEnumerable<IEnumerable<T>> Partition<T>
              (this IEnumerable<T> sequence, int size) {
    using(var enumerator = sequence.GetEnumerator()) {
        var isFinished = new Ref<bool>(false);
        while(!isFinished.Value) {
            yield return PartitionInner(
                 enumerator, size, isFinished
            );
        }
    }
}
static IEnumerable<T> PartitionInner<T>
      (IEnumerator<T> enumerator, int size, Ref<bool> isFinished) {
    while(size --> 0) {
          isFinished.Value = !enumerator.MoveNext();
        if (isFinished.Value) yield break;
        yield return enumerator.Current;
    }
}

This method is complicated by the need to communicate back from the inner iterator to the outer one.  Since iterators cannot have ref parameters, I need to make a “box” class that holds a reference to an int.  This allows the outer iterator to find out when the sequence finishes.

In addition, this implementation has a subtle bug: If the last partition is full, it will return an extra, empty, partition after it.
Fixing this issue would require that the outer method call MoveNext() before each call to the inner method.  This makes the code even more complicated; I won’t list it here (unless people really want me to)

This design has a more fundamental problem: The behavior of the outer method is determined by the inner ones.  It will only work if each inner IEnumerable<T> is enumerated exactly once, before the next MoveNext() call to the outer iterator.  If, for example, you iterate each inner iterator twice, it will behave unexpectedly:

Enumerable.Range(1, 8)
          .Partition(3)
          .Select(p => String.Join(", ", p.Concat(p)));

This code is intended to create strings that contain each partition twice.  It is supposed to return

1, 2, 3, 1, 2, 3
4, 5, 6, 4, 5, 6
7, 8, 7, 8

However, it actually creates the strings

1, 2, 3, 4, 5, 6
7, 8

Enumerating the inner iterator a second time will end up consuming extra items from the original sequence.

Thus, in order to produce enumerables that behave correctly, the inner enumerator needs to cache its items; it is impossible to make a fully lazy Partition method.

It gets worse.  In order to allow callers to write thingy.Partition(5).Skip(2), (which should skip the first two partitions) the outer enumerator needs to cache all items, because it cannot assume that the inner iterators will be called at all. 

Thus, the laziest possible Partition method must use the original approach:

public static IEnumerable<IEnumerable<T>> PartitionCorrect<T>
              (this IEnumerable<T> sequence, int size) {
    List<T> partition = new List<T>();
    foreach(var item in sequence) {
        partition.Add(item);
        if (partition.Count == size) {
            yield return partition;
            partition = new List<T>();
        }
    }
    if (partition.Count > 0)
        yield return partition;
}

It would be possible to write a slightly lazier version that combines these two approaches and passes a List<T> to the inner iterator, which would return whatever is in the list, then enumerate if necessary to fill the list. However, I’m too lazy to do it.  (unless people really want me to)

12/16/2010 Nested Iterators, part 1

C# 2.0 introduced a powerful feature called an iterator, a method which returns an IEnumerable<T> or IEnumerator<T> using the new yield keyword.

Using an iterator, you can quickly and easily create a method which returns lazily a sequence of values.  However, lazily returning a sequence of sequences (IEnumerable<IEnumerable<T>>) is not so simple.

The obvious approach is to yield return a List<T>:

IEnumerable<IEnumerable<int>> SemiLazy() {
    for(int i = 0; i < 10; i++) {
        List<int> numbers = new List<int>();
        for(int j = 0; j < 10; j++)
            numbers.Add(i * 10 + j);
            
        yield return numbers;
    }
}

(This can be shortened to a single LINQ statement, but that’s beyond the point of this post: Enumerable.Range(0, 10).Select(i => Enumerable.Range(10 * i, 10)) )

This approach is very simple, but isn’t very lazy; each subsequence will be computed in its entirety, whether it’s consumed or not.

This approach also has a subtle catch: the iterator must return a different List<T> instance every time.

If you “optimize” it to re-use the instance, you’ll break callers which don’t use the subsequences immediately:

IEnumerable<IEnumerable<int>> Wrong() {
    List<int> numbers = new List<int>();
    for(int i = 0; i < 10; i++) {
        numbers.Clear();
        for(int j = 0; j < 10; j++)
            numbers.Add(i * 10 + j);
            
        yield return numbers;
    }
}

Calling SemiLazy().ToArray()[0].First() will return 0 (the first element in the first subsequence); calling Wrong().ToArray()[0].First() will return 90 (since all subsequences refer to the same instance).

Next: How can we achieve full laziness?