Tuesday, August 26, 2008 10:40 PM bart

To Bind or Not To Bind – Dynamic Expression Trees – Part 1

In the previous post, I outlined the use of the expression trees from the System.Linq.Expressions namespace. Let’s recap to set the scene:

Expression<Func<string, int, int, string>> data = (string s, int a, int b) => s.Substring(a, b);

produces (deep breadth)

ParameterExpression s = Expression.Parameter(typeof(string), “s”);
ParameterExpression a = Expression.Parameter(typeof(int), “a”);
ParameterExpression b = Expression.Parameter(typeof(int), “b”);

Expression<Func<string, int, int, string>> data = Expression.Lambda<Func<string, int, int, string>>(
    Expression.Call(s, typeof(string).GetMethod(“Substring”, new Type[] { typeof(int), typeof(int) }), a, b),
    s, a, b
);

Func<string, int, int, string> fun = data.Compile();
Console.WriteLine(fun(“Bart”, 1, 2));

where I’ve indicated all the strong typing using underlines. Wow, that’s a lot dude! Based on all of this strong typing, there are little or no runtime surprises possible concerning running the right method (unless a MissingMethodException occurs for some reason). Obviously, expression trees could be much more complex but to illustrate the core points of the type system, we’ll restrict ourselves to parameters, method calls and lambdas.

So what do we want to try now? We want to design an API similar to the one used above but without all this type information. Essentially, it would look like:

ParameterExpression s = Expression.Parameter(“s”);
ParameterExpression a = Expression.Parameter(“a”);
ParameterExpression b = Expression.Parameter(“b”);

LambdaExpression data = Expression.Lambda(
    Expression.Call(s, “Substring”, a, b),
    s, a, b
);

Delegate fun = data.Compile();
Console.WriteLine(fun.DynamicInvoke(“Bart”, 1, 2));

and all of a sudden we see the dynamic aspect lurking around the corner on the very last line where we call through the weakly-typed delegate passing in three objects which just happen to be a string and two ints, causing the lookup for a Substring method applied to s (becoming “Bart”) with arguments a and b (respectively 1 and 2) to succeed. The important thing here though is that a “Substring” method with a compatible signature might be available on another type, maybe type Bar, but taking in two longs:

class Bar
{
    public Foo Substring(long a, long b) { … }
}

The calling code would still work and the console would print the result of Foo.ToString on the instance returned by Bar.Substring. What it takes to make this work consists of three things:

  • Dynamic expression trees (i.e. as the one above with stripped type information);
  • IL code generation at runtime on the fly (to produce the delegate “fun” in the sample above)
  • Binders (things that provide runtime support to resolve method calls)

Of course you could go much further than this with complete ASTs (the big brothers to expression trees) and “rules” but we’re not going to reinvent the DLR :-). Martin Maly has quite some information on those topics on his blog (must-reads!). Today we’ll cover the first bullet point.

 

Our dynamic expression trees

To disambiguate with the LINQ expression trees, let’s sneak the word Dynamic in, making our sample look like:

ParameterDynamicExpression s = DynamicExpression.Parameter(“s”);
ParameterDynamicExpression a = DynamicExpression.Parameter(“a”);
ParameterDynamicExpression b = DynamicExpression.Parameter(“b”);

LambdaDynamicExpression data = DynamicExpression.Lambda(
    DynamicExpression.Call(s, “Substring”, a, b),
    s, a, b
);

Delegate fun = data.Compile();
Console.WriteLine(fun.DynamicInvoke(“Bart”, 1, 2));

All of those *DynamicExpression classes extend the DynamicExpression base class while having a factory method on DynamicExpression too, following the design of LINQ’s expression trees. We’ll omit the NodeType property for simplicity and the Type property, because we obviously don’t want a static type to be associated with each expression tree node. We’ll also get rid of a lot of node types, just leaving the factories in for our three node types:

image

So, how does this look like? The factory methods will be just convenient syntax around internal constructor calls producing the concrete node types. In addition, we’ll override ToString to produce a friendly-on-the-eye string representation of expression trees, much like our static LINQ friends. First, the DynamicExpression base class:

abstract class DynamicExpression
{
    public static ParameterDynamicExpression Parameter(string name)
    {
        return new ParameterDynamicExpression(name);
    }

    public static MethodCallDynamicExpression Call(DynamicExpression instance, string method, params DynamicExpression[] arguments)
    {
        return new MethodCallDynamicExpression(instance, method, arguments);
    }

