Get a Grasp on Expression Trees

Developers familiar with functional programming languages might not need an explanation as to why expression trees are useful. For the rest of us expression trees are the most striking concept of all the new features in C# 3.0 or VB 9.0.

Charlie Calvert explains the Expression Tree Basics. He starts by describing the syntax and shows how to visualize expression trees with the help of the ExpressionTreeVisualizer that ships with the Visual Studio 2008 samples.

Expression trees are related to lambda expressions, which are the logical next step in the line of delegates and anonymous delegates.  In his article on expression trees Ian Griffiths gives a great introduction to lambda expressions and their relation to expression trees. As Ian points out "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":

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

[...]

The second line is more interesting. This takes that Func delegate, and uses it as the type parameter for a generic type called Expression. 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 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.

Charlie delves into the Expression details:

There are four properties in the Expression<TDelegate> class:

• Body: Retrieve the body of the expression.
• Parameters: Retrieve the parameters of the lambda expression.
• NodeType: Gets the ExpressionType for some node in the tree. This is an enumeration of 45 different values, representing all the different possible types of expression nodes, such as those that return constants, those that return parameters, those that decide whether one value is less than another (<), those that decide if one is greater than another (>), those that add values together (+), etc.
• Type: Gets the static type of the expression. In this case, the expression is of type Func<int, int, int>.

As almost all of the new features in C# 3.0 and VB 9.0 expression trees play a key role in "LINQ, and particularly in LINQ to SQL":

var query = from c in db.Customers
            where c.City == "Nantes"
            select new { c.City, c.CompanyName };

LINQ expressions return an IQueryable. IQueryable contains an expression tree, which represents the LINQ query. At the moment the query is created, no SQL statement is issued to the database. The SQL statement is created and executed when your code iterates the IQueryable object. This concept is called deferred execution.

Charlie Calvert explains the use of this approach:

Because the query comes to the compiler encapsulated in such an abstract data structure, the compiler is free to interpret it in almost any way it wants. It is not forced to execute the query in a particular order, or in a particular way. Instead, it can analyze the expression tree, discover what you want done, and then decide how to do it. At least in theory, it has the freedom to consider any number of factors, such as the current network traffic, the load on the database, the current results sets it has available, etc. In practice LINQ to SQL does not consider all these factors, but it is free in theory to do pretty much what it wants. Furthermore, one could pass this expression tree to some custom code you write by hand which could analyze it and translate it into something very different from what is produced by LINQ to SQL.

Marlon Grech shows how to work with expression trees and create an expression parser.  A summary of the expression tree expressions class hierarchy is provided by Octavio Hernández.