New Features in C# 3.0, Part 6: Expression Trees

bennie — Sun, 19 Aug 2007 00:33:23 GMT

Introduction

In the previous installment of this series, we looked at lambda expressions. During our little trip down memory lane, we concluded that lambda expressions are a logical evolution of anonymous functions, which in turn are (to some extent) an evolution of delegates. In the context of this article, it is very important to understand that lambda expressions are always directly compiled into IL code by the compiler, so a lambda expression is a representation of a unit of executable code, it is not a data structure.

Below is an example of a lambda expression that calculates the volume of a box:

Func<double, double, double, double> boxVolume = 
                (width, length, height) => width * length * height;

Next, let's take a look at this line of code:

Expression<Func<double, double, double, double>> volumeExpr = 
                (width, height, length) => m_width * m_height * m_length;

Essential, what we are doing in this line of code is taking our earlier lambda expression, and supplying it as the type argument for a generic type called Expression<T>. Expression<T> is defined in the System.Linq.Expressions namespace, and looks as follows:

 1     // Summary:
 2     //     Represents a strongly typed lambda expression as a data structure in the
 3     //     form of an expression tree. This class cannot be inherited.
 4     //
 5     // Type parameters:
 6     //   TDelegate:
 7     //     The type of the delegate that the System.Linq.Expressions.Expression<TDelegate>
 8     //     represents.
 9     public sealed class Expression<TDelegate> : LambdaExpression
10     {
11         // Summary:
12         //     Compiles the lambda expression described by the expression tree into executable
13         //     code.
14         //
15         // Returns:
16         //     A delegate of type TDelegate that represents the lambda expression described
17         //     by the System.Linq.Expressions.Expression<TDelegate>.
18         public TDelegate Compile();
19     }
20

When you look at the comments for the class, you notice that an Expression<T> represents a lambda expression as a data structure in the form of an expression tree. So, rather than directly compiling the lambda expression into executable IL that can directly evaluate the expression, what an Expression<T> does is create an in-memory tree of objects that represents the expression that was supplied as its type argument.

Now, when you look at the definition of Expression<T> you probably noticed it single method called Compile(). This method compiles the expression, and when the compilation is successful, generates the "real" lambda expression, which then in turn can be executed, because it really IS IL, ready to run! To execute a compiled Expression<T> instance, just use it's Invoke() method, supplying the required parameters.

An overview of this two-step process is shown below:

The in-memory representation of an Expression<T> is an expression tree, as is shown in the above figure.

Microsoft actually made a visualizer available, which is very useful for analyzing the structure of an expression tree. A screen shot of the visualizer for our expression looks as follows:

Getting the Expression Tree Visualizer up and running in Orcas Beta 2

In Beta 2 of Orcas, the expression tree visualizer is NOT installed by default. But fear not, and follow these steps to get the visualizer to work:

