Why does the Visitor pattern need double dispatch, and what trade-off does it make that Iterator does not?

principalnice to knowfreq 31%

answer

Single dispatch on receiver only → overloads bind on static arg type
accept(v) then v.visitX(this) = two hops = double dispatch
Expression problem: OO cheap on types, Visitor cheap on ops
Visitor needs a closed, stable hierarchy
Iterator = traversal vs representation, no such trade

basics

~20 s

Visitor lets you add new operations over a fixed set of node types without editing them. It needs two dispatches: the node picks accept(visitor), then calls visitor.visitX(this), so the right method is chosen by both the node type and the visitor type. The trade-off: adding an operation is easy, adding a node type breaks every visitor.

solid answer

~1 min

Most object-oriented languages dispatch dynamically on only the receiver — single dispatch — so a visit(node) overload is picked by the static type of the argument, which is useless for a polymorphic tree. Visitor recovers the missing dispatch manually: the client calls node.accept(visitor), which dynamically dispatches on the node; each concrete node's accept calls visitor.visitLiteral(this) where this has a known concrete type, dispatching a second time on the visitor. Two dispatches, hence double dispatch. The payoff is the expression problem trade-off: with ordinary polymorphism, adding a type is cheap and adding an operation touches every type; Visitor inverts that — new operations are one new class, but a new node type forces a change to the visitor interface and every implementation. So Visitor fits a stable structure with many, growing operations: AST compilers and linters, document exporters, IR passes. Iterator makes no such trade — it only decouples traversal from the collection's representation, offering sequential access without exposing internals, and it does not care what you do with each element. Visitor's other costs: it must expose enough node state to work (weakening encapsulation), traversal order gets entangled with visit logic unless separated, and recursion depth on deep trees can overflow the stack.

Most object-oriented languages dispatch dynamically on only the receiver — single dispatch — so a `visit(node)` overload is picked by the *static* type of the argument, which is useless for a polymorphic tree. Visitor recovers the missing dispatch manually: the client calls `node.accept(visitor)`, which dynamically dispatches on the node; each concrete node's `accept` calls `visitor.visitLiteral(this)` where `this` has a known concrete type, dispatching a second time on the visitor. Two dispatches, hence double dispatch. The payoff is the expression problem trade-off: with ordinary polymorphism, adding a *type* is cheap and adding an *operation* touches every type; Visitor inverts that — new operations are one new class, but a new node type forces a change to the visitor interface and every implementation. So Visitor fits a stable structure with many, growing operations: AST compilers and linters, document exporters, IR passes. Iterator makes no such trade — it only decouples traversal from the collection's representation, offering sequential access without exposing internals, and it does not care what you do with each element. Visitor's other costs: it must expose enough node state to work (weakening encapsulation), traversal order gets entangled with visit logic unless separated, and recursion depth on deep trees can overflow the stack.

code

pseudocode · 12 lines

pseudocode

// Hop 1 dispatches on the node; hop 2 dispatches on the visitor.
interface Node    { accept(v: Visitor): R }
class Lit(x)  : Node { accept(v) = v.visitLit(this) }
class Add(l,r): Node { accept(v) = v.visitAdd(this) }

interface Visitor { visitLit(n: Lit): R; visitAdd(n: Add): R }

class Eval : Visitor {           // new OPERATION = one new class
  visitLit(n) = n.x
  visitAdd(n) = n.l.accept(this) + n.r.accept(this)
}
// new NODE TYPE (e.g. Mul) = edit Visitor + every implementation

go deeper

for a junior

Say Visitor lets you add operations over a set of node types without changing them, and that accept plus visit is how the right method gets picked.

for a middle

Explain single vs double dispatch mechanically with the two-hop call, and note that adding node types is the expensive direction.

for a senior

Name the expression problem explicitly, discuss the stability precondition, defaulting base visitors versus exhaustiveness, and separating traversal from the visit operation.

for a principal

Reason about it as an API-evolution decision — who owns the hierarchy, what breaks downstream consumers, whether the language offers sealed exhaustive matching or multimethods, and the operational costs (stateful visitors, recursion depth, readability) versus a simpler design.

Single vs double dispatch

Dynamic dispatch means the runtime picks the method implementation from the runtime type of an object. Nearly all mainstream OO languages do single dispatch: the choice depends on the runtime type of the receiver only. Overloads (visit(Literal), visit(Add)) are resolved at compile time from the static type of the argument.

