IanG on Tap

Expression Trees astonished me more than any other new feature in C# 3.0. Most of the other language additions seem relatively straightforward - it's fairly easy to see how they relate to what I could already write with C# 2.0. They're useful, but all seem like small incremental steps. Expression trees on the other hand gave me a real "what the?.." moment when I first saw them.

Lambdas

Before we can look at expression trees, we need to look at another new C# 3.0 feature, lambdas. Lambdas are an incremental step in the steadily expanding support for functional programming idioms in C#. (They're not a pure functional feature, but they support a style of coding common in functional languages.) C# 3.0 lambdas are usually portrayed as the next step on from anonymous delegates, which is reasonable enough from a historical perspective. Here's the progression.

You've always been able to write methods in C#. (Yes, I'm starting from the very beginning, but please bear with me.) Often those methods return values. Here's just such a method:

public static bool IsOdd(int i)
{
    return (i & 1) == 1;
}		

If you like, you can call this method from other parts of your code. Alternatively, you can pass a reference to this function to someone else so they can call it. This feature has been present since C# 1.0 - this is what delegates do. To exploit this, we need to define a suitable delegate type:

public delegate bool NumberTester(int i);

Then we can write code that is able to use this kind of thing:

public static void PrintMatchingNumbers(int from, int to, NumberTester filter)
{
    for (int i = from; i <= to; ++i)
    {
        if (filter(i))
        {
            Console.WriteLine(i);
        }
    }
}

We can then call this, passing in the IsOdd function we wrote earlier as the filter:

PrintMatchingNumbers(1, 10, new NumberTester(IsOdd));

This is a rather roundabout way of getting this particular job done, but the power of this technique is that we are now free to plug in different filter functions - anything with the right signature will do. Instead of IsOdd we could write other filters such as IsEven or IsPrime. And having written those functions, we could then devise other functions that use them - as well as the PrintMatchingNumbers method, we could write one that displays numbers in a Windows Forms app, or writes them into a file. We've separated out the filtering from the use of the filter. This is a much more flexible approach than writing, say, a PrintOddNumbers function.

Of course it's nothing you couldn't achieve with abstract base classes or interfaces. But delegates require less work in scenarios where all you needed to do was pass a single function. Delegates are particularly handy when you want to connect lots of individual functions to lots of individual objects, such as when handling events in GUI applications.

Delegates can also carry around an object reference as well as a reference to a function. IsOdd is static, but if I want to use an instance method, I can do that. I can provide the target object when I create the delegate. (If you're a C++ developer, you might like to think of a delegate as the combination of a pointer to a method and a pointer to an object. It's not an exact analogy, but it gives a pretty good feel for what a delegate is like.)

C# 2.0 expanded on this with its support for anonymous methods. This is useful in scenarios where you never plan to call the method by name, and only ever want to pass it around via a delegate. Anonymous methods offer a new syntax that saves you from declaring the method, enabling you to write it inline in another method. So I can do this kind of thing:

public static void ShowOdd()
{
    PrintMatchingNumbers(1, 10,
        delegate(int i)
        {
            return (i & 1) == 1;
        });
}

This is exactly equivalent to the previous example. I've put the code that used to be in IsOdd inline. The C# compiler simply hoists it back out into a function for me at compile time. At first this may not seem particularly useful - it makes your code a little more compact, but is it really such a big deal? But then you discover the neat trick the C# compiler plays for you. Remember I said you can associate an object with a delegate? Well the C# compiler exploits that to make any variables in scope in the parent function available in the nested function. (To get the same effect in C# v1.0 you had to move any variables you wanted to share into an object shared by both methods. So you had to write a class specially. And of course this is exactly what the C# compiler now does for you under the covers.) So I can do this:

public static void ShowDivisible()
{
    for (int d = 1; d < 10; ++d)
    {
        Console.WriteLine("Numbers divisible by " + d);
        PrintMatchingNumbers(1, 10,
            delegate(int i)
            {
                return (i % d) == 0;
            });
    }
}

