Expression as a Compiler

It is no secret that I like playing with the Expression API. Well, I've finally spent some time collating some of my thoughts into a semi-coherent discussion on InfoQ. I hope it is useful to somebody.

Expression as a Compiler

Using Expression when creating runtime types

In .NET 3.5, the framework provides the (greatly appreciated) mechanism to compile an expression tree to a delegate - providing a convenient way to write dynamic methods without having to dabble in IL (never pretty).

Over the weekend, I've been looking in more depth at the DLR trees in 4.0 (beta) - and an interesting little nugget leapt out at me... you can now compile an expression tree into the body of a MethodBuilder! This means that even when writing a full type at runtime you can write the methods using an object model rather than Reflection.Emit.

My current example of this doesn't really illuminate much, so I won't post it "as is" - probably to follow. But does this sound "time" for people having to learn how to use ILGenerator?

Don't get me wrong - expression trees aren't trivial, and you need to think carefully when writing them - but they are a lot simpler than writing IL directly.

Exploring 4.0; Expression and Dynamic

You can't have missed that VS2010 beta 1 is now available. With the 4.0 release, most of the changes are in the framework dlls - there aren't a huge amount of C# language changes to pick up. I've done a little dabbling...

Expression

I looked previously at Expression on the CTP; well, guess what? They went and renamed everything... here's the previous example, updated; note the use of Expression.Block and Expression.Assign (rather than Comma and AssignProperty):

class Foo
{
   public string Bar { get; set; }
   public override string ToString()
   {
       return Bar;
   }
}
static void Main()
{
   var param = Expression.Parameter(typeof(Foo), "foo");
   var assign = Expression.Assign(
       Expression.Property(param, "Bar"),
       Expression.Constant("def", typeof(string)));
   var writeLine = Expression.Call(
       typeof(Console).GetMethod("WriteLine", new[] { typeof(object) }),
       param);

   var action = Expression.Lambda<Action<Foo>>(Expression.Block(assign, writeLine), param);
   var actionDel = action.Compile();
   Foo foo = new Foo();
   actionDel(foo);
}

It is also pretty clear that there are no plans to add language support for this (via a lambda); maybe something for the future.

Dynamic

I think "dynamic" is great if you are talking to COM or DLR; but should generally be avoided otherwise. Still; one interesting aspect is that it provides access to generic operators; which wasn't yet implemented on the last CTP. Well; it is here now - and it actually doesn't perform too badly... to avoid taking a dependency on an extra dll, I'd consider it...

int
Operator: 833ms (100000010)
Dynamic: 1383ms (100000010)

float
Operator: 786ms (3.355443E+07)
Dynamic: 1309ms (3.355443E+07)

decimal
Operator: 3974ms (100000010)
Dynamic: 3911ms (100000010)

As it happens the Nullable<T>performance isn't quite as good yet, but you can always use MiscUtil's Operator class ;-p

Other than that; unless I start writing lots of IronPython, I currently don't expect to use "dynamic" all that much.

Re-implementing Expression for Compact Framework

Background

In this previous post I gave an indication of how the RPC stack of protobuf-net is implemented - in particular (in .NET 3.5) with Expression - allowing:

  ProtoClient<IMyService> client = ...
  double amount = client.Invoke(svc => svc.DoSomeMaths(
    12, someObj.Qty));

where DoSomeMaths is a method defined on the IMyService interface. This works well, and avoids the need to do any kind of code generation, yet still have full static (compile time) checking that we're using methods that are defined on our service.

So what is the problem?

As always, there is a fly in the ointment; it transpires that the Expression API doesn't exist on Compact Framework 3.5. Perhaps Microsoft thought that it served little purpose without a matching Reflection.Emit implementation (allowing you to compile expressions to delegates) - who knows. But it is vexing that it works everywhere (including Silverlight 2.0) except here. So what can we do?

Well, pretty-much all of C# 3.0 is actually compiler magic hitting known types in the base class. For example, you can use LINQ (with delegates) with C# 3.0 targetting .NET 2.0 by declaring ExtensionAttribute and adding a pile of extension methods on IEnumerable etc (or more simply: download LINQBridge). So can we do the same here? I've previously always been dismissive of this, but it turns out that yes, we can.

What, all of Expression?