So this fails:

void render(Visitor v, Node n) { v.visit(n); }   // always picks visit(Node)

Even if n is really an Add, the compiler picked the overload from the declared type Node.

Double dispatch selects the implementation from the runtime types of two objects. Visitor simulates it with two single dispatches:

node.accept(visitor) — dispatches on the node's runtime type.
Inside Add.accept, the call is visitor.visitAdd(this) — this is statically known to be Add here, so the correct overload is chosen, and the call dispatches on the visitor's runtime type.

Two hops, both single dispatch, together equivalent to dispatching on the (node, visitor) pair.

interface Node    { accept(v: Visitor) }
class Add : Node  { accept(v) = v.visitAdd(this) }      // hop 2
class Lit : Node  { accept(v) = v.visitLit(this) }

interface Visitor { visitAdd(a: Add); visitLit(l: Lit) }
class Printer : Visitor { visitAdd(a){...}; visitLit(l){...} }

tree.accept(Printer())                                   // hop 1

The repetitive one-line accept in every node is the price of the language's missing multiple dispatch. Languages that have multiple dispatch (Common Lisp CLOS multimethods, Julia, Clojure's defmulti) do not need Visitor at all; languages with exhaustive pattern matching over sealed/closed hierarchies (Rust enums, Scala sealed traits, modern Java/Kotlin sealed types with when/switch patterns) get the same benefit with compiler-checked exhaustiveness and far less ceremony — an important modern caveat.

The expression problem

Phil Wadler's framing: you want to extend a system along two axes — new data variants and new operations — without modifying existing code and without losing type safety.

Plain OO polymorphism (a method on each node): adding a variant is cheap (one new class implementing the interface); adding an operation means editing every existing class.
Visitor: adding an operation is cheap (one new visitor class); adding a variant means editing the visitor interface and every implementation — potentially a lot of code, including code you do not own if visitors are public API.

Visitor deliberately buys operation-extensibility with variant-extensibility. That is a bet on which axis moves. It pays off when:

The node hierarchy is stable and closed (an AST for a fixed grammar, a fixed document model, a compiler IR).
Operations are numerous and growing (type-check, constant-fold, optimize, pretty-print, generate code, lint, compute metrics).
Each operation is cohesive — you want all the code for "pretty-print" in one place instead of smeared across 40 node classes.

It is the wrong bet when node types churn — the usual failure story is a plugin ecosystem where third parties add node kinds and every existing visitor breaks.

Mitigation. A DefaultVisitor base with no-op or "visit children" defaults means adding a node type only breaks visitors that care — but it trades compile-time exhaustiveness for silent omissions, which is a real correctness hazard in compilers.

Other Visitor costs

Encapsulation leak — visitors need access to node internals, so nodes expose accessors they otherwise would not.
Traversal entanglement — who walks the tree? If each visitX recurses into children, traversal order is duplicated across every visitor. Cleaner designs separate traversal (an explicit walker, or Iterator) from the per-node operation, and make order (pre/post/in-order) an explicit choice, which matters for scope resolution or evaluation semantics.
Deep recursion — deeply nested trees can overflow the stack; production compilers often use an explicit worklist/stack.
State across visits — a visitor is often stateful (accumulating output, a symbol table), which makes it non-reentrant and unsafe to share across threads.
Readability — control flow ping-pongs between accept and visit, which newcomers find genuinely hard to follow.

Contrast: Iterator

Iterator provides sequential access to the elements of an aggregate without exposing its underlying representation. Roles: an aggregate that produces an iterator, and an iterator with hasNext()/next() (or an internal forEach) holding the traversal cursor.

Its trade space is different and much smaller:

External iterator (client calls next()) gives the client control — early exit, interleaving two sequences, laziness. Internal iterator (collection.forEach(fn)) gives the collection control, which is simpler and enables optimized or parallel traversal but makes early exit awkward.
Concurrent modification: fail-fast iterators throw when the collection changes mid-traversal; snapshot/copy-on-write iterators see a stale view; weakly-consistent iterators see some updates. Each is a deliberate correctness choice.
It says nothing about what you do per element and imposes no expression-problem penalty. Adding a new collection type does not break existing consumers; adding a new operation is just new client code.