If you are running the Orcas Beta 2 VPC image, go to the directory: C:\Program Files\Microsoft Visual Studio 9.0\Samples\1033. Otherwise, go to the directory where you have Oracas installed.
In this directory, you will find a file called CSharpSamples.zip. Unzip this file to your preferred directory (I created a sub-directory CSharpSamples under the above directory).
After you unzipped the file, move to the sub-directory LinqSamples, in this sub-directory you will find another subdirectory called ExpressionTreeVisualizer. Go to this sub-directory.
In the ExpressionTreeVisualizer sub-directory, you will find a solution called ExpressionTreeVisualizer.sln. Open and build this solution.
After the build successfully completes, move to the \ExpressionTreeVisualizer\bin\Debug sub-directory. In this directory, you will find a file called ExpressionTreeVisualizer.dll. This is the actual visualizer dll used by Visual Studio.
Copy the ExpressionTreeVisualizer.dll to the C:\Documents and Settings\Administrator\My Documents\Visual Studio 2008\Visualizers directory (if not logged in as administrator, substitute administrator with your user name. This is the location where all Visual Studio visualizers live for your Visual Studio installation.
After you have completed the above steps, and have restarted Visual Studio, the following will happen when you are debugging an application with an Expression<T> instance, and you have a breakpoint on a unit of code with an Expression<T>:
- You will see the "Looking glass" icon, indicating that a visualizer is available for the object under the cursor.
- Click the looking glass icon.
- The "Expression Tree Visualizer" selector will pop up, as shown below:

Click the pop-up, and the visualizer will show the expression tree in all of its beauty, as shown earlier.

Creating Expression Trees

You can create an expression tree in two different ways:

You can write an Expression<T> as we did in our example in the previous section. by assigning an Expression<T> instance to a lambda expression. As we saw in the visual studio visualizer, the C# compiler automatically generated (in this case a quite elaborate) expression tree for us.
You can use the Expression API in the System.Linq.Expressions namespace to manually build your own expressions. While this quite a bit more complicated and time-consuming, it does open up all kinds of possibilities, as we will see in the "Dynamic Queries" section of this post.

We will take a closer look at each approach in the next sections.

Creating an expression tree based upon a lambda expression

The first approach to creating expression trees is fairly easy. You write a valid lambda expression, and supply it as the type argument to an Expression<T> instance. This is illustrated by the following code sample (this is the SimpleExample class in the SimpleExpressionTrees project of our sample code):

 1         /// <summary>
 2         /// This method shows how you can create an expression, based upon
 3         /// a Lambda Expression
 4         /// </summary>
 5         public static void CreateExpressionFromLamba()
 6         {
 7             // This is how you declare a lambda expression by itself
 8             Func<int, int, int> addLambda = (value1, value2) => value1 + value2;
 9 
10             // This is how you declare an equivalent lambda expression
11             Expression<Func<int, int, int>> lambdaExpression = (value1, value2) => value1 + value2;
12             Console.WriteLine("Lambda Expression: {0}", lambdaExpression.ToString());
13             dumpExpression(lambdaExpression);
14 
15             // Compile and execute the lambda expression in the Expression<T>
16             Func<int, int, int> lambda = lambdaExpression.Compile();
17             int v1 = 5;
18             int v2 = 10;
19             Console.WriteLine("Compiling and executing the expression");
20             Console.WriteLine("{0} + {1} = {2}", v1, v2, lambda.Invoke(v1, v2));
21 
22             // Note how I can use statements in a lambda expression
23             Func<int, int, bool> compareLambda = 
24                 (val1, val2) => { if (val1 == val2)  return true; else return false; };
25            
26             // The statement below will not compile, since you cannot use
27             // a lambda expressions with a statement to create an expression tree
28             //Expression<Func<int, int, bool>> compareExpression =
29             //    (val1, val2) => { if (val1 == val2)  return true; else return false; };
30         
31         } // method CreateExpressionFromLamba

In line 8, we create a simply lambda expression which adds the two integers passed as arguments. In line 11, I create an expression tree, based upon an identical lambda expression. Note also, how Expression<T> has a handy ToString() override which shows the lambda expression. The output of line 12 is shown below:

Lambda Expression: (value1, value2) => (value1 + value2)

So, what we get is a neat representation of the lambda expression on which the expression is based. To add some functionality to this I created a simple little dumpBLOCKED EXPRESSION function which prints out the details of an expression. The code for this method is shown below:

 1         /// <summary>
 2         /// This method prints out the details of the passed-in Expression
 3         /// </summary>
 4         /// <typeparam name="T"></typeparam>
 5         /// <param name="expression"></param>
 6         private static void dumpExpression<T>(Expression<T> expression)
 7         {
 8             Console.WriteLine("Lambda Expression: {0}", expression.ToString());
 9             Console.WriteLine("Expression Details: ");
10             Console.WriteLine("\tExpression Body: {0}", expression.Body);
11             for (int index = 0; index < expression.Parameters.Count; index++)
12             {
13                 var parameter = expression.Parameters[index];
14                 Console.WriteLine("\tParameter {0}: '{1}', Type: {2}",
15                     index, parameter, parameter.Type.Name);
16             }
17             Console.WriteLine("\tNodeType: {0}", expression.NodeType);
18         }

This code sample shows some interesting properties of the Expression<T> class:

The Body property of the Expression<T> gives us the body of the lambda expression.
The Parameters property returns a ReadOnlyCollection<T> where T is of type ExpressionParameter. The code simply loops over each parameter, and prints the index, name and type of each parameter.
Finally, the NodeType property provides the Node Type of the Expression. We'll have more to say about Node Types in the next section.

When we pass our expression to this function, we get the following output, which correctly represents our expression instance.

Lambda Expression: (value1, value2) => (value1 + value2)
Expression Details:
        Expression Body: (value1 + value2)
        Parameter 0: 'value1', Type: Int32
        Parameter 1: 'value2', Type: Int32
        NodeType: Lambda

When the invoke the Expression<T> Compile() method, we get our original lambda expression back, as is shown below:

Func<int, int, int> lambda = lambdaExpression.Compile();

Next, we can invoke the lambda expression directly with it's Invoke() method:

            int v1 = 5;
            int v2 = 10;
            Console.WriteLine("Compiling and executing the expression");
            Console.WriteLine("{0} + {1} = {2}", v1, v2, lambda.Invoke(v1, v2));

which produces our expected output:

Compiling and executing the expression
5 + 10 = 15

When we go back to our first listing, we see that we can also create a lambda expression, based upon a statement, instead of a simple expression:

1             // Note how I can use statements in a lambda expression
2             Func<int, int, bool> compareLambda = 
3                 (val1, val2) => { if (val1 == val2)  return true; else return false; };

However, you cannot use a lambda expression with a statement to initialize an expression. If I would attempt to compile a function with the following statement:

            // The statement below will not compile, since you cannot use
            // a lambda expressions with a statement to create an expression tree
            Expression<Func<int, int, bool>> compareExpression =
                (val1, val2) => { if (val1 == val2)  return true; else return false; };

The you would get the following compilation error:

Error    1    A lambda expression with a statement body cannot be converted to an expression tree    SimpleExpressionTrees

Manually Creating an Expression Tree

The System.Linq.Expression namespace offers a rich API, which allows you to dynamically build an expression tree of arbitrary complexity, without the limitations mentioned in the previous section. For example, the code sample below, shows how to use this API to build exactly the same expression as we did earlier in the first example of the CreateExpressionFromLamba() method:

 1         /// <summary>
 2         /// In this example, we build exactly the same expression as we 
 3         /// did in the first example of the CreateExpressionFromLamba()
 4         /// function
 5         /// </summary>
 6         public static void ManuallyBuildBLOCKED EXPRESSION
 7         {
 8             Console.WriteLine("\n\nManually Building an expression");
 9 
10             //  First, create the parameter expressions
11             ParameterExpression val1Expr = Expression.Parameter(typeof(int), "value1");
12             ParameterExpression val2Expr = Expression.Parameter(typeof(int), "value2");
13 
14             // Create the "add" expression
15             BinaryExpression addExpr = BinaryExpression.Add(val1Expr, val2Expr);
16             
17             // Wrap the add expression in a Lambda expression
18             var lambdaExpr = 
19                 Expression.Lambda<Func<int, int, int>>(
20                     addExpr, new ParameterExpression[] {val1Expr, val2Expr});
21 
22             // Dump the expression
23             dumpExpression(lambdaExpr);
24 
25             // Compile and execute the lambda expression in the Expression<T>
26             Func<int, int, int> lambda = lambdaExpr.Compile();
27             int v1 = 5;
28             int v2 = 10;
29             Console.WriteLine("Compiling and executing the expression");
30             Console.WriteLine("{0} + {1} = {2}", v1, v2, lambda.Invoke(v1, v2));
31 
32         } // method ManuallyBuildExpression

As you can see, the code is definitely more verbose, but not necessarily complicated. First, we create two ParameterExpressions to represent the value1 and value2 parameters to the lambda expression. Next, we create an Add BinaryExpression, which adds both values together. The BinaryExpression class has 17 overloads, which allow you to create just about any binary expression you would ever need.

Finally, we wrap our expression into a lambda expression, which is ultimately what we were planning to do from the start. Note that we need to specify the correct lambda prototype as type argument. The function arguments are the Binary Add expression, and both of our Parameter Expressions.

To verify that we indeed created the correct expression, we passed our expression on to our trusted dumpBLOCKED EXPRESSION function. Here is the output:

Lambda Expression: (value1, value2) => (value1 + value2)
Expression Details:
        Expression Body: (value1 + value2)
        Parameter 0: 'value1', Type: Int32
        Parameter 1: 'value2', Type: Int32
        NodeType: Lambda

And indeed, the output of our manually created expression tree is identical to our first expression, created directly from a lambda expression! An naturally, we can compile and invoke the expression as we did in our previous example.

Using Expression Trees to create Dynamic Query Expressions

One of the interesting applications of expression trees, is the enablement of more dynamic LINQ queries. The DynamicQueryWithExpression class of the sample code illustrates this. The constructor of this class generates an integer array with 20 elements, as is shown below:

1         public DynamicQueryWithExpressions()
2         {
3             for (int i = 0; i < 20; i++)
4             {
5                 m_myInts.Add(i);
6             }
7 
8             Console.WriteLine("\nDynamic Query Example");
9         } // constructor

The SimpleQuery() method performs a query against this list, retrieving all elements that are between 5 and 15 exclusive:

 1         /// <summary>
 2         /// This method executes a simple, very straightforward query
 3         /// </summary>
 4         public void SimpleQuery()
 5         {
 6 
 7             var results = from i in m_myInts
 8                             where i > 5 && i < 15
 9                                 orderby i
10                                     select i;
11 
12             showResults("SimpleQuery", results);
13         
14         } // method  SimpleQuery

The output from this query is shown below:

Results from query: QueryWithDynamicParameters
        7
        9
        11
        14

This query contains a very simple where clause that specifies our range. But what if we have a situation where we do not know at compile time what numbers we need? We might want to include some number, and at the same time, we might want to exclude some other numbers. Furthermore, the user might want to specify these numbers at runtime, through some type of user interface. In such a scenario, the above simple query construct will no longer work for us.

Scenario's such as the one describe above are a custom fit for custom expressions. As we mentioned before, we can construct any Expresssion<T> -based expression tree we want, of arbitrarily deep complexity. In the above example, what we have a need for is a way to build AND and OR expression "chains". One we can build these expression, we can build ourselves a "power where clause" we can use for our query.

I started writing a class to build these types of predicates, but then I came across a beautiful implementation by Josheph Albhari, and I decided that this was so nicely done that there was no way to improve upon his code, so credit where credit is due. By the way, I really recommend Joseph Albhari's blog, he has some great C# 3.0 examples in there. The name of his class is PredicateBuilder, and the code is shown below:

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 789cf3d0-cecf-4954-82a4-8ce73e39fdfb" style="padding-right:0px;display:inline;padding-left:0px;float:none;padding-bottom:0px;margin:0px;padding-top:0px;">

 1 using System; style="color:#0000FF;">using System.Collections.Generic; style="color:#0000FF;">using System.Linq; style="color:#0000FF;">using System.Linq.Expressions; style="color:#0000FF;">namespace SimpleExpressionTrees { /// <summary> /// This class allows us to build AND and OR expressions /// </summary> style="color:#000000;">    public static class PredicateBuilder { // These expressions define a true or false expression, which are // used as "anchor" expressions for build or AND or OR predicates style="color:#000000;">        public static Expression<Func<T, bool>> True<T>() { return f => true; } public static Expression<Func<T, bool>> False<T>() { return f => false; } /// <summary> /// This Extension method creates an OR Expression /// </summary> /// <typeparam name="T"></typeparam> /// <param name="expr1"></param> /// <param name="expr2"></param> /// <returns></returns> style="color:#000000;">        public static Expression<Func<T, bool>> Or<T>(this Expression<Func<T, bool>> expr1, Expression<Func<T, bool>> expr2) { // Invoke the second expression, passing in the parameters of the first expression style="color:#000000;">            var invokedExpr = Expression.Invoke(expr2, expr1.Parameters.Cast<Expression>()); // Create the Or Expression, and wrap it in a Lamba expression style="color:#000000;">            return Expression.Lambda<Func<T, bool>> (Expression.Or(expr1.Body, invokedExpr), expr1.Parameters);

} // method Or style="color:#000000;"> /// <summary> /// This Extension method creates an AND expression /// </summary> /// <typeparam name="T"></typeparam> /// <param name="expr1"></param> /// <param name="expr2"></param> /// <returns></returns> style="color:#000000;">        public static Expression<Func<T, bool>> And<T>(this Expression<Func<T, bool>> expr1, Expression<Func<T, bool>> expr2) { // Invoke the second expression, passing in the parameters of the first expression style="color:#000000;">            var invokedExpr = Expression.Invoke(expr2, expr1.Parameters.Cast<Expression>()); // Create the And Expression, and wrap it in a Lamba expression style="color:#000000;">            return Expression.Lambda<Func<T, bool>> (Expression.And(expr1.Body, invokedExpr), expr1.Parameters);

} // method And style="color:#000000;"> } // class PredicateBuilder style="color:#000000;">} //namespace SimpleExpressionTrees

