Tuesday, August 11, 2009 9:06 AM bart

Statement Trees With Less Pain – Follow-Up on System.Linq.Expressions v4.0

Introduction

In my last post, Expression Trees, Take Two – Introducing System.Linq.Expressions v4.0, I showed how to the extensions to the LINQ expression trees API opens up for full-blown statement trees including support for assignment, control flow, etc. One popular question that came up in the comments section is on the lack of language-level support for statement trees, like this:

Expression<Func<int, List<int>>> getPrimes = to =>
{
    var res = new List<int>();
    for (int n = 2; n <= to; n++)
    {
        bool found = false;

        for (int d = 2; d <= Math.Sqrt(n); d++)
        {
            if (n % d == 0)
            {
                found = true;
                break;
            }
        }

        if (!found)
            res.Add(n);
    }
    return res;
};

At this point, the above won’t work and trigger the following compile error:

A lambda expression with a statement body cannot be converted to an expression tree

This hasn’t changed from the previous release. Though it would be a nice feature to have, there are various reasons not to have it integrated with the language at this point. My posts to the comments section of my previous post elaborate on some of the conservative constraints employed during language design, applied to this particular case. So, sorry: not at this point.

The result is the above turns into quite an involved statement tree declaration if done by hand. Let’s repeat it here to set the scene:

var to = Expression.Parameter(typeof(int), "to");
var res = Expression.Variable(typeof(List<int>), "res");
var n = Expression.Variable(typeof(int), "n");
var found = Expression.Variable(typeof(bool), "found");
var d = Expression.Variable(typeof(int), "d");
var breakOuter = Expression.Label();
var breakInner = Expression.Label();
var getPrimes = 
    // Func<int, List<int>> getPrimes =
    Expression.Lambda<Func<int, List<int>>>(
        // {
        Expression.Block(
            // List<int> res;
            new [] { res },
            // res = new List<int>();
            Expression.Assign(
                res,
                Expression.New(typeof(List<int>))
            ),
            // {
            Expression.Block(
                // int n;
                new [] { n },
                // n = 2;
                Expression.Assign(
                    n,
                    Expression.Constant(2)
                ),
                // while (true)
                Expression.Loop(
                    // {
                    Expression.Block(
                        // if
                        Expression.IfThen(
                            // (!
                            Expression.Not(
                                // (n <= to)
                                Expression.LessThanOrEqual(
                                    n,
                                    to
                                )
                            // )
                            ),
                            // break;
                            Expression.Break(breakOuter)
                        ),
                        // {
                        Expression.Block(
                            // bool found;
                            new[] { found },
                            // found = false;
                            Expression.Assign(
                                found,
                                Expression.Constant(false)
                            ),
                            // {
                            Expression.Block(
                                // int d;
                                new [] { d },
                                // d = 2;
                                Expression.Assign(
                                    d,
                                    Expression.Constant(2)
                                ),
                                // while (true)
                                Expression.Loop(
                                    // {
                                    Expression.Block(
                                        // if
                                        Expression.IfThen(
                                            // (!
                                            Expression.Not(
                                                // d <= Math.Sqrt(n)
                                                Expression.LessThanOrEqual(
                                                    d,
                                                    Expression.Convert(
                                                        Expression.Call(
                                                            null,
                                                            typeof(Math).GetMethod("Sqrt"),
                                                            Expression.Convert(
                                                                n,
                                                                typeof(double)
                                                            )
                                                        ),
                                                        typeof(int)
                                                    )
                                                )
                                            // )
                                            ),
                                            // break;
                                            Expression.Break(breakInner)
                                        ),
                                        // {
                                        Expression.Block(
                                            // if (n % d == 0)
                                            Expression.IfThen(
                                                Expression.Equal(
                                                    Expression.Modulo(
                                                        n,
                                                        d
                                                    ),
                                                    Expression.Constant(0)
                                                ),
                                                // {
                                                Expression.Block(
                                                    // found = true;
                                                    Expression.Assign(
                                                        found,
                                                        Expression.Constant(true)
                                                    ),
                                                    // break;
                                                    Expression.Break(breakInner)
                                                // }
                                                )
                                            )
                                        // }
                                        ),
                                        // d++;
                                        Expression.PostIncrementAssign(d)
                                    // }
                                    ),
                                    breakInner
                                )
                            ),
                            // if
                            Expression.IfThen(
                                // (!found)
                                Expression.Not(found),
                                //    res.Add(n);
                                Expression.Call(
                                    res,
                                    typeof(List<int>).GetMethod("Add"),
                                    n
                                )
                            )
                        ),
                        // n++;
                        Expression.PostIncrementAssign(n)
                    // }
                    ),
                    breakOuter
                )
            ),
            res
        ),
        to
    // }
    ).Compile();