First - a caveat; I don't need all of Expression; for example, I don't need any compilation features, I don't need to be able to add things etc - all I need is:

• a lambda that accepts parameters
  • that can invoke methods
  • that can use constant argument values
  • that can use properties and fields as values
  • that can use captured values (which are implemented as fields)

Anything more complex, and the caller can simply pre-calculate their argument value into a variable, and pass that in via a capture - i.e. this won't work:

  double amount = client.Invoke(svc => svc.DoSomeMaths(
    12, someObj.Qty * 2));

but this will:

  int qty = someObj.Qty * 2;
  double amount = client.Invoke(svc => svc.DoSomeMaths(
    12, qty));

What is involved?

Actually, not a vast amount - but we are hampered a bit; the C# spec doesn't actually indicate what Expression features it uses, nor when. Very unusual for C#, which is usually very detailed in this sort of thing... but actually, we can get an appreciation of what we need from looking at what the compiler does behind the scenes (as discussed previously). Given the requirements above, it turns out that we need the static methods:

• Expression.Constant
• Expression.Parameter
• Expression.Field
• Expression.Property
• Expression.MethodCall
• Expression.Lambda<T>

and a few classes to hold the state for each of these, so that we can inspect it afterwards. Not a huge task at all.

plz send teh codez

OK, enough already... the code for this (and it isn't very much) is now committed into protobuf-net (but only applies to the CF35 build) - and is available here - at just over 250 lines (including comments), this seems a fairly pragmatic way of unifying service access over the different frameworks. Enjoy.

Visualizing Expressions in PropertyGrid

The problem

The Expression API is complex; not least because picking apart an Expression is complicated. For example, lets pick an expression that removes the first and last characters from a string:

s => s.Length > 2 ? s.Substring(1, s.Length - 2) : s;

If you are working regularly with Expression, you often need to be able to visualize it (if only to stay sane); this counts doubly if we want to understand how to construct our own Expression to do something similar. Ideally without needing any external tools / plug-ins, and something a bit more permanent than the inspector in the IDE.

If you wanted to write down what that actually means (which is what Expression has to do):

• given a parameter "s" 
  • branch by evaluating the greater-than operator with arguments: 
    • query the Length of "s"
    • the constant 2
  • if true, evaluate Substring on the parameter "s" with arguments: 
    • the constant 1
    • the result of the subtraction operator with arguments:
      • query the Length of "s"
      • the constant 2
  • if false, evaluate the parameter "s"

Although fairly mechanical, pulling apart Expressions can take time. If only the system could display it for us.

The naïve approach

But wait a minute! PropertyGrid is good at displaying tree-like data - lets try setting the SelectedObject to an instance of the above Expression:

Disappointed? It doesn't really help us (and note that the Parameters collection is not expandable). The problem is that PropertyGrid uses TypeDescriptor (and friends) to query the metadata, and Expression simply isn't configured to allow hierarchical browsing. But what many people don't realise is that TypeDescriptor allows runtime configuration.

Changing the type-converter

Behind the scenes, PropertyGrid uses the TypeConverter associated with a type (or an individual member), by querying GetPropertiesSupported(), and (if it returns true) GetProperties(). And even better, there is an inbuilt converter (ExpandableObjectConverter) that exposes all the public members for nested browsing.

Additionally, TypeDescriptor offers an indirect way to associate a different type-converter with a type; by adding an attribute at runtime*. Since Expression is the base class for all the interesting objects in the Expression API, we only have to tweak this one type:

  TypeDescriptor.AddAttributes(typeof(Expression),
   new TypeConverterAttribute(typeof(ExpandableObjectConverter)));

This is broadly equivalent to using the attribute at compile-time:

  [TypeDescriptor(typeof(ExpandableObjectConverter))]
 public abstract class Expression { /* ... */ }

*=for the pedants (myself included), I should note that we only add an attribute to the runtime model (System.ComponentModel); reflection is unaware of this change.

What does it look like now?

So how much difference does that one line make? Test again, and we see something very different - both in the main grid, and in the collection pop-ups:

So with just 1 line of code, we've obtained a free tool for exploring Expression; I'm not saying it is the prettiest tool ever, but it is plenty good enough, considering that the main audience would be you, the developer.

It begs the question; why isn't it expandable in the first place?

Explaining Expression

As part of planning for a user-group presentation, I've been trying to think how to distinguish between a delegate and an expression - ideally without mentioning the word "database".

For example, what is the difference between:

void Foo(Func<int,int,bool> func) {...}

and

void Foo(Expression<Func<int,int,bool>> func) {...}

? After all; both are called with identical syntax, for example:

Foo((x,y) => x==y);

My explanation

So here's my offering...

• The delegate version (Func<int,int,bool>) is the beligerant manager; "I need you to give me a way to get from 2 integers to a bool; I don't care how - when I'm ready, I'll ask you - and you can tell me the answer".
• The expression version (Expr<Func<int,int,bool>>) is the dutiful analyst; "I need you to explain to me - if I gave you 2 integers, how would you go about giving me a bool?"

In standard programming, the managerial approach is optimal; the caller already knows how to do the job (i.e. has IL for the purpose). But the analytic approach is more flexible; the analyst reserves the right to simply follow the instructions "as is" (i.e. call Compile().Invoke(...)) - but with understanding comes power. Power to inspect the method followed; report on it; substitute portions; replace it completely with something demonstrably equivalent, etc...

RPC Example

What does this mean? Well, for protobuf-net, I'm currently looking at the RPC stack. The design of protobuf-net is such that you *can* use code-generation, but it isn't enforced. I really want to avoid the messy approaches that you often need to use with WCF (for example).

Consider we have an RPC client that uses generics to indicate the interface that defines the service-contract (pretty common stuff if you are familiar with WCF):

class RpcClient<T> where T : class // T actually an interface

{}

Now; we can't expose the methods of T on RpcClient directly without using code generation; but we could use the approach of getting the caller to express their intent via the interface:

interface IFoo { string Bar(int i); }

var client = new RpcClient<IFoo>();

string s = client.Call(svc => svc.Bar(12345));

So what is Call? It wouldn't be useful as a delegate, as then we'd need to actually provide an IFoo instance to convince the caller to do the work for us... which means either code-generation or runtime type creation; the first is a pain, the second isn't even possible in some of the light-weight frameworks. But what about an expression?

TResult Call<TResult>(Expression<Func<T,TResult>> operation) {...}

Here, the caller gives us their version of what they would do with a hypothetical IFoo instance; we can take those instructions, dig out the MethodInfo (IFoo.Bar), evaluate the arguments (12345), and perform our own custom serialization on the wire. All without ever having an IFoo instance.

Application to Async

To take this a step further; consider Silverlight. All IO should be asynchronous. Yet we really don't want to have to start messing with Begin/End methods or events. We can use the same approach to let the caller express what they would do if running synchronously, but we'll execute it asynchronously. For example:

client.Call(svc => svc.Bar(12345),

result => Console.WriteLine(result()));

With

void Call(

Expression<Func<T,TResult>> operation,

Action<Func<TResult>> callback) {...}

The idea is that we will pick the Expression apart (like before), but rather than return the result, we'll execute the task asynchronously. The caller is requested to supply a callback which we'll invoke when we know the answer. Note that we don't give them the answer - we give them a function that they can invoke to find the answer; the distinction is that this also gives us a mechanism to convey an exception (i.e. if there was a problem the call to result() will re-raise the problem).

This also demonstrates mixing delegates and expressions in a single operation - we don't need to know what the caller wants with the answer in order to fetch it.

Summary

I've covered a lot in a small(ish) space, so feel free to pick it apart - but I hope this helps show some of the more interesting uses of Expression and delegates, and not a single database in sight!

Back to the coal face

With the summit now over, back to the day job - but first some thoughts (taking NDA etc into consideration):

• It is no secret that the big theme in .NET 4.0 is the DLR; despite some C# dabbling (here, here), I need to get my head around this "proper"... to that end, I've secured a copy of IronPython in Action, which I hope will set me on the one true path. Besides which - it is good to look at other languages occasionally (and I never really got far with F#).
• It is no secret that there are lots of changes afoot with Entity Framework and ADO.NET Data Services; now that I've had chance to see them, I'm encouraged that they might be a lot more usable in 4.0 - still waiting on the "bits" though ;-p
• Windows 7 continues to look very good; I've got the beta at home, and it runs very well on my ancient machine - and the newer builds look even better. Microsoft stand a good chance of actually getting some forgiveness for Vista.
• The EMP is very, very... odd. Beer, a live-rock/karaoke, an Xbox Rock Band arena and a robot museum all in one.

Other than that - back to the day job. Oh; and planning for a few user group sessions - so if you're in the UK and near Gloucester or Taunton, then I'll be talking about Expression. Feel free to say hi ;-p I also seem to have become involved in the "Balloon Debate" at the latter, so you can watch me try to defend the very existence of C#.

Pragmatic LINQ

LINQ, especially when talking to a database (or other back-end), arguably creates a bit of a tricky mess for proper application design.

Consider:

• I'm strongly in favour of proper unit testing
• As such, I like the repository pattern, since this allows me to mock my DAL
• In reality, I don't really need true POCO support; if I start needing my app to work with MySQL, I have bigger problems than POCO
• I like that LINQ-to-SQL / EF can maintain a basic object model for me
• Since it doesn't buy me anything, I don't really want to declare and maintain a "pure" (i.e. separate to the DAL) object model - I'm generally content to use partial classes to extend the classes we have generated
• For use in things like MVC, I want to know when data access happens; I don't want my view messing with lazy navigation properties
• I'm content (at the minute) to have a DAL that includes the LINQ-generated classes, the repository interface, and a class implementing that interafce, and think of it as "my object model assembly that happens (by coincidence) to contain a default repository implementation" (try saying that twice...)
• While I'm happy to know that LINQ to SQL supports POCO usage, the tooling doesn't make it easy. For now, I'm content to use attributed classes, and get on with the job...

So what?

Well, the first impact this has is: if you want it to be testable in any real sense, there isn't a lot of the LINQ stuff that can make it into the public API. For example:

• the data-context - has nothing to do with external callers in a repository implementation
• navigation properties - very quickly start crossing aggregates and/or causing lazy behaviour (not good if your context no longer exists)

My current thinking with this is that the data-context and most navigation properties should be marked as internal to the data layer (trivial either in the designer or dbml views). This means that your repository implementation can use the navigation properties to construct interesting queries, but the public API surfaced back to the caller doesn't include them. If the caller gets and order from the order repository, and wants details about the customer: tough - go and ask the customer repository. There is an edge-case for tightly coupled data (order header/details being a prime example), where it might be prudent to leave the navigation property public - but this is in the same aggregate, so this isn't a problem.

It isn't whiter than white - but it seems pretty workable:

• The repository interface protects our data-context from abuse; we know what use-cases we are supporting, and that they have been tested
• The lack of navigation properties means we know when data access happens : it is when the caller asks the repository

The bit where I'm a bit mixed is in the subject of allowing the caller to use Expression arguments on method calls; the ability to pass in an Expression<T,bool>-based predicate is powerful, but risky: we can't validate that our DAL covers all use cases (due to unmapped method calls etc), and we can't be 100% what TSQL is going to execute in reality (even small composed expressions can radically change the TSQL expression). I think I'd need to evaluate that on a need-by-need basis.

I don't know if I'm saying anything a: obvious, or b: stupid... but that is my thinking...

Future Expressions

Last post, I looked at what Expression offered in C# 3.5; to re-cap, very versatile at building simple queries, but not useful for writing manipulation code - in particular, the only in-built assignment is via Expression.MemberInit etc, which is useful only when creating new objects - or at a push you can perform a single update by obtaining the setter and using Expression.Call.

The interesting news is that this looks very different in .NET 4.0 (based on the public October 2008 CTP). It appears that Expression underpins much of the DLR / dynamic work - so there are all sorts of interesting new options - essentially, Expression is the new CodeDOM... personally I am very excited about this; I've always found Expression a far more intuitive and workable abstraction than the counterparts.

In .NET 3.5, there are 46 values in the ExpressionType enum; in .NET 4.0 (CTP), this jumps to 69, with options for loop constructs (loop/dowhile/break/continue/yield), member assignment, composite statements (block/comma?), and exception handling.

The new entries (again, based on the CTP) are:

• ActionExpression
• Assign
• Block
• BreakStatement
• Generator
• ContinueStatement
• Delete
• DoStatement
• EmptyStatement
• Extension
• IndexedProperty
• LabeledStatement
• LocalScope
• LoopStatement
• OnesComplement
• ReturnStatement
• Scope
• SwitchStatement
• ThrowStatement
• TryStatement
• Unbox
• Variable
• YieldStatement

I won't pretend to understand them much yet, but I will be investigating! I also understand that the C# 4.0 compiler doesn't support expressions with statement bodies at the moment (although you can build things by hand - which isn't trivial). It will be interesting to see if this changes (not least because reflector is such a good tool for discovering how you are meant to construct these expressions!).

[update] As an example, I previously gave the example of something you can't do in .NET 3.5:

    Expression<Action<Foo>> action = foo =>
    {
      foo.Bar = "def";
      Console.WriteLine(foo);
    };

Well, here it is in .NET 4.0:

   class Foo
   {
       public string Bar { get; set; }
       public override string ToString()
       {
           return Bar;
       }
   }
   static void Main()
   {
       var param = Expression.Parameter(typeof(Foo), "foo");
       var assign = Expression.AssignProperty(
           param,
           typeof(Foo).GetProperty("Bar"),
           Expression.Constant("def", typeof(string)));
       var writeLine = Expression.Call(
           typeof(Console).GetMethod("WriteLine", new[] { typeof(object) }),
           param);

       var action = Expression.Lambda<Action<Foo>>(Expression.Comma(assign, writeLine), param);
       var actionDel = action.Compile();
       Foo foo = new Foo();
       actionDel(foo);
   }

And of course, there are obvious issues with existing LINQ implementations: if you use some of the new constructs, you should expect your legacy LINQ provider to barf; and indeed, most of the new options simply don't make sense for a database call, so we shouldn't expect too much to change in LINQ-to-SQL/EF.

Express yourself

I thought I'd start by having a look at expressions - in particular System.Linq.Expressions.Expression.

Expression is an important part of the glue that makes LINQ work, but it has been almost completely hidden away by the spectacular job that C# 3.0 makes of lambda statements and LINQ.

For example, consider the following C# 3.0 query:

    var qry = from foo in source
where foo.Bar == "abc"
select foo;

Because of how query syntax is interpreted, this is identical to the following:

    var qry = source.Where(foo => foo.Bar == "abc"); // Sample A

But what does this mean? Well, first it depends on what our "source" is, or more accurately, whether our Where() method accepts a delegate or an expression tree. For LINQ-to-Objects, then the Where will accept a delegate (such as Func<T, bool>), and so (keeping the extension method syntax) this is identical to:

    var qry = source.Where(delegate(Foo foo) {
return foo.Bar == "abc"; });

However, for most other LINQ providers, it is likely that the Where method accepts an expression tree instead (such as Expression<Func<T,bool>>). So what is an expression tree? The short and imprecise answer is that is is an object representation of code - similar in some (very limited) ways to things like CodeDom - but aimed squarely at providing LINQ support - i.e. all the operations you might need for every-day queries, and the ability to point to framework methods for things that can't be expressed purely in expressions.

Doing It The Hard Way

So lets dissect our example: looking at the delegate version, you can see that the function (the argument to Where) accepts an argument called "foo" (of type Foo), performs member-access (.Bar), and performs an equality test with the string constant "abc". So lets try writing that (as an expression) ourselves:

    ParameterExpression foo = Expression.Parameter(typeof(Foo), "foo");
MemberExpression bar = Expression.PropertyOrField(foo, "Bar");
ConstantExpression abc = Expression.Constant("abc", typeof(string));
BinaryExpression test = Expression.Equal(bar, abc);

Expression<Func<Foo, bool>> lambda =
Expression.Lambda<Func<Foo, bool>>( test, foo);
var qry = source.Where(lambda);

Yikes! That looks like a lot of work! And you'd be right... but take it step-by-step and it makes sense:

• We declare a parameter "foo" of type Foo
• We perform member-access to get foo.Bar
• We define a string constant "abc"
• We test the value of .Bar against this constant
• Finally, we wrap the whole thing up in a lambda; this is just our way of baking the expression into something usable (and note that we need to explicitly re-state the parameter we expect).

[update] Note that the expression is typed using Expression<T>, where T is a delegate-type that reflects what we want. In this case we wan't to use the method as a predicate - i.e. to accept a Foo and return a bool - so we use Expression<Func<Foo,bool>>.

Doing It The Easy Way

The good news is that in most cases, we simply don't need to do any of this; the compiler does all the hard work for us; in fact, it can use a number of tricks that can't be done conveniently in regular C#, such as pointing directly at a MethodInfo for the "get" (.Bar); here's what reflector shows for our original "Sample A":

    ParameterExpression CS$0$0000;
IQueryable<Foo> qry = source.Where<Foo>(Expression.Lambda<Func<Foo, bool>>(Expression.Equal(Expression.Property(CS$0$0000 = Expression.Parameter(typeof(Foo), "foo"), (MethodInfo) methodof(Foo.get_Bar)), Expression.Constant("abc", typeof(string)), false, (MethodInfo) methodof(string.op_Equality)), new ParameterExpression[] { CS$0$0000 }));

OK, that isn't the easiest code to read... it is mainly the same as our previous example (but with explicit generics and "params" values). The parameter usage (CS$0$0000) looks tricky, but is still the same - just initialised and used in the same code block.

The two big differences are in how ".Bar" and "==" are performed; note the use of "methodof(Foo.get_Bar)" and "methodof(string.op_Equality)". No, this isn't a C# keyword you didn't know about - it is simply reflector doing the best job it can of displaying something that isn't valid C#, but is valid IL - using a MethodInfo directly instead of via reflection. In our hand-cranked version, the Expression API will get the same answer, but needs to jump through a few more hoops first.

So Why Bother?

It would be valid, at this point, to ask: "If the compiler can write expressions for me, and do it better, why should I care?". And in most day-to-day coding you would be right: please don't start re-writing your LINQ queries with hand-cranked expressions! And in particular, they are pretty-much a nightmare to use (manually) with anonymous types. However, they do have some intersting possibilities. For regular LINQ (even LINQ-to-Objects via .AsQueryable()), this can be useful for things like:

• Dynamic filters / sorts / etc based on properties that cannot be known at compile-time
• General expression-tree manipulation: merging trees (at InvocationExpression nodes), re-forming trees, etc

But for me, a more common-place usage is in using expressions as the basis of a micro-compiler: a hidden gem of an Expression<T> is the Compile() method; this lets us turn our lambda into a typed delegate, ready for use. But this isn't using reflection (when executed): it creates regular IL in a dynamic assembly that can be invoked very efficiently. This is as simple as:

    Func<Foo, bool> predicate = lambda.Compile();
Foo obj = new Foo { Bar = "abc" };
bool isAbc = predicate(obj);

Now, obviously there is some cost to this:

• we need to build an expression tree (with the reflection lookups etc)
• the library code needs to parse the expression tree (including validation), and emit IL

So this isn't something we'd want to do every time we call the method - but stick the delegate creation in some start-up code (perhaps in a static constructor / type initializer, storing it in a static readonly field) and you have a powerful tool.

So What Can We Do?

So far, I've only given a very small glimpse of the expression capabilities available, but the list is quite comprehensive, with no fewer than 60 different methods. This covers most of the common things you want to do, including:

• all common operators
• branching (conditional)
• object construction
• collection / array construction
• member access
• invocation (to both regular .NET methods and to pre-existing lambda expressions)
• casting / conversion

The biggest thing to note is that expression-trees are designed to encapsulate a functional statement; in particular:

• it doesn't lend itself to mutating existing instances
• it doesn't lend itself to writing a series of statements (unless you can chain them via a fluent API or an operator such as +)
• it should return something (i.e. not Action<T>)

What I mean is that you can't write the following (either in C# or manually):

    Expression<Action<Foo>> action = foo =>
{
  foo.Bar = "def";
  Console.WriteLine(foo);
};

since it fails all 3 conditions.

Example

So far, I've just tried to give a flavor of what you can do with expression trees. I've covered some more of this in various places, that might be interesting:

• Generic operators [overview | usage] - i.e. +-/* with generic T; this is used in MiscUtil as part of the Push LINQ code
• Object cloning [here] - efficient object cloning without the pain
• LINQ object construction [here]
• Partial LINQ projections [here]

I hope that has given you a taste for expressions, and a few ideas for when to use them.