Expression Evaluator: A Lightweight C# Compiler Service
While the .NET community eagerly awaits a production version of Roslyn, work must continue. So today we’re looking at another compiler service, Expression Evaluator. While other compiler services are trying to be as comprehensive as possible, here we see one that is going the other direction.
InfoQ: You refer to C# Expression Evaluator as a lightweight library. What makes it lightweight and what would you consider to be a heavyweight library?
Rupert Avery: For its purpose, which is evaluating expressions I consider Expression Evaluator to be lightweight as it is small in size (still under a megabyte), self-contained, not dependent on other non-core libraries (until Antlr) and specific in its function. I would consider Roslyn to be heavyweight as it requires a lot of supporting libraries. Of course each library has its goals, and there are things that Roslyn can do that Expression Evaluator may not ever be capable of doing, such as compiling entire assemblies, but for evaluating small expressions, I believe Expression Evaluator does its job well.
InfoQ: What is Antlr and why did you choose to incorporate it into your library?
Rupert: Antlr (an acronym for ANother Tool for Language Recognition) is a library originally written in Java that allows you to build complex parser code given a special syntax called a grammar. It's like Regex on steroids for language parsing. You can basically write out the rules on how a language works syntactically and Antlr generates the code for you.
Prior to Antlr I had written the parser myself, and it worked for all the basic things an expression evaluator needed to do. I was able to support expressions such as "a + b.method(c,d[e] == f)". The rules were pretty simple. I began running into difficulty as soon as I tried to support lambda syntax. For example, the expression "(a,b) => a == b" stumped me as (a, b) was first being parsed as an argument list, and then I had to contend with parsing everything to the left of the lambda symbol => which could be a block expression. I would have to do some sort of backtracking and throwing generated tokens out. My hand written parser was simply not up to the task.
Antlr made things simple for me and allowed me to focus on writing the code to handle the language cases instead of worrying about the parsing code.
I have to give kudos to the person who wrote the grammar file I am currently using. I found the grammar file from https://antlrcsharp.codeplex.com/. It is a very complete C#4.0 grammar file, and all I had to do was add the code for generating the proper Expressions for each case.
InfoQ: The documentation mentions LINQ expression trees. Can you elaborate on how you use it?
Rupert: LINQ Expressions are being used to store the parsed expression as a data structure. Rather than having to build your own data structure it makes sense to use the existing structure provided by the .NET framework. Expression trees also have the advantage that they can be compiled into .NET functions. With the expression compiled into actual .NET CLR code, evaluating the expression is done by calling the function. The result of having precompiled code is speed. Other libraries that do not use LINQ Expressions evaluate the expression by traversing the equivalent expression tree, executing code in order simulate to simulate code being executed, which is a huge overhead.
For example if you had an expression:
x == a + b
The Expression tree for this would be
node type: Equals
left child node: Parameter Expression x
right child node: (add expression)
node type: Add
left child node: Parameter Expression a
right child node: Parameter Expression b
This could be written in C# code as:
Expression.Equals(Expression.Parameter('x'), Expression.Add(Expression.Parameter('a'), Expression.Parameter('b'));
Expression Evaluator's job then is to parse the expression (using Antlr) and generate the proper Expression tree. Once this expression tree is built it can then be compiled by LINQ into a function. The application using the library can then execute this function as if it had been compiled in the first place. Once compiled to a function the expression tree is no longer really needed, however it can be used to analyze the expression, I believe some users have requested a way to enumerate variables or properties used by the expression. Since the Expression tree encodes the type of each expression it is possible to extract the information this way.
InfoQ: Let’s say you were writing a client-server system. And you needed to send search criteria (i.e,. where clauses) to the server from a client. Would you use this library for that? And if so what would that look like?
Rupert: Expression Evaluator would be useful in this scenario if the model is complex, or the query logic is complex and you allow the client to be able to freely define the query as a string. Expression Evaluator would work on the server side to parse the query and convert it into compiled code.
Well I'm not sure what you mean by how it would look like, but suppose a web application gave the user the ability to define a query using code, given a a set of parameters that the user can access the user could write the query in C# code and this would be sent over as-is to the server for parsing and compiling.
I think the library would prove most useful in this scenario where you need lots of conditional code to be run in your query and performance is needed. Rather than have a lot of conditional branches in your query, you could build a string expression based on the necessary conditions and compile that into the delegate to be run in your query.
The fact that it uses LINQ Expression trees does not limit its use to building dynamic where clauses for LINQ expressions. One of the applications Expression Evaluator is being used for is data binding. In this usage, an XML file stores the layout and uses attributes and special tokens to signify that the text should be data bound instead of interpreted as plain text. The XML elements are patterned after HTML, and tokens are double-curly braces patterned after AngularJS. The result was a layout and templating engine that had the look and feel of HTML/AngularJS with the target output being a set of PowerPoint slides.The layout engine gave developers the flexibility of HTML and Expression Evaluator allowed data to bind to and control the layout and produce rich reports in PowerPoint.
Expression Evaluator is available on CodePlex under the Simplified BSD License.
Mike Keane Dec 21, 2014
Jeremy Stieglitz Dec 21, 2014