Lambdas vs. Visitors

Posted on February 11, 2016

The visitor pattern is a design pattern for object-oriented languages originally presented in the Gang of Four “Design Patterns” book. I discovered an alternative to the visitor pattern using lambdas and single-dispatch. If you are already familiar with the visitor pattern, you may jump directly to the next section.

The Visitor Pattern

The visitor pattern allows to perform an operation on subclasses with a common supertype without instanceof checks. The “go to” examples for the visitor pattern is a class hierarchy that models the abstract syntax tree (AST) of arithmetic expressions.

public interface Expression {
  public <A> A accept(ExpVisitor<A> visitor);
}

This is the supertype of all arithmetic expressions. The accept method takes an expression visitor as input and implementors call the appropriate visit method depending on the dynamic type of the expression.

public interface ExpVisitor<A> {
  A visit(Const exp);
  A visit(Addition exp);
  A visit(Multiplication exp);
  ...
}

The expression visitor defines one visit method per expression subclass. The visit method is overloaded and the actual implementation is chosen by identifying the static type of expression that is passed in. The two dispatches of selecting an accept method implementation and a visit method implementation are called double dispatch. The return type of the visit method is generic and allows visitor implementors to choose an appropriate type.

public class Const implements Expression {
  public Const(int i) { ... }
  public int getValue() { ... }

  @Override
  public <A> A accept(ExpVisitor<A> visitor) {
    return visitor.visit(this);
  }
}

public class Addition implements Expression {
  public Addition(Expression x, Expression y) { ... }
  public Expression getLeft() { ... }
  public Expression getRight() { ... }

  @Override
  public <A> A accept(ExpVisitor<A> visitor) {
    return visitor.visit(this);
  }
}

public class Multiplication implements Expression {
  public Multiplication(Expression x, Expression y) { ... }
  public Expression getLeft() { ... }
  public Expression getRight() { ... }

  @Override
  public <A> A accept(ExpVisitor<A> visitor) {
    return visitor.visit(this);
  }
}

Each of these classes contain a trivial implementation for the accept method, i.e. the visit method of the visitor argument is called with the current instance of the expression and the result is returned.

public class Interpreter implements ExpVisitor<Integer> {
  @Override
  public Integer visit(Const exp) {
    return exp.getValue();
  }

  @Override
  public Integer visit(Addition exp) {
    int l = exp.getLeft().accept(this);
    int r = exp.getRight().accept(this);
    return l+r;
  }

  @Override
  public Integer visit(Multiplication exp) {
    int l = exp.getLeft().accept(this);
    int r = exp.getRight().accept(this);
    return l*r;
  }

  ...
}

The interpreter of arithmetic expression implements the visitor interface and overrides all visit methods. Each visit method deals with one specific expression type. On expressions with subexpressions the interpreter calls the accept method with the instance of the interpreter to recurse the entire AST of expressions.

public static void main() {
  Interpreter interpreter = new Interpreter();
  Expression expr = new Addition(new Const(2), new Const(3));
  int x = expr.accept(interpreter);
  System.out.printf("result: %d\n", x);
}

This main function shows how the interpreter is instantiated and passed to an example expression. The following shows a trace of method calls of the program above. The arrows indicate which kind of dispatch was used or which statement was executed.

Expression.accept(ExpVisitor visitor);
-> dynamic dispatch
Addition.accept(ExpVisitor visitor);
-> visitor.visit(this);
-> static dispatch
Interpreter.visit(Addition exp);
-> exp.getLeft().accept(this);
Expression.accept(ExpVisitor visitor);
-> dynamic dispatch
Const.accept(ExpVisitor visitor);
-> visitor.visitor(this);
-> static dispatch
Interpreter.visit(Const exp);
...

In summary the visitor pattern has the following advantages and drawbacks:

The Match Method Design Pattern

