When would you put the evaluation logic on the expression nodes themselves versus extracting it into a Visitor over the abstract syntax tree?

seniorshould knowfreq 16%

answer

expression problem: node types vs operations
nodes = add types cheap, add ops costly
Visitor = add ops cheap, add types costly
accept/visitX double dispatch boilerplate
sealed types + exhaustive match = modern middle ground

basics

~20 s

Put interpret() on the nodes when the language has few operations and you expect to add new node types. Use a Visitor when you need many operations over the same tree — evaluate, print, type-check, optimize — because each becomes one class instead of a method on every node.

solid answer

~50 s

This is the expression problem: two axes of extension, node types and operations, and each design makes one cheap and the other expensive. Putting interpret directly on each node — the textbook Interpreter — makes adding a node type purely additive (write one class) but adding an operation invasive (edit every class). A Visitor inverts it: node classes expose accept(visitor), and each operation is one visitor class with a method per node type, so adding PrettyPrinter, TypeChecker, Optimizer, or CostEstimator touches no node, while adding a node type forces every visitor to be updated (the compiler catches it if the visitor interface is exhaustive). Choose by which axis actually moves: a stable grammar with growing tooling needs Visitor; a growing grammar with a single operation keeps interpret on nodes. In practice, generated ASTs from parser tools ship with visitor scaffolding, so Visitor wins for anything nontrivial. Modern languages soften the trade-off with sealed hierarchies plus exhaustive pattern matching, which gives visitor-like separation without the double-dispatch boilerplate.

This is the expression problem: two axes of extension, node types and operations, and each design makes one cheap and the other expensive. Putting `interpret` directly on each node — the textbook Interpreter — makes **adding a node type** purely additive (write one class) but **adding an operation** invasive (edit every class). A Visitor inverts it: node classes expose `accept(visitor)`, and each operation is one visitor class with a method per node type, so adding `PrettyPrinter`, `TypeChecker`, `Optimizer`, or `CostEstimator` touches no node, while adding a node type forces every visitor to be updated (the compiler catches it if the visitor interface is exhaustive). Choose by which axis actually moves: a stable grammar with growing tooling needs Visitor; a growing grammar with a single operation keeps `interpret` on nodes. In practice, generated ASTs from parser tools ship with visitor scaffolding, so Visitor wins for anything nontrivial. Modern languages soften the trade-off with sealed hierarchies plus exhaustive pattern matching, which gives visitor-like separation without the double-dispatch boilerplate.

code

pseudocode · 14 lines

pseudocode

// A: operation on nodes  -> new node type is additive
class And(l, r) : Expr { interpret(ctx) = l.interpret(ctx) && r.interpret(ctx) }

// B: Visitor              -> new operation is additive
class And(l, r) : Expr { accept(v) = v.visitAnd(this) }
class Evaluator   : Visitor<Value>  { visitAnd(n) = n.l.accept(this) && n.r.accept(this) }
class PrettyPrint : Visitor<String> { visitAnd(n) = "(" + n.l.accept(this) + " AND " + n.r.accept(this) + ")" }

// C: sealed type + exhaustive match -> Visitor's separation, no accept() boilerplate
fun eval(e: Expr, ctx: Context): Value = when (e) {
  is And     -> eval(e.l, ctx) && eval(e.r, ctx)
  is Literal -> e.v
  // compiler errors here if a new Expr subtype is added
}

go deeper

for a junior

Say interpret() on nodes keeps each node self-contained; a Visitor gathers one operation in one place. Give one example of each.

for a middle

State the trade-off explicitly: nodes make new node types cheap, Visitor makes new operations cheap; tie the pick to what you expect to change.

for a senior

Name the expression problem, discuss exhaustiveness checking, visitor state, generics on return types, and hybrid designs that keep the hot operation on nodes.

for a principal

Position it as an evolution-cost decision for a long-lived language surface: how many operations the tooling will need, who extends the grammar, whether sealed types plus pattern matching replace Visitor, and how compiled evaluation changes the calculus.

The underlying tension: the expression problem

Any design over a tree of node types faces two directions of change:

New node types — the grammar gains BETWEEN, CASE, string functions.
New operations — you now need to pretty-print, type-check, cost-estimate, optimize, serialize, or explain the tree, not just evaluate it.

Standard object-oriented dispatch makes (1) cheap and (2) expensive. Functional-style dispatch (a function that matches on node type) makes (2) cheap and (1) expensive. Doing both cheaply, with static safety, is the expression problem.