They compose. A common architecture is: Iterator (or a dedicated walker) supplies the traversal; Visitor supplies the polymorphic per-node operation; the two evolve independently. Saying "Visitor and Iterator are alternatives" is a mischaracterisation — one is about how you reach the elements, the other about how you dispatch on them.

What a strong answer includes

Why single dispatch is insufficient, and the mechanical two-hop fix.
The expression problem as the underlying trade, named explicitly.
The stability precondition on the node hierarchy.
Modern alternatives — sealed hierarchies with exhaustive pattern matching, or true multimethods — and why Visitor persists in languages lacking them.
That Iterator makes no comparable trade; it decouples traversal from representation, nothing more.

## Single vs double dispatch **Dynamic dispatch** means the runtime picks the method implementation from the *runtime* type of an object. Nearly all mainstream OO languages do **single dispatch**: the choice depends on the runtime type of the *receiver* only. Overloads (`visit(Literal)`, `visit(Add)`) are resolved at compile time from the *static* type of the argument. So this fails: ``` void render(Visitor v, Node n) { v.visit(n); } // always picks visit(Node) ``` Even if `n` is really an `Add`, the compiler picked the overload from the declared type `Node`. **Double dispatch** selects the implementation from the runtime types of *two* objects. Visitor simulates it with two single dispatches: 1. `node.accept(visitor)` — dispatches on the node's runtime type. 2. Inside `Add.accept`, the call is `visitor.visitAdd(this)` — `this` is statically known to be `Add` here, so the correct overload is chosen, and the call dispatches on the visitor's runtime type. Two hops, both single dispatch, together equivalent to dispatching on the (node, visitor) pair. ``` interface Node { accept(v: Visitor) } class Add : Node { accept(v) = v.visitAdd(this) } // hop 2 class Lit : Node { accept(v) = v.visitLit(this) } interface Visitor { visitAdd(a: Add); visitLit(l: Lit) } class Printer : Visitor { visitAdd(a){...}; visitLit(l){...} } tree.accept(Printer()) // hop 1 ``` The repetitive one-line `accept` in every node is the price of the language's missing multiple dispatch. Languages that *have* multiple dispatch (Common Lisp CLOS multimethods, Julia, Clojure's `defmulti`) do not need Visitor at all; languages with exhaustive pattern matching over sealed/closed hierarchies (Rust enums, Scala sealed traits, modern Java/Kotlin sealed types with `when`/`switch` patterns) get the same benefit with compiler-checked exhaustiveness and far less ceremony — an important modern caveat. ## The expression problem Phil Wadler's framing: you want to extend a system along **two axes** — new data variants and new operations — without modifying existing code and without losing type safety. - **Plain OO polymorphism** (a method on each node): adding a **variant** is cheap (one new class implementing the interface); adding an **operation** means editing every existing class. - **Visitor**: adding an **operation** is cheap (one new visitor class); adding a **variant** means editing the visitor interface and every implementation — potentially a lot of code, including code you do not own if visitors are public API. Visitor deliberately buys operation-extensibility with variant-extensibility. That is a bet on which axis moves. It pays off when: - The node hierarchy is **stable and closed** (an AST for a fixed grammar, a fixed document model, a compiler IR). - Operations are **numerous and growing** (type-check, constant-fold, optimize, pretty-print, generate code, lint, compute metrics). - Each operation is **cohesive** — you want all the code for "pretty-print" in one place instead of smeared across 40 node classes. It is the wrong bet when node types churn — the usual failure story is a plugin ecosystem where third parties add node kinds and every existing visitor breaks. **Mitigation.** A `DefaultVisitor` base with no-op or "visit children" defaults means adding a node type only breaks visitors that care — but it trades compile-time exhaustiveness for silent omissions, which is a real correctness hazard in compilers. ## Other Visitor costs - **Encapsulation leak** — visitors need access to node internals, so nodes expose accessors they otherwise would not. - **Traversal entanglement** — who walks the tree? If each `visitX` recurses into children, traversal order is duplicated across every visitor. Cleaner designs separate traversal (an explicit walker, or Iterator) from the per-node operation, and make order (pre/post/in-order) an explicit choice, which matters for scope resolution or evaluation semantics. - **Deep recursion** — deeply nested trees can overflow the stack; production compilers often use an explicit worklist/stack. - **State across visits** — a visitor is often stateful (accumulating output, a symbol table), which makes it non-reentrant and unsafe to share across threads. - **Readability** — control flow ping-pongs between `accept` and `visit`, which newcomers find genuinely hard to follow. ## Contrast: Iterator **Iterator** provides sequential access to the elements of an aggregate without exposing its underlying representation. Roles: an aggregate that produces an iterator, and an iterator with `hasNext()`/`next()` (or an internal `forEach`) holding the traversal cursor. Its trade space is different and much smaller: - **External iterator** (client calls `next()`) gives the client control — early exit, interleaving two sequences, laziness. **Internal iterator** (`collection.forEach(fn)`) gives the collection control, which is simpler and enables optimized or parallel traversal but makes early exit awkward. - **Concurrent modification**: fail-fast iterators throw when the collection changes mid-traversal; snapshot/copy-on-write iterators see a stale view; weakly-consistent iterators see some updates. Each is a deliberate correctness choice. - It says nothing about *what* you do per element and imposes no expression-problem penalty. Adding a new collection type does not break existing consumers; adding a new operation is just new client code. **They compose.** A common architecture is: Iterator (or a dedicated walker) supplies the traversal; Visitor supplies the polymorphic per-node operation; the two evolve independently. Saying "Visitor and Iterator are alternatives" is a mischaracterisation — one is about *how you reach* the elements, the other about *how you dispatch* on them. ## What a strong answer includes 1. Why single dispatch is insufficient, and the mechanical two-hop fix. 2. The expression problem as the underlying trade, named explicitly. 3. The stability precondition on the node hierarchy. 4. Modern alternatives — sealed hierarchies with exhaustive pattern matching, or true multimethods — and why Visitor persists in languages lacking them. 5. That Iterator makes no comparable trade; it decouples traversal from representation, nothing more.

