Skip to main content

Visitor and the Double Dispatch Idea

What This Concept Is​

Visitor separates an operation from the objects it operates on. You have a stable hierarchy of element classes (AST nodes, shapes, filesystem entries) and many operations to perform over them (print, type-check, optimize). Visitor puts each operation in its own class with a method per element type.

The mechanism is double dispatch. Single dispatch (virtual method call) selects behavior based on one object's type: element.accept(visitor). The accept method then calls visitor.visitConcreteElement(this), which selects again based on the visitor's type. Two dispatches -- one for each role -- give you the effect of operation(elementType, visitorType) dispatch that most OO languages do not support directly.

Roles:

  • Element interface with accept(visitor).
  • Concrete elements each implementing accept as visitor.visitX(this).
  • Visitor interface with one visitX method per concrete element.
  • Concrete visitors implementing each operation.

Why It Matters Here​

Visitor is the right answer to "we have a fixed set of types and a growing set of operations". It sidesteps putting every operation on every element class. It also exposes the asymmetry that makes it expensive: adding a new element forces every visitor to change.

The double dispatch idea itself is worth knowing even when you do not adopt the full pattern -- language features like Clojure's multimethods or Rust's trait objects encode the same distinction.

Concrete Example​

A tiny expression tree with two operations as visitors.

interface Expr { <R> R accept(Visitor<R> v); }

class Num implements Expr {
    final double value;
    Num(double v) { this.value = v; }
    public <R> R accept(Visitor<R> v) { return v.visitNum(this); }
}

class Add implements Expr {
    final Expr left, right;
    Add(Expr l, Expr r) { this.left = l; this.right = r; }
    public <R> R accept(Visitor<R> v) { return v.visitAdd(this); }
}

class Mul implements Expr {
    final Expr left, right;
    Mul(Expr l, Expr r) { this.left = l; this.right = r; }
    public <R> R accept(Visitor<R> v) { return v.visitMul(this); }
}

interface Visitor<R> {
    R visitNum(Num n);
    R visitAdd(Add a);
    R visitMul(Mul m);
}

class Evaluate implements Visitor<Double> {
    public Double visitNum(Num n) { return n.value; }
    public Double visitAdd(Add a) { return a.left.accept(this) + a.right.accept(this); }
    public Double visitMul(Mul m) { return m.left.accept(this) * m.right.accept(this); }
}

class Print implements Visitor<String> {
    public String visitNum(Num n) { return Double.toString(n.value); }
    public String visitAdd(Add a) { return "(" + a.left.accept(this) + " + " + a.right.accept(this) + ")"; }
    public String visitMul(Mul m) { return "(" + m.left.accept(this) + " * " + m.right.accept(this) + ")"; }
}

Expr e = new Add(new Num(1), new Mul(new Num(2), new Num(3)));
System.out.println(e.accept(new Evaluate()));   // 7.0
System.out.println(e.accept(new Print()));      // (1.0 + (2.0 * 3.0))

Expr has no evaluate or print method. Each operation is one class. Adding "Differentiate" tomorrow is one more class; Expr stays untouched.

Common Confusion / Misconception​

  • "Why not just put evaluate on each node?" You can. Do that when the number of operations is tiny and stable, and the node set grows often. Visitor is for the opposite case: operations grow, nodes do not.
  • "Pattern matching solves this better." In languages with pattern matching (Scala, Kotlin when, Python match, Rust), visitor-style code often reduces to a match. The idea survives; the ceremony does not.
  • Visitor + mutable element state. A visitor that writes into elements during traversal is easy to get wrong. Prefer returning a value (Visitor<R>) over mutating.
  • Adding a new element type. Every visitor must grow a new method. That is the trade. If element types grow faster than operations, Visitor is the wrong pattern.
  • Confusing Visitor with Iterator. Iterator walks the structure and hands you elements; Visitor applies an operation uniformly, often in concert with an iterator for traversal.

How To Use It​

  1. Confirm the trade: element set mostly fixed; operations likely to grow.
  2. Declare an element interface with accept(visitor).
  3. Each concrete element calls the visitor's type-specific method and passes itself.
  4. Declare the visitor interface with one visit method per concrete element.
  5. Implement the first operation as one visitor. Subsequent ones are additive.
  6. Consider generic return types so the same visitor shape serves evaluation and printing.
  7. If the hierarchy grows, update every visitor deliberately; do not silently add a default.

Check Yourself​

  1. Why does accept need to dispatch to a specific visitX rather than taking Element as a parameter?
  2. What trade-off does Visitor make -- what grows cheaply, what grows expensively?
  3. When is pattern matching a better tool than Visitor?
  4. What goes wrong if a visitor mutates elements during traversal?

Mini Drill or Application​

Given a small AST for arithmetic (Num, Var, Add, Mul):

  1. Implement Evaluate(env) and Pretty visitors.
  2. Add a FreeVars visitor that collects the set of variable names.
  3. Add a new node Neg. Update all three visitors.
  4. Write a one-paragraph note: why Visitor was worth the ceremony -- or why a match would have been cleaner in your language of choice.

Read This Only If Stuck​