    public static LambdaDynamicExpression Lambda(DynamicExpression body, params ParameterDynamicExpression[] parameters)
    {
        return new LambdaDynamicExpression(body, parameters);
    }
    protected internal abstract void ToString(StringBuilder sb);

    public override string ToString()
    {
        StringBuilder sb = new StringBuilder();
        ToString(sb);
        return sb.ToString();
    }
}

We’ll extend this class a bit more in the next part where we’ll tackle compilation, but let’s move on to each of the three subtypes right now:

sealed class ParameterDynamicExpression : DynamicExpression
{
    internal ParameterDynamicExpression(string name)
    {
        Name = name;
    }

    public string Name { get; private set; }

    protected internal override void ToString(StringBuilder sb)
    {
        sb.Append(Name);
    }
}

Nothing surprising here. The expression for a dynamic method call is a slightly bit more complicated :-)…

sealed class MethodCallDynamicExpression : DynamicExpression
{
    internal MethodCallDynamicExpression(DynamicExpression instance, string method, params DynamicExpression[] arguments)
    {
        Object = instance;
        Method = method;
        Arguments = new ReadOnlyCollection<DynamicExpression>(arguments);
    }

    public ReadOnlyCollection<DynamicExpression> Arguments { get; private set; }
    public DynamicExpression Object { get; private set; }
    public string Method { get; private set; }
    protected internal override void ToString(StringBuilder sb)
    {
        Object.ToString(sb);
        sb.Append(".");
        sb.Append(Method);
        sb.Append("(");

        int n = Arguments.Count;
        for (int i = 0; i < n; i++)
        {
            Arguments[i].ToString(sb);
            if (i != n - 1)
                sb.Append(", ");
        }

        sb.Append(")");
    }
}

I told’ya it was going to be mind-blowing. The core thing to notice though is the composability because of the use of DynamicExpressions as the Object (i.e. the instance where we’ll invoke the method on) and the Arguments collection members. Also notice we don’t support static method calls in here (for which Object would be null – you can envision the right checking in the factory method, omitted for brevity) although it would be perfectly possible to come up with such a thing (think about “global functions” for example, but remember we don’t have a type that tells us where to look for the method – ideally you’d have a mixture of statically and dynamically typed trees interwoven). Oh, and the pretty printing logic in ToString isn’t too complex either…

Finally, let’s move on to the lambda expression class:

sealed class LambdaDynamicExpression : DynamicExpression
{
    internal LambdaDynamicExpression(DynamicExpression body, params ParameterDynamicExpression[] parameters)
    {
        Body = body;
        Parameters = new ReadOnlyCollection<ParameterDynamicExpression>(parameters);
    }

    public DynamicExpression Body { get; private set; }
    public ReadOnlyCollection<ParameterDynamicExpression> Parameters { get; private set; }

    public Delegate Compile()
    {
        return null;
    }
    protected internal override void ToString(StringBuilder sb)
    {
        sb.Append("(");

        int n = Parameters.Count;
        for (int i = 0; i < n; i++)
        {
            Parameters[i].ToString(sb);
            if (i != n - 1)
                sb.Append(", ");
        }

        sb.Append(") => ");
        Body.ToString(sb);
    }
}

Same deal concerning parameterization based on DynamicExpression instances. I promise you the Compile method will be pretty interesting to say the least, so stay tuned for the next post!

Del.icio.us | Digg It | Technorati | Blinklist | Furl | reddit | DotNetKicks

Filed under: ,

Comments

# To Bind or Not To Bind ??? Dynamic Expression Trees ??? Part 1

Pingback from  To Bind or Not To Bind ??? Dynamic Expression Trees ??? Part 1

# Dew Drop - August 27, 2008 | Alvin Ashcraft's Morning Dew

Wednesday, August 27, 2008 5:49 AM by Dew Drop - August 27, 2008 | Alvin Ashcraft's Morning Dew

Pingback from  Dew Drop - August 27, 2008 | Alvin Ashcraft's Morning Dew

# Reflective Perspective - Chris Alcock &raquo; The Morning Brew #167

Pingback from  Reflective Perspective - Chris Alcock  &raquo; The Morning Brew #167

# WMOC#18 - Microsoft Solver Foundation released - Service Endpoint

Pingback from  WMOC#18 - Microsoft Solver Foundation released - Service Endpoint

# Link for Linq &#8211; Even the right google question would be ok - Programmers Goodies

Pingback from  Link for Linq &#8211; Even the right google question would be ok - Programmers Goodies

# Expression trees | Pearltrees

Monday, August 26, 2013 1:26 AM by Expression trees | Pearltrees

Pingback from  Expression trees | Pearltrees