Expression Tree Rewriting, Followup

After a short trip around Google, I came across ExpressionVisitor. With ExpressionVisitor, I am able to visit each expression in the tree with the ability to replace that expression with another if needed.

Here's an ExpressionVisitor I wrote that finds all uses of one expression and replaced those uses with another expression:

public class Modifier : ExpressionVisitor
{
    private Expression _oldValue;
    private Expression _newValue;
	
    public Modifier(Expression oldValue, Expression newValue)
    {
        _oldValue = oldValue;
        _newValue = newValue;
    }

    public override Expression Visit(Expression b)
    {
        if (b == _oldValue)
            return _newValue;
		
        return base.Visit(b);
    }
}

It's really just that simple.  Look at every branch; if the branch uses expression A, replace with B; otherwise, look deeper into the branch.

Expression tree rewriting

I recently asked a question on MSDN's LINQ to Entities forum:
http://social.msdn.microsoft.com/Forums/en-US/adodotnetentityframework/thread/ddd2ddb4-ad77-415c-b9a3-781f759b0316

Here's the basics:
I would like to do the following transformation using an expression rewriter:

Func<string, bool> lengthFunc = s => s.Length > 5;
Func<string, bool> startFunc = s => s.StartsWith("a");

Func<string, bool> combinedFunc = s => ((s.Length > 5) && s.StartsWith("a"));

I began by making the variables lambda expressions and then combining their bodies in an AndAlso expression:

Expression<Func<string, bool>> lengthFunc = s => s.Length > 5;
Expression<Func<string, bool>> startFunc = s => s.StartsWith("a");

BinaryExpression combinedBody = Expression.AndAlso(lengthFunc.Body, startFunc.Body);
Expression<Func<string, bool>> combined = Expression.Lambda<Func<string, bool>>(combinedBody, lengthFunc.Parameters);

combined.ToString() returns: s => ((s.Length > 5) AndAlso s.StartsWith("a"))


This looks correct, but renaming the parameters in the input expressions shows the error in my approach:

Expression<Func<string, bool>> lengthExpr = sA => sA.Length > 5;
Expression<Func<string, bool>> startExpr = sB => sB.StartsWith("a");

BinaryExpression combinedBody = Expression.AndAlso(lengthExpr.Body, startExpr.Body);
Expression<Func<string, bool>> combined = Expression.Lambda<Func<string, bool>>(combinedBody, lengthExpr.Parameters);

combined.ToString() returns: sA => ((sA.Length > 5) AndAlso sB.StartsWith("a"))


I have an unsatisfied parameter requirement, sB, in the expression.

To get an expression body that references a single parameter, I would need to replace all uses of sB in startExpr with the ParameterExpression sA from lengthExpr.

Being that expressions are immutable, I can't simply crawl startExpr replacing all instances of sB with sA. I'll need to create a copy of startExpr with the parameter references swapped.