Saturday, April 7, 2007

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.