What does Expression.Reduce() do?

Question

I've been working with expression trees for a few days now and I'm curious to know what Expression.Reduce() does. The msdn documentation is not very helpful as it only states that it "reduces" the expression. Just in case, I tried an example (see below) to check if this method included mathematical reduction, but this doesn't seem to be the case.

Does anyone know what this method does and is it possible to provide a quick example showing it in action? Any good resources out there?

static void Main(string[] args)
{
    Expression<Func<double, double>> func = x => (x + x + x) + Math.Exp(x + x + x);
    Console.WriteLine(func);
    Expression r_func = func.Reduce();
    Console.WriteLine(r_func); // This prints out the same as Console.WriteLine(func)
}

Answer 1

The document you need to look at is expr-tree-spec.pdf.

This is the specification for the expression trees. Read the "2.2 Reducible Nodes" and "4.3.5 Reduce Method" sections.

Basically, this method is intended for people implementing or porting their dynamic langauges to .NET. So that they can create their own nodes that can "reduce" to standard expression tree nodes and can be compiled. There are some "reducible" nodes in the expression trees API, but I don't know whether you can get any practical examples (since all standard expression nodes compile anyway, as the end-user you probably do not care whether they are "reduced" behind the scenes or not).

Yes, MSDN documentation is very basic in this area, because the main source of info and docs for language implementers is on GitHub, with the documentation in its own subfolder.

Answer 2

With a little disassembling, I found that Expression.CanReduce always reutrns false and Expression.Reduce() always returns this. However, there are a few types that override both. LambdaExpression inherits the default implementations, which explains why the expressions that have been tried so far do not work.

One of the types that overrides Reduce() is MemberInitExpression, which led me to the following successful experiment:

class ReduceFinder : ExpressionVisitor {
    public override Expression Visit(Expression node) {
        if (node != null && node.CanReduce) {
            var reduced = node.Reduce();
            Console.WriteLine("Found expression to reduce!");
            Console.WriteLine("Before: {0}: {1}", node.GetType().Name, node);
            Console.WriteLine("After: {0}: {1}", reduced.GetType().Name, reduced);
        }
        return base.Visit(node);
    }
}

class Foo {
    public int x;
    public int y;
}

static class Program {
    static void Main() {
        Expression<Func<int, Foo>> expr = z => new Foo { x = (z + 1), y = (z + 1) };
        new ReduceFinder().Visit(expr);
    }
}

Output:

Found expression to reduce!  
Before: MemberInitExpression: new Foo() {x = (z + 1), y = (z + 1)}  
After: ScopeN: { ... }  

Answer 3

This is a fairly old question but it seems to have a bit of interest, so I'm adding this extra response with information on what the out-of-box .NET stuff does as of right now.

As far as I can tell, Reduce() is only overridden in complex operations that implement an assignment as part of their work. There seem to be three key scenarios.

1. Compound assignments are expanded to discrete binary arithmetic and assignment operations; in other words,

   x += y

   becomes

   x = x + y.

2. Pre-increment and post-increment operators are expanded to their discrete operations. For pre-increment/decrements,

   ++x

   becomes approximately:

   x = x + 1

   and

   x++

   becomes approximately:

   temp = x;
   x = x + 1;
   temp;
   

   I say approximately because the operation is not implemented as a binary operation x + 1 with the left operand being x and the right operand being the constant 1 but as a unary increment/decrement operation. The net effect is the same.

3. Member and list initializers are expanded from their short form to their long form. So:

   new Thing() { Param1 = 4, Param2 = 5 }

   becomes:

   temp = new Thing();
   temp.Param1 = 4;
   temp.Param2 = 5;
   temp;
   

   and:

   new List<int>() { 4, 5 }

   becomes:

   temp = new List<int>();
   temp.Add(4);
   temp.Add(5);
   temp;
   

Whether these changes make it easier or harder for a person to implement something that parses an expression tree is a matter of opinion, but bottom line is that's the level of reduction that seems to come out-of-box in the .NET framework.

Answer 4

Further to the answer by Nick Guerrera, I have found the following expressions that have overridden the CanReduce method:

• AssignBinaryExpression*
• BinaryExpression
• CoalesceConversionBinaryExpression*
• LogicalBinaryExpression*
• SimpleBinaryExpression*
• ListInitExpression
• MemberInitExpression
• UnaryExpression

* Denotes an internal derived type of BinaryExpression according to JustDecompile

Answer 5

im guessing its more for different linq providers to use those to transform certain node types into a simpler ast representation.

since the docs are scant, could be used for common subexpression elimination to eliminate redundant expressions. if your function computed x+x more than once without changing local x, you could simplify it by saving the result of the first expression into a temporary. maybe it would be up to the linq provider to optionally implement these transformations.

or if you had nested BlockExpressions that contained no code ( an expression like {{{}}} ), those could be eliminated, or an empty ConditionalExpression...