I’ve formatted a bunch of nodes in the expression tree above to indicate the “tiles” that are based on the v3.0 subset of the Expression Tree APIs, which do have language support. What if we could simplify the declaration above by leveraging the language support at places where it’s worthwhile? A tour through simplifying statement trees…

 

Abstraction + application = ???

Without much further ado, let’s dive straight into our pool of expression tree tricks and reveal the goods for this round: abstraction and application. Guess what, we’re back to fundamental lambda calculus. An explanation is in order:

  • Abstraction is the act of abstracting over an expression, i.e. introducing a parameterized function. Given an expression, turning a symbol therein into a parameter is what it takes to abstract over the expression:

    image
  • Application is also known as beta-reduction and corresponds to the act of applying a function given one or more arguments (strictly speaking one at a time):

    image 

Given those fundamental laws in lambda calculus, we can create a very round-about way of expressing 1 + 2. Just reverse the arrows in the last diagram: 2 becomes y, 1 becomes x, both “abstracting away” the constants one at a time, resulting in a function that’s readily applied to the two constants.

This basic insight is what will help us to simplify the statement tree declaration, allowing us to “tile in” expression trees in the bigger soup of statement tree nodes. But before we go there, let’s show the technique above in practice. Say we want to over-complicate the act of adding 1 and 2 together and do so through a deviation along the road of abstraction and application:

var x = Expression.Parameter(typeof(int), "x");
var y = Expression.Parameter(typeof(int), "y");
var f = Expression.Lambda<Func<int, int, int>>(
    Expression.Add(x, y),
    x, y
);
var three = Expression.Invoke(
    f,
    Expression.Constant(1),
    Expression.Constant(2)
);
var res = Expression.Lambda<Func<int>>(three).Compile();

Console.WriteLine(res());

