B# .NET Blog

Welcome back to the Visual Basic 9.0 Feature Focus blog series. In this post, we'll cover Expression Trees, a feature also available in C# 3.0 (see here). In the previous post of this series we did take a closer look at lambda expressions; expression trees are very closely related to lambda expressions. Simply stated, an expression tree is a data representation of lambda expression. Consider the following sample:

Dim square As Func(Of Integer, Integer) = Function(i) i * i

Note: Using Implicitly Typed Local Variables you can omit even the Func(Of Integer, Integer) part in the code fragment above. The compiler will create an anonymous delegate to represent the type of the function.

This is a very simple lambda expression that takes in an integer 'i' and produces its square value 'i * i'. So, to put a list of squares on the screen, you can write the following:

For i = 1 To 10
    Console.WriteLine("{0}² = {1}", i, square(i))
Next

As you can see, the square function can be called directly, like any other regular delegate can be called using plain simple method call syntax. In other words, the function has been fully compiled to IL code that can be executed directly at runtime. But what if we'd like to analyze the function expression at runtime? This is much more complicated but believe me there are various scenarios where this proves useful (one of which being LINQ query providers that translate expressions into some target query domain language, e.g. SQL in LINQ to SQL). Essentially, we want the compiler to translate the function from the sample above into something like this:

Read this tree from top to bottom: we're talking about a lambda expression that has one parameter called 'i' (left-hand side of the tree) and which has a body that produces the product (*) of 'i' and 'i' (leaf level). How can we have the compiler build this instead of regular IL-code for the function? The answer is by using the System.Linq.Expressions.Expression class, like this:

Dim square As Expression(Of Func(Of Integer, Integer)) = Function(i) i * i

Now the code fragment to produce squares won't work anymore, since square is an expression tree now:

Basically, whenever you assign a lambda expression to something of type Expression(Of T), either directly in a local variable or indirectly by calling a method that takes an Expression(Of T) as its argument, the compiler will produce an expression tree rather than an anonymous method for the lambda function. As a simple (!) example, consider a dynamic calculator below, which parses an expression at runtime in order to carry out the right calculation:

Imports System.Linq.Expressions

Module Demo

    Function Calc(ByVal f As Expression(Of Func(Of Integer, Integer)), ByVal i As Integer)
        If TypeOf f Is LambdaExpression Then
            Dim l = CType(f, LambdaExpression)
            If l.Parameters.Count <> 1 Then
                Throw New InvalidOperationException("Invalid number of parameters")
            End If

            Dim p = l.Parameters(0)
            If TypeOf l.Body Is BinaryExpression Then
                Dim b = CType(l.Body, BinaryExpression)

                Dim left = GetValue(b.Left, p, i)
                Dim right = GetValue(b.Right, p, i)

                Select Case b.NodeType
                    Case ExpressionType.Add, ExpressionType.AddChecked
                        Return left + right
                    Case ExpressionType.Subtract, ExpressionType.SubtractChecked
                        Return left - right
                    Case ExpressionType.Multiply, ExpressionType.MultiplyChecked
                        Return left * right
                    Case ExpressionType.Divide
                        Return left / right
                    Case ExpressionType.Modulo
                        Return left Mod right
                    Case Else
                        Throw New InvalidOperationException("Unsupported mathematical operator")
                End Select
            Else
                Throw New InvalidOperationException("Expected binary expression in function")
            End If
        Else
            Throw New InvalidOperationException("Invalid function expression")
        End If
    End Function

    Function GetValue(ByVal e As Expression, ByVal p As ParameterExpression, ByVal i As Integer) As Integer
        If e Is p Then
            Return i
        Else
            If TypeOf e Is ConstantExpression Then
                Return CType(e, ConstantExpression).Value
            Else
                Throw New InvalidOperationException("Function should only contain the function parameter or a constant value")
            End If
        End If
    End Function

    Sub Main()
        For i = 1 To 10
            Console.WriteLine("{0}² = {1}", i, Calc(Function(x) x * x, i))
        Next
    End Sub

End Module

It's a simple example because the parser is not very smart. It can just cope with simple "binary expressions" that have leafs which are either the lambda's parameter expression or a constant value. To build a really good dynamic calculator, you'll have to do much more (including the use of recursive parsing). However, it's a pretty good sample. Start by taking a look at the Main function which makes a call to Calc, passing in a lambda expression "Function(x) x * x". The reason for using 'x' is that 'i' is already in scope, but that doesn't change any meaning since it's just a dummy variable name (for math folks, that's the equivalent to α conversions in formal lambda calculus). Since the Calc method has an Expression(Of ...) as its first parameter, the compiler knows to translate the lambda to an expression tree instead of compiling it to final IL code. The Calc method itself inspects the expression tree to find out about its meaning and dynamically (at runtime) constructs the right result value. If you want to understand how it really works, debug the code above and step through the code. Also try to execute other lambdas like:

Function(x) x * 2
Function(x) x + 1
Function(x) 1 + 1
Function(x) x Mod 2

All of these should work fine.

In case you wonder where expression trees are used on an everyday basis, the answer is LINQ (to SQL for instance). If the following query is a LINQ to SQL one:

Dim res = From p In products Where p.Price > 100 Select New With { .Name = p.ProductName, p.Price }

this will get translated (lexically) into the following using extension methods (on an interface called IQueryable(Of T)) and lambdas:

Dim res = products.Where(Function(p) p.Price > 100).Select(Function(p) New With { .Name = p.ProductName, p.Price })

which is on its turn translated into:

Dim res = Queryable.Select(Queryable.Where(products, Function(p) p.Price > 100)), Function(p) New With { .Name = p.ProductName, p.Price });

These extension methods take in lambdas as Expression(Of T) objects, causing the compiler to translate them in expression trees. For instance, Function(p) p.Price > 100 becomes:

• LambdaExpression
• Parameters = { p }
• Body = BinaryExpression
• NodeType = GreaterThan
• Left = MemberExpression
• Property = Product.Price
• Right = ConstantExpression
• Value = 100

At runtime, these expression trees are parsed by the LINQ to SQL engine to translate it into the appropriate SQL fragment, for example for the total query above:

SELECT p.[ProductName] AS [ Name], p.[Price] FROM dbo.Products WHERE p.[Price] > 100

This query is sent to the server, results are fetched and the code can iterate over the produced results.

Happy coding!