Visitors: Chapter 2

Last time we talked about a case where a class hierarchy was being hopelessly overwhelmed with unrelated methods. Cruft was building up, and we wanted a way to create new logic for the class hierarchy without polluting the hierarchy itself.

Visitors solve these problems quite nicely. You can separate logic from the expression hierarchy, and keep different operations (printing, evaluating, etc) organized and in one place. It doesn’t require much boilerplate, either. Let’s see how it works:

To implement a Visitor pattern for your hierarchy, you first create a Visitor interface:

public interface Visitor {
}

Then, you add an accept method to your hierarchy:

public interface Expr {
  void accept(Visitor v);
}

This is actually the only method your entire hierarchy will ever need, and you can then attach any behavior you want. Also, users of your library can also easily attach behavior to your expression hierarchy, which is an added bonus.

Each expression type implements this method and invokes the visit method. For example:

@Override
public void accept(Visitor v) {
 v.visit(this);
}

Then in the Visitor itself, you provide several strongly typed visit methods:

public interface Visitor {
  void visit(Variable expr);

  void visit(ExprList expr);

  void visit(IntLiteral expr);

  void visit(Operation expr);

  void visit(ForExpr expr);
}

And that’s the basics of the pattern. Now let’s see how you add operations. We’ll start by adding print behavior:

import java.util.Stack;

public class PrintVisitor implements Visitor {
  private final Stack<String> printStack = new Stack<>();

  @Override
  public void visit(Variable expr) {
    printStack.push(expr.getName());
  }

  @Override
  public void visit(ExprList expr) {
    StringBuilder sb = new StringBuilder();
    for (Expr e : expr.getExpressions()) {
      e.accept(this);
      sb.append(printStack.pop()).append("\n");
    }
    printStack.push(sb.toString());
  }

  @Override
  public void visit(IntLiteral expr) {
    printStack.push(Integer.toString(expr.getValue()));
  }

  @Override
  public void visit(Operation expr) {
    expr.getLeft().accept(this);
    String l = printStack.pop();
    expr.getRight().accept(this);
    String r = printStack.pop();

    switch (expr.getType()) {
      case plus:
        printStack.push(l + " + " + r);
        break;
      case multiply:
        printStack.push(l + " * " + r);
        break;
      case less_than:
        printStack.push(l + " < " + r);
        break;
      case assignment:
        printStack.push(l + " = " + r);
        break;
    }
  }

  @Override
  public void visit(ForExpr expr) {
    expr.getInit().accept(this);
    String init = printStack.pop();
    expr.getCond().accept(this);
    String cond = printStack.pop();
    expr.getInc().accept(this);
    String inc = printStack.pop();
    expr.getBlock().accept(this);
    String block = printStack.pop();

    printStack.push("for (" + init + "; " + cond + "; " + inc + ") {\n" + block + "\n}");
  }

  public String getResult() {
    return printStack.pop();
  }
}

This PrintVisitor can be used like so:

PrintVisitor pv = new PrintVisitor();
e.accept(pv);
System.out.println(pv.getResult());

Next let’s move the evaluation code to a visitor:

public class Evaluation {
  private static final class EvalVisitor implements Visitor {
    private final Stack<Value> valueStack = new Stack<>();

    private final Map<String, Value> values = new HashMap<>();

    @Override
    public void visit(Variable expr) {
      valueStack.push(new Value(expr.getName()));
    }

    @Override
    public void visit(ExprList expr) {
      for (Expr e : expr.getExpressions()) {
        e.accept(this);
      }
    }

    @Override
    public void visit(IntLiteral expr) {
      valueStack.push(new Value(expr.getValue()));
    }

    @Override
    public void visit(Operation expr) {
      expr.getLeft().accept(this);
      Value l = valueStack.pop();
      expr.getRight().accept(this);
      Value r = valueStack.pop();

      switch (expr.getType()) {
        case plus:
          valueStack.push(new Value(getInt(l) + getInt(r)));
          break;
        case multiply:
          valueStack.push(new Value(getInt(l) * getInt(r)));
          break;
        case less_than:
          valueStack.push(new Value(getInt(l) < getInt(r)));
          break;
        case assignment:
          values.put(l.getName(), r);
          valueStack.push(r);
          break;
      }
    }

    @Override
    public void visit(ForExpr expr) {
      expr.getInit().accept(this);
      expr.getCond().accept(this);
      while (valueStack.pop().asBool()) {
        expr.getBlock().accept(this);
        expr.getInc().accept(this);
        expr.getCond().accept(this);
      }
    }

    private int getInt(Value r) {
      if (r.getName() != null) {
        return getInt(values.get(r.getName()));
      } else {
        return r.asInt();
      }
    }
  }

  public static int evaluate(Expr expr) {
    EvalVisitor v = new EvalVisitor();
    expr.accept(v);
    return v.valueStack.pop().asInt();
  }
}

Pretty neat, eh? We’ve gotten rid of two methods from our complicated class hierarchy and encapsulated all of the logic of those operations in one place. But there’s no such thing as a free lunch. Let’s talk about the tradeoffs.

First, you may notice that the logic is separated from the Expr class. That’s the whole point of the pattern, but it is a tradeoff. Usually, you want logic to be as close to the class as possible, and you want functions to have descriptive names and perform the task they’re named for. All of this is thrown out the window with Visitors. Instead, you should use good names for your Visitors, and just be happy that your expression classes don’t have to have thirty methods on them.

There’s also the obvious drawback of boilerplate. Dreaded boilerplate. Every time you want to use a Visitor, you have to go through this song and dance of creating the Visitor, calling accept, and getting some result from the Visitor. A lot of these problems can be ameliorated with a few tricks, but even if you hide this stuff behind some library, it still exists, and it is much more complicated than just calling some method and getting a result.

To everything, there is a season, and a time to every purpose. Should you use Visitors all the time? Hell no. Should you carefully analyze your problem, consider different designs, contemplate the pros and cons of each design, and maybe use Visitors if you decide that they work very well to solve your problem? Yes.