James Arendt

Serializing LINQ expression trees

I got simple LINQ expression trees to serialize last night. As I expected, the direct approach is to create a parallel set of expression types for each type in System.Linq.Expressions. With a set of serializable expression types, serialization is a snap. Here's what the code needs to do:

For Serialization

1. Perform partial evaluation on the LINQ expression tree. See this article by Matt Warren for code that supports partial evaluation. See my previous post for why this step is necessary.
2. Map each LINQ expression to a corresponding serializable expression. A visitor class greatly simplifies this step.
3. Serialize the expression tree. I tested with the BinaryFormatter, but I'm confident the DataContractSerializer would work as well with its support for [Serializable] types.

For De-serialization

1. De-serialize the expression tree.
2. Map each serializable expression back to its original LINQ expression. Again, a visitor class is recommended for this step.
3. Use the expression tree.

As of now, my code supports lambda, parameter, constant, methodcall, and a convert expressions. To support the rest, it should be just a matter of implementing the remaining expression types as the proof of concept worked.

LINQ expression visualizer

Much like how Mole is useful as you learn to work with WPF, having a visualizer for LINQ expressions comes in handy as well. Visual Studio 2008 comes with a sample code for LINQ including code for a visualizer.

Updated versions of the sample code can be found here:

C# Code Samples

Working with LINQ expression trees

For some code I'm working on, I've been teaching myself how to build and modify expression trees. I can say initially I found myself a little intimidated.

Whether your code modifies elements within the tree, translates the expressions into another form, or simply visualizes the nodes, it will need to recursively visit each node in the tree. There's quite a variety of node types in System.Linq.Expressions. Writing code to support visiting all those node types just isn't my idea of fun.

If you consider for a moment that Microsoft's own libraries had to do just that to support LINQ to SQL, one would imagine that there must be a class in the framework that simplifies this. And there is! The class is ExpressionVisitor.

Of course, it's conveniently marked internal and you can't use it. :-)

Fortunately, code for an ExpressionVisitor is available as part of a how-to article on MSDN:

How to: Implement an Expression Tree Visitor

Expression trees are immutable so you cannot modify the expression nodes in place unlike some other common tree models. Much like how a string operation returns a copy of the string with the modifications in place, the same has to be done with expression trees. Expression tree visitors come to the rescue here to make it easy to visit all the nodes, return copies of the ones you want to keep, and build new nodes for the changes you want to make.

MSDN has a follow up how-to that covers how to do this:

How to: Modify Expression Trees

For the scenario I'm investigating, serializing expression trees, I realized that if I have any hope in getting it to work, I need to evaluate part of the tree to remove references to locally accessed variables (closures) in the lambdas. The reason for this is two-fold:

• C# and Visual Basic implement closures by generating non-serializable classes. Let's say I come up with a solution for creating a serializable set of expression nodes. I would still have the dilemma that these classes were not serializable even though the fields they contain are serializable. We don't have control over how the compiler generates the closures, so it would be best just to get them out of the picture.
• If the idea is to serialize the tree, for persistence or sending over a network, why serialize information that can be calculated once?

I worked through it in my head that to achieve this I would have to walk the tree and find which expression nodes depended on the fields in the closures. Better yet, find the nodes that are not dependent on the parameters passed into the expression. The idea is that if I find nodes that are not dependent on the parameters, I can evaluate them and replace them with constant expressions. This requires finding the node, wrapping the node in a lambda expression, compiling the lambda into a delegate, invoking the delegate, and finally creating a new constant expression with the value returned from the delegate invocation.

The real trick is finding at what level can you replace the nodes with a constant expression. Given enough time, I'm sure I could've figured out a slick way of doing this myself. But, again, I am not a glutton for punishment. LINQ to SQL has to take a similar course of action before it attempts to translate the LINQ expression into a SQL statement. There's got to be code out there that does some of this dirty work for me.

If you look deep enough into System.Data.Linq in Reflector, you'll eventually find something called Funcletize that does this dirty work.

I don't feel comfortable taking code out of Reflector and plugging it into a solution. I have to really "get it" so I can be sure to customize it to my own needs. Finding this information was useful in that it did point me in the right direction. Most LINQ providers need to do this work. Although, I'm not writing a LINQ provider the problem space overlaps a great deal with what I'm trying to do. It was high time I got to reading some articles and blog postings I had bookmarked about implementing custom LINQ providers.

