Как стать автором
Обновить

Аппликация Expressions

Время на прочтение 4 мин
Количество просмотров 4.6K
Добрый день.

Просматривая недавно чужой код, наткнулся на довольно интересную задачу о IQueryable и Expession trees. Надеюсь, решение будет кому-нибудь полезно.

Задача заключается в том, чтобы повторно использовать некоторый Expression внутри другого Expression, например, у нас есть некий f:

Expression<Func<int, int, int>> f = (a, b) => a + b;


И мы бы хотели использовать этот f внтури другого expression, например так:

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


Причем необходимо, чтобы результирующий expression был «чистым», т.е. пригодным для использования внутри IQueryable (без скомпилированных функций и т.п.)



Если попробовать скомпилировать эти две строчки, то окажется, что определение g ошибочно: 'f' is a 'variable' but is used like a 'method', что, в общем-то и понятно, f — это корень дерева выражений, а ни как не функция или функтор. Можно попробовать написать так:
Expression<Func<int, int, int, int>> g = (a, b, c) => f.Compile()(a+b,b)*c;


Но тогда наше выражение в итоге будет выглядеть так:

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

Естественно, наш IQueryable такого не поймет.

Самая простая и очевидная идея — просто подставить вместо f само ее тело — грубо говоря, сделать «аппликацию» терма f в g (Честно говоря, я совсем не силен в лямбда-исчеслении, но по-моему это будет именно аппликация).

Для такой «аппликации» нам нужно немного переписать дерево выражения для g, конкретно — заменить вызов Invoke(Compile()) на тело функции f, и в самом теле f заменить ее параметры на значения аргументов Invoke, то есть из:

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

получить
(a, b, c) => ((a+b)+b)*c


Для начала, давайте избавимся от громоздкого Invoke(Compile) и заменим его на такой вот метод-расширение:

public static T Apply<T,T1,T2>(this Expression<Func<T1,T2,T>> expression, T1 t1, T2 t2)
{
	return expression.Compile()(t1, t2);
}

//...

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


На самом деле тело функции Apply не важно — оно никогда не будет вызвано при преобразовании, но полезно иметь валидное тело, если кто-то будет использовать g без упрощения.

Теперь внимательно приглядимся к получившемуся дереву:


Собственно вот шаги, которые надо сделать:
  1. Найти вызов метода Apply.
  2. Получить лямбда-функцию f из первого аргумента функции Apply.
  3. Заменить в теле лямбды аргументы на остальные параметры функции Apply.
  4. Заменить в дереве .Call на тело f.


Первый пункт сделать достаточно легко — используем класс ExpressionVisitor из пространства имен System.Linq.Expressions. Это очень удобный класс, который позволяет не только посетить все узлы дерева выражений, но и переписать его часть (подробнее — http://msdn.microsoft.com/en-us/library/bb546136%28v=vs.90%29.aspx) Мы предполагаем, что метод Apply находится в классе ExpressionReductor:
private class InvokerVisitor : ExpressionVisitor
{
	protected override Expression VisitMethodCall(MethodCallExpression node)
	{
		if (node.Method.DeclaringType == typeof (ExpressionReductor) && node.Method.Name == "Apply")
		{
                           // Тут будут остальные пункты
		}
		return base.VisitMethodCall(node);
	}
}

Второй пункт несколько сложнее. Как видно из дерева, f стало полем автогенерированного класса ExpressionReducer.Program+<>c__DisplayClass0 — так C# поступает со всеми функторами или выражениями, объявленными в теле методов или пришедшими как параметры методов. Из других возможных вариантов — это поле или свойство именованного класса или результат вызова функции.
Для простоты будем рассматривать только первый случай (остальные можно реализовать аналогично): f — это поле некоего класса.
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);
	}
}

Третий пункт достаточно прост — составим Dictionary (параметр f -> параметр Apply) и заменим все ParameterExpression в теле f:
internal class Replacer : ExpressionVisitor
{
	private Dictionary<ParameterExpression, Expression> _replacements;

	public Replacer(IEnumerable<ParameterExpression> what, IEnumerable<Expression> 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);
	}
}


Последний пункт покажет все в сборе:
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<Expression> 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);
	}
}


Cам метод Simplify:
public static Expression<T> Simplify<T>(this Expression<T> expression)
{
	var invoker = new InvokerVisitor();
	return (Expression<T>) invoker.Visit(expression);
}


Все и сразу можно найти здесь.

В итоге мы получили то, что хотели:
Expression<Func<int, int, int>> f = (a, b) => a + b;
Expression<Func<int, int, int, int>> g = (a, b, c) => f.Apply(a + b, b)*c;

g = g.Simplify();


Оставшиеся проблемы:
  1. Как достать f в других случаях.
  2. Если параметры Apply — это вызовы других функций, у которых есть side-эффекты, то подстановка некорректна. В нашем случае такого быть не может, так как мы оперируем с IQueryable, но стоит иметь это ввиду.
  3. Функция Simplify не сворачивает вычисления: f.Apply(5, 5) упростится до (5+5), а не до (10).
  4. Функция Simplify не рекурсивна, то есть на таких примерах — f.Apply(a, f.Apply(b,c)) — ее придется вызывать несколько раз.
Теги:
Хабы:
+31
Комментарии 16
Комментарии Комментарии 16

Публикации

Истории

Работа

.NET разработчик
66 вакансий

Ближайшие события

Московский туристический хакатон
Дата 23 марта – 7 апреля
Место
Москва Онлайн
Геймтон «DatsEdenSpace» от DatsTeam
Дата 5 – 6 апреля
Время 17:00 – 20:00
Место
Онлайн
PG Bootcamp 2024
Дата 16 апреля
Время 09:30 – 21:00
Место
Минск Онлайн
EvaConf 2024
Дата 16 апреля
Время 11:00 – 16:00
Место
Москва Онлайн