Application Expressions

Good afternoon.

Looking through someone else’s code recently, I came across a rather interesting problem about IQueryable and Expession trees. I hope the solution will be useful to someone.

The task is to reuse some Expression inside another Expression, for example, we have some f :

Expression> f = (a, b) => a + b;

And we would like to use this f inside the other expression, for example like this:

Expression> g = (a, b, c) => f(a+b,b)*c;

Moreover, it is necessary that the resulting expression be "pure", i.e. suitable for use inside IQueryable (without compiled functions, etc.)



If you try to compile these two lines, it turns out that the definition of g is wrong: 'f' is a 'variable' but is used like a 'method' , which, in in general, it’s clear that f is the root of the expression tree, but not as a function or functor. You can try to write like this:

Expression> g = (a, b, c) => f.Compile()(a+b,b)*c;

But then our expression in the end will look like this:

(a, b, c) => (Invoke(value(ExpressionReducer.Program+<>c__DisplayClass0).f.Compile(), (a + b), b) * c)

Naturally, our IQueryable will not understand this.

The simplest and most obvious idea is simply to substitute f for its body itself - roughly, make an “application” of the term f in g (Honestly, I’m not at all strong at lambda disappearance, but in my opinion it will be the application).

For such an “application” we need to rewrite the expression tree for g a little, specifically, replace the Invoke (Compile ()) call with the body of the function f, and in the body f replace its parameters with the values ​​of the Invoke arguments, that is, from:

(a, b, c) => f.Compile()(a+b,b)*c

receive

(a, b, c) => ((a+b)+b)*c

To get started, let's get rid of the bulky Invoke (Compile) and replace it with such an extension method:

public static T Apply(this Expression> expression, T1 t1, T2 t2)
{
	return expression.Compile()(t1, t2);
}
//...
Expression> g = (a, b, c) => f.Apply(a + b, b) * c;

In fact, the body of the Apply function is not important - it will never be called during the conversion, but it is useful to have a valid body if someone uses g without simplification.

Now take a closer look at the resulting tree:


Actually, here are the steps to be taken:

1. Find the call to the Apply method.
2. Get the lambda function f from the first argument to the Apply function.
3. Replace the arguments in the lambda body with the remaining parameters of the Apply function.
4. Replace in the .Call tree with body f.

The first item is easy enough to do - we use the ExpressionVisitor class from the System.Linq.Expressions namespace. This is a very convenient class that allows you to not only visit all nodes of the expression tree, but also rewrite part of it (for more details, see http://msdn.microsoft.com/en-us/library/bb546136%28v=vs.90%29.aspx ) We assume that the Apply method is in the ExpressionReductor class:

private class InvokerVisitor : ExpressionVisitor
{
	protected override Expression VisitMethodCall(MethodCallExpression node)
	{
		if (node.Method.DeclaringType == typeof (ExpressionReductor) && node.Method.Name == "Apply")
		{
                           // Тут будут остальные пункты
		}
		return base.VisitMethodCall(node);
	}
}

The second point is somewhat more complicated. As you can see from the tree, f has become a field of the auto-generated class ExpressionReducer.Program + <> c__DisplayClass0 - this is how C # acts with all functors or expressions declared in the body of the methods or coming as method parameters. Of the other options, this is a field or property of a named class or the result of a function call.
For simplicity, we will consider only the first case (the rest can be implemented similarly): f is a field of a certain class.

class FieldLambdaFinder : ExpressionVisitor
{
	protected override Expression VisitMember(MemberExpression node)
	{
		var constantExpression = (ConstantExpression) node.Expression;
		var info = (FieldInfo) node.Member;
		var fieldValue = (Expression)info.GetValue(constantExpression.Value);
		return fieldValue;
	}
	public Expression Find(Expression expression)
	{
		return Visit(expression);
	}
}

The third item is quite simple - we will compile a Dictionary (parameter f -> parameter Apply) and replace all the ParameterExpression in the body f:

internal class Replacer : ExpressionVisitor
{
	private Dictionary _replacements;
	public Replacer(IEnumerable what, IEnumerable with)
	{
		_replacements = what.Zip(with, (param, expr) => new { param, expr }).ToDictionary(x => x.param, x => x.expr);
	}
	public Expression Replace(Expression body)
	{
		return Visit(body);
	}
	protected override Expression VisitParameter(ParameterExpression node)
	{
		Expression replacement;
		return _replacements.TryGetValue(node, out replacement) ? replacement : base.VisitParameter(node);
	}
}

The last item will show everything in assembly:

private class InvokerVisitor : ExpressionVisitor
{
	protected override Expression VisitMethodCall(MethodCallExpression node)
	{
		if (node.Method.DeclaringType == typeof (ExpressionReductor) && node.Method.Name == "Apply")
		{
			var lambda = GetLambda(node.Arguments[0]);
			return Replace(lambda, node.Arguments.Skip(1));
		}
		return base.VisitMethodCall(node);
	}
	private Expression Replace(LambdaExpression lambda, IEnumerable arguments)
	{
		var replacer = new Replacer(lambda.Parameters, arguments);
		return replacer.Replace(lambda.Body);
	}
	private LambdaExpression GetLambda(Expression expression)
	{
		var finder = new FieldLambdaFinder();
		return (LambdaExpression) finder.Find(expression);
	}
}

Simplify method itself:

public static Expression Simplify(this Expression expression)
{
	var invoker = new InvokerVisitor();
	return (Expression) invoker.Visit(expression);
}

Everything at once can be found here .

As a result, we got what we wanted:

Expression> f = (a, b) => a + b;
Expression> g = (a, b, c) => f.Apply(a + b, b)*c;
g = g.Simplify();

The remaining problems:

1. How to get f in other cases.
2. If the Apply parameters are calls to other functions that have side effects, then the substitution is incorrect. In our case, this cannot be, since we are operating with IQueryable, but you should keep this in mind.
3. The Simplify function does not collapse calculations: f.Apply (5, 5) simplifies to (5 + 5), and not to (10).
4. The Simplify function is not recursive, that is, on such examples - f.Apply (a, f.Apply (b, c)) - it will have to be called several times.