What’s happening here is not that difficult as it may seem at first glance. The “f” lambda expression simply is a function that goes from x and y to x + y (in C# lingo, (x, y) => x + y). Expression.Invoke is used to invoke a delegate (lambdas ultimately are delegates), this time supplying the arguments. So, “three” is shorthand for ((x, y) => x + y)(1, 2), which is longhand for 1 + 2. Finally, the “res” lambda expression is a simple function returning an int, being the result of the invocation of the sum abstraction.

image

Looking at the generated IL code for the “res” delegate (using the tricks revealed in the previous post), we see the following:

IL_0000: ldc.i4.1
IL_0001: ldc.i4.2
IL_0002: stloc.1
IL_0003: stloc.0
IL_0004: ldloc.0
IL_0005: ldloc.1
IL_0006: add
IL_0007: ret

Did you see it? You did? Great! Exactly, no single trace of a delegate call in here. The combination of application (InvocationExpression) over an abstraction (LambdaExpression) got optimized away. Instead of pushing constants 1 and 2 on the stack in preparation of a delegate invocation call instruction, they get stored in locals, followed by a dump of the invoked function’s IL where the expected ldarg instructions are replaced by ldloc instructions. All in all, it’s still as if we’d written:

var res = Expression.Lambda<Func<int>>(
    Expression.Add(
        Expression.Constant(1),
        Expression.Constant(2)
    )
).Compile();

which translates in slightly simpler IL code:

IL_0000: ldc.i4.1
IL_0001: ldc.i4.2
IL_0002: add
IL_0003: ret

Eliminating the excessive stloc/ldloc pairs in the original fragment is something the JIT compiler could take care of it feels happy to do so, but the core message here is that this trick of “abstract & apply” is cheaper than it looks.

Why am I telling you all of this? In fact, the trick outlined above is what we’ll use to tile in language-generated expression trees in a bigger sea of hand-crafted statement trees. For the sample above, what if we made the function definition through abstraction happen using the language-level support, while keeping the invocation call in plain hand-crafted expression trees:

var three = Expression.Invoke(
    (Expression<Func<int, int, int>>)((x, y) => x + y),
    Expression.Constant(1),
    Expression.Constant(2)
);
var res = Expression.Lambda<Func<int>>(three).Compile();

See it coming? Think about it for a while: we’re combining a compiler-generated expression tree with a manually created bigger one in which we embed the smaller one.

 

Theory applied

To keep things a bit more controlled, focus on one part of the original statement tree:

Expression.IfThen(
    // (!
    Expression.Not(
        // d <= Math.Sqrt(n)
        Expression.LessThanOrEqual(
            d,
            Expression.Convert(
                Expression.Call(
                    null,
                    typeof(Math).GetMethod("Sqrt"),
                    Expression.Convert(
                        n,
                        typeof(double)
                    )
                ),
                typeof(int)
            )
        )
    // )
    ),
    // break;
    Expression.Break(breakInner)
),

This corresponds to the terminating condition for the inner loop:

for (int d = 2; d <= Math.Sqrt(n); d++)
{
    if (n % d == 0)
    {
        found = true;
        break;
    }
}

As we all know, that’s a plain old valued expression that could be turned into a function as follows:

Func<int, int, bool> cond = (x, y) => x <= Math.Sqrt(y);
for (int d = 2; cond(d, n); d++)
{
    if (n % d == 0)
    {
        found = true;
        break;
    }
}

Now we’re getting somewhere. The code above is exactly the same as the original one, but we’ve abstracted over the condition by turning it into a function of its own, which we subsequently apply given d and n. For regular code, that doesn’t make much sense, but it’s exactly the trick we’re talking about here and that will make the expression tree case simpler. What if we translated the code above as follows?

Expression<Func<int, int, bool>> cond = (x, y) => x <= Math.Sqrt(y);
for (int d = 2; cond.Compile()(d, n); d++)
{
    if (n % d == 0)
    {
        found = true;
        break;
    }
}

Heh, there’s our expression tree for the condition. As we’re still not generating the whole for-loop in a statement tree, we have to call Compile explicitly on the intermediate lambda expression to invoke it in the condition part of the for-loop. Now we can take it one step further and go back to the expression tree for the whole for-loop, patching it up with our intermediate “cond” expression tree … using application. At the same time, we can eat the “Not” node:

Expression.IfThen(
    // (!
    Expression.Not(
        // d <= Math.Sqrt(n)
        Expression.LessThanOrEqual(
            d,
            Expression.Convert(
                Expression.Call(
                    null,
                    typeof(Math).GetMethod("Sqrt"),
                    Expression.Convert(
                        n,
                        typeof(double)
                    )
                ),
                typeof(int)
            )
        )
    // )
    ),
    // break;
    Expression.Break(breakInner)
),

In essence, the first argument to IfThen (i.e. the if-statement’s condition expression) contains two variables from the outer scope: d and n. We’ll abstract over those, introducing an intermediate lambda expression, and invoke (apply) that one using d and n. Code is worth a thousand words:

Expression.IfThen(
    // (!(d <= Math.Sqrt(n)))
    Expression.Invoke(
        (Expression<Func<int, int, bool>>)((x, y) => !(x <= Math.Sqrt(y))),
        d,
        n
    ),
    // break;
    Expression.Break(breakInner)
),

Wow, that got a bit simpler, didn’t it? The formatted (bold, underline) part corresponds to the language-generated expression tree. All we have to do is wrap that thing in an InvocationExpression, passing in d and n as arguments (respectively being bound to x and y).

Similarly, we can simplify other parts of the statement tree. For example:

// if (n % d == 0)
Expression.IfThen( Expression.Equal( Expression.Modulo( n, d ), Expression.Constant(0) ), // { Expression.Block( // found = true; Expression.Assign( found, Expression.Constant(true) ), // break; Expression.Break(breakInner) // } ) )

It doesn’t make sense to try to abstract Expression.Constant calls (it would only blow up the code size and make things more cumbersome), but the n % d == 0 part is something we could ask the compiler to generate for us:

// if (n % d == 0)
Expression.IfThen(
    Expression.Invoke(    
        (Expression<Func<int, int, bool>>)((x, y) => x % y == 0),
        n,
        d
    ),
    // {
    Expression.Block(
        // found = true;
        Expression.Assign(
            found,
            Expression.Constant(true)
        ),
        // break;
        Expression.Break(breakInner)
    // }
    )
)

It’s a little unfortunate lambda expressions need to have a type forced upon them to emit them either as a delegate (Func<…> types) or an expression tree (Expression<Func<…>> types), requiring us to use an explicit cast to demand the compiler to generate an expression tree. This blows up the code significantly, but still we’re saving quite a bit of code. Also for method invocations, we can get rid of the ugly reflection code required to get the right overload, e.g.:

// if
Expression.IfThen(
    // (!found)
    Expression.Not(found),
    //    res.Add(n);
    Expression.Call(
        res,
        typeof(List<int>).GetMethod("Add"),
        n
    )
)

Finding the Add method is simple in this case, but if you end up creating a MethodCallExpression with a bunch of arguments to a method with lots of overloads available, the code gets quite complicated. In the sample above, there’s little to gain, but just for the sake of illustration:

// if
Expression.IfThen(
    // (!found)
    Expression.Not(found),
    //    res.Add(n);
    Expression.Invoke(
        (Expression<Action<List<int>, int>>)((l, e) => l.Add(e)),
        res,
        n
    )
)

Moreover, when typing the lambda expression above you’ll get full-blown (statically typed) IntelliSense:

image

In fact, this trick is a runtime-aided trick to implement an “infoof” operator (info-of) which I use from time to time. For example, if you want to get the MethodInfo for Console.WriteLine(“{0} is {1}”, “Bart”, 26) that can get quite involved using reflection flags (public, static), a method name in a string (“WriteLine”), a type array for the arguments (beware of the “params” behavior above), etc. Instead, you could do this:

static MethodInfo InfoOf(Expression<Action> ex)
{
    var mce = ex.Body as MethodCallExpression;
    if (mce != null)
    {
        return mce.Method;
    }
    else
    {
        throw new InvalidOperationException("InfoOf called on expression without any kind of member access.");
    }
}

static MemberInfo InfoOf<T>(Expression<Func<T>> ex)
{
    var me = ex.Body as MemberExpression;
    if (me != null)
    {
        return me.Member;
    }
    else
    {
        throw new InvalidOperationException("InfoOf called on expression without any kind of member access.");
    }
}

which we can call as follows:

var cw = InfoOf(() => Console.WriteLine("{0} is {1}", "Bart", 26));
var now = InfoOf(() => DateTime.Now);

So, all in all, the lack of statement tree support in the language is a pity, but by leveraging existing expression tree support we can simplify the task at hand in some cases. The result for our sample is as follows:

var to = Expression.Parameter(typeof(int), "to");
var res = Expression.Variable(typeof(List<int>), "res");
var n = Expression.Variable(typeof(int), "n");
var found = Expression.Variable(typeof(bool), "found");
var d = Expression.Variable(typeof(int), "d");
var breakOuter = Expression.Label();
var breakInner = Expression.Label();
var getPrimes = 
    // Func<int, List<int>> getPrimes =
    Expression.Lambda<Func<int, List<int>>>(
        // {
        Expression.Block(
            // List<int> res;
            new [] { res },
            // res = new List<int>();
            Expression.Assign(
                res,
                Expression.New(typeof(List<int>))
            ),
            // {
            Expression.Block(
                // int n;
                new [] { n },
                // n = 2;
                Expression.Assign(
                    n,
                    Expression.Constant(2)
                ),
                // while (true)
                Expression.Loop(
                    // {
                    Expression.Block(
                        // if
                        Expression.IfThen(
                            // (!
                            Expression.Not(
                                // (n <= to)
                                Expression.LessThanOrEqual(
                                    n,
                                    to
                                )
                            // )
                            ),
                            // break;
                            Expression.Break(breakOuter)
                        ),
                        // {
                        Expression.Block(
                            // bool found;
                            new[] { found },
                            // found = false;
                            Expression.Assign(
                                found,
                                Expression.Constant(false)
                            ),
                            // {
                            Expression.Block(
                                // int d;
                                new [] { d },
                                // d = 2;
                                Expression.Assign(
                                    d,
                                    Expression.Constant(2)
                                ),
                                // while (true)
                                Expression.Loop(
                                    // {
                                    Expression.Block(
                                        // if
                                        Expression.IfThen(
                                            // (!(d <= Math.Sqrt(n)))
                                            Expression.Invoke(
                                                (Expression<Func<int, int, bool>>)((x, y) => !(x <= Math.Sqrt(y))),
                                                d,
                                                n
                                            ),
                                            // break;
                                            Expression.Break(breakInner)
                                        ),
                                        // {
                                        Expression.Block(
                                            // if (n % d == 0)
                                            Expression.IfThen(
                                                Expression.Invoke(    
                                                    (Expression<Func<int, int, bool>>)((x, y) => x % y == 0),
                                                    n,
                                                    d
                                                ),
                                                // {
                                                Expression.Block(
                                                    // found = true;
                                                    Expression.Assign(
                                                        found,
                                                        Expression.Constant(true)
                                                    ),
                                                    // break;
                                                    Expression.Break(breakInner)
                                                // }
                                                )
                                            )
                                        // }
                                        ),
                                        // d++;
                                        Expression.PostIncrementAssign(d)
                                    // }
                                    ),
                                    breakInner
                                )
                            ),
                            // if
                            Expression.IfThen(
                                // (!found)
                                Expression.Not(found),
                                //    res.Add(n);
                                Expression.Invoke(
                                    (Expression<Action<List<int>, int>>)((l, e) => l.Add(e)),
                                    res,
                                    n
                                )
                            )
                        ),
                        // n++;
                        Expression.PostIncrementAssign(n)
                    // }
                    ),
                    breakOuter
                )
            ),
            res
        ),
        to
    // }
    ).Compile();

Still quite involved to write, but a bit simpler than our previous attempt. As an exercise, identify a few other potential rewrite sites in the fragment above. Have fun!

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

Filed under: , ,

Comments

# re: Statement Trees With Less Pain – Follow-Up on System.Linq.Expressions v4.0

Tuesday, August 11, 2009 5:48 PM by Olmo

There's no more big pure-expressions that could be rewriten with the nice Invoke trick, so the only options is to re-compose the C# for statement in a For function like this:

       public static Expression For(VariableExpression variable, Expression initialValue, Expression maxValue, Func<LabelExpression, Expression> body)

       {

           var @break = Expression.Label();

           return Expression.Block(

           new[] { variable },

           Expression.Assign(variable, initialValue),

           // while (true)

           Expression.Loop(

               Expression.Block(

                   // if(!(n <= to)

                   Expression.IfThen(Expression.Not(Expression.LessThanOrEqual(variable, maxValue)),

                       // break;

                       Expression.Break(@break)

                   ),

                   body(@break),

                   // n++;

                   Expression.PostIncrementAssign(n)

               ),

               @break

           ));

       }

Note how a Func<LabelExpression, Expression> is taken to build the body, making the label available if necessary. I would use LessThan in a generar purpose method, but LessThanOrEqual is ok for this example.

Then we could re-write the code like this:

           var to = Expression.Parameter(typeof(int), "to");

           var res = Expression.Variable(typeof(List<int>), "res");

           var n = Expression.Variable(typeof(int), "n");

           var found = Expression.Variable(typeof(bool), "found");

           var d = Expression.Variable(typeof(int), "d");

           var getPrimes =

               // Func<int, List<int>> getPrimes =

               Expression.Lambda<Func<int, List<int>>>(

                   Expression.Block(

                       // List<int> res;

                       new[] { res },

                       // res = new List<int>();

                       Expression.Assign(res, Expression.New(typeof(List<int>))),

                       // for (int n = 2; n <= to; n++)

                       For(n, Expression.Constant(2), to, _ => //Don't care about the break

                         Expression.Block(

                           // bool found;

                           new[] { found },

                           // found = false;

                           Expression.Assign(found, Expression.Constant(false)),

                           //for (int d = 2; d <= Math.Sqrt(n); d++)

                           For(d, Expression.Constant(2), Expression.Invoke((Expression<Func<int, int, bool>>)(y => (int)Math.Sqrt(y)), n), breakInner =>

                               Expression.IfThen(

                                       Expression.Invoke((Expression<Func<int, int, bool>>)((x, y) => x % y == 0), n, d),

                                       Expression.Block(

                                   // found = true;

                                          Expression.Assign(found, Expression.Constant(true)),

                                   // break;

                                          Expression.Break(breakInner)

                                       )

                               )),

                             // if(!found)

                             Expression.IfThen(Expression.Not(found),

                             //    res.Add(n);

                                    Expression.Invoke((Expression<Action<List<int>, int>>)((l, e) => l.Add(e)), res, n)

                             )

                         )

                      )

               )).Compile();

I haven't tested it cos I don't have .Net 4 installed yet, but it should work.

One last thing, Is the new ExpressionVisitor going to have some Expression-only sibling with no statement support. I've a LINQ provider and i would consider changing my base Visitor if so, but I don't want to add all the statement mess that won't have a translation to SQL anyway.

BTW: I support the conservative position of not supporting automatic statements in the Expression<T> lambdas by the compiler; otherwise it will make all the Linq providers look flawed.

Thanks’ Bart for such a brilliant blog!

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

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

# Dew Drop &#8211; August 12, 2009 | Alvin Ashcraft's Morning Dew

Wednesday, August 12, 2009 5:42 AM by Dew Drop – August 12, 2009 | Alvin Ashcraft's Morning Dew

Pingback from  Dew Drop &#8211; August 12, 2009 | Alvin Ashcraft's Morning Dew

# re: Statement Trees With Less Pain – Follow-Up on System.Linq.Expressions v4.0

Wednesday, August 12, 2009 9:15 AM by bart

Hi Olmo,

You're reading my thoughts on planned follow-up posts. I do indeed have additional factory methods for various C#-specific and VB-specific statement constructs, such as a For-loop. They have a bit more overloads than the one you showed and are closer to the language specification in terms of their arguments (e.g. the for loop initializer can be more complex than a single assignment), but the core idea is the same.

On the new ExpressionVisitor, posts are coming up in the foreseeable future as well. To answer your question: there's no such thing as an "expression-only" visitor, but one could easily derive such a beast from the bigger one, which throws an exception upon encountering a statement-only construct.

Thanks,

-Bart

# re: Statement Trees With Less Pain – Follow-Up on System.Linq.Expressions v4.0

Wednesday, August 12, 2009 11:42 AM by Olmo

Hi bart,

Sorry if I've ruined the follow-up posts, But I'm sure you still have some ideas to keep it interesting.

About the ExpressionVisitor, I think there are two major scenarios for expression trees (apart from tiny things like infoof()) :

* Building a LINQ provider (old .Net 3.5): You need compiler support for creating Expressions from lambdas an a base ExpressionVisitor that you can steal from here blogs.msdn.com/.../linq-building-an-iqueryable-provider-part-ii.aspx

* Metaprogramming (new .Net 4.0): You build complex algorithms with statements and block Expressions manually and then compile it. Cleaner than using MSIL directly.

Maybe there's an scenario where modifying a statement expression with a visitor is useful, but I think it will be really hard, specially since the high level constructs are lost in translation (for, whiles, switch..).

Writing a LINQ provider is hard enought, I wouldn't add more complexity by having dummy statement-related methods that just throw NotSupportedException.

That's why I think having ExpressionVisitor (.Net 3.5 state of the art) and StatementVisitor: ExpressionVisitor (.Net 4.0 BLOCKED EXPRESSION will be a better solution.

However, I understand that timeframe or other issues will make my idea impossible to accomplish.

Thank' again

Olmo

# re: Statement Trees With Less Pain – Follow-Up on System.Linq.Expressions v4.0

Wednesday, August 12, 2009 3:10 PM by bart

Hi Olmo,

Plenty of ideas over here, so don't worry about ruining my posts with comments on the same topic :-).

You're right about our current two major scenarios, one derived from the past (LINQ) and one newborn (or at least extended over previous eras) to facilitate the poor man's (meaning still rather manual effort-driven with no language surface) metaprogramming.

Indeed, rewriting expression trees can be hard if intermediate front-end language stages are lost. Same with going from IL to source code as done in Reflector. This said, some of the "atoms" are much telling, like method calls which are a typical target for rewrites or analysis (e.g. "do not call this dangerous method"). You should really think about expression trees as a way to facilitate all sorts of tools, most of which don't need full-fidelity language-specific construct reconstruction: FxCop rules, instrumentation, simple rewrites, etc. Though others, like refactoring engines, could benefit from a closer-to-the-language representation. Along those lines, while and do are fairly easy to trace backwards, for is a bit more involved; switch is easy as there's a specialized set of nodes for that (like SwitchCase) due to the IL-level support for int-based switches.

For the LINQ provider case, you can still use our new (statement + expression) visitor as a base type for another abstract type that deals with expressions only. The name would be a bit cumbersome I guess since we already took ExpressionVisitor to span the whole realm of System.Linq.Expressions - maybe something like ExpressionOnlyVisitor :-). Idea would be to inherit all virtuals but override all the statement-specific ones with code that throws an exception upon visitation.

I understand your feedback on the expression/statement naming within the API but the mix of backwards compatibility, unification with DLR, etc were all influential to shape the API as it appears in .NET 4.0. Unfortunately, naming got sacrificed a bit, but only if you come from a C# or similar perspective... Why's that? Well, in languages like Ruby, everything is an expression (including loops and ifs). It'd be wrong to say they are wrong or to force C#-specific naming on them, so calling everything an "expression" seems reasonable. E.g. a LINQ-call originating from a hypothetical Ruby-with-(our)-expression-tree-capturing-support might use an if-"statement" (as an expression) to be the same as the conditional "ternary" operator (?:) "expression".

Thanks,

-Bart

# re: Statement Trees With Less Pain – Follow-Up on System.Linq.Expressions v4.0

Wednesday, August 12, 2009 3:57 PM by Olmo

Hi again!

Fron the Fxcop example...should we expect system.linq.expression to be the main Api for this future extensible c# compiler? That would be neat but probably you will need more textual info (comments, line numbers) in order to allow refactorings for example. It's gonna be great to have a open compiler :)

about naming, in fact there are two problems with system.linq.expression: it's not about expressions only, and is not only for linq anymore.  I understand that backwards compatibility is more important and the name is good enought.

Renaming my ExpressionVisitor to ExpressionOnlyVisitor wont be hard, it's only used internally by my Linq provider.

What will hurt is changing the name of our Lazy<T> www.signumframework.com/Default.aspx to make room to the new guy in town msdn.microsoft.com/.../dd642331(VS.100).aspx that already has a flat in System street in mscorlib downtown :). Unfortunately we have lot of client code  relying on IT :S

