Visitors: Chapter 1

No Such Thing as a Free Lunch

I’m leery of engineers who believe patterns are the answer to all problems. These engineers are easy to spot. They carry around that GoF book like a bible, and as you discuss designs with your peers, they will snarkily murmur things like “flyweight” and “decorator” in the background. I tend to view patterns as yet another tool in the toolchest, and all tools have their strengths and weaknesses.

I would never discourage new engineers from learning patterns. In fact, I quite enjoyed the Gang of Four book, and I’ve recommended it to people on numerous occasions. But I also stress to young engineers to truly examine the pros and cons of using some pattern to solve some problem. Is the boilerplate of the pattern worth the flexibility? Will the pattern truly be elegant given the warts of the problem? Does the pattern incur some additional cost that is unnecessary? These are all important questions, and you should be asking yourself these questions if you think you’ve found a silver bullet to solve your problem.

Okay, now that I’ve gotten that rant off my chest, I’d like to tell you about a pattern I really like: the visitor pattern.

The Problem

Programming big systems can be thought of as a herculean task of organization. Most problems that need to be solved on a daily basis are probably not that difficult. The difficulty lies in creating a cohesive web of components that inter-operate well together, and are isolated enough so that the complexity of one component does not bleed over into the complexity of another component.

The Visitor is a pattern which allows you to separate algorithmic complexity from structural complexity. In other words, it allows you to create new behavior for a class hierarchy, but define that behavior outside of the hierarchy.

Let’s use an example we’ve used before: Abstract Syntax Trees.

I’ve discussed abstract syntax trees in the past. They are an incredibly powerful tool that can be used to represent things like mathematical expressions or languages (programming and otherwise). Typically, you will have some overarching interface, such as:

public interface Expr {
}

And then each syntactical element of your languages will extend or implement this interface. For this post, we’ll use a simple programming language as an example. The language will have integers, variables, operators, and a for loop.

// int literal
public final class IntLiteral implements Expr {
  private final int value;

  public IntLiteral(int value) {
    this.value = value;
  }

  public int getValue() {
    return value;
  }
}
// operation
public final class Operation implements Expr {
  private final OpType type;
  private final Expr left;
  private final Expr right;

  public Operation(OpType type, Expr left, Expr right) {
    this.type = type;
    this.left = left;
    this.right = right;
  }

  public Expr getLeft() {
    return left;
  }

  public Expr getRight() {
    return right;
  }

  public OpType getType() {
    return type;
  }
}

// for loop
public final class ForExpr implements Expr {
  private final Expr init;
  private final Expr cond;
  private final Expr inc;
  private final Expr block;

  public ForExpr(Expr init, Expr cond, Expr inc, Expr block) {
    this.init = init;
    this.cond = cond;
    this.inc = inc;
    this.block = block;
  }

  public Expr getInit() {
    return init;
  }

  public Expr getCond() {
    return cond;
  }

  public Expr getInc() {
    return inc;
  }

  public Expr getBlock() {
    return block;
  }
}

Let’s do something with this class hierarchy. We’ll start with evaluation. We have to add a method to the interface, then implement the method on all the classes:

public interface Expr {
  // new method. Memory holds values of variables during
  // program execution
  void evaluate(Memory memory);
}

// in IntLiteral
@Override
public void evaluate(Memory memory) {
  memory.push(new Value(value));
}

// in Operation
@Override
public void evaluate(Memory memory) {
  left.evaluate(memory);
  Value l = memory.popValue();
  right.evaluate(memory);
  Value r = memory.popValue();

  switch (type) {
    case plus:
      memory.push(new Value(getInt(memory, l) + getInt(memory, r)));
      break;
    case multiply:
      memory.push(new Value(getInt(memory, l) * getInt(memory, r)));
      break;
    case less_than:
      memory.push(new Value(getInt(memory, l) < getInt(memory, r)));
      break;
    case assignment:
      memory.setValue(l.getName(), r);
      break;
  }
}

private int getInt(Memory m, Value v) {
  if (v.getName() != null) {
    return getInt(m, m.getValue(v.getName()));
  }
  return v.asInt();
}
 
// and for loop
@Override
public void evaluate(Memory memory) {
  init.evaluate(memory);
  while (true) {
    cond.evaluate(memory);
    if (memory.popValue().asBool()) {
      block.evaluate(memory);
      inc.evaluate(memory);
    } else {
      break;
    }
  }
}

Now we can execute a simple program! I’ve created a mini-DSL for creating the various expression types. It’s nothing fancy, I’ll include a small snippet of it so you get the idea:

// Expression DSL
public class ExprDSL {
  public static ExprList list(Expr ... exprs) {
    return new ExprList(Arrays.asList(exprs));
  }

  public static Operation assignment(Expr left, Expr right) {
    return new Operation(OpType.assignment, left, right);
  }

  public static Variable v(String name) {
    return new Variable(name);
  }

  public static IntLiteral i(int val) {
    return new IntLiteral(val);
  }
  // and so on...
  
public class Main {
  public static void main(String[] args) {
    // create program
    // result = 0
    // for (i = 5; i < 10; i = i + 1) {
    //   result = result + i
    // }
    Memory memory = new Memory();
    Expr e = list(
        assignment(v("result"), i(0)),
        forLoop(
            assignment(v("i"), i(5)),
            lessThan(v("i"), i(10)),
            assignment(v("i"), add(v("i"), i(1))),
            assignment(v("result"), add(v("result"), v("i"))))
    );
    Memory m = new Memory();
    e.evaluate(m);
    System.out.println(m.getValue("result").asInt());
  }
}

The executed program prints 35. Great! Okay, but now we need to add more functionality to our expr hierarchy. First, we need to be able to print the AST as code, then we need to be able to print the AST as a tree, then we need type checking utilities (for instance, is the for loop conditional a boolean expression?). Then, if you recall from an earlier blog post, we may need the ability to rotate an Operation node if operator precedence is out of whack. After a few weeks, our Expr interface ends up looking like this:

public interface Expr {
  void evaluate(Memory memory);

  String print(IndentStack indent);

  void printAsTree(TreeStack ts);

  void validateTypes(TypeChecker checker);

  int getPrecedence();

  Expr rotateRight();

  // elides noop statements
  Expr simplify();

  int compare(Expr other);
  
  Expr copy();
  
  // converts variable and function names to random strings
  // of 1-5 characters
  Expr obfuscate();
}

Each one of these methods has to be implemented in all of our expression classes. In some cases, the logic of each method will be very different from the others (printing trees and validating types probably won’t share a lot of code).

If only there was a way to define algorithms and operations separately from our data structure! Oh wait, there is, it’s called the Visitor pattern :-)

In our next chapter, we’ll discuss how the Visitor pattern is implemented and show a few examples.