I found just what I was looking for in Matt Warren's series on building an IQueryable provider. Specifically, part 3 of his series he discusses performing partial evaluation to replace expression nodes with constant expressions. The write-up is good and the code even better!

With Matt's code, I can get the expression down to the bare minimum for serialization. The next step will be to transform the tree into a serializable form. I'm not sure if that's necessarily going to be as involved as these steps or if it'll just require a lot of busy work. I'm suspecting more the latter case as my current thinking suggests that I'll be building for all intents and purposes a hierarchy of types that are equivalent to the expression types in System.Linq.Expressions. The difference would be that mine are serializable.

Anonymous types (tuples) come up far short

I like anonymous types in C#. Syntactically, they fit into the language and provide a lightweight means of creating an immutable type. (It is worth pointing out that Visual Basic's anonymous types can be mutable or immutable.) In many other languages, we would call anonymous types a tuple.

The use case for anonymous types is to support the creation of intermediate types when working with statements and expressions inside a method. Where this is primarily useful is with LINQ expressions.

The problem with anonymous types is that they really don't go far enough. It's like being teased.

"We're going to give you a tuple type. Ok, well, not really. It's like a tuple. Unlike a tuple, you can't pass it easily into a method. You can't return it from a method. Oh yea, you can also forget about easily serializing it too. Other than that, sure, we gave you a tuple."

The designers of both the C# and Visual Basic teams went only about a half way to implementing true tuples in their respective languages.

The problem about coming up short with the tuple implementations is that developers want to use them outside of the local method scopes. I recall when the feature was brought out in the open, comments in the blogs from developers asked for taking them the rest of the way.

Where as with nullable types, the language and CLR teams got together to fix the implementation late in the development cycle of .NET 2.0, the same was not done for anonymous types. And that's even with feedback early in the previews of LINQ well ahead of the betas for Orcas. It's worth noting that unlike nullable types, improving the tuple support would not require an adjustment to the CLR.

It's unfortunate because developers, sometimes unwisely, will plod forward trying to make it work with warts and all. We see hacks found in new toolkits like ASP.NET MVC where an anonymous type is expected into a method that specifies System.Object. You lose type information. Unless you read the documentation, you will not know what the format of the anonymous type should be in.

The method that takes the anonymous type then performs reflection pulling out the values for each of the properties. It can store it in dictionary or copy it to yet another anonymous type.

Developers do these tricks because tuples are useful as a means of working with small groups of related data.

The situation is a little reminiscent of anonymous methods in C# 2.0. Where there were lots of examples of good approaches for creating lambdas/closures (LISP, Python, Ruby, ML, F#, Haskell, and others), the team chose to take an approach more akin to the hairball, anonymous inner classes, Sun coughed up in Java. (I used anonymous inner classes a lot in Java. I found them useful. But, I didn't like them.)

Fortunately, the introduction of anonymous methods did not result in "damages" to libraries. It was just an unpleasant syntax that leveraged delegates with additional capabilities. The libraries could go ahead and use delegates as parameters or return values for methods. If a developer chose to use anonymous methods, fine. If not, they could still use the routines in the libraries. (Visual Basic 2005 did not offer support for anonymous methods, but it could use methods that used delegates with their existing language features for delegates.)

With the introduction of lambdas in C# 3.0 and Visual Basic, developers can use a syntax more akin to the languages that long have paved the way. The existing libraries using delegates could be leveraged with the improved syntax without changes in the libraries themselves.

When true tuple support is added to C# 4.0 and the next version of Visual Basic, libraries will more than likely have to be adapted to utilize the improved support. Sure, existing code using reflection may continue to work with the true tuples. But, if developers want to leverage the type safety offered by the ability to declare the tuple types being pass in or returned, adaptations will likely need to be made to the libraries.

You may note I said when and not if true tuple support is added. Although no announcement has been made by either team, I have a hard time seeing the teams not improving the support for tuple-like types in their respective languages. With the push towards immutability and declarative styles of programming in both languages, having a tuple type is extremely useful.

The following recent posts by Jeffrey Palermo and Jon Skeet inspired this post:

Use caution with anonymous types and other new C# language features

C# 4, part 2: Ideas from other community members