LINQ Expression tree to generate prefix notation of expressions


Yesterday I was goint through one of the LINQ hands on lab. I was always interested by the new Expression tree in C#3.0 and one of the expression tree sample in the lab grabbed my attention. I built onto it to create a postfix notation generator from any lambda expression.


What are Expression trees


Expression tree is a very interesting concept which allows creation of in-memory expression-tree’s out of lambda expressions and then manipulate/inspect the expression as data. Expression trees are created as follows

Expression<Func<int, bool>> filter = n => !((n * 3) < 5);

Now filter contains the expression n => !((n * 3) < 5) as data and it can be manipulated and changed at will.


Pre-fix notation generation


This Expression tree is just as any other tree and can be traversed preorder to generate the prefix notation of the expression. So given the expression !((n * 3) < 5) it should be easy to generate the prefix form as in ! ( < ( * ( n  3 ) 5 )).


I wrote up a small extension method that works on Expressions to print the post fix notation doing a preorder traversal as follows

static void PrefixForm(this Expression exp)
{
if (exp is BinaryExpression)
{
BinaryExpression binEx = (BinaryExpression)exp;
Console.Write(” {0} “, NodeTypeLookUp[(int)binEx.NodeType]);
Console.Write(“(“);
binEx.Left.PrefixForm();
binEx.Right.PrefixForm();
Console.Write(“)”);
}
else if (exp is UnaryExpression)
{
UnaryExpression unEx = (UnaryExpression) exp;
Console.Write(” {0} “, NodeTypeLookUp[(int)unEx.NodeType]);
Console.Write(“(“);
unEx.Operand.PrefixForm();
Console.Write(“)”);

}
else if (exp is ParameterExpression)
{
Console.Write(” {0} “, ((ParameterExpression)exp).Name);
}
else if (exp is ConstantExpression)
{
Console.Write(” {0} “, ((ConstantExpression)exp).Value);
}
else
{
Console.WriteLine(“{0} is not yet supported”, exp.GetType().FullName);
}
}

Expression<Func<int, bool>> filter = n => !((n * 3) < 5);
filter.Body.PrefixForm();


Not all types of expressions like method call, delegate invokes are supported here. The tree uses ExpressionType enum to represent the operators and so I wrote a lookup table to convert them to the operator they represents. I should’ve used the enum.GetDescription but was feeling to lazy to get that up 🙂


The complete code is available here. You’ll need Visual Studio 8 and the Linq preview for RTM to build and run it.

Comments (5)

  1. nicolas says:

    very neat exemple 😉

  2. zproxy says:

    After you compile such an expression, why cant I get it’s IL via reflection? It throws invalid operation while doing it.

  3. Rob Conery says:

    LINQ: How To Use LINQ To Query Just About Anything

  4. Henn Sarv says:

    I have extended and edited a bit Your function PrefixForm:

    Might be interested

    With bests

    henn@sarv.ee

    ——————–

           public static void PrefixForm(this Expression exp)

           {

               if (exp is BinaryExpression)

               {

                   BinaryExpression binEx = (BinaryExpression)exp;

                   Console.Write(" {0} ", binEx.NodeType);

                   Console.Write("(");

                   binEx.Left.PrefixForm();

                   Console.Write(",");

                   binEx.Right.PrefixForm();

                   Console.Write(")");

               }

               else if (exp is ConditionalExpression)

               {

                   ConditionalExpression condEx = (ConditionalExpression)exp;

                   Console.Write(" {0} ", condEx.NodeType);

                   Console.Write("(");

                   condEx.Test.PrefixForm();

                   Console.Write("?");

                   condEx.IfTrue.PrefixForm();

                   Console.Write(":");

                   condEx.IfFalse.PrefixForm();

                   Console.Write(")");

               }

               else if (exp is UnaryExpression)

               {

                   UnaryExpression unEx = (UnaryExpression)exp;

                   Console.Write(" {0} ", unEx.NodeType);

                   Console.Write("(");

                   unEx.Operand.PrefixForm();

                   Console.Write(")");

               }

               else if (exp is ParameterExpression)

               {

                   Console.Write(" {0} ", ((ParameterExpression)exp).Name);

               }

               else if (exp is ConstantExpression)

               {

                   Console.Write(" {0} ", ((ConstantExpression)exp).Value);

               }

               else

               {

                   Console.WriteLine("{0} is not yet supported", exp.GetType().FullName);

               }

           }

       }

  5. How the expression tree is helpful. Is there any benifit to use expression tree or it is only simplify the code structure.