Good day. Expression trees, especially when combined with the Visitor pattern, have always been a rather confusing topic. Therefore, the more diverse information on this topic, the more examples, the easier it will be for those who are interested to find something that is clear and useful to them.
The article is built as usual - it starts with the conceptual framework and definitions and ends with examples and ways of use. Table of contents below.Basics of Expression TreesSyntax of Expression Trees ExpressionTypesPattern MatchingNaive VisitorClassic VisitorWell, the goal is not to impose a specific solution or say that one is better than the other. I propose to draw conclusions ourselves, taking into account all the nuances in your case. I will express my opinion on my example.Expression Trees
The basics
First you need to deal with expression trees. They mean the type of Expression or any of its heirs (they will be discussed later). In the usual scenario, the expression / algorithms are presented in the form of executable code / instructions with which the user may not have much to do (mainly execute). The Expression type allows you to represent an expression / algorithm (usually lambdas, but not necessary) as data organized in a tree structure to which the user has access. The tree-like way of organizing information about the algorithm and the name of the class give us "expression trees".For clarity, we will analyze a simple example. Suppose we have lambda(x) => Console.WriteLine (x + 5)This can be represented as the following treeThe root of the tree is the top of the MethodCall , the parameters of the method are also expressions, therefore it can have any number of children.In our case, there is only one descendant - the peak of " ArithmeticOperation ". It contains information about what kind of operation it is and the left and right operands are also expressions. Such a vertex will always have 2 descendants.The operands are represented by a constant ( Constant ) and a parameter ( Parameter ). Such expressions have no descendants.These are very simplified examples, but fully reflect the essence.The main feature of expression trees is that they can be parsed and read all the necessary information about what the algorithm should do. From some point of view, this is the opposite of attributes. Attributes are a means of declarative description of behavior (very conditional, but the ultimate goal is approximately the same). While expression trees are using a function / algorithm to describe data.They are used, for example, in entity framework providers . The application is obvious - to parse the tree of expressions, to understand what should be executed there and to make SQL from this description . Less well-known examples are the moq library for moking . Expression trees are also used in DLR.(dynamic language runtime). Compiler developers use them to ensure compatibility between the dynamic nature and dotnet, instead of generating MSIL .It is also worth mentioning that expression trees are immutable.Syntax
The next thing worth discussing is the syntax. There are 2 main ways:- Creating expression trees through static methods of the Expression class
- Using lambda expressions compiled in Expression
Static Methods of the Expression Class
Creating expression trees through static methods of the Expression class is less commonly used (especially from a user point of view). This is cumbersome, but quite simple, we havea lot of basic bricks at our disposal, from which you can build quite complexthings. Creation happens through static methods since expression constructors have an internal modifier . And this does not mean that you need to uncover reflection.As an example, I will create an expression from the example above:(x) => Console.WriteLine (x + 5)ParameterExpression parameter = Expression.Parameter(typeof(double));
ConstantExpression constant = Expression.Constant(5d, typeof(double));
BinaryExpression add = Expression.Add(parameter, constant);
MethodInfo writeLine = typeof(Console).GetMethod(nameof(Console.WriteLine), new[] { typeof(double) });
MethodCallExpression methodCall = Expression.Call(null, writeLine, add);
Expression<Action<double>> expressionlambda = Expression.Lambda<Action<double>>(methodCall, parameter);
Action<double> delegateLambda = expressionlambda.Compile();
delegateLambda(123321);
This may not be a very convenient way, but it fully reflects the internal structure of expression trees. Plus, this method provides more features and features that can be used in expression trees: starting from loops, conditions, try-catch, goto, assignment, ending with fault blocks, debugging information for breakpoints, dynamic, etc.Lambda expression
Using lambdas as expressions is a more frequent way. It works very simply - the smart compiler at the compilation stage looks at what lambda is used for. And compiles it either into a delegate or into an expression. On an already mastered example, it looks as followsExpression<Action<double>> write = => Console.WriteLine( + 5);
It is worth clarifying such a thing - an expression is an exhaustive description. And it is enough toget the result. Expression trees such as LambdaExpression or its descendants can beconverted to an executable IL. The remaining types cannot be directly converted to executable code (but this does not make much sense).By the way, if someone is critical of fast compilation of an expression, you can take a look at this third-party project.The converse is not true in the general case. A delegate cannot just pick it up and introduce himself as an expression (but this is still possible).Not all lambdas can be converted to expression trees. These include:- Containing assignment operator
- Contributing dynamic
- Asynchronous
- With body (braces)
double variable;
dynamic dynamic;
Expression<Action> assignment = () => variable = 5;
Expression<Func<double>> dynamically = () => dynamic;
Expression<Func<Task>> asynchon = async () => await Task.CompletedTask;
Expression<Action> body = () => { };
Types of Expressions
I suggest a quick look at the available types to represent what opportunities we have. All of them are in the System.Linq.Expressions namespace.I suggest that you first get acquainted with several really interesting and unusual features. The simpler types of expressions I put together in a tablet with a brief description.Dynamic
Using DynamicExpression it is possible to use dynamic and all its features in expression trees. There is a rather confusing API, I sat on this example longer than on all the others combined. All the confusion is provided by a bunch of various flags. And some of them are similar to the ones you are looking for, but they are not necessarily. And when working with dynamic in expression trees, it is difficult to get a talking error. Example:var parameter1 = Expression.Parameter(typeof(object), "name1");
var parameter2 = Expression.Parameter(typeof(object), "name2");
var dynamicParam1 = CSharpArgumentInfo.Create(CSharpArgumentInfoFlags.None, null);
var dynamicParam2 = CSharpArgumentInfo.Create(CSharpArgumentInfoFlags.None, null);
CallSiteBinder csb = Microsoft.CSharp.RuntimeBinder.Binder.BinaryOperation(CSharpBinderFlags.None, ExpressionType.Add, typeof(Program), new[] { dynamicParam1, dynamicParam2 });
var dyno = Expression.Dynamic(csb, typeof(object), parameter1, parameter2);
Expression<Func<dynamic, dynamic, dynamic>> expr = Expression.Lambda<Func<dynamic, dynamic, dynamic>>(dyno, new[] { parameter1, parameter2 });
Func<dynamic, dynamic, dynamic> action = expr.Compile();
var res = action("1", "2");
Console.WriteLine(res);
res = action(1, 2);
Console.WriteLine(res);
I explicitly indicated where the Binder comes from in order to avoid confusion with the binder from System.Reflection. Of interesting things, we can do ref and out parameters, named parameters, unary operations, and in principle, everything that can be done through dynamic, but this will require some skill.Exception catch blocks
The second thing I’ll pay attention to is the try / catch / finally / fault functionality, or rather, the factthat we have access to the fault block. It is not available in C #, but it is in MSIL. This is a kind offinally analog that will be executed in case of any exception. In the example below, an exception will be thrown, after which “Hi” will be displayed and the program will wait for input. Only after that it will fall completely. I do not recommend this practice for use.var throwSmth = Expression.Throw(Expression.Constant(new Exception(), typeof(Exception)));
var log = Expression.Call(null, typeof(Console).GetMethod(nameof(Console.WriteLine), new[] { typeof(string) }), Expression.Constant("Hi", typeof(string)));
var read = Expression.Call(null, typeof(Console).GetMethod(nameof(Console.ReadLine)));
var fault = Expression.TryFault(throwSmth, Expression.Block(new[] { log, read }));
Expression<Action> expr = Expression.Lambda<Action>(fault);
Action compiledExpression = expr.Compile();
compiledExpression();
Brief Description of Available Expression Tree TypesTable
- ExpressionVisitor — . .
- DynamicExpressionVisitor — DynamicExpression ( VisitDynamic)
This information is enough to start comparing the methods of working with expression trees. I decided to parse all this by the example of finding the derivative. I did not foresee all possible options - only basic ones. But if for some reason someone decided to modify and use it, I will be glad to share the improvements through the request to my repository .Pattern matching
So, the task is to make a calculus of derivatives. You can estimate the following: there are a couple of rules for finding the derivative for different types of operations - multiplication, division, etc. Depending on the operation, you must select a specific formula. In such a banal formulation, the task is ideally placed on switch / case . And in the latest version of the language, we were presented with switch / case 2.0 or pattern matching .It's hard to discuss something here. On a hub, such a quantity of code looks cumbersome and poorly read, so I suggest looking at github . For an example of a derivative, it turned out like this:Example public class PatterntMatchingDerivative
{
private readonly MethodInfo _pow = typeof(Math).GetMethod(nameof(Math.Pow));
private readonly MethodInfo _log = typeof(Math).GetMethod(nameof(Math.Log), new[] { typeof(double) });
private readonly ConstantExpression _zero = Expression.Constant(0d, typeof(double));
private readonly ConstantExpression _one = Expression.Constant(1d, typeof(double));
public Expression<Func<double, double>> ParseDerivative(Expression<Func<double, double>> function)
{
return Expression.Lambda<Func<double, double>>(ParseDerivative(function.Body), function.Parameters);
}
private Expression ParseDerivative(Expression function) => function switch
{
BinaryExpression binaryExpr => function.NodeType switch
{
ExpressionType.Add => Expression.Add(ParseDerivative(binaryExpr.Left), ParseDerivative(binaryExpr.Right)),
ExpressionType.Subtract => Expression.Subtract(ParseDerivative(binaryExpr.Left), ParseDerivative(binaryExpr.Right)),
ExpressionType.Multiply => (binaryExpr.Left, binaryExpr.Right) switch
{
(ConstantExpression _, ConstantExpression _) => _zero,
(ConstantExpression constant, ParameterExpression _) => constant,
(ParameterExpression _, ConstantExpression constant) => constant,
_ => Expression.Add(Expression.Multiply(ParseDerivative(binaryExpr.Left), binaryExpr.Right), Expression.Multiply(binaryExpr.Left, ParseDerivative(binaryExpr.Right)))
},
ExpressionType.Divide => (binaryExpr.Left, binaryExpr.Right) switch
{
(ConstantExpression _, ConstantExpression _) => _zero,
(ConstantExpression constant, ParameterExpression parameter) => Expression.Divide(constant, Expression.Multiply(parameter, parameter)),
(ParameterExpression _, ConstantExpression constant) => Expression.Divide(_one, constant),
_ => Expression.Divide(Expression.Subtract(Expression.Multiply(ParseDerivative(binaryExpr.Left), binaryExpr.Right), Expression.Multiply(binaryExpr.Left, ParseDerivative(binaryExpr.Right))), Expression.Multiply(binaryExpr.Right, binaryExpr.Right))
},
},
MethodCallExpression methodCall when methodCall.Method == _pow => (methodCall.Arguments[0], methodCall.Arguments[1]) switch
{
(ConstantExpression constant, ParameterExpression _) => Expression.Multiply(methodCall, Expression.Call(null, _log, constant)),
(ParameterExpression param, ConstantExpression constant) => Expression.Multiply(constant, Expression.Call(null, _pow, param, Expression.Constant((double)constant.Value - 1, typeof(double)))),
(ConstantExpression constant, Expression expression) => Expression.Multiply(Expression.Multiply(ParseDerivative(expression), methodCall), Expression.Call(null, _log, constant)),
},
_ => function.NodeType switch
{
ExpressionType.Constant => _zero,
ExpressionType.Parameter => _one,
_ => throw new OutOfMemoryException("Bitmap best practice")
}
};
}
It looks a bit unusual, but interesting. It was a pleasure to write this - all the conditions fit organically on one line.The example speaks for itself, you can’t describe it better with words.Naive visitor
In such a task, an expression tree visitor immediately comes to mind, which makes a lot of noiseand a little bit of panic among amateurs to discuss agile in the kitchen. “Fear not ignorance, but false knowledge. It’s better not to know anything than to consider truth that which is not true. ” Remembering this wonderful phrase of Tolstoy, acknowledging ignorance and enlisting the support of Google, you can find the following guide .I have this link is the first (after Siberia in 1949) for the query "Expression tree visitor".At first glance, this is exactly what we need. The title of the article fits what we want to do, and the classes in the examples are named with the suffix Visitor .After reviewing the article and making, by analogy for our example with derivatives, we get:Link to github.Examplepublic class CustomDerivativeExpressionTreeVisitor
{
public Expression<Func<double, double>> Visit(Expression<Func<double, double>> function)
{
return Expression.Lambda<Func<double, double>>(Visitor.CreateFromExpression(function.Body).Visit(), function.Parameters);
}
}
public abstract class Visitor
{
protected static readonly MethodInfo Pow = typeof(Math).GetMethod(nameof(Math.Pow));
protected static readonly MethodInfo Log = typeof(Math).GetMethod(nameof(Math.Log), new[] { typeof(double) });
protected readonly ConstantExpression Zero = Expression.Constant(0d, typeof(double));
protected readonly ConstantExpression One = Expression.Constant(1d, typeof(double));
public abstract Expression Visit();
public static Visitor CreateFromExpression(Expression node)
=> node switch
{
BinaryExpression be => new BinaryVisitor(be),
MethodCallExpression mce when mce.Method == Pow => new PowMethodCallVisitor(mce),
_ => new SimpleVisitor(node),
};
}
public class BinaryVisitor : Visitor
{
private readonly BinaryExpression _node;
public BinaryVisitor(BinaryExpression node)
{
_node = node;
}
public override Expression Visit()
=> _node.NodeType switch
{
ExpressionType.Add => Expression.Add(ParseDerivative(binaryExpr.Left), ParseDerivative(binaryExpr.Right)),
ExpressionType.Subtract => Expression.Subtract(ParseDerivative(binaryExpr.Left), ParseDerivative(binaryExpr.Right)),
ExpressionType.Multiply => (binaryExpr.Left, binaryExpr.Right) switch
{
(ConstantExpression _, ConstantExpression _) => _zero,
(ConstantExpression constant, ParameterExpression _) => constant,
(ParameterExpression _, ConstantExpression constant) => constant,
_ => Expression.Add(Expression.Multiply(ParseDerivative(binaryExpr.Left), binaryExpr.Right), Expression.Multiply(binaryExpr.Left, ParseDerivative(binaryExpr.Right)))
},
ExpressionType.Divide => (binaryExpr.Left, binaryExpr.Right) switch
{
(ConstantExpression _, ConstantExpression _) => _zero,
(ConstantExpression constant, ParameterExpression parameter) => Expression.Divide(constant, Expression.Multiply(parameter, parameter)),
(ParameterExpression _, ConstantExpression constant) => Expression.Divide(_one, constant),
_ => Expression.Divide(Expression.Subtract(Expression.Multiply(ParseDerivative(binaryExpr.Left), binaryExpr.Right), Expression.Multiply(binaryExpr.Left, ParseDerivative(binaryExpr.Right))), Expression.Multiply(binaryExpr.Right, binaryExpr.Right))
},
};
}
public class PowMethodCallVisitor : Visitor
{
private readonly MethodCallExpression _node;
public PowMethodCallVisitor(MethodCallExpression node)
{
_node = node;
}
public override Expression Visit()
=> (_node.Arguments[0], _node.Arguments[1]) switch
{
(ConstantExpression constant, ParameterExpression _) => Expression.Multiply(_node, Expression.Call(null, Log, constant)),
(ParameterExpression param, ConstantExpression constant) => Expression.Multiply(constant, Expression.Call(null, Pow, param, Expression.Constant((double)constant.Value - 1, typeof(double)))),
(ConstantExpression constant, Expression expression) => Expression.Multiply(Expression.Multiply(CreateFromExpression(expression).Visit(), _node), Expression.Call(null, Log, constant)),
};
}
public class SimpleVisitor : Visitor
{
private readonly Expression _node;
public SimpleVisitor(Expression node)
{
_node = node;
}
public override Expression Visit()
=> _node.NodeType switch
{
ExpressionType.Constant => Zero,
ExpressionType.Parameter => One,
};
}
In fact - we spread the switch cases for different classes. There were no less of them, magic did not appear. All the same cases, much more lines. And where is the promised double dispatch dispatch?Classic visitor and dual dispatch
Here it’s worth telling about the Visitor template itself , it is also Visitor , which is the basis of Expression tree visitor . Let's analyze it just on the example of expression trees.For a second, suppose we design expression trees. We want to give users the ability to iterate through the expression tree and, depending on the types of nodes (Expression types), do certain actions.The first option is to do nothing. That is, force users to use switch / case. This is not such a bad option. But here there is such a nuance: we spread the logic responsible for a particular type. Simply put, polymorphism and virtual challenges ( aka late binding) make it possible to shift the type definition to the runtime and remove these checks from our code. It is enough for us to have logic that creates an instance of the desired type, then everything will be done by the runtime for us.The second option.The obvious solution is to pull the logic into virtual methods. By overriding the virtual method in each successor, we can forget about switch / case. The mechanism of polymorphic calls will decide for us. The method table will work here, methods will be called by the offset in it. But this is a topic for an entire article, so let's not get carried away. Virtual methods seem to solve our problem. But unfortunately, they create another. For our task, we could add the GetDeriviative () method. But now the expression classes themselves look weird. We could add such methods for all occasions, but they do not fit the general logic of the class. And we still did not provide the opportunity to do something similar to users (in an adequate way, of course). We need to let the user define the logic for each particular type,but keep the polymorphism (which is available to us).Only the efforts of the user to do this will not succeed.This is where the real visitor lies. In the basic type of hierarchy (Expression in our case), we define a method of the formvirtual Expression Accept(ExpressionVisitor visitor);
In the heirs, this method will be overridden.ExpressionVisitor itself is a base class that contains a virtual method with the same signaturefor each type of hierarchy. Using the ExpressionVisitor class as an example, VisitBinary (...), VisitMethodCall (...), VisitConstant (...), VisitParameter (...).These methods are called in the corresponding class of our hierarchy.Those. The Accept method in the BinaryExpression class will look like this:
protected internal override Expression Accept(ExpressionVisitor visitor)
{
return visitor.VisitBinary(this);
}
As a result, in order to define a new behavior, the user only needs to create an heir to the ExpressionVisitor class, in which the corresponding methods for solving one problem will be redefined. In our case, a DerivativeExpressionVisitor is created.Further, we have some objects of the successors of Expression, but which ones are unknown, but not necessary.We call the virtual Accept method with the ExpressionVisitor implementation we need, i.e. with DerivativeExpressionVisitor. Thanks to dynamic dispatching, an overridden implementation of Accept is called, such as a run-time, say BinaryExpression. In the body of this method, we perfectly understand that we are in BinaryExpression, but we don’t know which ExpressionVisitor successor came to us. But since VisitBinary is also virtual, we do not need to know. Again, we simply call by reference to the base class, the call is dynamically (at run time) dispatched and an overridden VisitBinary implementation of the runtime type is called. So much for the double dispatch - ping-pong in the style of “you do it” - “no, you”.What does it give us. In fact, this makes it possible to “add” virtual methods from outside, notchanging the class. It sounds great, but has its downsides:- Some leftist in the form of the Accept method, which is responsible for everything and for nothing at the same time
- The ripple effect of a good hash function is that when you add just one heir to the hierarchy, in the worst case, everyone will have to finish their visitors
But the nature of expression trees allows these costs because of the specifics of working with expressions, because this kind of workarounds is one of their main features.Here you can see all the methods available for overloading.So, let's see how it looks in the end.Link to github.Examplepublic class BuildinExpressionTreeVisitor : ExpressionVisitor
{
private readonly MethodInfo _pow = typeof(Math).GetMethod(nameof(Math.Pow));
private readonly MethodInfo _log = typeof(Math).GetMethod(nameof(Math.Log), new[] { typeof(double) });
private readonly ConstantExpression _zero = Expression.Constant(0d, typeof(double));
private readonly ConstantExpression _one = Expression.Constant(1d, typeof(double));
public Expression<Func<double, double>> GetDerivative(Expression<Func<double, double>> function)
{
return Expression.Lambda<Func<double, double>>(Visit(function.Body), function.Parameters);
}
protected override Expression VisitBinary(BinaryExpression binaryExpr)
=> binaryExpr.NodeType switch
{
ExpressionType.Add => Expression.Add(Visit(binaryExpr.Left), Visit(binaryExpr.Right)),
ExpressionType.Subtract => Expression.Subtract(Visit(binaryExpr.Left), Visit(binaryExpr.Right)),
ExpressionType.Multiply when binaryExpr.Left is ConstantExpression && binaryExpr.Right is ConstantExpression => _zero,
ExpressionType.Multiply when binaryExpr.Left is ConstantExpression && binaryExpr.Right is ParameterExpression => binaryExpr.Left,
ExpressionType.Multiply when binaryExpr.Left is ParameterExpression && binaryExpr.Right is ConstantExpression => binaryExpr.Right,
ExpressionType.Multiply => Expression.Add(Expression.Multiply(Visit(binaryExpr.Left), binaryExpr.Right), Expression.Multiply(binaryExpr.Left, Visit(binaryExpr.Right))),
ExpressionType.Divide when binaryExpr.Left is ConstantExpression && binaryExpr.Right is ConstantExpression => _zero,
ExpressionType.Divide when binaryExpr.Left is ConstantExpression && binaryExpr.Right is ParameterExpression => Expression.Divide(binaryExpr.Left, Expression.Multiply(binaryExpr.Right, binaryExpr.Right)),
ExpressionType.Divide when binaryExpr.Left is ParameterExpression && binaryExpr.Right is ConstantExpression => Expression.Divide(_one, binaryExpr.Right),
ExpressionType.Divide => Expression.Divide(Expression.Subtract(Expression.Multiply(Visit(binaryExpr.Left), binaryExpr.Right), Expression.Multiply(binaryExpr.Left, Visit(binaryExpr.Right))), Expression.Multiply(binaryExpr.Right, binaryExpr.Right)),
};
protected override Expression VisitMethodCall(MethodCallExpression methodCall)
=> (methodCall.Arguments[0], methodCall.Arguments[1]) switch
{
(ConstantExpression constant, ParameterExpression _) => Expression.Multiply(methodCall, Expression.Call(null, _log, constant)),
(ParameterExpression param, ConstantExpression constant) => Expression.Multiply(constant, Expression.Call(null, _pow, param, Expression.Constant((double)constant.Value - 1, typeof(double)))),
(ConstantExpression constant, Expression expression) => Expression.Multiply(Expression.Multiply(Visit(expression), methodCall), Expression.Call(null, _log, constant)),
};
protected override Expression VisitConstant(ConstantExpression _) => _zero;
protected override Expression VisitParameter(ParameterExpression b) => _one;
}
findings
Perhaps, as in most programming tasks, a definite answer cannot be given. Everything, as always, depends on the specific situation. I like the usual pattern matching for my example, because I did not develop it to the scale of industrial development. If this expression would increase uncontrollably, it would be worth thinking about the visitor. And even a naive visitor has the right to life - after all, this is a good way to scatter a large amount of code into classes if the hierarchy has not provided support on its part. And even here there are exceptions.Likewise, the visitor’s support from the hierarchy is a very controversial thing.But I hope that the information provided here is enough to make the right choice.