Silverlight and Anonymous Types: A Cautionary Tale

As you may or may not know know I've been working hard on Silverlight controls for the last few months. I know this blog is covered in a thin layer of virtual dust but I want to say this to the three of you left who haven't dropped me from your RSS readers in disgust: "I'm back baby." No, really. Get ready for a flurry of posts on Silverlight 2 and our upcoming controls. You can read more about them on my boss's blog. Not everything I've been working on has been announced yet (nothing in fact) so until PDC I will have to keep it general rather than specific. However after Tuesday no amount of pleading e-mails will be able to get me to shut up about Silverlight controls. So stay tuned. To whet your appetite I'll tell you a cautionary tale about a developer who found his love of functional programming and Silverlight in direct conflict.

Once upon a time there was a developer who was hired by Microsoft to write Silverlight controls. This developer understood well the benefits of functional programming and had been dutifully using query comprehensions, anonymous types, and closures whenever possible. His code was terse and declarative. Life was good. One day the tester visited the programmer. "Anonymous types are forcing our code coverage down. The compiler generates a GetHashCode function and a ToString function for them and and our test can't cover them." The developer was initially dismissive of the tester's concerns. He saw limited value in covering compiler generated code. The true coverage numbers were much higher he reasoned. Denial. "Anonymous types also account for about 15% of our DLL size." Moments later our developer regained consciousness, dazed and confused, and began to crawl out from the ton of bricks that had fallen on him. This was another problem entirely. He hadn't given a moments thought to executable size. After all, how much code could really be generated by an itty-bitty little anonymous type? var rootNode = new { Node = node, Resources = node.GetResources() };

Turns out...a lot. A class with constructor, two properties, a structural equality overload, a ToString overload, and a GetHashCode overload. The developer groused and complained that the compiler should be able to detect and omit the unused code. Anger.

The developer bargained, telling himself that he would use anonymous types sparingly, only in cases where omitting them would detract from the clarity of the code. Finally he accepted the fact that he couldn't subject users to longer download times for the sake of his high-minded ideals. He swore to never use anonymous types again...in Silverlight.

The moral of the story is it's important to avoid casually using anonymous types in Silverlight projects. This is more difficult that it seems because sometimes you are using them without even knowing. How many anonymous types do you think are generated by the following code?

var types = from type in this.GetType().Assembly.GetTypes() let name = type.FullName orderby name ascending select new { Name = name, Type = type, SuperClass = type.BaseType };

The answer is two. Let statements generate anonymous types. Under the hood an anonymous type was created for the name and type pair in addition to the triple that is actually returned from the query.

The dilemma: How to be a good developer and write stateless, declarative code while respecting your end-users precious time?

1. DON'T use the query syntax.

Many people find query comprehensions very readable, especially when doing joins. The problem is that it's too easy to inadvertently create anonymous types.

2. DO use tuples.

A tuple is an immutable generic class that is basically identical to an anonymous type but without the named properties. You can use it again and again without bloating your assembly. Here is a triple, which is like a tuple but with three properties instead of two. internal struct Triple<T0,T1,T2> { public T0 First { get; private set; } public T1 Second { get; private set; } public T2 Third { get; private set; } public Triple(T0 first, T1 second, T2 third) : this() { First = first; Second = second; Third = third; } }

We also need one last thing, a nice helper class to create them for us. The reason we need a helper class is that constructors don't support type inference. It's certainly no fun typing...

new Triple<string,Type,Type>(name, type, type.BaseType);

..is it. I have a FunctionalProgramming static class I use (which I usually alias to FP):

public static FunctionalProgramming {
public Triple<T0,T1,T2> Triple(T0 first, T1 second, T2 third)
{
return new Triple<T0,T1,T2>(first, second, third);}
}
}

Once you've built yourself a triple and a helper class you're ready to go. Now we can rewrite the code above:

var types = this .GetType() .Assembly .GetTypes() .Select(type => FP.Triple(type.FullName, type, type.BaseType));