Design A — interpret() on the nodes (textbook Interpreter)

interface Expr { Value interpret(Context ctx) }
class And(l, r) : Expr { interpret(ctx) = l.interpret(ctx) && r.interpret(ctx) }

Good: adding Between = one new class, nothing else recompiles or changes. Each node is cohesive and unit-testable in isolation. No double dispatch, no boilerplate; often marginally faster (one virtual call instead of two).

Bad: adding "pretty-print with correct parentheses" means a second method on every class; "type-check" a third; "estimate selectivity" a fourth. Node classes bloat into grab-bags of unrelated concerns, and each new concern is a shotgun edit. Cross-cutting semantics (source positions in errors, a step budget, null handling) also spread across all classes.

Design B — Visitor over the AST

interface Expr    { R accept(Visitor<R> v) }
interface Visitor<R> { R visitAnd(And n); R visitNot(Not n); R visitLiteral(Literal n); ... }
class And(l, r) : Expr { accept(v) = v.visitAnd(this) }
class Evaluator(ctx) : Visitor<Value> { visitAnd(n) = n.l.accept(this) && n.r.accept(this) ... }

Good: nodes become plain, dumb data. Each operation is one class holding all cases side by side, which is exactly what you want for printing, type-checking, and optimizing — logic that must reason about the whole grammar consistently. Operations can carry their own state (an indentation level, a symbol table, an error list) without polluting nodes. If the visitor interface has no default methods, the compiler flags every visitor when a node type is added.

Bad: adding a node type touches every visitor. Double dispatch (accept → visitX) is boilerplate and slightly indirect. Recursion control is manual, and getting return types right often needs generics.

Practical selection rules

One operation, growing grammar → nodes. A small feature-flag rule evaluator that only ever evaluates.
Stable grammar, many operations → Visitor. Anything with a real front end: you will want evaluate + validate + format + explain.
Both axes moving → Visitor plus a default/base visitor that handles unknown nodes generically, accepting that you lose exhaustiveness checking in exchange for not breaking every visitor. Or move to a sealed hierarchy with exhaustive matching.
Generated ASTs → whatever the generator produces, which is almost always visitors/listeners.

The modern middle ground