In lines 15 and 16, we have a True and a False static Expression, which can be used an "anchor points" for building an AND or and OR expression chain. The implementations of both the And and the Or methods is very elegant and straightforward. First (in lines 29 and 48), we create an InvocationExpression, passing in the second expression and their parameters. Next, we create a BinaryExpression by performing and And or an Or between the body of our first expression and the InvocationExpression created earlier (lines 32 and 51), and then wrap the result in a Lambda Expression. The above class can be found in the PredicateBuilder.cs class of the sample code.

Based upon this PredicateBuilder class, I created a method in the DynamicQueryWithExpressions class that can build an OR filter chain. The code for this method is shown below:

 1         /// <summary>
 2         /// This method builds up a dynamic expression with OR statements
 3         /// for each number that should be included. It uses the PredicateBuilder
 4         /// to build to expression
 5         /// </summary>
 6         /// <param name="numbersToInclude"></param>
 7         /// <returns></returns>
 8         private Expression<Func<int, bool>> filterByIntList(params int[] numbersToInclude)
 9         {
10             // Since we are building OR statements, we start out with a FALSE expression,
11             // otherwise our OR statement would always evaluate to true..
12             var predicate = PredicateBuilder.False <int> ();
13  
14             // Loop over each number to include, and add an OR predicate
15             // to the expression
16             for (int index = 0 ; index < numbersToInclude.Length; index++)
17             {
18                 int value = numbersToInclude[index];
19                 predicate = predicate.Or(i => i == value);
20             }
21             return predicate;
22 
23         } // method filterByIntList

