Expression Structure

Expressions are trees.  Well, they can be networks if you've removed redundancies, but let's start out as seeing them as trees.  Each node in the expression tree is either a constant node (representing a fixed value) or a function node (representing a function call).  Function nodes have parameters, which are the branches of the tree, and parameters point at other expression nodes.

In the previous post, we were working on creating a closure.  The expression at the heart of the closure was this:

x.AddYears(int.Parse(y.ToString()) + z * k)
Fig. 2.1: The control part of a lambda expression

The expression tree that we can build out of this is like the following:

Expression {
    Function: DateTime.AddYears(int);
    Parameters {
        [0]: x;
        [1]:Expression {
            Function: int.+(int);
            Parameters {
                [0]: Expression {
                    Function: int.Parse(string);
                    Parameters {
                        [0]: null; /* Static Method */
                        [1]: Expression {
                            Function: string.ToString();
                            Parameters {
                                [0]: y;
                            }
                        }
                    }
                }
                [1]: Expression {
                    Function: int.*(int);
                    Parameters {
                        [0]: z;
                        [1]: k;
                    }
                }
            }
        }
    }
}
Fig. 2.2: The tree structure of the expression

Note that we have two types of open variables here.  The variables x and y are parameters, and we will require them to have values before the expression can be evaluated.  The variables z and k are drawn from the lexical environment, and by pointing to their own expression trees, we can effectively insert them directly into the tree.

In the next post, I will write the C# code to encapsulate an expression node, and see how that disassembles into CIL.