Tuples are used in functional programming to return multiple values and as a way of temporarily grouping related objects. There's no reason why you can't use them in C# in lieu of anonymous types.

And so our story comes to an end. With a little adjustment the developer continued to use Linq in his Silverlight project to create terse, declarative code and lived mostly happily ever after.

Multimethods in C# (Part 2)

In part 1 I demonstrated how to use my multimethod library in C#:

var collision = DynamicDispatch.CreateFunc<SpaceObject,SpaceObject,bool>((obj1, obj2) => this.Collision(obj1,obj2));

// dispatches to Collision(XWing xWing, TieFighter tieFigher)
collision(new XWing(), new TieFighter());

Although it appears that CreateFunc accepts a lambda function, in reality the type of its argument is a lambda expression. A Lambda expressions is the data representation of a lambda function. The CreateFunc functions analyzes the lambda expression and retrieves the overloads of the function invoked in the expression. Finally it generates the code to do a dynamic dispatch based on the argument types and returns a delegate of type Func<>.

Based on the type of the arguments passed to the collision delegate it invokes the correct method overload at run-time. In order to generate the code for this delegate I use the objects defined in the System.Linq.Expressions namespace. The code for the collision method looks something like this:



This may look a little complicated but really it's not. I simply create a function for each overload that attempts to cast the arguments to the concrete types expected. If any of the arguments are null, which they will be if the "as" operator fails, the process is repeated for the next overload until finally it reaches the most abstract overload.

So how is this done? Well first we must get a list of all the overloads and sort them in the appropriate order, from most abstract to most derived.



Some of the functions used here warrant some explanation. Iterate is a function that accepts a starting argument and a function and then generates a stream that takes an initial value, returns it, and then returns the results of recursively applying the function to the previous value. In other words FP.Iterate(0, x => x + 1) yields the following stream: 0,1,2,3,4,etc. In this case I use Iterate to walk up the inheritance tree of a type and find out what its depth is. Since the Iterate function is stateless and returns a stream I can use it in a Linq query. I sort the overloads by the max depth of any type in a given overload, and then by the sum of all the argument depths. Note that I sort the overloads in ascending order from most abstract to most derived instead of vice-versa. The reasons for this are clear when you examine how I build the expression.



Due to the fact that I want to build the expression using functional programming I will have to build it inside out recursively, starting with the most abstract function and ending with the most derived function. The reason for this is that more derived functions must call the most abstract functions, meaning they must exist before the derived functions are created. In order to achieve this I use a very versatile function: Enumerable.Aggregate. Aggregate takes an initial value, a function that accepts two arguments, and a stream. The first argument to the function is the initial value passed to the Aggregate. The second argument is the current item in the stream. Every time the function passed to aggregate is run the result is used for the accumulator variable. For example the following code yields 10:

var nums = new[]{1,2,3,4};
var output = nums.Aggregate(0, (x,y) => x + y);

Aggregate can work on anything, not just numbers. In this case my stream contains all the overloads, my accumulator variable is the expression I've built so far, and the function creates a new expression that invokes the current overload if the types match or invokes the expression in the accumulator if they don't.

This approach works well and is very elegant, but aren't we forgetting something?

What if instead of this...

collision(new XWing(), new TieFighter());

...the following code is run:

collision(new TieFighter(), new XWing());

Whoops! It wont match our first overload even though that would probably make the most sense under the circumstances. Within each handler we could write some manual code to try and reverse the arguments but that is exactly the kind of drudgery we want to avoid. Next time I'll show you how to modify our algorithm to generate code to try all the various combinations of argument orders.

Why are dynamic languages so...static?