(By the way, the nested function can modify variables defined in the outer scope. So the nested function doesn't merely get a copy of these variables - variables are shared between the parent and nested function. Under the covers this is implemented by moving any shared variables into a generated class.)

C# 3.0 takes this one step further by introducing a slightly more compact syntax. We can simplify the call to PrintMatchingNumbers like so:

PrintMatchingNumbers(1, 10, i => (i % d) == 0);

That's an example of a lambda expression. Lambda expressions are always of this form:

parameters => expression

The effect in this particular example is pretty similar to using an anonymous delegate. It's just more compact. And if you're familiar with certain functional programming languages, the syntax will seem pretty obvious too. For example, here's the ML for a function similar to the divisor one (ML's mod operator does the same as C#'s %):

fn i => (i mod d) = 0;

So far, lambdas don't appear to offer anything I didn't already have with anonymous methods besides a different syntax. However, they turn out to be able to do something that anonymous methods cannot.

Lambdas as Expression Trees

Consider the following code:

Func<int, bool> nonExprLambda = x => (x & 1) == 0;
Expression<Func<int, bool>> exprLambda = x => (x & 1) == 0;

The first line is just using the lambda syntax to initialize a delegate. The only thing we've not seen before here is the use of the generic Func delegate type supplied as part of LINQ. There's nothing terribly exciting about it - it looks like this:

It's just a handy generic delegate type that can be used to represent any single-parameter function.

The second line is more interesting. This takes that Func delegate, and uses it as the type parameter for a generic type called Expression<T>. It then proceeds to initialize it in exactly the same way, so you'd think it was doing much the same thing. But it turns out that the compiler knows about this Expression<T> type, and behaves differently. Rather than compiling the lambda into IL that evaluates the expression, it generates IL that constructs a tree of objects representing the expression.

This was the point at which I went: "what the?.."

To be more explicit about this, here's roughly what that second line compiles into:

ParameterExpression xParam = Expression.Parameter(typeof(int), "x");
Expression<Func<int, bool>> exprLambda = Expression.Lambda<Func<int, bool>>(
    Expression.EQ(
        Expression.BitAnd(xParam, Expression.Constant(1)),
        Expression.Constant(0)),
    xParam);

(Aside: there has been a tendency to dismiss all the new features of C# 3.0 as 'syntactic sugar'. If you think this is another example, then I guess you probably feel the same way about assembly language, and feel that there haven't really been any significant coding innovations since the front panel with toggle switches.)

As it happens, I've been playing with LISP a lot lately. (Nothing to do with Don, by the way, in case you've seen his recent Scheming and were wondering. In any case, I've been looking at Common LISP, not Scheme. So I blame Paul Graham.) The idea of an in-memory data structure that represents parsed code is therefore a familiar one to me. Then again, LISP's syntax is pretty straightforward, so it's a whole lot easier to do that in LISP...

If you're familiar with LISP, you probably don't need any explanations as to why expressions-as-data-structures are useful. But if you're not familiar with things LISPish, you might be wondering why on earth the C# team has done this. This was driven by LINQ. This language feature is applicable to a wide range of other scenarios, but there's a particular use case in LINQ for which this is particularly important.

Expression Trees, LINQ, Deferred Queries, and Databases

LINQ (Language Integrated Query) defines a standard way of performing queries against various types of data in a way that can be tightly integrated into a language. Both C# 3.0 and VB 9 (each of which is currently in early preview) provide language features intended to support LINQ. Indeed most of the new C# 3.0 languages features have been added on LINQ's behalf, although none of them is inextricably bound to LINQ.

I won't do the full introduction to LINQ at this point - there are plenty of other people who have done that. But I will point out that the standard intro usually shows fairly early on how LINQ queries let you chain together and filter IEnumerable<T> streams, which is what enables you to perform queries over objects.

A little further into the demo, you will typically see something like this:

DataContext db = new DataContext("server=.;initial catalog=northwind");
Table<Orders> orders = db.GetTable<Orders>();
Table<Customers> customers = db.GetTable<Customers>();

var q = from o in orders, c in customers
        where o.ShipCity == "London" && (o.CustomerID == c.CustomerID)
        select new { o.OrderDate, c.CompanyName, c.ContactTitle, c.ContactName };

foreach (var item in q)
{
    Console.WriteLine("Order for {0} {1} at {2} placed on {3}",
        item.ContactTitle, item.ContactName, item.CompanyName, item.OrderDate);
}

This is the new query expression syntax in C# 3.0. That deserves a blog entry of its own, but for now, it's enough to know that it gets translated into a bunch of method calls. It's equivalent to this:

var q = orders.Where(o => o.ShipCity == "London").SelectMany(
    o => customers.Where(c => o.CustomerID == c.CustomerID).
            Select(c => new { o.OrderDate, c.CompanyName, c.ContactTitle, c.ContactName }));

This in turn is relying on the new extension method syntax, so it's really just a shorthand for:

var q = QueryExtensions.SelectMany(
    QueryExtensions.Where(orders, o => o.ShipCity == "London"),
    o => QueryExtensions.Select(
            QueryExtensions.Where(customers, c => o.CustomerID == c.CustomerID),
            c => new { o.OrderDate, c.CompanyName, c.ContactTitle, c.ContactName }));

(Hey! In just a single statement I worked in var, extension methods, lambdas, LINQ, and, as will shortly become clear, expressions! Do I get a prize?)

Given that earlier in the intro we see LINQ doing what appears to be iteration over IEnumerable<T> streams of objects, this looks terrifying. You might leap to the conclusion that the first call to QueryExtensions.Where will generate a call to the database selecting all the orders with a ShipCity of 'London' and that the QueryExtensions.SelectMany call will then iterate through the results, issuing multiple SELECT statements to the DB to retrieve the customer information, one for each order in turn.

In other words, it looks like it's going to do the dreaded join-on-client. Fortunately it doesn't. It's smarter than that.

I used SQL Profiler to find out what ends up getting sent to the database as a result of the code above. (Any of the three variations cause the same query to be sent as they are all equivalent.) Here's what I saw:

exec sp_executesql N'SELECT [t1].[CompanyName], [t1].[ContactName], [t1].[ContactTitle], [t0].[OrderDate]
FROM [Orders] AS [t0], [Customers] AS [t1]
WHERE ([t0].[ShipCity] = @p0) AND ([t0].[CustomerID] = [t1].[CustomerID])', N'@p0 nvarchar(6)', @p0 = N'London'

That looks pretty reasonable. It has generated a single query that returns exactly the data we require in the form we want. Not only is the join on the Orders and Customers table being done in the DB where it should be, the query has also been suitably frugal about the columns it has retrieved.

DLinq was able to do this because the lambdas supplied to the Where methods were converted into expression trees. This enabled it to analyse the structure of the query and generate suitable SQL.

This ability for code to work with the structure of an expression is here for DLinq's benefit, but it's a pretty powerful language feature to have.

Expression Trees

So what do these expression trees look like? At the core of the API is an abstract base class called Expression. (Confusingly, this not the same class as the generic Expression<T> class we saw earlier. The latter is used to generate the former. Slightly more confusingly still, Expression<T> derives indirectly from Expression by way of LambdaExpression.) All nodes in the expression tree will be of some type derived from Expression. There are specialised node types for different parts of the expression:

Some of these node types can be used in various different ways, so there's a NodeType property to indicate which particular variation is in use. For example, a BinaryExpression might have a NodeType of ExpressionType.EQ for an equality comparison, while one representing an addition would have ExpressionType.Add.

It seems pretty powerful. I've not yet tried in earnest to see if there's anything that would be valid in a normal expression that wouldn't be supported in an expression tree, but as far as I can tell, the idea is to support everything. Code that processes expression trees could of course elect not to support everything. DLinq won't be able to convert all possible C# expressions into SQL, because mappings don't necessarily exist. But it looks like all valid C# expressions can now be had as expression trees. This is my favourite new C# 3.0 feature.