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

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

  1. Print the type of every node of the first tree.
  2. Build n => n + 1 by hand and compile it.
  3. Compile the same tree twice and compare the time of a hundred thousand calls with a lambda written directly.
  4. 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.

  1. 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.

  2. 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.

  3. 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.

  4. What does Compile do?

    Answer

    Turns the tree into a callable delegate

    The compiled delegate is then called like any other.

  5. 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.

  6. Which node reads a property or a field?

    Answer

    MemberExpression

    A query provider maps a member read to a column.

  7. 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.

  8. 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.

  9. 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.

  10. 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