So you’ve seen LINQ to SQL in action and it looks like voodoo. How does the compiler turn that funny looking query statement that you’ve written in C# and make a working SQL query out of it? There are a couple of other key parts to it, but right in the middle are expression trees, forming the neutral map from which either a lambda statement (which is what your LINQ query breaks up into) or a SQL query can be generated.

So what’s an expression tree? To start with we first need to remember that the expressions we write are often really a number of smaller expressions chained together. These smaller expressions in their linear form are commonly viewed as lambda’s, but if we pull apart the smaller, simpler expressions we can view them in an entirely different manner. This is where our expression tree comes in. It represents each piece of an expression as a node in a tree form. Operators form root nodes for their expression, with operands becoming leaf nodes of the operator.

In .Net these nodes are represented by specific types based on their attributes. These types are available in the System.Linq.Expressions namespace, and I’ll show you how to use them to build a representation of our tree later in the post.

Now we’ve covered the basics, let’s take a simple (x,y) => x > y lambda and turn it into a tree. The first thing we need in a tree is a root. In this case we have a single statement made up of 1 operator and 2 operands. In this case, finding our root is quite simple. Our operator forms our root – which gives us:

This now leaves us with our 2 operands – which in this case are x and y. These become leaves of our expression tree that hang off our root node as follows:

So as you can see, creating an expression tree is really quite simple. First we identify the operator, and it becomes our root. Next we attach our two operands to our root, and all of a sudden we have a tree! Now, let’s move on to a more complex example.

For our first example we created a single expression tree. This time around, we’ll give a mutliple expression tree a go, and in the process will learn how expressions can be linked together in trees. This time we’ll create a tree from the expression (x, y, z) => (x > y) & (x < z).

First up we’ll create our root. In this case the root is not so clear – we have 3 operators here, a greater than, a less than and a logical and operator. To pick the root, we’ll need to break our expression up into its constituent expressions. Here way have expression a: x > y, expression b: x < z and finally expression c: (a) & (b). Because expression c contains both of our other expressions, it makes the most obvious root expression. This gives us:

It looks like a simple peice, however it forms the basis for our later work once more. Next up, we’ll take expression (a) and turn it into a tree. Once again we pick the operator, and attach the operands as we did in our first example. This will give us the following:

Looks familiar right? Next – on to expression (b)! Once again, we take the operator which in this case is a less than operator. We then attach the two operands, in this case x and z to form our expression tree.

Ok now we have the 3 parts of of our intial expression mapped to a tree, we can begin to peice them back together to form our complete tree. We do this by attaching the two child trees back to our root node as follows:

And there it is! A tree representation of our more complex expression. There’s plenty more to learn here, but this will give you enough to start constructing basic trees on paper. Now onto the interesting part – building these trees in .Net.

Given our first example expression tree lambda we have (x,y) => x > y. We know what this looks like when it’s drawn into a tree, and we have an approach – taking the root first. The problem is that the root isn’t the same in this case. When creating tree’s using the .Net framework we take the source lamda, and it becomes our root. Given that little fact, we can move to the parameter side of this expression (the left hand side).

The 2 leaves we’ve got here are represented in .Net by the ParameterExpression type that I mentioned earlier. These parameter expressions are generated using the following code:

ParameterExpressionparameterX = Expression.Parameter(typeof(int), “X”);

ParameterExpressionparameterY = Expression.Parameter(typeof(int), “Y”);

You’ll notice we use the Expression class to generate our ParameterExpressions. The Expression class is a factory class that provides a number of expression class generation methods as well as being the abstract base class for our expression types.

Ok so now we have the (x, y) parameter definition of our lambda. That must mean it’s time to move on to the right hand side of the expression. On the right hand side we have the x > y expression. This is a binary type expression due to the fact that we have 2 operands (x and y) and 1 operator (greater than). This then adds a third branch to our tree, so that we now have something along the lines of this…

Now we have all our expressions in our tree. Our representation is not quite accurate though as the parameters x and y that are shown in our BinaryExpression on the right are actually references to the ParameterExpressions on the left hand side. As you can see the tree looks quite different, this is mainly due to the way the data structures are represented in .Net. Its still the same expression though in a pure form.

So where can we go from here? Well, the beauty of expression trees is that they are a fairly agnostic way to represent expressions. From an expression tree we can generate a query in the syntax of any language that we are provided a operator mapping for. As an example, LINQ to SQL would convert the demonstration tree into a SQL statement. Imagine x and y were field names from a table, we could have something like

WHERE Table1.FieldX > Table1.FieldY

Or if we substitute our Y parameter expression for a constant expression with an arbitrary value of 10, we could have something like…

WHERE Table1.FieldX > 10.

There are a lot more possibilities to be explored but as you can see from this basic example expression trees are quite simple, yet powerful tools.

Andrew MatthewsHi Steve,

An excellent post! Very well explained. Am looking forward to the next installment. I have an interesting problem if you’re looking for material for it…

:^]

Andrew