<Rant> I'm frustrated by the glacial pace of evolution we see in the dynamic language space, specifically in the area of parallelism. This article on Ars Technica echoes what many of us have long suspected: the future is massively parallel. It was so obvious to me that the way to write parallel programs was not to deliberately assign certain types of tasks to certain cores that I was genuinely surprised at how wide-spread the practice was. We need to start expressing programs in such a way that they can be scaled to as many cores as there are available without developers having to manage the process. When you are dealing with 16, 32, 100+ cores it's no longer about making efficient parallelism easier. It about making it possible. Nobody's that good and if they tell you so they're lying. There is no silver bullet and there are many tasks that just can't be done in parallel. However the key to democratizing parallel programming is to give developers a clean way to express algorithms as stateless programs (read: functional programming), and give them access to their language's parse tree. Languages like LISP, ML, C#, VB.NET, and Perl 6 (if it is every released) expose the syntax tree to the developer allowing them to leverage the most important idea in computer science. Libraries can analyze this parse tree and rewrite it to run efficiently in a variety of different hardware scenarios. Given that the multi-core future is bearing down on us it's only natural to assume that the various popular programming languages would be scrambling to add the necessary idioms to support parallelism. Not so much. Ruby's got some functional programming constructs, but no way of getting at the AST. Python was just redesigned from the ground up and there was a grand total of zero language features added to support parallelism. Javascript was just moved to 2.0 and is similarly lacking. What's so criminal about this omission is that it is so easy to rectify. When you call "eval" an AST is created somewhere. It's simply a matter of exposing it before converting it into executable code. I just wrote a rudimentary chess AI in C# 3.0. I achieved just short of 4x speed increase on my quad-core simply by adding a single line of code and referencing the new ParallelFX CTP. I challenge anyone to achive a similar level of code clarity and performance with the dynamic languages en vogue today. </Rant>

MS has hired me

Sorry about the blog hiatus but I have a decent excuse: Microsoft has hired me on as a Senior Developer on the Silverlight team. Obviously I'm ecstatic. I'm going to be moving to Seattle and I'm hoping to start work on August 4th at which point I will resume posting.

Complaining about .NET 3.5

I been doing some pretty serious functional programming with the .NET framework since the LINQ preview was released early last year. After rougly a year of use I feel that I now have the experience to confidently make a list of complaints. This is by no means a rant. The .NET framework is excellent but the following omissions are really needling me. 1. No IRandomAccessCollection<T> interface. We need a way of indicating that a collection is randomly accessible. This means it has an O(1) method to access a given element in an array and an O(1) count property. IList<T> and System.Array should both inherit from it. Often I want to perform a stream operation that requires random access to elements in order to do its job efficiently. Either an Array or a List will do. Copying a stream into an array is potentially expensive. If the stream is already an Array or a List it's worthwhile to attempt a run-time cast because it may save considerable time. As a result I end up doing two casts and writing an adapter. This is essentially what's done in ParallelFX today and I overhead that Joe Duffy was looking for feedback as to whether an interface like this one should be added to the BCL. Yes please. 2. No BigInteger. By this I mean an integer that grows to any size (until it uses up available memory). It was announced that this would be introduced in .NET 3.5 but it was made internal at the last second. Blog posts asking for an explanation were ignored. I believe I understand the reasoning. There is always a way of avoiding using a BigInteger and producing a more efficient algorithm. That said, sometimes I want to trade efficiency for elegance, reliability (no overflows), and speed of development. That's a decision that should be left up to me. Occasionally the lack of a BigInteger is inconvenient enough to make me use IronPython instead of C# for certain programs.* 3. Cost of Concat. Concatenating IEnumerable's together is costly. This is unacceptable because streams are a fundamental C# idiom. Wes Dyer explains more fully in this blog post. This problem has really affected the efficiency and elegance of my functional algorithms. To address this problem the following new C# syntax has been proposed: yield return someValue yield foreach someIEnumerable; I hope this is adopted. This is a big issue. 4. Having to implement IEnumerable.MoveNext() every time I implement IEnumerable<T>. C# already has syntactical support for streams (yield). Would it have been so hard for the compiler to generate this function if it didn't already exist? I know this is probably a non-starter and not that big a deal, but frankly it's an embarrassing amount of cruft to have to write. 5. Having to read/write "IEnumerable<IEnumerable<string>>" is awful. In the same vein as the previous complaint, why not provide syntactical support for declaring streams. C-Omega, the precursor to C#, used the asterisk to indicate a type was a stream in a similar way that [] indicates a type is an array. Streams are so pervasive in C# that I believe they are worthy of the same syntactical support as an array. I know the asterisk is out because C# already uses them for pointer arithmetic, but what about this: T[...][...] GetPermutations<T>(this T[...] stream) { // ... } That's just off the top of my head and there may be a better syntax but you see my point. 6. Lack of a non-null modifier. One of the unfortunate but necessary attributes of C# is that it has the concept of nullness. This is necessary because C# wants to play well with unmanaged code. Nevertheless nullness breaks polymorphism. A great way of mitigating this issue is to provide compiler support to prevent NullReferenceExceptions. C-Omega allowed you to add "!" to the end of a type and the compiler would enforce that a null value couldn't be assigned to it. Customer! cust = null; // compiler error I don't understand why this wasn't added to C#. I assume there's a good reason. Perhaps someone could explain it to me? That's all I can think of at the moment. I'll no doubt update this post as I run across further issues. *I like Python. I do think C#'s query comprehensions and its ubiquitous stream monad make it better suited for functional programming though.

