## 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.**factory method.*<operation>*(Expression left, Expression right) - 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.

Filed under: C# 3.0

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

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

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

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