In line 12, we set our "anchor expression", which should be:

False if we are building an OR filter chain (otherwise our result would always be true).
True is we are building an AND filter chain (otherwise our result would always be false)

We get the arguments to include in the numbersToInclude params array, so we simply need to loop over each element of the array, and invoke the predicate.Or() method with the lambda expression:

i => i == value

as argument. This lamda expression will guarantee that our value is included in the results if it is present in the source array. So, in effect what we are doing during this loop is building and expression which gets more and more complex, and finally includes all values that should be used in the Where clause of our query.

Below is then finally the query which uses this expression:

 1         /// <summary>
 2         /// This method extends our query with dynamic and and or elements
 3         /// </summary>
 4         /// <param name="numbersToFind"></param>
 5         public void QueryWithDynamicParameters(params int[] numbersToInclude)
 6         {
 7             Expression<Func<int, bool>> predicate = filterByIntList(numbersToInclude);
 8             Func<int, bool> isInArray = predicate.Compile();
 9 
10             var results = from value in m_myInts.Where(isInArray)
11                           where value > 5 && value < 15
12                           orderby value
13                           select value;
14 
15             showResults("QueryWithDynamicParameters", results);
16 
17         } // method QueryWithDynamicParameters

in line 7 be invoke our method to create our expression, and in line 8, we compile the expression, which gives us back a lambda expression. Note that we selected to actually apply the lambda expression directly on the m_myInts array, so we can use the power of a "standard, static" where clause together with the power of a dynamically created expression. The application of the Where condition on the array effectively invokes the following extension method of IEnumerable<T>:

 public static IEnumerable<TSource> Where<TSource>(this IEnumerable<TSource> source, Func<TSource, bool> predicate);