Multimethods in C# (Part 1)

Have you ever needed to perform an action based on the run-time type of one or more objects? Let's take a hypothetical spaceship game for example. There are three types of objects: an Asteroid, an X-Wing and a TIE-Fighter. They are related in the following inheritance hierarchy:



We have a collection of SpaceObjects that we update in a tight loop. We need to handle collisions between these objects. For example if a TIE-Fighter collides with an asteroid we might want to apply damage to the space ship and replace the asteroid with several smaller asteroids. One way of doing this is to determine the concrete type of each SpaceObject and then call one of several overloads to handle the collision:

bool Collison(SpaceObject leftSpaceObject, SpaceObject rightSpaceObject)
{
TieFighter tieFighter = leftSpaceObject as TieFighter;
Asteroid asteroid = rightSpaceObject as Asteroid;
if (tieFighter != null && asteroid != null)
{
  return Collision(tieFighter, asteroid);
}

XWing xWing = leftSpaceObject as XWing;
if xWing != null && asteroid != null)
{
  return Collision(xWing, asteroid);
}

//try again with reversing left and right parameters

// and on and on for every combination of every object in every order...
}

bool Collision(TieFighter tieFighter, Asteroid asteroid)
{
// handle collision
}

bool Collision(XWing xwing, Asteroid asteroid)
{
// handle collision
}

The method that dispatches to the correct overload smells. It is error-prone because you have to be careful to cast in order from the most derived to least derived classes. Failure to do so will not result in the most correct method being selected. It is also repetitive because all of the information required to write this code can be inferred from information you've already declared in your overloads and your class definitions. It's also a maintenance nightmare because if we make any changes to the class hierarchy we will need to remember to update the method.

Multimethods

Essentially we want virtual method dispatch but we need it on multiple types and we need it bound at run-time because the compiler can't know enough information to do it at compile-time. This is exactly what multimethods allow us to do. In a compiler that supports multimethods you simply declare the various overloads and the compiler ensures the correct overload is called. Here's what this might look like if it were added to C#:

// when invoked this checks argument types and dynamically dispatches to overloads below
multimethod bool Collision(SpaceObject obj1, SpaceObject obj2);

bool Collision(TieFighter tieFighter, Asteroid asteroid)
{
// handle collision
}

bool Collision(XWing xwing, Asteroid asteroid)
{
// handle collision
}

bool Collision(TieFighter tieFighter1, TieFighter tieFighter2)
{
//handle collision
}

