Compiling to Assembly
from Scratch

Chapter 12
Visitor Pattern

We are about to add more passes to our compiler: type checking, and code generation for dynamic typing. What we could do is extend the AST interface with new methods, one for each pass. It can look something like this:

interface AST {
  emit(env: Environment): void;
  emitDynamic(env: Environment): void;
  typeCheck(env: TypeEnvironment): Type;
  equal(other: AST): boolean;
}

And this is perfectly fine. However, this way, code for each pass is intertwined with code for every other pass. In other words, code is grouped by an AST node and not by a pass.

Using the visitor pattern we can group the code for each pass together under a separate class. The visitor pattern allows us to decouple our passes from AST by using indirection. Instead of having a method per pass, per AST node we add a single method per AST node called visit that delegates the action to a class that implements the visitor interface. The visitor interface has one method per AST node: visitAssert, visitLength, visitNumber, etc.

interface AST {
  visit<T>(v: Visitor<T>): T;
  equal(other: AST): boolean;
}

interface Visitor<T> {
  visitAssert(node: Assert): T;
  visitLength(node: Length): T;
  visitNumber(node: Number): T;
  visitBoolean(node: Boolean): T;
  visitNot(node: Not): T;
  visitEqual(node: Equal): T;
  …
}

Each AST node implements the new AST interface by calling the corresponding visitor method. For example, Assert calls visitAssert, Length calls visitLength, etc.

class Assert implements AST {
  constructor(public condition: AST) {}

  visit<T>(v: Visitor<T>) {
    return v.visitAssert(this);
  }

  equals(other: AST): boolean {…}
}

class Length implements AST {
  constructor(public array: AST) {}

  visit<T>(v: Visitor<T>) {
    return v.visitLength(this);
  }

  equals(other: AST): boolean {…}
}

The visitor interface Visitor<T> is generic. That means it can be used to implement passes that return different things. For example, Visitor<AST> produces an AST node, Visitor<void> can emit code as a side-effect.

Let’s convert our existing code generation pass into a visitor. Since our existing emit method returned void, our new visitor will implement Visitor<void>. Instead of having a separate Environment class, we make the visitor constructor take all the environment parameters. In a way, the visitor becomes the environment.

class CodeGenerator implements Visitor<void> {
  constructor(public locals: Map<string, number>,
              public nextLocalOffset: number) {}

  visitAssert(node: Assert) {
    node.condition.visit(this);
    emit(`  cmp r0, #1`);
    emit(`  moveq r0, #'.'`);
    emit(`  movne r0, #'F'`);
    emit(`  bl putchar`);
  }

  visitLength(node: Length) {
    node.array.visit(this);
    emit(`  ldr r0, [r0, #0]`);
  }

  …
}

We copy the body of each method, like Assert.emit and Length.emit into the visitor methods, like visitAssert and visitLength.

In emit methods we used to call emit recursively for inner nodes, like this:

  emit(env: Environment): void {
    this.array.emit(env);
    emit(`  ldr r0, [r0, #0]`);
  }

Now, instead, we call the visit method on them.

  visitLength(node: Length) {
    node.array.visit(this);
    emit(`  ldr r0, [r0, #0]`);
  }

Previously this referred to the AST node, but now the node is passed as the parameter called node. Now, this refers to the visitor itself, which we pass instead of the env parameter.

In rare places where we created a new environment, we create a new visitor instead with the updated environment. Here’s an example from visitFunction.

Before:

    let env = new Environment(locals, -20);
    this.body.emit(env);

After:

    let visitor = new CodeGenerator(locals, -20);
    node.body.visit(visitor);

As you can see, converting from an AST-based pass to a visitor-based pass is a purely mechanical transformation. New passes that we will introduce will also be based on the visitor pattern.