Аппликация Expressions

    Добрый день.

    Просматривая недавно чужой код, наткнулся на довольно интересную задачу о 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)) — ее придется вызывать несколько раз.
    Поделиться публикацией

    Комментарии 16

      +9
      You are not a Sane, you are insane :)
      В хорошем смысле :)
        +2
        Я тоже использую данный подход в своём проекте. Однако, не понимаю, почему разработчики C# не могли добавить нативную поддержку разворачивания экспрешнов в язык. Лично я не вижу никаких концептуальных проблем. В вашем примере
        Expression<Func<int, int, int, int>> g = (a, b, c) => f(a+b,b)*c;
        
        f не может быть воспринята никак, кроме вызова делегата, а значит её можно подставить в экспрешн. Было бы круто =)
          0
          Можно спросить Липперта, но я думаю, он ответит, что просто незачем.
            0
            Ну, наверное, потому, что экспрешены — всё же навеска. Кроме того, это хороший задел добавить фичу в следующую версию шорпия :)
              +1
              Я бы не сказал, что expression — это навеска. Это мощный инструмент, на основе которого построен LINQ2* и, например, в .net 4 экспрешенны получили достаточно сильное развитие вполть до возможности представлять в expressions целые методы.
                0
                Я имел в виду под «навеской» не малозначимость инструмента для платформы, а степень его интеграции в язык.

                А причина отсутствия разворачивания экспрешнов, возможно, — их генерация во время компиляции и сложность с инициализацией замыканий.
                  0
                  Да, очень похоже на замыкания. Плюс f может стать рекурсивной и вообще здесь попахивает проблемой остановки.
                    0
                    С замыканиями по-моему проблем не должно быть. Ваш метод ведь работает с замыканиями?

                    А вот с рекурсией да, могут возникнуть проблемы.
            +2
            Есть опыт написание подобного визитора, но только для иных целей:
            Полученные выражения могут использоваться как для IQueryable так и для IEnumerable, если инетерсно — могу попробовать написать статью :)
              0
              В смысле безопасно использованы: добавляетяс проверка на null
                +1
                А можно в двух словах, для чего конкретно?
                  +2
                  наиример, есть экспрешен вида: Expression<Func<Entity, bool>> f = (e) => e.Field.Other.Name == "qwe";
                  Если передавать это в IQueryable — все будет хорошо. Есди сделать f.Compile().Invoke(new Entity()) — получим NullReferenceException если какое-то поле в цепочке будет Null.
                  Мой Visitor превращает такое выражение во что-то типа Expression<Func<Entity, bool>> f = (e) => e != nul && e.Field != null && e.Field.Other != null && e.Field.Other.Name == "qwe";
                    0
                    использую в своих проектах этот подход, вполне читаем, легко был понят коллегами.
                    //Groovy:
                    bossName = Employee?.Supervisor?.Manager?.Boss?.Name
                    //C#:
                    bossName = Nullify.Get(Employee, e => e.Supervisor, s => s.Manager, m => m.Boss, b => b.Name);
                +2
                А чем вы рисовали такую красивую схему?
                  +2
                  XMind
                  +1
                  Клево, но такие подходы интересны небольших приложений, а на практике, когда дело доходит до бизнес функции, советую использовать Specification Pattern, который можно легко тестировать и внести в документацию на систему.

                  Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                  Самое читаемое