What is the motivation of C# ExpressionVisitor's implementation?

Question

I have to design a solution for a task, and I would like to use something theoretically similar to C#'s ExpressionVisitor.

For curiosity I opened the .NET sources for ExpressionVisitor to have a look at it. From that time I've been wondering why the .NET team implemented the visitor as they did.

For example MemberInitExpression.Accept looks like this:

protected internal override Expression Accept(ExpressionVisitor visitor) {
    return visitor.VisitMemberInit(this);
}

My - probably noob - question is: does it make any sense? I mean shouldn't the Accept method itself be responsible of how it implements the visiting within itself? I mean I've expected something like this (removing the internal visibility to be overridable from outside):

protected override Expression Accept(ExpressionVisitor visitor) {
    return this.Update(
            visitor.VisitAndConvert(this.NewExpression, "VisitMemberInit"),
            visitor.Visit(this.Bindings, VisitMemberBinding)
            );
}

But this code is in the base ExpressionVisitor's VisitMemberInit method, which gets called from MemberInitExpression.Accept. So seems like not any benefit of the Accept implementation here.

Why not just process the tree in the base ExpressionVisitor, and forget about all the Accept methods?

I hope you understand my points, and hope someone could shed some light on the motivation behind this implementation. Probably I don't understand the Visitor pattern at all?...

Johen

Answer 1

A visitor can override the way any expression is visited. If your proposal was implemented in all places the visitor never would be called. All the visitation logic would be in the overrides of Accept. Non-BCL code cannot override this method.

If you write visitor.Visit((Expression)this.SomeExpression) (like you do in the question) then how are you going to perform dynamic dispatch on the type of SomeExpression? Now the visitor has to perform the dynamic dispatch. Note, that your 2nd code snippet makes the simplifying assumption that all sub-expressions to be visited have known type. Try to write the code for BinaryExpression to see what I mean.

Maybe I did not understand something but this proposal does not make sense.

The purpose of the Accept method is a performance optimization. Each accept is a virtual call which is rather cheap. The alternative would be to have a huge switch in the visitor over the expression type (which is an enum). That's probably slower.

Lynxeyed

Thanks. I kind of understand the performance point. Anyway of course I ment in my proposal that the Accept method would not be internal, only protected virtual. I will correct my question, sorry for misleading. – Ceramics

That doesn't help because you might have multiple visitors doing different things. You cannot expect user code to override this method. – Lynxeyed

As for your edit, dynamic displatch is done right now in the ExpressionVisitor.Visit method, in a huge switch I think (based on NodeType), but I have to check. – Ceramics

No.. there is really no huge switch, probably I was thinking of some earlier, 3rd party implementation. Give me few minutes to think a bit :) – Ceramics

Ok, I was a bit confused.. let's separate two things: my proposal is a bad implementation, I see (I wasn't thinking too much). Secondly, my main question was why are the Accept methods needed in the Expression classes. Your answer is that it's due to performance reasons? I mean that having a huge switch examining the node types in the base ExpressionVisitor would be a valid alternative. Am I right? – Ceramics

Yes, that's a valid alternative. That's how you would do it if you were to implement the visitor yourself. You can't modify the Expression class. – Lynxeyed

Answer 2

The visitor pattern allows the algorithm to essentially be separated from the structure it's operating on. In this case the structure it operates on is the expression tree.

Notice that the Accept method in the visitor is virtual. This means we could conceivably write different implementations of ExpressionVisitor that do different things to an expression tree (and, indeed, there are different implementations). And we can do this without changing any code in the expression tree classes themselves.

Examples of different visitor implementations might be something like having one visitor that turns the expression tree back into a string representing C# code (or perhaps code in another language).

Peroxidize

Yes I understand that, and that's why I was asking about the need of the Accpet methods in the Expression classes. But @Lynxeyed has pointed out that it's due to performance reasons. – Ceramics

It's not really for performance, though, it's about where the code lives. He's right about the dynamic dispatch, but that's not the reason you can't just pull the Visit implementation straight into the Accept method. There's two levels of dynamic dispatch happening here. One is to dispatch depending on the node type being visited, but the second is to dispatch to different visitor implementations (without requiring a change to the node types). – Peroxidize

Yes now I understand that my proposed implementation is bad design because it hardcodes the expression traversal. The other question was purely about why there are Accept methods instead of doing the dynamic dispatch in a huge switch in a base ExpressionVisitor. Unfortunately I can't accept two answers, but thank you anyway for your hints. – Ceramics