Higher Logics

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 predica

To kick off my first post, I thought I'd cover a post on another blog that I found interesting . Basically, the gist of the post is that object oriented visitor pattern does not lend itself to the problem of walking trees, and general symbolic manipulation, despite that being its claim to fame. In general, algebraic data types and pattern matching are much simpler, and more concise. I agree, however I think that post goes a bit too far in saying that visitors simply can't do this elegantly, because in fact there's a straightforward translation of a pattern matching function into a visitor, as long as you keep your objects "functional", ie. treat them as variants. For instance, let's say we are constructing an evaluator: //the Expression type public abstract class Exp { public abstract Val Visit(IVisitor v); } //the type of Values public abstract class Val : Exp { } //the type representing an application public sealed class App : Exp { Exp e0; Exp e1;