thanks

olmo

# re: Statement Trees With Less Pain – Follow-Up on System.Linq.Expressions v4.0

Wednesday, August 12, 2009 5:01 PM by bart

Hi Olmo,

At this point we can't comment on where expression trees are going to be taken next but it's widely known the managed language compilers are being rewritten in managed code to facilitate the creation of a code-as-data object model, allow hosting of language services, etc. There's a bunch of things to be figured out, and more tree structures (like parse trees) are needed before we can get to a point where potentially more compile phases can be opened up. Stay tuned for subsequent releases.

I hear your comments on the naming: the System.Linq namespace becomes a weirder place for this extended functionality to live in, and - in the C#/VB sense - things are beyond the level of expressions indeed. But yes, compatibility wins over such debates.

I'm sorry to hear about the Lazy<T> clash, but core building blocks (including things like Tuple as well) belong to the System namespace, which always introduces the potential of compile-time breaking existing code (though already compiled binaries obviously will continue to work fine).

Thanks,

-Bart

# re: Statement Trees With Less Pain – Follow-Up on System.Linq.Expressions v4.0

Thursday, August 13, 2009 2:49 PM by Olmo

I completely understand the need to rearrange the assemblies in .Net 4.0, and I support your solution, even causing me some headaches

Cheers!

# re: Statement Trees With Less Pain – Follow-Up on System.Linq.Expressions v4.0

