On this page

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 instanceof branches, and they all have to agree.
  • Missing cases fail at runtime. When Neg was added, eval was updated and print wasn't. Nothing caught it until a user hit it. The final throw is 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

ParticipantIn the exampleResponsibility
ElementExprDeclares accept(visitor). Every element type must implement it.
Concrete elementNum, Var, Add, Mul, NegImplements accept with one line: call the visitor method for my type, passing this. Exposes the data visitors need.
VisitorExprVisitor<R>Declares one visit method per concrete element type. The type parameter R is what the operation produces.
Concrete visitorEvaluator, Printer, ConstantFolderOne operation. Holds any state the operation needs (an environment, a buffer, a symbol table).
Object structurethe tree itselfThe collection being visited. Here it's recursive (a Composite), but a flat list of mixed elements works too.
ClientmainBuilds 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:

  • accept is identical in every class, but you can't hoist it into a base class. The whole trick depends on this having the concrete static type inside each class, so the compiler picks the right visit overload. A base-class accept would see this as Expr and fail to compile in Java (there's no visit(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:

  1. expr.accept(printer) dispatches on the runtime type of expr. If it's a Num, Num.accept runs.
  2. Inside Num.accept, this has static type Num, so visitor.visit(this) resolves at compile time to the visit(Num) overload, and the virtual call dispatches on the runtime type of the visitor, so Printer.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.

OptionHow it worksGood forWatch out for
Visitor drivesvisitAdd calls left.accept(this) itselfOperations that need control: evaluation order, early exit, returning values built from childrenEvery visitor repeats the recursion
Element drivesAdd.accept visits its children, then calls visitor.visitAdd(this)Simple "do something at every node" passesThe visitor can't skip subtrees or reorder
Base visitor with default traversalA base class walks children by default, subclasses override only the node types they care aboutLarge trees with dozens of node types where each pass touches a fewForgetting 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:

ChangePlain polymorphism (methods on nodes)Visitor
Add a new operation (type-check, compile)Edit every node classAdd one new visitor class. Nothing else changes.
Add a new node type (Pow, Call)Add one new classEdit 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?

QuestionPrefer classic VisitorPrefer 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 switchesJava 21+, Kotlin, Scala, Rust, Swift, TypeScript, Python with a type checker
Do you match on nested shapes?RarelyOften (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.TypeVisitor and AnnotationValueVisitor let a processor run code per kind of program element (type, method, variable) without casting. The JDK ships SimpleElementVisitor base classes with default behaviour.
  • javac's tree API. com.sun.source.tree.TreeVisitor and the TreeScanner base 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 a FileVisitor with callbacks per directory and file. Its return values (CONTINUE, SKIP_SUBTREE, TERMINATE) show how a visitor can steer the walk.
  • Python's ast module. ast.NodeVisitor and ast.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 visitor object whose keys are node types (Identifier, CallExpression). ESLint rules return an object of node-type handlers from create(context). Both are the reflective, keyed-by-type flavour.
  • Bytecode libraries. ASM's ClassVisitor and MethodVisitor stream 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.
  • 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 in eval, print and typeCheck, each ending in throw new IllegalArgumentException("unknown node").
  • Element classes growing unrelated methods. toJson(), toSql(), render(), estimateCost() and validate() 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

  1. "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.

  2. "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, then visitor.visit(this) inside that element dispatches on the visitor's runtime type, with the overload already fixed by the static type of this. The method that finally runs depends on both runtime types.

  3. "Why can't accept live in an abstract base class?" Because overload resolution is static. In the base class, this has the base type, so visitor.visit(this) would need a visit(Expr) overload and would call the same method for every element. Each concrete class must contain its own copy of the one-line accept so this has the concrete type.

  4. "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.

  5. "How would you do this in Java 21 without Visitor?" Make the element hierarchy a sealed interface of records and write each operation as a switch with type and record patterns. The compiler checks exhaustiveness over the permitted subtypes, nested patterns like Neg(Neg(var x)) work, and no accept methods are needed. The visitor is still useful when you can't modify the element types.

  6. "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.

  7. "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