//the pattern matching visitor
public interface IVisitor<T>
//return type is now parameterized
T App(Exp e0, Exp e1);
This of course requires a modification to the class variants as well:
//the type representing an expression application
public sealed class App : Exp
public App(Exp e0, Exp e1)
this.e0 = e0;
this.e1 = e1;
//add a generic constraint to the Visit method, so the client can
//specify the return type
public override T Visit<T>(IVisitor<T> v)
return v.App(e0, e1);
So instead of IVisitor being hard-coded as an evaluator, I can now write an IVisitor that performs transformations on the expression tree (such as rewriting optimizations), or a visitor that implements some arbitrary predicate over the expression tree (such as type-checking, type inference, etc.).
Like pattern matching functions over ordinary parameterized algebraic data types, the return value of the visitor must be T or a subtype of T.
In fact, this visitor pattern, minus the decomposition as in pattern matching, is featured in Generalized Algebraic Data Types and Object-Oriented Programming; see also the LTU discussion.
According to the paper, generics as in C# are almost capable of encoding GADTs. Unfortunately, they lack some flexibility in declaring type dependencies between class type parameters, and method type parameters. The paper provides some very interesting C# examples of type-safe type checking, evaluation, phantom types, and representation types. This generics black magic warrants further study for the advanced C# student.