Sunday, August 16, 2009 10:34 AM by shawn

This is a great series!  As a C# developer with a Ruby background, I'm really looking forward to the increased dynamism of a compiler-as-a-service future. :)

It would be especially nice to see EF/LINQ take advantage of these new features to bake in a more seamless integration between client-side object properties and remote LINQ calls (ie SQL), ala:

damieng.com/.../client-side-properties-and-any-remote-linq-provider

# ContinousLearner: Links (8/13/2009) | Astha

Wednesday, September 09, 2009 2:33 PM by ContinousLearner: Links (8/13/2009) | Astha

Pingback from  ContinousLearner: Links (8/13/2009) | Astha

# Top 9 Posts from 2009

Sunday, January 03, 2010 1:08 AM by B# .NET Blog

select top 9 [Subject] from dbo . cs_Posts where postlevel = 1 and usertime &lt; &#39;01/01/2010&#39;

# Twitter Trackbacks for Statement Trees With Less Pain ??? Follow-Up on System.Linq.Expressions v4.0 - B# .NET Blog [bartdesmet.net] on Topsy.com

Pingback from  Twitter Trackbacks for                 Statement Trees With Less Pain ??? Follow-Up on System.Linq.Expressions v4.0 - B# .NET Blog         [bartdesmet.net]        on Topsy.com