// and so on for all cominbations...

Unfortunately there is no "multimethod" modifier in C# and it's quite unlikely there ever will be. Thankfully C# 3.0 does have a feature which allows us to seamlessly add this feature: Expressions.

Adding Multimethods to C#

Let's create a library that examines our class hierarchy and a group of method overloads using reflection and then creates the method that does the dynamic dispatch for us. We'll design it so it has the following API:

var collision = DynamicDispatch.CreateFunc<SpaceObject,SpaceObject,bool>((obj1, obj2) => this.Collision(obj1,obj2));

// dispatches to Collision(XWing xWing, TieFighter tieFigher)
collision(new XWing(), new TieFighter());

What's going on here? The CreateFunc method accepts a lambda in which the most abstract version of the collision method is invoked. It returns an instance of Func<>, a new delegate type introduced in C# 3.0 that wraps a method that returns no arguments. How do I manage to generate the code required to do dynamic dispatch from a lambda function? I'll cover that in the next installment. Stay tuned. :-)

Using Operators with Generics

Many .NET users have no doubt run into issues using math functions with generics. Let's say you want to write a Matrix class. You would like to make it a generic class so that you can use it with doubles, ints, and so on. The definition might look like this:



Attempt to compile this will fail. The compiler chokes on the following line:

output[x,y] = (value1.numbers[x,y] + value2.numbers[x,y]);


The compiler can't confirm that type T will have the + operator. Normally the way you resolve this is by using a constraint. However there is only two kinds of constraints: type-based and constructor-based. The operators aren't part of an interface and I'm not sure they should be. A better solution would have been for C# to allow operator-based constraints. After all, an exception is made for constructors. They may have decided against this route for CLS compliance. We'll probably never know.



All this conjecture doesn't get us any closer to our Matrix class. There are two ways of getting what we want. The first is reflection. In fact, if you are using late binding VB.NET will compile a modified version of the code above happily and resolve the operator using reflection at run-time. Reflection is slow though and typically we want math operations to run quickly.



That leaves us with code generation. I've been talking alot about Lambda Expressions in recent posts. Lambda Expressions are a new .NET 3.5 feature that makes it easy to generate methods on the fly quickly. The code below is a refinement of the work done by Rüdiger Klaehn. He uses low-level IL generation API's available in .NET 2.0. Observe how his code can be simplified dramatically by using lambda expressions instead.



This class creates and compiles expressions for each of the operators (only addition shown above for brevity). The lambda expression worries about exactly which add method to bind to based on the parameter types when it is compiled into a delegate. Pretty readable eh? Now let's rewrite our Matrix class.



Notice that the consumer of our API doesn't need to futz about with the Num class at all. They use the Matrix exactly as they would expect to:

var leftMatrix = new Matrix<int>(new[,]{ {2,2,1},{5,2,1} });
var rightMatrix = new Matrix<int>(new[,]{ {1,2,4},{1,9,1} });

var newMatrix = leftMatrix + rightMatrix;

So what's the catch? You lose static typing. If you parameterize the Matrix class with a type that doesn't have the operators defined it will trigger a run-time error. There is no way around this because there is no way of confirming the operators exist at compile-time. Does this make you uncomfortable? Get used to it.

Many statically and dynamically typed languages are gradually moving towards a new model: Static Typing Where Possible, Dynamic Typing When Needed. VB.NET is already there with its optional late binding. A similar feature is being discussed for C#. If you do a lot of work with run-time code generation you will begin to notice two things:

1. You will have to compromise on compile-time type safety more and more.
2. You will find yourself caring less and less.

Static typing is a tool, not a religion. Frankly it was never very useful for assuring program correctness and if you are test-driven it is even less useful. Static typing is most useful as metadata for your development tools. It often makes sense to live without it in specific cases where doing so prevents you from repeating yourself. Using code generation to avoid writing identical Matrix implementations for each numeric base type is an excellent example. Can you think of any others?