Using the DLR to build Expression Trees

What Will I Learn?

How to use the DLR to build Expression Trees

Requirements

• .NET Framework

Difficulty

Intermediate

Tutorial Contents

• Code Generation Code
• Typical Expression Tree Building Syntax
• The .NET DLR and Expression Trees
• Implementing an IDynamicMetaObjectProvider
• Implementing a DynamicMetaObject subclass
• How does this work at runtime?
• Setting members
• ParameterExpressions and LambdaExpressions

Code Generation Code

With the introduction of LINQ Expressions, generating code from a .NET application became much less cumbersome and error-prone. Instead of using Reflection.Emit to generate individual CLR instructions, an application now builds a tree of expressions much like the syntax tree used by a typical compiler, and then calls a simple Compile method on the final tree to generate a dynamic function or to populate a MethodBuilder. Expression trees form a Turing Complete language, meaning that an expression tree can be used to generate the equivalent of any C# function.

Typical Expression Tree Building Syntax

While code that builds expression trees is more readable than code that uses Reflection.Emit directly, it is still a bit noisy when used to generate significant bodies of code. Building an expression tree that uses methods, fields, or properties requires those members to be referenced with MemberInfo objects or with strings. Literal values used in an expression tree must be wrapped in ConstantExpression instances. The Expression building API does not include any operator overloading, so building up arithmetic expressions requires a function call to build each step. 

// Generates an expression for: param1.Prop1.Length

Expression result = Expression.PropertyOrField(

    Expression.PropertyOrField(expParam1, "Prop1"), "Length");

The .NET DLR and Expression Trees

.NET introduces the Dynamic Language Runtime (DLR). It allows programmers to define and use "dynamic types"; that is, types that can have members added and removed at runtime. When using such a type, the validity and definition of members will be evaluated at runtime. Naturally, this imposes a substantial performance penalty compared to using members of a regular type, but it does allow the decision of which members a given type supports to be postponed until runtime.There are three basic flavors of dynamic objects, defined by three types that live in the System.Dynamic namespace:

• ExpandoObject: This type is not inheritable, and by implementing IDictionary<string,object> it allows members to be added and removed on-the-fly.
• DynamicObject: An abstract base class with overridable members through which the DLR requests runtime member definitions.
• IDynamicMetaObjectProvider: An interface through which the DLR requests instances of DynamicMetaObject, which itself has overridable members through which the DLR requests runtime member expressions.

ExpandoObject and DynamicObject are both implemented behind-the-scenes using IDynamicMetaObjectProvider, which is the lowest level at which a programmer can implement a dynamic object.

Implementing an IDynamicMetaObjectProvider

For our expression tree building library, we will define implementations of IDynamicMetaObjectProvider. As noted above, an IDynamicMetaObjectProvider must produce instances of DynamicMetaObject subclasses, and those DynamicMetaObject subclass instances must then respond to DLR requests in order to allow the overall dynamic type to be used. The IDynamicMetaObjectProvider implementation itself is relatively simple: 

public CGValue : IDynamicMetaObjectProvider

