Expression trees
A lambda is code; an Expression<Func<...>> is a data structure that describes code. The compiler turns the lambda into a tree of nodes instead of a delegate, and a program can read the tree, change it, translate it to SQL or compile it back into a delegate. LINQ to SQL and Entity Framework are built on this: the query is an expression tree that the provider reads.
An expression as data
The same lambda assigned to a Func and to an Expression produces different things: a delegate, or a tree that can be printed:
using System.Linq.Expressions;
Expression<Func<int, int>> square = x => x * x;
Console.WriteLine($"body {square.Body}");
Console.WriteLine($"node {square.Body.NodeType}");
Console.WriteLine($"param {square.Parameters[0].Name}");
Console.WriteLine($"text {square}");
var compiled = square.Compile();
Console.WriteLine($"compiled {compiled(5)}");
dotnet run
body (x * x)
node Multiply
param x
text x => (x * x)
compiled 25
The body is a BinaryExpression whose node type is Multiply, and the parameter kept its name x. Printing the expression gives the lambda back in a canonical form with the parentheses the tree implies. Nothing ran until Compile, which built a delegate and produced 25.
The nodes of a tree
- ParameterExpression is a variable of the lambda.
- ConstantExpression is a literal, and BinaryExpression is an operation on two others.
- MethodCallExpression is a call, which is how a provider turns s.Name.StartsWith("A") into an LIKE.
- MemberExpression is a property or field read, the node a query provider maps to a column.
- Every node has a NodeType and a Type, and the tree is immutable: a change builds a new tree.
Building one by hand
The factory methods of Expression build a tree without a lambda in the source. The program makes n => n * 3 node by node:
using System.Linq.Expressions;
var parameter = Expression.Parameter(typeof(int), "n");
var body = Expression.Multiply(parameter, Expression.Constant(3));
var triple = Expression.Lambda<Func<int, int>>(body, parameter).Compile();
Console.WriteLine($"triple {triple(4)}");
Console.WriteLine($"body {body}");
dotnet run
triple 12
body (n * 3)
A parameter, a constant and one operation made a delegate that multiplies by three. A provider builds trees like this from a query a user typed, which is the mechanism behind a dynamic filter or a rule engine. The type of every node has to match what the operation expects, and a mismatch throws ArgumentException when the node is built.
Compiling it
Compile turns a tree into a delegate and costs a little; the delegate is then as fast as one written by hand. A predicate compiled once is a filter that a program can build at run time:
using System.Linq.Expressions;
Expression<Func<int, bool>> isEven = n => n % 2 == 0;
var compiled = isEven.Compile();
var numbers = Enumerable.Range(1, 6).Where(compiled);
Console.WriteLine(string.Join(",", numbers));
Console.WriteLine(isEven.Body.NodeType);
dotnet run
2,4,6
Equal
The filter kept the three even numbers, and the body of the predicate is an Equal node because the comparison is the outermost operation. Where accepted the compiled delegate directly; the source of the query was an ordinary array, and the tree was only the predicate. A database provider never calls Compile: it reads the tree and writes SQL, which is why a method the provider does not know throws at query time instead of running on the client.
Exercises
- Print the type of every node of the first tree.
- Build n => n + 1 by hand and compile it.
- Compile the same tree twice and compare the time of a hundred thousand calls with a lambda written directly.
- Use a MethodCallExpression to call string.ToUpper on a parameter and print the tree.
Questions
A new set of questions in a new order every time. Choose one answer for each, then check.
-
What is an Expression<Func<int, int>>?
Answer
A tree of nodes that describes a function
The compiler writes the tree instead of a delegate when the target is an Expression.
-
What does the Body property of an expression hold?
Answer
The outermost node of the lambda
For x => x * x it is the Multiply node.
-
What does this program print?
using System.Linq.Expressions; Expression<Func<int, int>> square = x => x * x; Console.WriteLine(square.Body.NodeType);Answer
Multiply
The body is the multiplication, as the measured run printed.
-
What does Compile do?
Answer
Turns the tree into a callable delegate
The compiled delegate is then called like any other.
-
What does this program print?
using System.Linq.Expressions; Expression<Func<int, int>> square = x => x * x; var compiled = square.Compile(); Console.WriteLine(compiled(5));Answer
25
Five squared is twenty-five, the measured result.
-
Which node reads a property or a field?
Answer
MemberExpression
A query provider maps a member read to a column.
-
What does this program print?
using System.Linq.Expressions; var parameter = Expression.Parameter(typeof(int), "n"); var body = Expression.Multiply(parameter, Expression.Constant(3)); var triple = Expression.Lambda<Func<int, int>>(body, parameter).Compile(); Console.WriteLine(triple(4));Answer
12
Four times three is twelve.
-
What does this program print?
using System.Linq.Expressions; Expression<Func<int, bool>> isEven = n => n % 2 == 0; var compiled = isEven.Compile(); Console.WriteLine(string.Join(",", Enumerable.Range(1, 6).Where(compiled)));Answer
2,4,6
The predicate keeps the even numbers.
-
What is the NodeType of the body of n => n % 2 == 0?
Answer
Equal
The comparison is the outermost operation, as the measured line showed.
-
Why does a database provider read the tree instead of compiling it?
Answer
It translates the nodes into SQL that the database runs
The query must run in the database, so the provider needs the structure, not a delegate.
The code on this page was built with the .NET SDK 10.0.303 and run on Alpine Linux 3.24.3 (x86_64) in a Docker container.
Article author: Arthur Isaev