Understanding Expression Trees

Introduction

C# 3.0 came up with many interesting features including Lambda Expressions, field and collection initializers, anonymous types, type interference, and others. One of them is expression trees – mysterious topic tightly coupled with LINQ.

This article will describe in detail what expression trees are. It will also show you how to construct and how to use them in C#. It will end up with answering several important questions about expression trees – what is so special about them? Why and when to use them? And what is the difference between expression trees and Lambda Expressions?

This article assumes that you have at least a decent knowledge about Lambda Expressions, as well as about LINQ (LINQ to Objects especially).

Expression trees definition

In general, Expression Trees are special kind of binary trees. A binary tree is a tree in which all the nodes contain zero, one, or two children. Why have expression trees been implemented as binary trees? Mainly because binary trees allow you to quickly find what you are looking for. The upper limit of steps necessary to find the required information in binary trees equals to log₂N, where N denotes the number of all nodes in a tree.

Let's give the following example careful consideration:

Func<int, int, bool> f = (a, b) => a < b; 

It is a simple declaration of Lambda Expression that takes two numbers as parameters and returns true whenever the first number is less than the second one and false otherwise. Fairly simple. But, we could also write the same logic in an expression tree. What is the difference? Before answering this question, let's take a look at how to create them.

Constructing expression trees

To create an expression tree that refers to the previous example, we have to use the following syntax:

Expression<Func<int, int, bool>> f = (a, b) => a < b; 

Pretty much the same. The only difference is the use of the Expression<T> class. This class is somewhat handy as it contains four interesting properties holding useful information about the underlying expression tree:

1. Body
2. NodeType
3. Parameters
4. Type

Alternatively, you could also build the same expression tree in another way – step by step:

ParameterExpression par1 = Expression.Parameter(typeof(int), "p1"); 
ParameterExpression par2 = Expression.Parameter(typeof(int), "p2"); 
BinaryExpression expr = Expression.LessThan(par1, par2); 
var f = Expression.Lambda<Func<int, int, bool>>(expr, 
                   new ParameterExpression[] { par1, par2 });

Using expression trees

So far, I have shown that constructing expression trees is more difficult and complex than constructing simple Lambda Expressions. So is the way they are used. To use an expression tree, you must first compile it:

var func = f.Compile();

From now on, you can use as any other function:

var result = func(2,5); 

Pretty much overhead, isn't it? Then, why bother yourself about expression trees if the same goals may be achieved using lambda expressions in a simpler and faster way?

Expression trees purpose

In the previous example, I have shown that the given expression tree must be compiled before it can be used. This is because the expression tree is actually a data structure, not compiled code. Why? Because this code is expected to be used across wire, or – in other words – in other processes (running possibly on other computers). For example, a query in LINQ to SQL constructed on my machine will be send to the database server. The server will construct itself a specific expression, run it, and return the requested values. It is much easier for external data providers to construct an appropriate query based on the expression tree (which is the data structure) than based on the compiled piece of code.

This does not apply to LINQ to Objects, however. In this case, your queries will be run in the same process they were called, and there is no need to create any special data structure to represent your query. This is why in LINQ to Objects, Lambda Expressions may be used. In all other cases, you must rely on expression trees.

Summary

Expression trees are a very interesting concept. At the beginning, it might seem that they simply double up the functionality offered by Lambda Expressions. The difference is noticeable, however, when different kinds of LINQ than LINQ to Objects are used. In such cases, your queries will be send across wire and run in different processes and possibly on different machines. It is a cool idea that makes such scenarios possible, and is very easy and straightforward.