Visitor

Idea: Parameterize an operation by the class of objects that it acts on. By using the visitor pattern, this can be done without having to add additional code to either class (the code is encapsulated into a visitor class instead).

Connection: the visitor pattern is typically used to implement double dispatch in OOP languages as a result of the expression problem. Languages like Julia and Common Lisp support multiple dispatch natively, which basically makes the visitor pattern useless in those languages.

In the below example, we will re-use the sample expression language from Interpreter. We will implement two different example visitors that operate on the same AST. Notice that all of the “business logic” has been factored out into the visitors instead of in being spread across each subclass of Expression.

abstract class Expression {
  abstract accept(visitor: Visitor);
}

class Literal extends Expression {
  value: number

  constructor(value: number) {
    super();
    this.value = value;
  }

  accept(visitor: Visitor) {
    return visitor.visitLiteral(this);
  }
}

class Add extends Expression {
  left: Expression;
  right: Expression;

  constructor(left: Expression, right: Expression) {
    super();
    this.left = left;
    this.right = right;
  }

  accept(visitor: Visitor) {
    return visitor.visitAdd(this);
  }
}

class Multiply extends Expression {
  left: Expression;
  right: Expression;

  constructor(left: Expression, right: Expression) {
    super();
    this.left = left;
    this.right = right;
  }

  accept(visitor: Visitor) {
    return visitor.visitMultiply(this);
  }
}

abstract class Visitor {
  abstract visitLiteral(node: Literal): any;
  abstract visitAdd(node: Add): any;
  abstract visitMultiply(node: Multiply): any;
}

class VisitorInterpreter extends Visitor {
  visitLiteral(node: Literal) {
    return node.value;
  }
  visitAdd(node: Add) {
    return node.left.accept(this) + node.right.accept(this);
  }
  visitMultiply(node: Multiply) {
    return node.left.accept(this) * node.right.accept(this);
  }
}

// compiles the expression into reverse polish notation
class VisitorCompiler extends Visitor {
  stack: (string | number)[] = [];

  visitLiteral(node: Literal) {
    this.stack.push(node.value);
  }
  visitAdd(node: Add) {
    node.left.accept(this);
    node.right.accept(this);
    this.stack.push("+")
  }
  visitMultiply(node: Multiply) {
    node.left.accept(this);
    node.right.accept(this);
    this.stack.push("*")
  }
}

function main() {
  const expr = new Add(new Multiply(new Literal(2), new Literal(3)), new Literal(1))
  
  const interpreter = new VisitorInterpreter();
  console.log(expr.accept(interpreter)); // "7"

  const compiler = new VisitorCompiler();
  expr.accept(compiler);
  console.log(compiler.stack); // [ 2, 3, "*", 1, "+" ]
}