Visitor Pattern
Visitor is the pattern people learn last and misuse least, mostly because it looks strange at first. It turns an operation into an object and lets that object walk over a structure of differently typed elements, running the right code for each type without a single instanceof.
The grouped Behavioral Patterns overview doesn't cover Visitor at all, so this page starts from zero. It also covers what has changed since 1994: languages now have sealed types and exhaustive pattern matching, and in many codebases these replace Visitor outright.
Intent
Represent an operation over a fixed set of element types as a separate object, so you can add new operations without changing the element classes.
Three ideas sit inside that sentence:
- Fixed set of element types. Visitor assumes the kinds of thing rarely change (number, variable, addition, multiplication), while the things you do with them keep growing (evaluate, print, simplify, type-check, compile).
- Operation as an object. All the code for "pretty-print" lives in one class, not smeared across ten node classes.
- No type tests. The right method runs for each element type through double dispatch, which the language does for you once the plumbing is in place.
The problem
You're building a tiny calculator language. A parser produces a tree of nodes: numbers, variables, additions, multiplications and negation. The first feature is evaluation. Then someone wants a pretty-printer for error messages. Then a simplifier that folds 2 + 3 into 5. Then a list of free variables for a "fill in these inputs" form.
There are two naive ways to build this, and both hurt.
Option A: put every operation on every node. Num gets eval(), print(), simplify(), freeVars(). So do Add, Mul and the rest. Every new feature edits every node class. Evaluation logic ends up scattered across five files.
Option B: keep nodes as plain data and write functions that switch on type. This is what most people write first:
import java.util.Map;
record Num(double value) {}
record Var(String name) {}
record Add(Object left, Object right) {}
record Mul(Object left, Object right) {}
record Neg(Object operand) {} // added later by another developer
class Calculator {
static double eval(Object node, Map<String, Double> env) {
if (node instanceof Num n) return n.value();
if (node instanceof Var v) return env.get(v.name());
if (node instanceof Add a) return eval(a.left(), env) + eval(a.right(), env);
if (node instanceof Mul m) return eval(m.left(), env) * eval(m.right(), env);
if (node instanceof Neg g) return -eval(g.operand(), env);
throw new IllegalArgumentException("unknown node " + node);
}
static String print(Object node) {
if (node instanceof Num n) return String.valueOf(n.value());
if (node instanceof Var v) return v.name();
if (node instanceof Add a) return "(" + print(a.left()) + " + " + print(a.right()) + ")";
if (node instanceof Mul m) return "(" + print(m.left()) + " * " + print(m.right()) + ")";
// nobody remembered to add Neg here
throw new IllegalArgumentException("unknown node " + node);
}
}
class BeforeDemo {
public static void main(String[] args) {
Object expr = new Add(new Var("x"), new Neg(new Num(2)));
assert Calculator.eval(expr, Map.of("x", 5.0)) == 3.0;
try {
Calculator.print(expr);
throw new AssertionError("expected a failure");
} catch (IllegalArgumentException expected) {
System.out.println("print failed at runtime: " + expected.getMessage());
}
}
}
What's wrong with it:
- The type test is repeated in every operation. Five node types times four operations is twenty
instanceofbranches, and they all have to agree. - Missing cases fail at runtime. When
Negwas added,evalwas updated andprintwasn't. Nothing caught it until a user hit it. The finalthrowis an admission that the compiler can't help. - Fields are typed as
Object. The tree has no type of its own, so anything can be put in it.
Visitor fixes the first three: each node type gets exactly one visit method per operation, the compiler forces every visitor to implement all of them, and the tree gets a proper Expr type.
Structure
classDiagram
class Expr {
<<interface>>
+accept(visitor) R
}
class Num {
+value double
+accept(visitor) R
}
class Var {
+name String
+accept(visitor) R
}
class Add {
+left Expr
+right Expr
+accept(visitor) R
}
class ExprVisitor~R~ {
<<interface>>
+visitNum(n) R
+visitVar(v) R
+visitAdd(a) R
}
class Evaluator {
-env Map
+visitNum(n) Double
+visitVar(v) Double
+visitAdd(a) Double
}
class Printer {
+visitNum(n) String
+visitVar(v) String
+visitAdd(a) String
}
class Client
Expr <|.. Num
Expr <|.. Var
Expr <|.. Add
Add o-- Expr : children
ExprVisitor <|.. Evaluator
ExprVisitor <|.. Printer
Num ..> ExprVisitor : calls visitNum
Client --> Expr
Client --> ExprVisitor
The diagram shows three node types to stay readable. The code below has five (Num, Var, Add, Mul, Neg) and three visitors.
Participants
| Participant | In the example | Responsibility |
|---|---|---|
| Element | Expr | Declares accept(visitor). Every element type must implement it. |
| Concrete element | Num, Var, Add, Mul, Neg | Implements accept with one line: call the visitor method for my type, passing this. Exposes the data visitors need. |
| Visitor | ExprVisitor<R> | Declares one visit method per concrete element type. The type parameter R is what the operation produces. |
| Concrete visitor | Evaluator, Printer, ConstantFolder | One operation. Holds any state the operation needs (an environment, a buffer, a symbol table). |
| Object structure | the tree itself | The collection being visited. Here it's recursive (a Composite), but a flat list of mixed elements works too. |
| Client | main | Builds or receives the structure and applies visitors to it. |
Implementation
The three versions below build the same calculator. Each has an evaluator (returns a number), a printer (returns a string) and a constant folder (returns a new tree, which shows that a visitor's result type can be anything, including the element type itself).
import java.util.Map;
import java.util.NoSuchElementException;
interface Expr {
<R> R accept(ExprVisitor<R> visitor);
}
interface ExprVisitor<R> {
R visit(Num n);
R visit(Var v);
R visit(Add a);
R visit(Mul m);
R visit(Neg n);
}
record Num(double value) implements Expr {
public <R> R accept(ExprVisitor<R> v) { return v.visit(this); }
}
record Var(String name) implements Expr {
public <R> R accept(ExprVisitor<R> v) { return v.visit(this); }
}
record Add(Expr left, Expr right) implements Expr {
public <R> R accept(ExprVisitor<R> v) { return v.visit(this); }
}
record Mul(Expr left, Expr right) implements Expr {
public <R> R accept(ExprVisitor<R> v) { return v.visit(this); }
}
record Neg(Expr operand) implements Expr {
public <R> R accept(ExprVisitor<R> v) { return v.visit(this); }
}
final class Evaluator implements ExprVisitor<Double> {
private final Map<String, Double> env;
Evaluator(Map<String, Double> env) { this.env = env; }
public Double visit(Num n) { return n.value(); }
public Double visit(Var v) {
Double value = env.get(v.name());
if (value == null) throw new NoSuchElementException("unbound variable " + v.name());
return value;
}
public Double visit(Add a) { return a.left().accept(this) + a.right().accept(this); }
public Double visit(Mul m) { return m.left().accept(this) * m.right().accept(this); }
public Double visit(Neg n) { return -n.operand().accept(this); }
}
final class Printer implements ExprVisitor<String> {
static String fmt(double d) { return d == Math.rint(d) ? Long.toString((long) d) : Double.toString(d); }
public String visit(Num n) { return fmt(n.value()); }
public String visit(Var v) { return v.name(); }
public String visit(Add a) { return "(" + a.left().accept(this) + " + " + a.right().accept(this) + ")"; }
public String visit(Mul m) { return "(" + m.left().accept(this) + " * " + m.right().accept(this) + ")"; }
public String visit(Neg n) { return "-" + n.operand().accept(this); }
}
/** Returns a simpler, equivalent tree. Never mutates the input. */
final class ConstantFolder implements ExprVisitor<Expr> {
public Expr visit(Num n) { return n; }
public Expr visit(Var v) { return v; }
public Expr visit(Add a) {
Expr l = a.left().accept(this), r = a.right().accept(this);
if (l instanceof Num x && r instanceof Num y) return new Num(x.value() + y.value());
if (l instanceof Num x && x.value() == 0) return r;
if (r instanceof Num y && y.value() == 0) return l;
return new Add(l, r);
}
public Expr visit(Mul m) {
Expr l = m.left().accept(this), r = m.right().accept(this);
if (l instanceof Num x && r instanceof Num y) return new Num(x.value() * y.value());
if (l instanceof Num x && x.value() == 1) return r;
if (r instanceof Num y && y.value() == 1) return l;
return new Mul(l, r);
}
public Expr visit(Neg n) {
Expr inner = n.operand().accept(this);
if (inner instanceof Num x) return new Num(-x.value());
if (inner instanceof Neg double_) return double_.operand(); // --e is e
return new Neg(inner);
}
}
class VisitorDemo {
public static void main(String[] args) {
// (x + 0) * (2 + 3)
Expr e = new Mul(new Add(new Var("x"), new Num(0)), new Add(new Num(2), new Num(3)));
assert e.accept(new Printer()).equals("((x + 0) * (2 + 3))");
assert e.accept(new Evaluator(Map.of("x", 4.0))) == 20.0;
Expr folded = e.accept(new ConstantFolder());
assert folded.equals(new Mul(new Var("x"), new Num(5))); // records compare by value
assert folded.accept(new Printer()).equals("(x * 5)");
assert new Neg(new Neg(new Var("y"))).accept(new ConstantFolder()).equals(new Var("y"));
try {
new Var("z").accept(new Evaluator(Map.of()));
throw new AssertionError("expected unbound variable");
} catch (NoSuchElementException expected) { }
System.out.println("visitor ok: " + folded.accept(new Printer()));
}
}
from __future__ import annotations
from abc import ABC, abstractmethod
from dataclasses import dataclass
from typing import Protocol
class ExprVisitor[R](Protocol):
def visit_num(self, n: Num) -> R: ...
def visit_var(self, v: Var) -> R: ...
def visit_add(self, a: Add) -> R: ...
def visit_mul(self, m: Mul) -> R: ...
def visit_neg(self, n: Neg) -> R: ...
class Expr(ABC):
@abstractmethod
def accept[R](self, visitor: ExprVisitor[R]) -> R: ...
@dataclass(frozen=True)
class Num(Expr):
value: float
def accept[R](self, visitor: ExprVisitor[R]) -> R:
return visitor.visit_num(self)
@dataclass(frozen=True)
class Var(Expr):
name: str
def accept[R](self, visitor: ExprVisitor[R]) -> R:
return visitor.visit_var(self)
@dataclass(frozen=True)
class Add(Expr):
left: Expr
right: Expr
def accept[R](self, visitor: ExprVisitor[R]) -> R:
return visitor.visit_add(self)
@dataclass(frozen=True)
class Mul(Expr):
left: Expr
right: Expr
def accept[R](self, visitor: ExprVisitor[R]) -> R:
return visitor.visit_mul(self)
@dataclass(frozen=True)
class Neg(Expr):
operand: Expr
def accept[R](self, visitor: ExprVisitor[R]) -> R:
return visitor.visit_neg(self)
class Evaluator:
def __init__(self, env: dict[str, float]) -> None:
self._env = env
def visit_num(self, n: Num) -> float:
return n.value
def visit_var(self, v: Var) -> float:
if v.name not in self._env:
raise KeyError(f"unbound variable {v.name}")
return self._env[v.name]
def visit_add(self, a: Add) -> float:
return a.left.accept(self) + a.right.accept(self)
def visit_mul(self, m: Mul) -> float:
return m.left.accept(self) * m.right.accept(self)
def visit_neg(self, n: Neg) -> float:
return -n.operand.accept(self)
class Printer:
@staticmethod
def _fmt(x: float) -> str:
return str(int(x)) if float(x).is_integer() else str(x)
def visit_num(self, n: Num) -> str:
return self._fmt(n.value)
def visit_var(self, v: Var) -> str:
return v.name
def visit_add(self, a: Add) -> str:
return f"({a.left.accept(self)} + {a.right.accept(self)})"
def visit_mul(self, m: Mul) -> str:
return f"({m.left.accept(self)} * {m.right.accept(self)})"
def visit_neg(self, n: Neg) -> str:
return f"-{n.operand.accept(self)}"
class ConstantFolder:
"""Returns a simpler, equivalent tree. Never mutates the input."""
def visit_num(self, n: Num) -> Expr:
return n
def visit_var(self, v: Var) -> Expr:
return v
def visit_add(self, a: Add) -> Expr:
l, r = a.left.accept(self), a.right.accept(self)
if isinstance(l, Num) and isinstance(r, Num):
return Num(l.value + r.value)
if isinstance(l, Num) and l.value == 0:
return r
if isinstance(r, Num) and r.value == 0:
return l
return Add(l, r)
def visit_mul(self, m: Mul) -> Expr:
l, r = m.left.accept(self), m.right.accept(self)
if isinstance(l, Num) and isinstance(r, Num):
return Num(l.value * r.value)
if isinstance(l, Num) and l.value == 1:
return r
if isinstance(r, Num) and r.value == 1:
return l
return Mul(l, r)
def visit_neg(self, n: Neg) -> Expr:
inner = n.operand.accept(self)
if isinstance(inner, Num):
return Num(-inner.value)
if isinstance(inner, Neg):
return inner.operand
return Neg(inner)
if __name__ == "__main__":
e = Mul(Add(Var("x"), Num(0)), Add(Num(2), Num(3)))
assert e.accept(Printer()) == "((x + 0) * (2 + 3))"
assert e.accept(Evaluator({"x": 4})) == 20
folded = e.accept(ConstantFolder())
assert folded == Mul(Var("x"), Num(5)) # dataclasses compare by value
assert folded.accept(Printer()) == "(x * 5)"
assert Neg(Neg(Var("y"))).accept(ConstantFolder()) == Var("y")
try:
Var("z").accept(Evaluator({}))
raise AssertionError("expected unbound variable")
except KeyError:
pass
print("visitor ok:", folded.accept(Printer()))
function assert(cond: unknown, msg = "assertion failed"): asserts cond {
if (!cond) throw new Error(msg);
}
interface ExprVisitor<R> {
visitNum(n: Num): R;
visitVar(v: Var): R;
visitAdd(a: Add): R;
visitMul(m: Mul): R;
visitNeg(n: Neg): R;
}
interface Expr {
accept<R>(visitor: ExprVisitor<R>): R;
}
class Num implements Expr {
constructor(readonly value: number) {}
accept<R>(v: ExprVisitor<R>): R { return v.visitNum(this); }
}
class Var implements Expr {
constructor(readonly name: string) {}
accept<R>(v: ExprVisitor<R>): R { return v.visitVar(this); }
}
class Add implements Expr {
constructor(readonly left: Expr, readonly right: Expr) {}
accept<R>(v: ExprVisitor<R>): R { return v.visitAdd(this); }
}
class Mul implements Expr {
constructor(readonly left: Expr, readonly right: Expr) {}
accept<R>(v: ExprVisitor<R>): R { return v.visitMul(this); }
}
class Neg implements Expr {
constructor(readonly operand: Expr) {}
accept<R>(v: ExprVisitor<R>): R { return v.visitNeg(this); }
}
class Evaluator implements ExprVisitor<number> {
constructor(private readonly env: ReadonlyMap<string, number>) {}
visitNum(n: Num): number { return n.value; }
visitVar(v: Var): number {
const value = this.env.get(v.name);
if (value === undefined) throw new Error(`unbound variable ${v.name}`);
return value;
}
visitAdd(a: Add): number { return a.left.accept(this) + a.right.accept(this); }
visitMul(m: Mul): number { return m.left.accept(this) * m.right.accept(this); }
visitNeg(n: Neg): number { return -n.operand.accept(this); }
}
class Printer implements ExprVisitor<string> {
visitNum(n: Num): string { return String(n.value); }
visitVar(v: Var): string { return v.name; }
visitAdd(a: Add): string { return `(${a.left.accept(this)} + ${a.right.accept(this)})`; }
visitMul(m: Mul): string { return `(${m.left.accept(this)} * ${m.right.accept(this)})`; }
visitNeg(n: Neg): string { return `-${n.operand.accept(this)}`; }
}
/** Returns a simpler, equivalent tree. Never mutates the input. */
class ConstantFolder implements ExprVisitor<Expr> {
visitNum(n: Num): Expr { return n; }
visitVar(v: Var): Expr { return v; }
visitAdd(a: Add): Expr {
const l = a.left.accept(this), r = a.right.accept(this);
if (l instanceof Num && r instanceof Num) return new Num(l.value + r.value);
if (l instanceof Num && l.value === 0) return r;
if (r instanceof Num && r.value === 0) return l;
return new Add(l, r);
}
visitMul(m: Mul): Expr {
const l = m.left.accept(this), r = m.right.accept(this);
if (l instanceof Num && r instanceof Num) return new Num(l.value * r.value);
if (l instanceof Num && l.value === 1) return r;
if (r instanceof Num && r.value === 1) return l;
return new Mul(l, r);
}
visitNeg(n: Neg): Expr {
const inner = n.operand.accept(this);
if (inner instanceof Num) return new Num(-inner.value);
if (inner instanceof Neg) return inner.operand;
return new Neg(inner);
}
}
const e: Expr = new Mul(new Add(new Var("x"), new Num(0)), new Add(new Num(2), new Num(3)));
const printer = new Printer();
assert(e.accept(printer) === "((x + 0) * (2 + 3))");
assert(e.accept(new Evaluator(new Map([["x", 4]]))) === 20);
const folded = e.accept(new ConstantFolder());
assert(folded.accept(printer) === "(x * 5)");
assert(new Neg(new Neg(new Var("y"))).accept(new ConstantFolder()) instanceof Var);
let threw = false;
try { new Var("z").accept(new Evaluator(new Map())); } catch { threw = true; }
assert(threw, "expected unbound variable");
console.log("visitor ok:", folded.accept(printer));
A few details are worth pointing out because interviewers ask about them:
acceptis identical in every class, but you can't hoist it into a base class. The whole trick depends onthishaving the concrete static type inside each class, so the compiler picks the rightvisitoverload. A base-classacceptwould seethisasExprand fail to compile in Java (there's novisit(Expr)). In Python and TypeScript the methods are named per type (visit_num,visitNum) because those languages have no overloading, so the name itself carries the type.- Recursion is driven by the visitor.
Evaluator.visit(Add)decides to visit both children. That lets a visitor skip subtrees, change the order (post-order for evaluation, pre-order for printing a prefix form) or stop early. The alternative, where elements visit their own children, is covered below. - The folder never mutates. It returns new nodes and reuses unchanged ones. Immutable trees make visitors safe to run in any order, cache and share between threads.
Double dispatch, explained properly
"Dispatch" means choosing which method body runs for a call. Java, Python and TypeScript all use single dispatch: x.m(y) picks the body of m based on the runtime type of x only. The type of y matters only at compile time (in Java, through overload resolution) or not at all.
That is the root of the problem. You want the code that runs to depend on two runtime types: which operation (printer or evaluator) and which node (Num or Add). Overloading looks like it should help, but overloads are chosen from the static type of the argument:
class OverloadDemo {
static String describe(Object o) { return "object"; }
static String describe(String s) { return "string"; }
public static void main(String[] args) {
Object hidden = "hello";
assert describe("hello").equals("string");
assert describe(hidden).equals("object"); // runtime type ignored: overloads are compile-time
System.out.println("overloads are picked statically");
}
}
So printer.visit(someExpr) with someExpr declared as Expr can't pick visit(Num). Visitor gets around this by making two single-dispatch calls in a row:
expr.accept(printer)dispatches on the runtime type ofexpr. If it's aNum,Num.acceptruns.- Inside
Num.accept,thishas static typeNum, sovisitor.visit(this)resolves at compile time to thevisit(Num)overload, and the virtual call dispatches on the runtime type of the visitor, soPrinter.visit(Num)runs.
sequenceDiagram
participant C as Client
participant A as "Add node"
participant P as Printer
participant N as "Num node"
C->>A: accept(printer)
A->>P: visit(this as Add)
P->>N: left.accept(this)
N->>P: visit(this as Num)
P-->>N: "2"
N-->>P: "2"
P-->>A: "(2 + x)"
A-->>C: "(2 + x)"
Two runtime types picked the method, using only the single dispatch the language already has. That's double dispatch. Languages with true multiple dispatch, such as Common Lisp (CLOS) and Julia, don't need the pattern at all; you write a method for each combination and the runtime picks it.
Who walks the tree?
There are three places traversal logic can live, and real libraries use all three.
| Option | How it works | Good for | Watch out for |
|---|---|---|---|
| Visitor drives | visitAdd calls left.accept(this) itself | Operations that need control: evaluation order, early exit, returning values built from children | Every visitor repeats the recursion |
| Element drives | Add.accept visits its children, then calls visitor.visitAdd(this) | Simple "do something at every node" passes | The visitor can't skip subtrees or reorder |
| Base visitor with default traversal | A base class walks children by default, subclasses override only the node types they care about | Large trees with dozens of node types where each pass touches a few | Forgetting to call the default traversal stops the walk silently |
The third option is what Python's standard library does. ast.NodeVisitor dispatches by building a method name from the node's class (visit_Call, visit_Name) and falls back to generic_visit, which walks all children. Here is a real, runnable pass over Python source code that counts calls to named functions:
import ast
class CallCounter(ast.NodeVisitor):
def __init__(self) -> None:
self.calls: dict[str, int] = {}
def visit_Call(self, node: ast.Call) -> None:
if isinstance(node.func, ast.Name):
self.calls[node.func.id] = self.calls.get(node.func.id, 0) + 1
self.generic_visit(node) # keep walking into the arguments
source = "print(len(x))\nprint(max(a, len(b)))"
counter = CallCounter()
counter.visit(ast.parse(source))
assert counter.calls == {"print": 2, "len": 2, "max": 1}, counter.calls
print("calls:", counter.calls)
Remove the self.generic_visit(node) line and len disappears from the result, because the visitor stops descending at the outer print call. That's the classic bug of the default-traversal style.
Notice also that ast.NodeVisitor uses reflective dispatch (getattr(self, "visit_" + type(node).__name__)), not accept methods on the nodes. In a dynamic language, that's a reasonable shortcut: the node classes stay untouched and the visitor chooses its method by name. You give up any static check that all node types are handled.
The trade-off: the expression problem
Visitor makes one kind of change cheap and the other expensive. This is a well-known tension called the expression problem:
| Change | Plain polymorphism (methods on nodes) | Visitor |
|---|---|---|
| Add a new operation (type-check, compile) | Edit every node class | Add one new visitor class. Nothing else changes. |
Add a new node type (Pow, Call) | Add one new class | Edit the visitor interface and every visitor |
So the pattern is right exactly when node types are stable and operations keep arriving. That's true of programming-language syntax trees (the grammar changes once a year, but tools keep multiplying), document object models, and file system trees. It's false of a plugin system where third parties add element types.
When a new node type does arrive, the good news is that the compiler finds every place to update: each visitor stops compiling until it implements the new method. That's far better than the instanceof chain, which kept compiling and failed in production.
The modern alternative: sealed types and pattern matching
The whole Visitor apparatus exists to get two things in a language that lacks them: dispatching on the type of a value from outside the class, and a guarantee that every type is handled. Modern languages provide both directly.
Java 21: sealed interfaces, records and switch patterns
Since Java 21, switch can match on types and deconstruct records, and when the matched type is a sealed interface the compiler checks that every permitted subtype is covered. No default branch is needed, and adding a new record to permits turns every non-exhaustive switch into a compile error, exactly like adding a method to a visitor interface.
import java.util.Map;
sealed interface Expr permits Num, Var, Add, Mul, Neg {}
record Num(double value) implements Expr {}
record Var(String name) implements Expr {}
record Add(Expr left, Expr right) implements Expr {}
record Mul(Expr left, Expr right) implements Expr {}
record Neg(Expr operand) implements Expr {}
final class Ops {
static double eval(Expr e, Map<String, Double> env) {
return switch (e) {
case Num n -> n.value();
case Var v -> env.get(v.name());
case Add(Expr l, Expr r) -> eval(l, env) + eval(r, env);
case Mul(var l, var r) -> eval(l, env) * eval(r, env);
case Neg(var x) -> -eval(x, env);
}; // no default: the compiler proves this is exhaustive
}
static Expr simplify(Expr e) {
return switch (e) {
case Neg(Neg(var inner)) -> simplify(inner); // nested record pattern
case Neg(var x) -> simplify(x) instanceof Num(var v) ? new Num(-v) : new Neg(simplify(x));
case Add(var l, var r) -> {
Expr a = simplify(l), b = simplify(r);
yield a instanceof Num(var x) && b instanceof Num(var y) ? new Num(x + y) : new Add(a, b);
}
case Mul(var l, var r) -> {
Expr a = simplify(l), b = simplify(r);
yield a instanceof Num(var x) && b instanceof Num(var y) ? new Num(x * y) : new Mul(a, b);
}
case Num n -> n;
case Var v -> v;
};
}
}
class SealedDemo {
public static void main(String[] args) {
Expr e = new Add(new Neg(new Neg(new Var("x"))), new Mul(new Num(2), new Num(3)));
assert Ops.eval(e, Map.of("x", 1.0)) == 7.0;
assert Ops.simplify(e).equals(new Add(new Var("x"), new Num(6)));
System.out.println("sealed ok: " + Ops.simplify(e));
}
}
Note the nested pattern: case Neg(Neg(var inner)) matches a shape two levels deep in one line. A classic visitor dispatches on one level only and needs an instanceof inside visit(Neg) for that.
Python 3.10+: match with dataclasses
from dataclasses import dataclass
from typing import assert_never
@dataclass(frozen=True)
class Num:
value: float
@dataclass(frozen=True)
class Var:
name: str
@dataclass(frozen=True)
class Add:
left: "Expr"
right: "Expr"
@dataclass(frozen=True)
class Neg:
operand: "Expr"
type Expr = Num | Var | Add | Neg
def evaluate(e: Expr, env: dict[str, float]) -> float:
match e:
case Num(value):
return value
case Var(name):
return env[name]
case Add(left, right):
return evaluate(left, env) + evaluate(right, env)
case Neg(Neg(inner)): # nested pattern
return evaluate(inner, env)
case Neg(operand):
return -evaluate(operand, env)
case _:
assert_never(e) # a type checker flags any missing case here
expr = Add(Neg(Neg(Var("x"))), Num(2))
assert evaluate(expr, {"x": 5}) == 7
print("match ok")
Python's runtime doesn't enforce exhaustiveness. The assert_never(e) call does two jobs: mypy and pyright report an error if some member of the Expr union can reach it, and at runtime it raises if an unexpected value slips through.
TypeScript: discriminated unions
type Expr =
| { kind: "num"; value: number }
| { kind: "var"; name: string }
| { kind: "add"; left: Expr; right: Expr }
| { kind: "neg"; operand: Expr };
function assertNever(x: never): never {
throw new Error(`unhandled node: ${JSON.stringify(x)}`);
}
function evaluate(e: Expr, env: Record<string, number>): number {
switch (e.kind) {
case "num": return e.value;
case "var": {
const v = env[e.name];
if (v === undefined) throw new Error(`unbound variable ${e.name}`);
return v;
}
case "add": return evaluate(e.left, env) + evaluate(e.right, env);
case "neg": return -evaluate(e.operand, env);
default: return assertNever(e); // compile error here if a kind is missing
}
}
const expr: Expr = {
kind: "add",
left: { kind: "var", name: "x" },
right: { kind: "neg", operand: { kind: "num", value: 2 } },
};
if (evaluate(expr, { x: 5 }) !== 3) throw new Error("wrong result");
console.log("discriminated union ok");
The kind field is the discriminant. Inside each case, TypeScript narrows e to that variant, so e.left is only accessible where it exists. If you add { kind: "mul"; ... } to the union and forget a case, e is no longer never in the default branch and the call to assertNever fails to type-check.
So which one?
| Question | Prefer classic Visitor | Prefer sealed types plus pattern matching |
|---|---|---|
| Can you edit the element types? | No (a library hands you its own classes, which offer accept) | Yes, you own them |
| Does the language check exhaustiveness? | Older Java, C++, C# without exhaustive switches | Java 21+, Kotlin, Scala, Rust, Swift, TypeScript, Python with a type checker |
| Do you match on nested shapes? | Rarely | Often (optimisers, rewriters) |
In a fresh Java 21+ or TypeScript codebase that owns its types, pattern matching is usually the better default. Visitor remains the right answer when the element classes belong to a library (you can't add a sealed modifier to someone else's types), when you're on an older language level, or when the framework you use is already built around visitors.
Real-world uses
- Java annotation processing.
javax.lang.model.element.ElementVisitor,javax.lang.model.type.TypeVisitorandAnnotationValueVisitorlet a processor run code per kind of program element (type, method, variable) without casting. The JDK shipsSimpleElementVisitorbase classes with default behaviour. - javac's tree API.
com.sun.source.tree.TreeVisitorand theTreeScannerbase class (which visits all children by default) are how tools such as Error Prone inspect Java source. - File system walking.
java.nio.file.Files.walkFileTree(start, visitor)takes aFileVisitorwith callbacks per directory and file. Its return values (CONTINUE,SKIP_SUBTREE,TERMINATE) show how a visitor can steer the walk. - Python's
astmodule.ast.NodeVisitorandast.NodeTransformer(which returns replacement nodes, like our constant folder) are the standard way to write linters and code rewriters in Python. - JavaScript tooling. Babel plugins export a
visitorobject whose keys are node types (Identifier,CallExpression). ESLint rules return an object of node-type handlers fromcreate(context). Both are the reflective, keyed-by-type flavour. - Bytecode libraries. ASM's
ClassVisitorandMethodVisitorstream a class file as a sequence of visit calls, which tools chain together to analyse or rewrite bytecode.
When NOT to use it
- The element types change often. Every new type edits every visitor. If you're adding node types more often than operations, put the operation on the nodes instead (plain polymorphism).
- There's only one operation. A visitor interface with one implementation is ceremony. Write the method on the classes, or a single
switch. - Your language has exhaustive pattern matching and you own the types. The sealed-type version above is shorter, checks the same things and supports nested patterns.
- The visitor needs private state of the elements. Visitors only see what elements expose. If every visitor needs internals, you'll end up adding public getters you didn't want, which weakens encapsulation. Ask whether the behaviour belongs inside the element.
- The structure is a graph with cycles. Naive recursive visiting loops forever. You need a visited-set, at which point the traversal deserves its own class (an Iterator or graph walker) and the visitor should only receive nodes.
Related patterns
- Composite. Composite gives you the tree, Visitor gives you operations over it. They're used together so often that ASTs are the textbook example of both. Composite alone puts operations on the nodes (each node knows how to
render()itself); adding Visitor moves them out. - Interpreter. Interpreter puts
interpret()on each grammar class, so evaluation lives in the nodes. Once you need a second and third operation over the same grammar (print, optimise, explain), refactoring Interpreter towards Visitor is the standard move. - Iterator. Iterator walks a structure and hands you each element, but you still have to figure out what type each one is. Visitor walks and dispatches by type. You can combine them: iterate over a flat list of mixed items and call
item.accept(visitor)on each. - Strategy. Both turn an algorithm into an object. A strategy is one algorithm with one entry point that the context calls. A visitor is one operation split into one method per element type, called by the elements.
The smell that suggests it
Look for these in a codebase or in your own interview code:
- The same type switch in several places.
if (node instanceof Add) ... else if (node instanceof Mul) ...appears ineval,printandtypeCheck, each ending inthrow new IllegalArgumentException("unknown node"). - Element classes growing unrelated methods.
toJson(),toSql(),render(),estimateCost()andvalidate()all living on the same small data classes, owned by different teams. - "Every feature touches all twelve node classes." If adding a capability means a pull request that edits every subclass of one base type, the operation wants to be one class.
- A "kind" enum plus casts.
switch (node.getKind()) { case ADD: Add a = (Add) node; ... }is a hand-rolled visitor without the type safety.
Interview questions
-
"What problem does Visitor solve that plain polymorphism doesn't?" Adding new operations without editing the element classes. With polymorphism, a new operation means a new method on every class. With Visitor, it's one new class. The trade-off is that adding a new element type becomes expensive instead.
-
"Explain double dispatch." Java and most OO languages choose a method body using only the runtime type of the receiver. Visitor makes two calls:
element.accept(visitor)dispatches on the element's runtime type, thenvisitor.visit(this)inside that element dispatches on the visitor's runtime type, with the overload already fixed by the static type ofthis. The method that finally runs depends on both runtime types. -
"Why can't
acceptlive in an abstract base class?" Because overload resolution is static. In the base class,thishas the base type, sovisitor.visit(this)would need avisit(Expr)overload and would call the same method for every element. Each concrete class must contain its own copy of the one-lineacceptsothishas the concrete type. -
"What happens when you add a new node type?" You add a method to the visitor interface, and every visitor stops compiling until it implements it. That's the cost, but it's also a safety net: the compiler lists every operation that needs updating. A base visitor with a default method for every type trades that safety for less churn.
-
"How would you do this in Java 21 without Visitor?" Make the element hierarchy a
sealedinterface of records and write each operation as aswitchwith type and record patterns. The compiler checks exhaustiveness over the permitted subtypes, nested patterns likeNeg(Neg(var x))work, and noacceptmethods are needed. The visitor is still useful when you can't modify the element types. -
"Doesn't Visitor break encapsulation?" Somewhat. Visitors are outside the element classes, so elements must expose the data the operations need. That's acceptable for data-centric structures like syntax trees, whose whole purpose is to be inspected. It's a bad fit for rich domain objects whose invariants depend on hidden state.
-
"Should the visitor or the elements walk the tree?" The visitor, when order or skipping subtrees matters (evaluation, scoping). A base visitor with default child traversal suits simple passes over big trees, but forgetting to call it silently stops the walk.
Further reading
- Behavioral Patterns: the grouped overview of the behavioral family.
- Composite and Interpreter: the patterns that produce the trees visitors walk.
- Open/Closed Principle: Visitor keeps the element classes closed to new operations.
- Pattern Selection Guide: how Visitor compares with its look-alikes.
- Common LLD Mistakes: especially leaky enums, the
switch-everywhere version of this smell.