How to reduce a binary/lambda expression?

Question

I have the following function:

public double Probability(Expression<Func<double, bool>> predicate)
{
    var expr = BinaryExpression.Lambda(predicate);  
    // Implementation
}

that I call like this:

Probability(x => x > 3 && x > 4 && x > 5)

When I debug my code I can see that expr looks like this: () => x => (((x > 3) AndAlso (x > 4)) AndAlso (x > 5))

I would like to be able to reduce it to: () => x => (x > 5))

Question: Is there something that I can use out of the box or do I have to implement this on my own?

Bonus question: What is the difference between LambdaExpression and BinaryExpression?

You mean besides changing your call to `Probability(x => x > 5);`? ;) — itsme86, Nov 13 '15 at 20:18
I would not expect to find something that does this, it's essentially (an easy) part of an optimizing compiler. Re bonus: a `LambdaExpression` represents a method that you can call -- it has an argument list and a body. A `BinaryExpression` represents simply a binary operation -- there is no context, no argument list, you can't compile it and call it. — Jon, Nov 13 '15 at 20:19
http://stackoverflow.com/questions/1101841/linq-how-to-perform-max-on-a-property-of-all-objects-in-a-collection-and-ret look at that MaxBy() extension method implementation by @JonSkeet — eran otzap, Nov 13 '15 at 20:21
I would like to be able to call Reduce() on it, but Reduce on BinaryExpression does not do anything. Documentation is also not very sophisticated...:-P — Michal B., Nov 13 '15 at 20:24
`Reduce` has to do with 'extension' Expressions. See [here](https://msdn.microsoft.com/library/system.linq.expressions.expression.reduceextensions%28v=vs.100%29.aspx) and [here](http://stackoverflow.com/questions/2038759/net-4-0-what-does-expression-reduce-do). Basically extension expressions are expressions not part of CLR, rather they're custom to whatever else you're doing. They are generally 'reducible' to CLR expressions. — Shlomo, Nov 13 '15 at 20:28
`BinaryExpression.Lambda()` is just a very confusing way to write `Expression.Lambda()`. It works, because `BinaryExpression` inherits from `Expression`. — svick, Nov 14 '15 at 02:29
@Jon I don't think it's that easy to optimize away (because the pattern is too uncommon to special case the compiler for it) and the .NET JITs surely do not do it because they lack sophisticated data flow tracking and simplifications based on it. — usr, Nov 14 '15 at 20:17

score 0 · Answer 1 · answered Nov 14 '15 at 19:48

I'll start with the second question.
What is the difference between LambdaExpression and BinaryExpression?
The same difference between a function and an expression within the function.
The BinaryExpression is an expression between two (binary) nodes

x > 5

This is a binary expression of type GreaterThan which its left side is a parameter named x and its right side is a constant that has a value of 5.

Expression<Func<double, bool>> add = x => x > 5;

This is a lambda expression that has a binary expression body. (check the add.Body)

This is a naive solution for your question.

class Program
{
    static void Main(string[] args) {
        Expression<Func<double, bool>> predicate = x => x > 3 && x > 4;
        var visitor = new BinaryExpressionVisitor();
        predicate = (Expression<Func<double, bool>>)visitor.Visit(predicate);
    }
}

public class BinaryExpressionVisitor : ExpressionVisitor
{
    private bool root = true;
    private List<ConstantExpression> constants = new List<ConstantExpression>();
    private List<BinaryExpression> binaryExpressions = new List<BinaryExpression>();
    private HashSet<ParameterExpression> @params = new HashSet<ParameterExpression>();

    protected override Expression VisitBinary(BinaryExpression node) {
        if (IsSimpleBinaryExpression(node)) {
            binaryExpressions.Add(node);
        }
        else if (node.NodeType != ExpressionType.AndAlso) {
            return node;
        }

        if (root) {
            root = false;
            Visit(node.Right);
            Visit(node.Left);

            if (@params.Count == 1) {
                var @param = @params.ElementAt(0);
                var hashSet = new HashSet<ExpressionType>(binaryExpressions.Select(be => be.NodeType));

                if (hashSet.Count == 1) {
                    var binaryExpression = binaryExpressions[0];
                    var nodeType = binaryExpression.NodeType;
                    var constant = GetConstantByNodeType(nodeType);

                    return Expression.MakeBinary(nodeType, @param, constant);
                }
            }
        }

        return base.VisitBinary(node);
    }

    protected override Expression VisitConstant(ConstantExpression node) {
        constants.Add(node);

        return base.VisitConstant(node);
    }

    protected override Expression VisitParameter(ParameterExpression node) {
        @params.Add(node);

        return base.VisitParameter(node);
    }

    private bool IsSimpleBinaryExpression(Expression node) {
        return node.NodeType == ExpressionType.GreaterThan || node.NodeType == ExpressionType.LessThan;
    }

    private ConstantExpression GetConstantByNodeType(ExpressionType expressionType) {
        var values = constants.Select(c => c.Value);
        var value = expressionType == ExpressionType.GreaterThan ? values.Max() : values.Min();

        return Expression.Constant(value);
    }
}

How to reduce a binary/lambda expression?

1 Answers1