Visitor Pattern

Put each operation over a fixed family of classes into its own visitor object, so new operations do not touch the classes.

Overview

The problem: many operations over a fixed set of types

An expression tree has a few node types: numbers, additions, multiplications. The program needs many operations on that tree: evaluate it, print it, count its nodes, check its types, simplify it. The obvious design adds one method per operation to every node class.

Num — method — method — method — method — method
Add — method — method — method — method — method
Mul — method — method — method — method — method

Each new operation is a new column: one more method in every node class, and code for one concern (say, printing) scattered across three files. When the set of node types is stable and the set of operations keeps growing, that is the wrong way around. The Visitor pattern turns each column into one class.

The pattern

Visitor is one of the 23 patterns in the 1994 Gang of Four book (Gamma, Helm, Johnson and Vlissides). Each element class gets a single method, accept(visitor), whose body is always the same one line: call the visitor's method for my type, passing myself. Each visitor class has one method per element type and holds the whole of one operation.

Double dispatch

Ordinary method calls pick the code to run from one type: the receiver's. Here the code depends on two types, the node and the visitor. The pattern gets there with two ordinary calls in a row.

That is why every accept body is one line. The line is the first dispatch. The method name inside it (visit_add, not visit) is what makes the second dispatch work without an isinstance check.

A runnable example

Adding NodeCounter did not open Num, Add or Mul. Adding a fourth node type, say Neg, would open all three visitors. That is the trade the pattern makes.

The expression problem

Philip Wadler named this tension the expression problem in 1998: you want to add both new cases (types) and new functions (operations) without recompiling existing code, and keep static type safety. Plain objects and Visitor each solve half of it.

Methods on each class — Edit every class — Add one class
Visitor — Add one class — Edit every visitor

Pick by which one changes more often. Compilers, linters, formatters and document tools have a grammar that is fixed by a specification and a list of passes that grows for years, so they lean on Visitor. A domain model whose entities keep changing should not.

Alternatives in modern languages

Much of the boilerplate exists to get a second dispatch out of a language that only has one. Newer language features give you that dispatch directly.

Python match statement — Branch on the node's class with case Add(left=l, right=r); added in Python 3.10 — PEP 634
Python functools.singledispatch — A generic function that dispatches on the type of its first argument, with register per type — Python docs
Java 21 pattern matching for switch — switch on a sealed interface; the compiler checks the cases are exhaustive from the permits clause — JEP 441
Python ast.NodeVisitor — The standard library's own Visitor: visit() calls visit_ClassName or falls back to generic_visit() — Python docs

Here is the same expression tree with two of the operations written as match statements.

Same shape, no accept methods. What you lose is the compile-time guarantee that every operation handles every type, which Java's sealed switch keeps and Python does not. In an interview, offer the pattern, then say when the language makes it unnecessary.

What you will be able to do

Say in one sentence what Visitor optimizes for, and what it makes harder.
Explain double dispatch with the two calls, and why accept is always one line.
Write an expression-tree visitor from memory and add a second operation without touching the nodes.
Name the expression problem and place Visitor on the right side of its table.
Offer pattern matching or single dispatch as the modern alternative, with the trade-off.

Interview questions

Show the smell Visitor fixes, and the fix.
Explain double dispatch. Why does Visitor need two calls?
When is Visitor the wrong choice?
What happens when you add a new element type to a Visitor design?
How does Visitor relate to Composite and Iterator?