Jan 19, 2010

Expression, Expression Tree, Lamda, Lamda expression, IQueryable

Expression trees in .net 3.5 provide an abstract way of representing code as a tree of objects, these objects are expressions. As it said, Expression tree is a tree of expressions, and expression tree is also an expression, a composite of expressions. In .net there is no such type ExpressionTree, they are all Expressions.

Expression firstArgExpression = Expression.Constant(2);
Expression secondArgExpression = Expression.Constant(3);
Expression addExpressionTree = Expression.Add(firstArgExpression, secondArgExpression);

Expression, and expression tree is not much fun, until it can do something. So to do something, and we need to compile it into code, and execute the code. This a multiple steps process. First we need to convert the expression tree into a DelegateReadyExpression, then we compile DelegateReadyExpression into delegate instance, which is essentially a method, and finally we execute the method. In .net there is no such class DelegateReadyExpression, it is actually named LambdaExpression. LambdaExpression is an abstract sub-class of Exppression, it has a method "public Delegate Compile();". You may ask, why named LambdaExpression, why not DelegateReadyExpression, I will cover later in this post. The following code does these steps.

LambdaExpression lamdaExpression = Expression.Lambda(addExpressionTree);
Delegate unTypedDelegate = lamdaExpression.Compile();
object untypedResult = unTypedDelegate.DynamicInvoke();
Console.WriteLine(untypedResult);

Seemingly, the above code is not good enough. As LambdaExpression is not strongly typed. We need to create a strongly type LamdaExpression, which is Expression<T>.


Expression<Func<int>> stronglyTypedLamdaExpression = Expression.Lambda<Func<int>>(addExpressionTree);
Func<int> stronglyTypedDelegate = stronglyTypedLamdaExpression.Compile();
int result = stronglyTypedDelegate();
Console.WriteLine(result);

So the purpose of expression, and expression tree is light weight code generation. But it still too complicated to use. If we want to generate the following method,

bool IsStartedWith(string x, string y)
{
  return x.StartsWith(y);
}

We need programatically to do the following.

MethodInfo method = typeof(string).GetMethod("StartsWith", new[] { typeof(string) });
var target = Expression.Parameter(typeof(string), "x");
var methodArg = Expression.Parameter(typeof(string), "y");
Expression[] methodArgs = new[] { methodArg };
Expression call = Expression.Call(target, method, methodArgs);
var lambdaParameters = new[] { target, methodArg };
var lambda = Expression.Lambda<Func<string, string, bool>>(call, lambdaParameters);
var compiled = lambda.Compile();
Console.WriteLine(compiled("First", "Second"));
Console.WriteLine(compiled("First", "Fir"));

Seemingly this is too tedious. It turns out Lamda Expression is very good to represent the an expression tree. Here we just use lamda to represent lamda expression. There are two forms of lambda expression (type Expression), statement lamda, expression lamda. The body of statement lambda expression can contains statements, and expression lambda expression can only contains expression only. We already know that we can use lambda expression represent a anonymous method, delegate, like the following. Both statement lamda and expression can do that.

Func<string, string, bool> IsStartedWith = (x, y) =>
{
    return x.StartsWith(y);
};
//or
Func<string, string, bool> IsStartedWith = (x, y) => x.StartsWith(y);

Console.WriteLine(IsStartedWith("First", "Fir"));

But statement lamda is not good to represent an tree of object, but expression lamda is good to represent a tree because is a tree in syntax. So expression lamda can be converted in a expression tree.

Expression<Func<string, string, bool>> stronglyTypedLamdaExpression = (x, y) => x.StartsWith(y);
Assert.IsTrue(stronglyTypedLamdaExpression is LambdaExpression);

var isStartedWith = stronglyTypedLamdaExpression.Compile();
var result = isStartedWith("First", "Fir");
Assert.IsTrue(result);

So you may understand why DelegateReadyExpression is named as LamdaExpression, because DelegateReadyExpression can be easily expressed as "lambda expression", so lets just call it LamdaExpression. We use "lambda expression" to create expression tree (Expression) then we convert expression tree into DelegateReadyExpression(LamdaExpression) object. LamdaExpression is ready to to complied into delegate. The following error may help you understand this process.

//A lambda expression with a statement body cannot be converted to an expression tree
Expression<Func<int>> y = () => { return 5; };

If you decompile the above code with reflector, it will be the following. But using expression lamda is much elegant want to represent code.

Expression<Func<string, string, bool>> stronglyTypedLamdaExpression = (x, y) => x.StartsWith(y);
//complied to 
ParameterExpression x;
ParameterExpression y;
Expression<Func<string, string, bool>> stronglyTypedLamdaExpression = 
    Expression.Lambda<Func<string, string, bool>>
    (
        Expression.Call(
                          x = Expression.Parameter(typeof(string), "x"), 
                          (MethodInfo)methodof(string.StartsWith), 
                          new Expression[] { y = Expression.Parameter(typeof(string), "y") }
                       ), 
        new ParameterExpression[] { x, y }
    );

In summary, "Both expression lambda expression and statement lambda expression" can be pre-compiled to delegate in compiled time by compiler. "only expression lambda expression" can be used to create expression tree(Expression), "statement lambda expression" can not be compiled to expression tree(Expression object). Expression object can be convert to "LamdaExpression object" or "Expression<T>", then compiled to delegate in runtime. Expression object can be also compiled other forms of code using IQuerable model.