The invocation of this method and the results are shown below:

 1             // These examples show how to create a dynamic
 2             // query with an Expression
 3             DynamicQueryWithExpressions dynQuery = new DynamicQueryWithExpressions();
 4             ....
 5             dynQuery.QueryWithDynamicParameters(new int[] { 2, 7, 9, 11, 14, 17 });
 6 
 7 Results from query: QueryWithDynamicParameters
 8         7
 9         9
10         11
11         14

As you see, all supplied values are included except for 2 and 17, because they do not satisfy the "static" where clause.

The above example is very simple, but you can see how you could easily build powerful expression generators with classes like the PredicateBuilder.

Expression Trees and LINQ Query Providers

Besides enabling you to create dynamic queries, expression trees are also used in a "deferred execution" mode in LINQ. For example, in LINQ to SQL, here is the sequence of events:

The user writes a method which contains a LINQ-to-SQL query.
The compiler compiles the SQL-like query into a sequence of method calls.
The compiler then compiles the series of method calls into an expression tree.
The expression trees is used by the LINQ-to-SQL infrastructure to create an optimized T-SQL statement. So, in this case, the expression tree is NEVER directly executed, it is simply used as a rich data structure, from which we can create a Transact-SQL query.
The first time the results of the query are actually accessed, the SQL Statement is sent to the designated SQL server and executed, and the results are returned to the client.

Note that the above description is greatly simplified. The next (and final) installment of this series will dive deep into the bowels of the interfaces and classes that enable all of this to happen. Also, note that this model is not necessarily limited to LINQ-to-SQL. Most (if not all) LINQ providers use an identical model where some type of query is created from the expression tree, and executed when the results of the query are first accessed.

Bennie's Weblog : LINQ, C#