One of the talks I've done in the recent past is called "Evolving .NET". The talk covers the basics of evolutionary computation and uses an example of evolving function implementations. I've only done the talk a couple of times but it was fun to put together and give (I hope I can do the talk more in the future). I use classes in the System.Linq.Expressions namespace to do this. Before 4.0, expressions were immutable, so I had to use some classes to get around that. Now there's an ExpressionVisitor class available to make this a little easier. The ExpressionVisitor class is just the framework - i.e. it's an abstract class. The developer is responsible for handling all of the necessary tree traversal. In this post I'll demonstrate how this works.

Let's say I have two functions that are used in the Collatz Conjecture:

//Expression<Func<int, int>> evenExpression = x => x / 2;
var evenParameter = Expression.Parameter(typeof(int), "x");
var evenExpression = Expression.Lambda<Func<int, int>>(
    Expression.Divide(evenParameter, Expression.Constant(2, typeof(int))),
    evenParameter);

//Expression<Func<int, int>> oddExpression = x => 3 * x + 1;
var oddParameter = Expression.Parameter(typeof(int), "x");
var oddExpression = Expression.Lambda<Func<int, int>>(
    Expression.Add(Expression.Multiply(Expression.Constant(3, typeof(int)), oddParameter), 
        Expression.Constant(1, typeof(int))),
    oddParameter);

I've included comments so you can map the manual creation of the expression to the one-line approach. In my evolution example, I can't declare it the easier way; I have to manually create them, but as you can see, it's not that hard to create expressions.

Now that I have these expressions, I want to mutate them. I'm going to replace the parameters from one expression's body with the body of the other expression. In other words, I want this:

// x => ((3 * x) + 1) / 2
// x => 3 * (x / 2) + 1

I'll show you how I do the first one - the second mutation works the same way:

var newEvenExpression = Expression.Lambda<Func<int, int>>(
    new ReplacementVisitor().Transform(
        evenExpression.Body, evenExpression.Parameters, 
        evenParameter, oddExpression.Body),
    evenParameter);

Simple, right? So ... what's ReplacementVisitor? I'm glad you asked:

internal sealed class ReplacementVisitor 
    : ExpressionVisitor
{
    public Expression Transform(Expression source, 
        ReadOnlyCollection<ParameterExpression> sourceParameters,
        Expression find, Expression replace)
    {
        this.Find = find;
        this.SourceParameters = sourceParameters;
        this.Replace = this.Visit(replace);
        return this.Visit(source);
    }

    private Expression ReplaceNode(Expression node)
    {
        if(node == this.Find)
        {
            return this.Replace;
        }
        else
        {
            return node;
        }
    }

    protected override Expression VisitBinary(BinaryExpression node)
    {
        var result = this.ReplaceNode(node);

        if(result == node)
        {
            switch(node.NodeType)
            {
                case ExpressionType.Add:
                    result = Expression.Add(
                        this.Visit(node.Left), this.Visit(node.Right));
                    break;
                case ExpressionType.Subtract:
                    result = Expression.Subtract(
                        this.Visit(node.Left), this.Visit(node.Right));
                    break;
                case ExpressionType.Multiply:
                    result = Expression.Multiply(
                        this.Visit(node.Left), this.Visit(node.Right));
                    break;
                case ExpressionType.Divide:
                    result = Expression.Divide(
                        this.Visit(node.Left), this.Visit(node.Right));
                    break;
                default:
                    throw new NotSupportedException(string.Format(
                        "Unexpected binary type: {0}", node.NodeType));
            }
        }

        return result;
    }

    protected override Expression VisitParameter(ParameterExpression node)
    {
        Expression result = null;

        if(!this.SourceParameters.Contains(node))
        {
            result = (from sourceParameter in this.SourceParameters
                         where sourceParameter.Name == node.Name
                         select sourceParameter).First();
        }
        else
        {
            result = this.ReplaceNode(node);
        }

        return result;
    }

    protected override Expression VisitConstant(ConstantExpression node)
    {
        return this.ReplaceNode(node);
    }

    private Expression Find { get; set; }
    private Expression Replace { get; set; }
    private ReadOnlyCollection<ParameterExpression> SourceParameters { get; set; }
}

Here's what it does. When Transform() is called, the function stores the arguments as properties, but before it visits the source expression, it has to visit the replacement expression and swap out any of its parameters with the parameters from the first expression. If you don't, you'll get an exception that looks something like this:

Unhandled Exception: System.InvalidOperationException: variable 'x' of type 'System.Int32' referenced from scope '', it is not defined

Once the parameters are swapped, the source is visited. In my case, all I need to do is find parameter, binary and constant expressions. There are a slew of VisitXYZ() methods you can override from ExpressionVisitor, so you may need to override more than what I'm doing. Also, note that visiting one node may require you to do another visitation with child nodes (see how the Left and Right nodes are visited in VisitBinary() before the new BinaryExpression is created).

That's it. When I run this code:

Console.Out.WriteLine("New even expression: {0}", newEvenExpression.ToString());
Console.Out.WriteLine("New even expression: e(3) = {0}", newEvenExpression.Compile()(3));

I see this on the command line:

New even expression: x => (((3 * x) + 1) / 2)
New even expression: e(3) = 5

Perfect! That's exactly what I want. Now I can go back into my presentation code and use ExpressionVisitor.

I hope this has been useful. LINQ expressions are extremely powerful in 4.0, but unfortunately there's not a lot out there to look at. Hopefully this will get you steered down the right path if you want to know how to use ExpressionVisitor. Enjoy!