Thursday, November 23, 2006 9:08 AM bart

DynCalc - Dynamic Compilation Illustrated - Part 4: C# 3.0 Expression Trees

Introduction

In the previous posts on DynCalc, we explored how to write a simple parser for simple calculations, transforming it from infix to postfix and finally to a tree that can be interpreted or compiled for execution of the calculation.

In a short summary, we did the following:

  • Infix to postfix: The input expression ((1+2)+3)*2-8/4 is translated into 1 2 + 3 + 2 * 8 4 / -.
  • Postfix to expression tree: 1 2 + 3 + 2 * 8 4 / - is translated into a tree representation like this:

    +Sub
     +Mul
      +Add
       +Add
        1
        2
       3
      2
     +Div
      8
      4

  • Expression tree to IL: The real dynamic compilation turns the tree above into the following piece of IL, ready for execution:

    ldc.i4.s 1
    ldc.i4.s 2
    add
    ldc.i4.s 3
    add
    ldc.i4.s 2
    mul
    ldc.i4.s 8
    ldc.i4.s 4
    div
    add

As of C# 3.0, there's library support for expression trees and compilation of these. In this post, we'll transform our DynCalc sample into an equivalent application using C# 3.0 Expression Trees.

 

Building the Expression Tree

As illustrated in Part 2: Building an expression tree we take a queue of MathOpOrVal tokens (representing either a mathematical operation or an integer value) and turn it into an expression tree as follows:

static TreeNode ToTree(Queue<MathOpOrVal> q) { Stack<TreeNode> stack = new Stack<TreeNode>(); foreach (MathOpOrVal mv in q) { if (mv.Value != null) stack.Push(new TreeNode(mv.Value.Value)); else { TreeNode right = stack.Pop(); TreeNode left = stack.Pop(); stack.Push(new TreeNode(mv.Op.Value, left, right)); } } return stack.Pop(); }

In here, the TreeNode was an internal class to represent a tree node consisting of an operation together with a left and right node. All of this can be replaced by the C# 3.0 Expression Trees, as follows:

1 static Expression<Func<int>> ToTree2(Queue<MathOpOrVal> q) 2 { 3 Stack<Expression> stack = new Stack<Expression>(); 4 5 foreach (MathOpOrVal mv in q) 6 { 7 if (mv.Value != null) 8 stack.Push(Expression.Constant(mv.Value.Value)); 9 else 10 { 11 Expression right = stack.Pop(); 12 Expression left = stack.Pop(); 13 switch (mv.Op.Value) 14 { 15 case MathOp.Add: 16 stack.Push(Expression.Add(left, right)); 17 break; 18 case MathOp.Sub: 19 stack.Push(Expression.Subtract(left, right)); 20 break; 21 case MathOp.Mul: 22 stack.Push(Expression.Multiply(left, right)); 23 break; 24 case MathOp.Div: 25 stack.Push(Expression.Divide(left, right)); 26 break; 27 case MathOp.Mod: 28 stack.Push(Expression.Modulo(left, right)); 29 break; 30 } 31 } 32 } 33 34 return Expression<Func<int>>.Lambda<Func<int>>( 35 stack.Pop(), 36 new ParameterExpression[0] 37 ); 38 }

Let's explain this code step-by-step:

  • The signature (line 1) indicates we consume the same queue as we did before, but this time we return an Expression (namespace System.BLOCKED EXPRESSION supplied by the Orcas C# 3.0 Framework. The Expression<Func<int>> indicates that the expression represents a function with return type int. Func<int> is a generic type "instance" of Func<R> in which R stands for "return type". Basically Func<R> is a delegate with signature public delegate R Func<R>();. In case the expression tree would consume a parameter, one could use Expression<Func<int,int>> or Expression<Func<int,int,int>> (2 int parameters).
  • Instead of building a stack of custom tree nodes, we now build a Stack<Expression> as shown in line 3.
  • Next, we iterate over the queue in lines 5 to 32.
    • In case the value of the MathOpOrVal object in the queue is set, we have to add a constant value to the stack, which is constructed via the factory method Expression.Constant in line 8.
    • Otherwise an operation will be set. In this case, we have to pop both arguments to the binary operation from the stack (lines 11, 12) and do case analysis based on the binary operation desired (lines 13 to 30). To represent a binary operation in the tree, one uses the Expression.<operation>(Expression left, Expression right) factory method.
  • Finally (line 34), the resulting expression is popped from the stack and wrapped in a lambda expression that can be returned. Notice the use of ParameterExpression[0] to indicate no parameters are required.

The cool thing of the built expression is that it doesn't require manual compilation as we did in Part 3: Compilation to IL. Instead we can just call Compile() on the expression. To illustrate this, the Main method is changed as follows:

1 static void Main(string[] args) 2 { 3 Console.WriteLine("Dynamic calculator"); 4 Console.WriteLine("------------------"); 5 Console.WriteLine(); 6 7 Console.Write("Expression: "); 8 string expr = Console.ReadLine(); 9 10 Queue<MathOpOrVal> q = Expr.InfixToPostfix(expr); 11 12 Console.WriteLine(); 13 Console.Write("Postfix representation: "); 14 Print(q); 15 16 Console.WriteLine(); 17 Console.WriteLine("Tree representation:"); 18 //TreeNode tree = ToTree(q); 19 //Print(tree); 20 Expression<Func<int>> f = ToTree2(q); 21 StringBuilder sb = new StringBuilder(); 22 f.BuildString(sb); 23 Console.WriteLine(sb.ToString()); 24 25 Console.WriteLine(); 26 Console.Write("Dynamic calculation: "); 27 //Console.WriteLine("Result = {0}", Execute(tree)); 28 Console.WriteLine("Result = {0}", f.Compile().Invoke()); 29 }

As you can see (line 28), execution is piece of cake thanks to the System.Expressions library. Also, printing the tree is relatively straightforward using a StringBuilder (lines 20 to 23). A sample execution of this application is shown below:

Dynamic calculator ------------------ Expression: ((1+2)+3)*2-8/4 Postfix representation: 1 2 Add 3 Add 2 Mul 8 4 Div Sub Tree representation: () => Subtract(Multiply(Add(Add(1, 2), 3), 2), Divide(8, 4)) Dynamic calculation: Result = 10

Notice the equivalence of our tree representation, i.e.

+Sub
 +Mul
  +Add
   +Add
    1
    2
   3
  2
 +Div
  8
  4

and the C# 3.0 Expression Tree lambda expression, i.e.

() => Subtract(Multiply(Add(Add(1, 2), 3), 2), Divide(8, 4))

Stay tuned for even more Expression Tree fun in the future.

Del.icio.us | Digg It | Technorati | Blinklist | Furl | reddit | DotNetKicks

Filed under:

Comments

# The IQueryable tales - LINQ to LDAP - Part 0

Thursday, April 05, 2007 7:04 PM by B# .NET Blog

Here we are again for some cool LINQ stuff. In the past I've been blogging on C# 3.0 language innovation

# The IQueryable tales - LINQ to LDAP - Part 0: Introduction

Friday, April 06, 2007 5:04 AM by B# .NET Blog

Here we are again for some cool LINQ stuff. In the past I've been blogging on C# 3.0 language innovation

# Introducing “The C# Ducktaper” – Bridging the dynamic world with the static world

Monday, November 10, 2008 7:58 AM by B# .NET Blog

Why this is not a C# 4.0 blog post… By now most of you have probably heard about the dynamic capabilities