Your language has sealed hierarchies and exhaustive pattern matching. Do you still need Visitor?
Usually not. A `when`/`match` over a sealed set gives the same operation-side extensibility with compiler-checked exhaustiveness, no `accept` boilerplate, and no encapsulation leak. Visitor still earns its place when the hierarchy cannot be sealed, when you need dynamic visitor selection or a visitor object that carries state and configuration, or when the operation set is a published extension point.
How do you keep traversal logic out of every visitor?
Separate the walker from the operation: a traversal component owns child recursion and order (pre/post/in-order), invoking a per-node callback or visitor that only handles the node itself. That removes duplicated recursion from each visitor, makes order an explicit and testable choice, and lets you swap in an iterative worklist to avoid stack overflow on deep trees.
What breaks when a third party adds a node type to a hierarchy you visit?
Every visitor implementing the full interface stops compiling — including visitors you do not own. Adding a defaulting base visitor keeps things compiling but silently skips the new node, which in a compiler or serializer is a correctness bug rather than a build failure. That tension is the practical face of the expression problem, and it is why Visitor demands a closed hierarchy.

Think of a customs desk. Single dispatch is one officer handling whatever arrives. Double dispatch is: the traveller first declares which queue they belong to (accept), then the specialist officer for that queue and that inspection type handles them (visitX). Adding a new inspection type means hiring one specialist team; adding a new traveller category means retraining every team that already exists.

saying these in an interview costs you the question

Saying method overloading alone gives double dispatch — overloads bind on the static argument type.
Describing Visitor as making a class hierarchy easier to extend; it makes adding *operations* easier and adding *types* harder.
Presenting Visitor and Iterator as competing solutions to the same problem.
Ignoring the encapsulation leak Visitor forces on node classes.
Recommending Visitor for a hierarchy that changes frequently or is open to third-party extension.
Forgetting that sealed types with exhaustive matching, or true multimethods, remove the need for it.

Why does the Visitor pattern need double dispatch, and what trade-off does it make that Iterator does not?

§ answer

basics

solid answer

code

§ go deeper

▾level notes4 levels

▾deep dive~5 min

Single vs double dispatch

The expression problem

Other Visitor costs

Contrast: Iterator

What a strong answer includes

▾common follow-ups3 questions

▾analogy~20 s

▾red flags6 flags

§ context

▾related questions5 questions

▾related topics4 topics

Single vs double dispatch

The expression problem

Other Visitor costs

Contrast: Iterator

What a strong answer includes

answer

go deeper

context