An Expression Tree From Scratch

Now that we have taken a expression lambda and converted it to an expression tree and then taken the expression tree and converted it back to the lambda all that is left is to build the expression tree from scratch. If you think about how complex a method can be you can see that this is an equally complex topic. Most of the methods that you need to generate an expression tree from scratch are provided by the Expression static class and its methods.

As a simple example of how this all works, let's create the squaring lambda from scratch. First we need to define the parameter:

ParameterExpression param = Expression.Parameter(
                              typeof(int), "x");

The parameter name "x" is only used in debugging and system messages. Next we need to define the body of the lambda and this is where things can get complicated:

Expression square = Expression.Multiply(param, param);

The Multiply method takes a lefthand side expression and a righthand side expression and multiplies them together. In this case we simply multiply the parameter by itself.

Now we can buld the expression tree:

Expression<Func<int,int>> ExTree = 
        Expression.Lambda<Func<int,int>>(square,param);

There are a number of different ways of creating an expression tree but the Lambda method simply takes the body and parameter and puts them together using the specified delegate type to define the type of the lambda.

Following this we can use the expression tree as if it had been derived from a lambda in the first place. For example:

Func<int, int> MyNewDelegate = ExTree2.Compile();
Console.WriteLine( MyNewDelegate(3).ToString());

will display 9.

The most important point to understand is that you can build an expression tree that corresponds to a multiline method in this way. That is you can only automatically convert a single line expression lambda to an expression tree but you can build much more complex expression trees using the Expression static methods.

Lambda expression and expression trees are used extensively by LINQ but they are a facilities that have much more general uses.

Closure?

You will often hear Javascript and functional programmers talking about “closure” and now you can join in because C# also has “closure” in the form of the variable capture that anonymous methods and lambdas use.

Consider the following code:

int i = 0;
MyHelloDelegateType1 Hello2 = ()=>
 {
  i++;
  MessageBox.Show(i.ToString());
 };
Hello2();
Hello2();
Hello2();
MessageBox.Show(i.ToString());

There is nothing really suprising about this code - the lambda has access to all of the variables that are in scope when it was defined. So each time you call Hello2 the local variable i is incremented. What is more surprising is that this works even if the local variable has gone out of scope and been destroyed as far as the rest of the program is concerned. When you declare a lambda or an anonymous method there is a bond created between it and all of the variables that are in scope when is was defined and this bond continues beyond the lifetime of the variables. 

Usually the way that the function outlives the variables it was defined alongside is that it is referenced by a longer lived variable or returned as the result of a method - see the earlier example. An easier to way to see that this happens is to make int i local to an inner code block.

MyHelloDelegateType1 Hello2;
{ 
  int i = 0;
  Hello2 = () =>
     {
       i++;                                   
       MessageBox.Show(i.ToString());
     };
}
Hello2();
Hello2();
Hello2();
MessageBox.Show(i.ToString());

If you try this you will find that you get a compiler error complaining that i doesn't exist when you try to display it using the Show method. This is reasonable as i is only in scope withing the outer braces. However a call to Hello2 still works as you can discover by deleting the line starting MessageBox. 

This capturing of the variables is generally referred to as a closure.

Although the use of a variable with block scope is a very direct way to show that the captured variable persists it is not the most common way that it occurs. In most cases the function could be referenced by a variable with a longer lifetime because it is declared outside of the method that creates the lambda  or the lambda could be returned as a result by another method. 

For example suppose we define a class member variable:

public partial class Form1 : Form
{
 delegate void mytest();
 mytest test;

and create a function referenced by the test variable in an initialization method:

public Form1()
{
 InitializeComponent();
 int c = 1;
 test = delegate ()
        {
         button1.Text = c.ToString();
         };
 c = 0;
}

Notice that the delegate sets the button's text to the value of c. What value of c do you think is used, 1 or 0?

To find you you have to call the function away from the initialization method:

private void button1_Click(object sender, EventArgs e)
{
 test();
}

Now you can see that the only reason that you can still call the function is that it is referenced by a class member that is in scope for the event handler. You can now also see clearly why there is doubt about the value of c as the variable no longer exists. However the test method captured the variable and its final value before it went out of scope and was destroyed. If you try the program you will find that c is 0. All of the variables captured are initially frozen at their final value before they go out of scope and are destroyed. The functions that capture the variables can change their values but note that all anonymous functions defined within the same scope share the same set of captured variables. 

To demonstrate how subtle the effects of closure can be consider the following example:

MyHelloDelegateType1[] Count=
                 new MyHelloDelegateType1[10];
for(int i=0;i<10;i++)
{
 Count[i] = ()=>
  {
   MessageBox.Show(i.ToString());
  };
}

Notice that we create an array of 10 delegates and each one is the same anonymous method that simply displays the current value of i. What do you think is going to be the result of calling one of the delegates, Count[0] say? 

The simplest thing to do is call each of the delegates:

for (int j = 0; j < 10; j++)
{
 Count[j]();
}

works perfectly and displays the value 10 for each delegate.

What happens is that the variable i is captured when each of the delegates is created but all of the delegates share the same variable with the local environment.

When the outer function changes the variable then all the delegates see the change and, in this case, the delegates’ captured copy of i slowly counts up to 10 as the for loop progresses.

When the loop ends the local version of the variable goes out of scope but the captured copy of i lives on in the delegates and it has the value 10.

Examples of closure can become more complicated than this simple for loop and if you find yourself using such constructions you probably should reconsider and find a more clear expression of what you are trying to do.

However the principle is simple enough; the compiler creates a hidden class wrapper for all of the variables in scope when the delegates are created. If a variable is recreated each time the delegate is created then each delegate will capture a new copy.

For example:

MyHelloDelegateType1[] Count=new
MyHelloDelegateType1[10];
for(int i=0;i<10;i++)
{
  int j = i;
  Count[i] = delegate()
    {
     MessageBox.Show(j.ToString());
    };
};

In this case the variable j is recreated each time through the loop and each delegate captures its own copy.

If you now try calling each delegate in turn you will find that it now displays 0,1,2, and so on, reflecting the value of i at the time the delegate was created.

Notice that j is out of scope when the loop ends so you can’t discover what its current value is – only the captured copies survive the loop.