{

    public Expression Expr {get; private set;}

    public CGValue(Expression expr)

    {

        Expr = expr;

    }

    // Implicit wrapping and unwrapping

    public static implicit operator Expression(CGValue v)

    {

        return v.Expr;

    }

    public static implicit operator CGValue(Expression x)

    {

        return new CGValue(x);

    }

    // Implementation of IDynamicMetaObjectProvider.GetMetaObject

    public DynamicMetaObject GetMetaObject(Expression parameter)

    {

        // For "parameter", the DLR passes a LINQ expression representing

        // this CGValue instance.

        return new CGValueMetaObject(parameter, BindingRestrictions.Empty, this);

    }

    // ...

Here, CGValue is a wrapper for a System.Linq.Expression instance that implements IDynamicMetaObjectProvider. The DLR doesn't provide a way to directly turn a regular class into a dynamic class (although it will happily let you use regular classes as if they were dynamic, while rejecting any attempts to add members to them), so we have to define our own class to wrap it.

Implementing a DynamicMetaObject subclass

The DynamicMetaObject subclass, however, is much more involved. Each of the overridable member-getting operations must return not a member, but another DynamicMetaObject containing an Expression tree representing the member's value (which in our case is itself an Expression tree). In our case, that means we will be building expression trees that represent expression tree building code. In other words, in our DynamicMetaObject method overrides, we are writing code that generates code that generates code.For instance, our override of BindGetMember must build an expression tree that represents a direct or indirect call to Expression.PropertyOrField. Here we'll add a method to CGValue that simply calls Expression.PropertyOrField with the wrapped Expression instance:

Listing 1: CGValue.Get 

public CGValue Get(string name)

{

    return Expression.PropertyOrField(this.Expr, name);

}

and have the tree built by BindGetMember represent a call to CGValue.Get:

Listing 2: CGValueMetaObject.BindGetMember 

public override DynamicMetaObject BindGetMember(GetMemberBinder binder)

{

    // DynamicMetaObject.Expression is a LINQ expression representing the

    // dynamic object instance (the CGValue instance).  But its declared type

    // is Object; we need to cast it to CGValue before we can call anything

    // on it. 

    Expression instanceExprExpr = Expression.Convert(Expression, LimitType);



    // Build an expression representing a call to CGValue.Get 

    Expression memberExprExpr = Expression.Call(instanceExprExpr, "Get", null,

    Expression.Constant(binder.Name));



    // Package it up in a new DynamicMetaObject

    // NOTE: The binding restriction parameter pertains to the dynamic object whose

    // member is being accessed, not the dynamic object resulting from the member

    // access.  So as a general rule, just pass through the binding restrictions

    // for this DynamicMetaObject instance, which matches the dynamic object whose

    // member is being accessed.

    return new DynamicMetaObject(memberExprExpr, BindingRestrictions.GetTypeRestriction(Expression, LimitType));

}

By doing it that way, we don't have to include code to build expression tree nodes to extract the Expression instance from the CGValue instance.With this in place, we can replace this application code to build a member access expression: 

// Assume TestInstance has a String 



property named Prop1

Expression expTestInstance = ...;

// result becomes an Expression representing TestInstance.Prop1

Expression result = Expression.PropertyOrField(expTestInstance, "Prop1");

with this code that uses our new CGValue wrapper to do the same thing: 

// Assume TestInstance has a String property named Prop1

// expTestInstance is a CGValue

dynamic expTestInstance = ...;

// result becomes a CGValue wrapping an Expression representing TestInstance.Prop1

dynamic result = expTestInstance.Prop1;

So how does this work at runtime?

At runtime, when expTestInstance.Prop1 is evaluated:

1. The DLR calls IDynamicMetaObjectProvider.GetMetaObject on the dynamic object instance (expTestInstance) and gets a DynamicMetaObject instance (in this case a CGValueMetaObject instance)
2. The DLR calls DynamicMetaObject.BindGetMember on the DynamicMetaObject instance it got in step 1. It gets back another DynamicMetaObject instance.
3. It pulls the expression tree from the DynamicMetaObject instance it got in step 2.
4. The expression tree is executed, and the result (in this case, a CGValue instance wrapping an Expression representing the member Prop1 of TestClass1) becomes the runtime-evaluated value of expTestInstance.Prop1.

This can be chained any number of times: 

// Now result becomes a 



CGValue wrapping an expression representing

// TestInstance.Prop1.Length

dynamic result = expTestInstance.Prop1.Length;

Here, expTestInstance.Prop1 is evaluated as above, and the result has the member "Length" accessed. The DLR simply repeats the process, calling IDynamicMetaObjectProvider.GetMetaObject on expTestInstance.Prop1, calling BindGetMember on the returned DynamicMetaObject, executing the expression tree contained in that returned DynamicMetaObject, and using the result as the runtime-evaluated value of the Length property, which in this case is a CGValue instance wrapping an Expression representing the member Length of System.String.

Setting members

A set member operation uses BindSetMember. When we return a DynamicMetaObject, the expression tree it contains needs to evaluate to a CGValue wrapping the result of calling Expression.Assign. That way, we can take the assignment expression and include it in a BlockExpression so we can execute it and code that depends on it: 

Expression[] statements = new Expression[] 

{

    // The whole set expression here needs to evaluate to an AssignExpression so 

    // that the assignment will run as part of the block.



    expTestInstance.Prop1 = expNewStringValue,



    // expressions to use the updated test instance

    // ...

};

Expression block = Expression.Block(statements);

This is the reason we needed to implement an IDynamicMetaObjectProvider. When using either of the other two methods of defining dynamic objects, you cannot make the member set operation evaluate to anything other than the runtime value being assigned to that member. In this case, we need for the member set expression to not evaluate to the expression on the right, but instead evaluate to an assignment expression derived from it:

Listing 3: CGValue.Set 

public CGValue Set(String name, Expression xval)

{

    Expression member = Get(name);

    return Expression.Assign(member, xval);

}

Listing 4: CGValueMetaObject.BindSetMember 

public override DynamicMetaObject BindSetMember(SetMemberBinder binder, 



DynamicMetaObject value)

{

    // Expression representing the CGValue instance whose member is being set

    Expression instanceExprExpr = Expression.Convert(Expression, LimitType);



    // Expression representing a call to CGValue.Set with the member name

    // and a CGValue wrapping an Expression representing the value to assign

    // to the member.  CGValue.Set will return an expression representing

    // the assignment.

    Expression assignExprExpr = Expression.Call(instanceExprExpr, "Set", null,

    Expression.Constant(binder.Name),value.Expression);



    // Package up the result

    return new DynamicMetaObject(assignExprExpr, BindingRestrictions.GetTypeRestriction(Expression, LimitType));

}

ParameterExpressions and LambdaExpressions

Our CGValue class can be used to build expression trees, but it doesn't help you define lambda parameters to be used in it. We still need to call Expression.Parameter for each one to get parameters to be fed to the dynamic expression builders we defined above and to Expression.Lambda to get a lambda expression that can be turned into a delegate and executed.To simplify this, let's define a CGFunc class. It will wrap a set of parameters, a set of variables, and a set of LINQ expressions, all of which will be used to construct a lambda expression. Since we're defining CGFunc as another implementation of IDynamicMetaObjectProvider, we get to choose the set of members it exposes at runtime. In this case, we'll have one named member for each lambda parameter and each internal variable we define. That way, client code can go like this:

Type arg0Type = ...;

Type arg1Type = ...;

// Create a function that returns the Length property of the Prop1 property of

// the argument.  Note that the only requirement for this part to work is that 

// arg0Type have a Prop1 property whose declared type has a Length property,

// and arg0Type also have a Prop2 property assignable from type arg1Type.

// So long as those requirements are met, arg0Type does not have to be, or 

// derive from, any particular named type.  Since 'lambda' represents ordinary 

// early-bound .NET code without any DLR overheads, we get this type flexibility

// without adding any runtime overhead to 'lambda'.

dynamic fn = new CGFunc(arg0Type, "arg0", arg1Type, "arg1");

fn.Eval(

    fn.arg0.Prop2 = arg1,

    // etc.

    // ...

    // Last expression in the body of a lambda becomes the lambda's return value.

    fn.arg0.Prop1.Length);LambdaExpression lambda = fn.CreateLambda();



    // Now we can create a delegate from 'lambda' or populate a MethodBuilder with it.

    // ...

To make that happen, we'll make CGFunc expose public methods to create expressions that get and set arguments and variables, a method to add Expressions to an internal list, and of course an implementation of IDynamicMetaObjectProvider that returns a CGFuncMetaObject:

Listing 5: CGFunc 

public class CGFunc : IDynamicMetaObjectProvider

{

    // Mapping from name to the corresponding ParameterExpression

    public IDictionary<string, parameterexpression> ParameterMap { get; private set; }

    // Ordered list of ParameterExpression representing the arguments

    public IList<parameterexpression> Parameters { get; private set; }

    // Ordered list of ParameterExpressions representing local variables

    public IList<parameterexpression> Variables { get; private set; }

    // The expressions making up the body of the resulting function

    List<expression> _members = new List<expression>();

    // This is only run only at construction time

    private void Init()

    {

        ParameterMap = new Dictionary<string, parameterexpression>();

        Parameters = new List<parameterexpression>();

        Variables = new List<parameterexpression>();

    }

    // Constructors for various numbers of parameters

    public CGFunc()

    {

        Init();

    }

    public CGFunc(Type pt0, String pn0)

    {

        Init();

        AddParam(pt0, pn0);

    }

    public CGFunc(Type pt0, String pn0, Type pt1, String pn1)

    {

        Init();

        AddParam(pt0, pn0);

        AddParam(pt1, pn1);

    }

    // Implementation of IDynamicMetaObjectProvider.GetMetaObject

    public DynamicMetaObject GetMetaObject(System.Linq.Expressions.Expression parameter)

    {

        return new CGFuncMetaObject(parameter, this);

    }

    // Adds a parameter.

    public void AddParam(Type pt, String pn)

    {

        var p = Expression.Parameter(pt, pn);

        Parameters.Add(p);

        ParameterMap[pn] = p;

    }

    // Adds a local variable

    public void Var(Type vt, String vn)

    {

        var p = Expression.Parameter(vt, vn);

        Variables.Add(p);

        ParameterMap[vn] = p;

    }

    // Gets a CGValue whose Expr represents the named argument or variable

    public CGValue Get(String name)

    {

        return ParameterMap[name];

    }

    // Gets a CGValue whose Expr represents an assignment to the named

    // argument or variable

    public CGValue Set(String name, Expression xval)

    {

        ParameterExpression p;

        // This part creates the variable if it didn't previously exist.

        // If that's not the behavior you want, skip this whole if block.

        if (!ParameterMap.TryGetValue(name, out p))

        {

            p = Expression.Parameter(xval.Type, name);

            Variables.Add(p);

            ParameterMap[name] = p;

        }

        return Expression.Assign(p, xval);

    }

    // Adds expressions to the body of the function

    public void Eval(params Expression[] instrs)

    {

        _members.AddRange(instrs);

    }

    // Call this to create a LambdaExpression after you are done

    // adding statements.

    public LambdaExpression CreateLambda()

    {

        return Expression.Lambda(

            Expression.Block(Variables, _members), Parameters);

    }

}

The CGFuncMetaObject only needs definitions for BindGetMember and BindSetMember, since we only need to intercept get and set operations on the CGFunc instance to make them evaluate to the corresponding named argument or variable:

Listing 6: CGFuncMetaObject 

public class CGFuncMetaObject : DynamicMetaObject

{

    public CGFuncMetaObject(Expression parameter, object value)

        : base(parameter, BindingRestrictions.Empty, value)

    {

    }

    public override DynamicMetaObject BindGetMember(GetMemberBinder binder)

    {

        // Build Expression representing this CGFunc instance

        Expression fnExp = Expression.Convert(Expression, LimitType);

        // Build Expression representing a call to CGFunc.Get

        Expression getResult = Expression.Call(fnExp, "Get", null, Expression.Constant(binder.Name));

        // Package up the result

        return new DynamicMetaObject(getResult, BindingRestrictions.GetTypeRestriction(Expression, LimitType));

    }

    public override DynamicMetaObject BindSetMember(SetMemberBinder binder, DynamicMetaObject value)

    {

        // Build Expression representing this CGFunc instance

        Expression fnExp = Expression.Convert(Expression, LimitType);

        // Build Expression representing a call to CGFunc.Set

        // CGFunc.Set will return an expression representing the assignment to

        // the argument or local variable.

        Expression setResult = Expression.Call(fnExp, "Set", null,

            Expression.Constant(binder.Name),

            value.Expression);

        // Package up the result

        return new DynamicMetaObject(setResult, BindingRestrictions.GetTypeRestriction(Expression, LimitType));

    }

}

What about BindInvokeMember? Aren't we calling methods on CGFunc in our client code? Yes, but the default implementation of each overridable method on DynamicMetaObject uses reflection on the corresponding dynamic object instance to find the corresponding member definition of its runtime type. That means that the default implementation of BindInvokeMember uses reflection to get the corresponding method of CGFunc and uses that in the expression it builds. That lets calls to methods defined directly on CGFunc to do what one would normally expect; that's the behavior we want, so we don't override it.

Summary

While the DLR offers flexibility and a convenient syntax, it comes at a run-time cost. However, in this case, the DLR's run-time cost happens while generating code; the final generated code is ordinary non-DLR .NET code, meaning we get many of the benefits of the DLR without the runtime cost usually associated with it.In my next article, I'll extend CGValue to support method calls, operators (such as +, -, etc.), and so on, and introduce a new dynamic class to support building expressions to represent static member and constructor usage. I'll also add support for implicit conversions from literals to ConstantExpressions so you can write code like: 

cgfunc.Eval(

    // ...,

    expTestInstance.Prop1 = "Blah blah",

    // ...

);

instead of: 

cgfunc.Eval(

    // ...,

    expTestInstance.Prop1 = new CGValue(Expression.Constant("Blah blah"));

    // ...

);

 

---

Posted on Utopian.io - Rewarding Open Source Contributors

---