The Power of Yield

Generating all the permutations of a set is a little bit dry and academic but it illustrates some of the power that yield gives us.


To start here is the code which will ask for all the permutations and print them out.

///////////

        static void Main(string[] args)
        {
            foreach (List permutation in permutations(9))
            {
                string result = string.Empty;
                foreach (int number in permutation)
                {
                    result += number.ToString();
                }
                Console.WriteLine(result);                         
            }
            Console.ReadLine();
        }

///////////

If you use the refactor tools of Visual Studio it will generate the shell of the following function.
For the body, recursively call the permutations(int) function, then place the current item in all positions of resulting permutations. Of course the recursions have to stop somewhere so on the smallest set, a set of one, just return the list with one item.

///////////

        private static IEnumerable permutations(int size)
        {
            if (size == 1)
            {
                List list = new List();
                list.Add(1);
                yield return list;
            }
            else
            {
                foreach (List permutation in permutations(size - 1))
                {
                    for (int i = 0; i <> list = new List(permutation);                         list.Insert(i, size);                         yield return list;                     }                 }             }         } 

///////////

If you run this code, it generates all permutations as expected.

What is surprising is some of the performance aspects of this code.
Even though there is recursion involved here the recursion is only invoked 'n' times.
At the same time the memory being used is also a constant times 'n' squared.
And an additional kicker the number of cycles of execution is a constant (I think between 3 and 4) times 'n' factorial.
(The last is actually pretty good. If you had a really long program that hardcoded each permutation it would take 'n' factorial lines of code.)

If you study your Knuth you could probably unearth some code that performs better on one or more of these aspects. But the readability of such code is a bit obtuse and slight changes result in disasterous results where the errors are not obvious.

Compare this to how natural it was to write this code. The code reads as a description of how to generate permutations.

The performance comes from the strange nature of yield. It converts the method into a Generator instead of a Subroutine.

permalink

Yield The Danger

In "Return Yield and Return"
http://andrewboland.blogspot.com/2008/05/return-yield-and-return.html
I pointed out the odd implementation and behavior of the yield statement.

Here is an example of unexpected behavior of yield. Consider the code:

class Program
{
public static int globalCount;
static void Main(string[] args)
{
foreach (int number in collection())
{
Console.WriteLine(number.ToString());
SecretFunction();
}
Console.ReadLine();
}
private static IEnumerable collection()
{
globalCount = 1;
yield return globalCount;
globalCount++;
yield return globalCount;
globalCount++;
yield return globalCount;
}
private static void SecretFunction()
{
//
}
}

/////////////////
As written this results in the output:
1
2
3

However if the body of SecretFunction() is replaced with
globalCount = 0;

The resulting output is:
1
1
1

According to the rules this is all correct but this might come as a surprise.
We are used to considering functions in isolation. In fact this is the prime reason for functions. By isolating code we reduce the cognitive load required. But given the way yield is implemented this cognitive load is radically increased. We cannot mentally checkoff the collection function, we have to be aware of this behavior.

It gets worse if we touch this code. Consider if we change the collection function with this allegedly equivalent code:

private static IEnumerable collection()
{
List list = new List();
list.Add(1);
list.Add(2);
list.Add(3);
return list;
}

/////////
Under both implementations of SecretFunction, it results in:
1
2
3

/////////
What are we to think here?
There is no doubt this will result in unexpected bugs being coded as result of this obscure behavior of yield.

permalink

Return Yield and Return?

Debugging some c# code involving the yield statement revealed some interesting behavior.

The implementation of the yield statement is more complex than it appears on the surface.

Consider the following code:

class Program

{

static void Main(string[] args)
{
foreach (string state in collection())
{
Console.WriteLine(state);
}

Console.ReadLine();
}

private static IEnumerable collection()
{
// Console.WriteLine("before Alaska");
yield return "Alaska";
// Console.WriteLine("before Alabama");
yield return "Alabama";
// Console.WriteLine("before Kentucky");
yield return "Kentucky";

}

}

///////////////////

As expected this code results in:
Alaska
Alabama
Kentucky

Now uncomment the additional Console.Writeline statements and the code will result in:
before Alaska
Alaska
before Alabama
Alabama
before Kentucky
Kentucky

Unless you have discovered this already this should be unsettling. If you are not seeing what the big deal is set breakpoints on every line of code (stepping through is not enough). What you will see is the code appearing to hop in and back out of the collection function and then back in at the line after the line it left on. It is not executing the function repeatedly and it is not exiting it completely.

This behavior has few equivalents anywhere else in the c# language. There is power here (probably not widely known) and there is danger here (probably now widely understood).

permalink