Sealed/algebraic data types plus exhaustive pattern matching (Kotlin sealed + when, Scala/Rust/Swift enums, Java sealed interfaces with switch patterns, F#/OCaml variants) give you operation-as-a-function with compile-time exhaustiveness: each operation is one function, and adding a node type makes every non-exhaustive match fail to compile. That is Visitor's separation without accept boilerplate — the reason many contemporary codebases write no literal Visitor at all.

Hybrid designs are common and legitimate: keep the single hottest operation (interpret) inlined on the nodes for speed and simplicity, and express the rarer tooling operations (print, validate, optimize) as visitors.

Interviewer's real target

A strong answer does not pick a winner. It names the expression problem, states which axis each design optimizes, ties the choice to expected change, and mentions pattern matching as the modern resolution.

## The underlying tension: the expression problem Any design over a tree of node types faces two directions of change: 1. **New node types** — the grammar gains `BETWEEN`, `CASE`, string functions. 2. **New operations** — you now need to pretty-print, type-check, cost-estimate, optimize, serialize, or explain the tree, not just evaluate it. Standard object-oriented dispatch makes (1) cheap and (2) expensive. Functional-style dispatch (a function that matches on node type) makes (2) cheap and (1) expensive. Doing both cheaply, with static safety, is the *expression problem*. ## Design A — interpret() on the nodes (textbook Interpreter) ``` interface Expr { Value interpret(Context ctx) } class And(l, r) : Expr { interpret(ctx) = l.interpret(ctx) && r.interpret(ctx) } ``` **Good**: adding `Between` = one new class, nothing else recompiles or changes. Each node is cohesive and unit-testable in isolation. No double dispatch, no boilerplate; often marginally faster (one virtual call instead of two). **Bad**: adding "pretty-print with correct parentheses" means a second method on every class; "type-check" a third; "estimate selectivity" a fourth. Node classes bloat into grab-bags of unrelated concerns, and each new concern is a shotgun edit. Cross-cutting semantics (source positions in errors, a step budget, null handling) also spread across all classes. ## Design B — Visitor over the AST ``` interface Expr { R accept(Visitor<R> v) } interface Visitor<R> { R visitAnd(And n); R visitNot(Not n); R visitLiteral(Literal n); ... } class And(l, r) : Expr { accept(v) = v.visitAnd(this) } class Evaluator(ctx) : Visitor<Value> { visitAnd(n) = n.l.accept(this) && n.r.accept(this) ... } ``` **Good**: nodes become plain, dumb data. Each operation is one class holding all cases side by side, which is exactly what you want for printing, type-checking, and optimizing — logic that must reason about the whole grammar consistently. Operations can carry their own state (an indentation level, a symbol table, an error list) without polluting nodes. If the visitor interface has no default methods, the compiler flags every visitor when a node type is added. **Bad**: adding a node type touches every visitor. Double dispatch (`accept` → `visitX`) is boilerplate and slightly indirect. Recursion control is manual, and getting return types right often needs generics. ## Practical selection rules - **One operation, growing grammar** → nodes. A small feature-flag rule evaluator that only ever evaluates. - **Stable grammar, many operations** → Visitor. Anything with a real front end: you will want evaluate + validate + format + explain. - **Both axes moving** → Visitor plus a default/base visitor that handles unknown nodes generically, accepting that you lose exhaustiveness checking in exchange for not breaking every visitor. Or move to a sealed hierarchy with exhaustive matching. - **Generated ASTs** → whatever the generator produces, which is almost always visitors/listeners. ## The modern middle ground Sealed/algebraic data types plus exhaustive pattern matching (Kotlin `sealed` + `when`, Scala/Rust/Swift enums, Java sealed interfaces with switch patterns, F#/OCaml variants) give you operation-as-a-function with **compile-time exhaustiveness**: each operation is one function, and adding a node type makes every non-exhaustive match fail to compile. That is Visitor's separation without `accept` boilerplate — the reason many contemporary codebases write no literal Visitor at all. Hybrid designs are common and legitimate: keep the single hottest operation (`interpret`) inlined on the nodes for speed and simplicity, and express the rarer tooling operations (print, validate, optimize) as visitors. ## Interviewer's real target A strong answer does **not** pick a winner. It names the expression problem, states which axis each design optimizes, ties the choice to expected change, and mentions pattern matching as the modern resolution.

How does a Visitor let the compiler catch an unhandled node type, and how do you lose that guarantee?
If the visitor interface declares an abstract method per node type with no defaults, adding a node type breaks compilation of every visitor until it is handled. You lose that safety by adding a base visitor with default no-op or generic-fallback implementations, which trades exhaustiveness for not breaking existing visitors.
Is a Visitor slower than putting interpret() on the nodes?
Slightly, in principle: double dispatch means two virtual calls per node instead of one, and visitor state adds indirection. In practice the difference is minor compared with allocation and cache effects; if evaluation is genuinely hot, the answer is to compile the tree to closures or bytecode rather than to argue about dispatch.
Why do many modern codebases skip Visitor entirely?
Sealed/algebraic node hierarchies plus exhaustive pattern matching give the same operation-per-function separation with compile-time exhaustiveness checks and none of the accept/visitX boilerplate.

A restaurant menu versus a stack of recipe cards. Putting the method on each node is like every dish knowing how to cook itself: adding a dish is trivial, but a new demand — 'every dish must also report its allergens' — means editing every dish. A Visitor is one allergen-report card that lists all dishes: new reports are trivial, but a new dish means updating every card.

saying these in an interview costs you the question

Claiming Visitor is universally better without naming the axis it makes expensive
Not recognizing the expression problem behind the question
Believing Visitor lets you add both node types and operations for free
Adding default no-op methods to a visitor base without acknowledging the lost exhaustiveness checking
Treating pattern matching over a sealed hierarchy as unrelated to Visitor

When would you put the evaluation logic on the expression nodes themselves versus extracting it into a Visitor over the abstract syntax tree?

§ answer

basics

solid answer

code

§ go deeper

▾level notes4 levels

▾deep dive~3 min

The underlying tension: the expression problem

Design A — interpret() on the nodes (textbook Interpreter)

Design B — Visitor over the AST

Practical selection rules

The modern middle ground

Interviewer's real target

▾common follow-ups3 questions

▾analogy~20 s

▾red flags5 flags

§ context

▾related questions6 questions

▾related topics4 topics

The underlying tension: the expression problem

Design A — interpret() on the nodes (textbook Interpreter)

Design B — Visitor over the AST

Practical selection rules

The modern middle ground

Interviewer's real target

answer

go deeper

context