# Lambdas vs. Visitors

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:

- Adding new visitor implementations is easy
- Adding new expression subclasses is hard
- The code in the visitor is scattered across multiple
`visit`

methods

## 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:

Adding new methods that make use of the

`match`

method is easyAdding new expression subclasses is hard

Recursion within methods that use

`match`

methods becomes explicit whereas visitors disguise the recursion behind`accept`

methodsMethods that use

`match`

methods can specify additional parameters and chose a different return type than the`match`

call, whereas visitors cannot easily pass down extra argumentsThe lambda arguments to the

`match`

function can close over stateThe overriding of the

`match`

method inside expression subclasses is more difficult because the method signature has more arguments than`visit`

methodsThis pattern might not scale for expression types with hundreds of subclasses due to the previous point

## 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.