General Pattern Matching with Visitors

My previous definition of IVisitor hard-coded the return value as a type of Val, but one can generalize a visitor to any kind pattern-matching function by adding a generic type parameter to the interface:

//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
{
  Exp e0;
  Exp e1;

  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.