At this point I want to introduce an alternative to the visitor pattern called the match method pattern. The name of the pattern is derived from the Scala keyword match that does pattern matching on case classes. It uses Java 8 lambdas and only a single dispatch to solve the same problem as the visitor pattern.

public interface Expression {
  public <A> A match(
                Function<Const,A> f,
                Function<Addition,A> g,
                Function<Multiplication,A> h,
                ...
              );
}

The supertype of expressions now contains a match method that contains one lambda parameter per expression subclass. The argument type of each lambda is one of the expression subclasses and the result type is generic but the same across all lambdas.

public class Const implements Expression {
  ...

  @Override
  public <A> A match(
                Function<Const,A> f,
                Function<Addition,A> g,
                Function<Multiplication,A> h,
                ...
              ) {
    return f.apply(this);
  }
}

public class Addition implements Expression {
  ...

  @Override
  public <A> A match(
                Function<Const,A> f,
                Function<Addition,A> g,
                Function<Multiplication,A> h,
                ...
              ) {
    return g.apply(this);
  }
}

public class Multiplication implements Expression {
  ...

  @Override
  public <A> A match(
                Function<Const,A> f,
                Function<Addition,A> g,
                Function<Multiplication,A> h,
                ...
              ) {
    return h.apply(this);
  }
}

Each expression subclass overrides the match method and calls the appropriate lambda argument with the current instance and returns the result.

public static int evaluate(Expression expr) {
  return expr.<Integer>match(
    con -> con.getValue(),
    add -> evaluate(add.getLeft()) + evaluate(add.getRight()),
    mul -> evaluate(mul.getLeft()) * evaluate(mut.getRight()),
    ...
  );
}

The code for the evaluation of arithmetic expressions can now been written within a single method. The evaluate method uses the match method to differentiate subclasses of expression without using instanceof checks. Each argument to the match method handles a single expression subclass. For expression subclasses with multiple subexpressions, the evaluated method is called recursively and the result combined with the appropriate arithmetic operation of the meta language. The code of evaluate is much shorter than the corresponding visitor. Furthermore the recursion of evaluate is explicit, whereas the visitor calls accept to recurse on subexpressions.

Another advantage of this pattern is that extra arguments can be passed down while traversing the expression type. A visitor does not allow this because the signature of the visit methods is fixed.

public static Type typecheck(Context ctx, Expression expr) {
  return expr.<Type>match(
    var -> context.lookup(var)
                  .orElse(new TypeError("Variable not in scope")),
    lam -> {
      Context newCtx = ctx.extend(lam.variable(),lam.variableType());
      Type bodyType = typecheck(newCtx, lam.body());
      return new FunType(lam.variableType(), bodyType);
    },
    app -> {
      Type t1 = typecheck(context,app.getLeft());
      Type t2 = typecheck(context,app.getRight());
      return t1.<Type>match(
        funType -> funType.argumentType().equals(t2)
                 ? funType.resultType()
                 : new TypeError("Wrong argument type to lambda"),
        baseType -> new TypeError("Expected function type"),
        error -> error
      );
    }
  );
}

This example shows a type checking function for the simply typed lambda calculus. A context is passed down while traversing the expression. It uses two match methods, one on expressions and one on types. Type errors are part of the Type class hierarchy and are returned whenever type checking fails. This example illustrates how well different match methods can be used together.

I want to emphasize that the match method is much weaker than actual pattern matching with the match keyword in Scala. For example the caller of the match method always has to handle all cases and cannot chose to handle only certain cases. Deep pattern matching inside nested structures or pattern guards are also not possible with this approach. But all these missing features can be worked around.

Compared to the visitor pattern the match pattern has the following advantages and drawbacks:

Conclusion

I do not claim that the match pattern is always better than the visitor pattern, but in cases with a small number of expression subclasses the match pattern is more flexible. Also people say that a design pattern is short coming of a programming language that it lacks a certain feature. The match pattern shows that Java has a real need for pattern matching.