Tree-Walking Interpreters
One recursive function, `evaluate(node)`, switching on the node kind and calling itself on the children. It is the simplest correct implementation of a language, it is the right first one to write, and it pays a pointer chase and a dispatch for every node it visits.
Can I just walk the syntax tree and execute it, and what does that cost me?
The program stays a typed AST — a heap of node objects connected by pointers — and execution is a traversal of it. There is no separate executable form at all: the tree the type checker annotated is the thing that runs, and the interpreter's own call stack is the program counter. The question this representation answers is "what is the smallest thing that can correctly run this language", and the answer is "the tree you already have".
The interpreter must evaluate subexpressions in the order the language specifies, must apply the same coercion and overflow rules the type checker assumed, and must raise the language's errors at the points the language says they occur. It is entitled to assume the tree is well-formed and well-typed, because semantic analysis ran first — which is exactly why an interpreter for a checked language can omit runtime type tests that an interpreter for an unchecked one cannot.
Key points
- A tree-walking interpreter is one recursive function over the AST, and the host language's call stack serves as the program counter.
- It is the simplest implementation that is fully correct, which makes it the right first one and a durable oracle for every later one.
- The cost is per node: an indirect dispatch, dependent pointer loads with poor locality, and a host call frame for work that is often one arithmetic operation.
- Name lookup by string is frequently the dominant cost, and resolving names to slots ahead of time recovers much of it without abandoning the tree.
- Everything the language *means* is decided here — evaluation order, scoping, truthiness, error points — and no later implementation may change it.
- Leaving the tree buys speed and buys the ability to have a backend at all; those are two separate reasons and only one of them is about performance.
The whole implementation is one function
A tree-walking interpreter is evaluate(node, environment): switch on the node kind, recurse into the children, combine. Literals return themselves, identifiers look themselves up, binary nodes evaluate both sides and apply the operator, if evaluates the condition and then exactly one branch. It fits on a page, and everything about it is obvious, which is the point.
That obviousness is worth real money. The interpreter *is* the specification of your language's dynamic semantics in the early days, and the fact that you can read it in one sitting means disagreements about what the language means get settled by reading rather than by arguing. Every implementation strategy after this one is measured against the behavior this one defined.
1function evaluate(node, env):2 switch node.kind:3 case "Int": return node.value4 case "Name": return env.lookup(node.name)5 case "Binary": left = evaluate(node.left, env)6 right = evaluate(node.right, env)7 return apply(node.op, left, right)8 case "If": if truthy(evaluate(node.cond, env)):9 return evaluate(node.then, env)10 else:11 return evaluate(node.else, env)12 case "Call": fn = evaluate(node.callee, env)13 args = [evaluate(a, env) for a in node.args]14 return evaluate(fn.body, env.child(fn.params, args))Two decisions are hiding in plain sight. The Binary case evaluates the left operand before the right, which is a language decision this code silently makes law. And the Call case builds a child environment, which is where lexical versus dynamic scoping is decided — see [[static-vs-dynamic-scoping]]. An interpreter this small still contains every semantic commitment the language makes.
What each node visit costs
Executing one addition means: follow a pointer to the binary node, read a tag or make a virtual call to find out what kind of node it is, recurse into the left child through another pointer, do the same on the right, then combine. The arithmetic is one machine instruction. Everything else is overhead, and the overhead is not a constant factor away from the arithmetic — it dwarfs it.
The locality is the part people underestimate. AST nodes are separately allocated objects scattered across the heap, so a traversal is a chain of dependent loads that the prefetcher cannot help with. A bytecode array, by contrast, is contiguous, and the next instruction is usually already in cache — the argument made in [[bytecode]] and the reason the same program runs several times faster with no change to the semantics.
- One indirect dispatch per node, whether by a switch on a tag or by a virtual call in a visitor — see
[[visitor-pattern]]. - One or more dependent pointer loads per node, with poor locality because nodes were allocated at parse time in parse order and are visited in evaluation order.
- Host-language call overhead per node: a real stack frame, saved registers and a return, for what is often a single arithmetic operation.
- Environment lookup by name if the interpreter has not resolved variables to slots — a hash lookup per variable read, which is frequently the single largest cost.
- No opportunity to amortize: the same node costs the same on the ten-millionth visit as on the first, which is precisely the gap
[[jit-compilation]]exists to close.
It is still the right first implementation
Write this one first, and not as a stepping stone you feel embarrassed about. It gets you a language you can run, which means you can write tests, which means every later implementation has an oracle to be checked against. Differential testing a new bytecode backend against the tree-walker is the cheapest correctness insurance in the whole project — the technique [[differential-testing]] generalizes.
It also front-loads the decisions that matter and defers the ones that do not. Scoping, evaluation order, truthiness, error semantics and closure capture all get settled here, in code anyone can read. Instruction encoding, slot numbering and dispatch technique are all deferred, and none of them change what the language means.
case "Name": return env.lookup(node.name) // hash lookup, every read
case "Name": return frame.slots[node.slot] // index, resolved once at check time
Only if name resolution ran before evaluation and assigned every identifier a fixed slot in a frame whose layout is known statically — which requires that the language has no construct able to introduce a binding at runtime that the resolver did not see. Under that condition the slot index and the name denote the same storage on every execution.
If the language has eval, dynamic variable creation, or an import *-style form that can add bindings to a scope at runtime. Then a name may refer to storage that did not exist when the resolver ran, and the precomputed slot is either wrong or absent — which is why languages with those features keep a dictionary on the frame and pay for it.
Why AtlasLang did not stop here
Our implementation could have ended at the typed AST. It executes correctly, it would have been a third of the code, and for the programs a learner types it would be indistinguishable in speed. We went on to IR and bytecode for reasons that are about teaching and about downstream stages, not about performance, and it is worth being explicit about that rather than implying we needed the speed.
The reasons: the pipeline explorer's whole argument is that each representation answers a question the previous one could not, and a tree-walker demonstrates that argument by omission at best. [[register-allocation]], [[instruction-selection]] and [[live-ranges]] have nothing to operate on without a linear form. The VM stepper needs an instruction pointer to step. And [[out-of-ssa]] only becomes a visible problem when something downstream has to execute the result, which a tree-walker never does. We built the rest of the pipeline because the rest of the domain needed something to be about.
How it works
The steps, in the order the compiler takes them.
- Parse and type-check first, so the evaluator may assume a well-formed, well-typed tree and skip defensive checks.
- Define an environment: a chain of frames mapping names, or better slots, to values, with a child frame per call.
- Write
evaluate(node, env)as a switch on node kind, recursing into children in the order the language specifies. - Implement control flow with the host language's own control flow — an
ifnode becomes anifin the evaluator, a loop node becomes a loop. - Implement calls by evaluating the callee and arguments, building a child environment, and recursing into the body, which makes the host stack the language's call stack.
- Implement non-local exits —
return,break, exceptions — with host exceptions or an explicit result-status union, because a plain recursive evaluator has no other way to unwind.
How it breaks
What the engineer observes when it goes wrong — not what goes wrong internally.
- Deep recursion in the interpreted program overflows the host stack, and the user sees a host-language stack trace mentioning
evaluatetwo thousand times instead of an error about their program. - The evaluator implicitly fixes an evaluation order the language never specified, and a program with side effects in both operands behaves differently under a later bytecode implementation.
- The environment chain is captured by reference where the language specified by value, and a closure created in a loop sees the loop variable's final value — the classic symptom, and it is decided entirely in this file.
- A node kind added to the parser is not added to the evaluator, and the switch falls through to a default that returns a null-like value, producing a wrong answer rather than an error.
- Performance degrades non-linearly as programs grow, because name lookup is a hash lookup per read and scope chains get deeper — the user reports that "the language gets slow on big files" with no single hot spot.
When it helps
- The first implementation of any new language, always.
- A configuration or expression language where programs are small, run once, and startup dominates — generating bytecode would cost more than interpreting the tree.
- As a reference implementation to differential-test a faster one against, for as long as the project lives.
- Embedded or scripted extension points where implementation size matters more than throughput.
When it hurts
- Long-running or loop-heavy programs, where the per-node overhead is paid millions of times and nothing amortizes it.
- Anything that needs a backend: there is no linear form for a register allocator, a peephole pass or a JIT to work on.
- Deeply recursive interpreted programs, because the host stack becomes a hard limit on the guest's recursion depth.
What it costs
Every one of these is paid by something.
- Executing the tree buys the smallest possible implementation and pays a per-node dispatch and pointer chase on every single operation, forever, with no amortization.
- Using the host call stack for the language's call stack buys enormous simplicity and pays by making the guest's recursion depth a function of the host's stack size — a limit you did not choose and cannot easily raise.
- Keeping names as strings buys
evaland dynamic scopes and pays a hash lookup per variable read; resolving to slots buys that back and pays by forbidding runtime binding creation. - Skipping the linear form buys weeks of implementation time and pays them back later with interest if a JIT is ever needed, because the JIT will have to build the representation you skipped.
What else you could do
What a different compiler or language does instead, and when that is better.
- Compile the tree to bytecode and interpret that: several times faster, a code generator to write, and a linear form everything downstream wants —
[[bytecode-compiler]]. - Closure compilation: walk the tree once, turning each node into a host closure that takes the environment and returns a value. The traversal and the type dispatch happen once instead of per execution, and the tree structure is preserved. Often two to three times faster than naive walking for a fraction of the work of a bytecode backend.
- Compile ahead of time to native code and have no interpreter —
[[aot-compilation]]. - Transpile to a language that already has a fast implementation, which is the cheapest way to get a fast language and the most expensive way to get good error messages —
[[typescript-pipeline]].
See it for yourself
The flag, dump or tool that shows you this directly.
- Read one: Ruby before YARV, early Lisp evaluators and most teaching interpreters are tree-walkers, and they are short enough to read end to end in an evening.
- Profile your own with any sampling profiler; the flame graph of a tree-walker is a tower of
evaluateframes, which is itself the clearest possible picture of the cost model. - Compare against a bytecode implementation of the same language where one exists — Ruby's move to YARV and Python's bytecode compiler are both well documented, with before-and-after numbers.
- Our pipeline stops showing the tree at
/compilers/pipelineand continues into IR and bytecode; the AST panel is the representation a tree-walker would have executed directly.
Plausible wrong readings
Stated the way a confident engineer states them.
- "A tree-walking interpreter is not a real implementation." It is a complete and correct implementation of the language. It is slow, which is a different property.
- "Tree-walking is slow because recursion is slow." Recursion is cheap. The costs are the per-node dispatch, the scattered pointer loads, and — very often — name lookup by string.
- "It executes the source code." It executes a tree the parser and type checker already produced. The characters are long gone; only the spans survive.
- "Adding a bytecode stage means throwing this away." Keep it. It is your semantics oracle, and running both on the same inputs catches backend bugs nothing else will.
Misconceptions
The claim, and what is actually true.
Go deeper
The same idea at increasing depth. Stop wherever it stops being useful.
overview
Write a function that takes a syntax-tree node and returns its value, and have it call itself on the node's children. Numbers evaluate to themselves, + evaluates both sides and adds, if evaluates the condition and then one branch. That is a working language implementation, and it is where every language should start.
practical
Two changes buy most of the available speed without leaving the tree. First, resolve names to frame slots during semantic analysis so a variable read is an array index rather than a hash lookup. Second, avoid re-deciding what kind of node you are looking at on every visit — either cache the decision on the node or convert each node into a closure once. If after both of those the interpreter is still too slow, that is the honest moment to write a bytecode backend, and you will have a reference implementation to test it against.
advanced
The reason a tree-walker cannot be made fast has a name: there is nothing to amortize over. Every optimization technique that matters at runtime — inline caching, superinstructions, speculation, compiling a hot loop — needs a stable place to attach the optimized version of some recurring work. A bytecode instruction stream provides that place; a tree traversal does not, because the "instruction" is a node visit whose identity is entangled with the traversal itself. Closure compilation is interesting precisely because it manufactures such a place: the closure per node is a stable object you can specialize, which is how partial-evaluation-based interpreter frameworks get from tree-walking speed to compiled speed without ever emitting bytecode.
How much this depends on
Nothing in this domain is true of every compiler. These say how much.
If you were asked this in an interview
- Write the evaluator for a language with integers, addition and
if. Now tell me which language decisions you just made without noticing. - Your tree-walking interpreter is too slow. What do you try before writing a bytecode compiler?
- You are adding a bytecode backend. What do you do with the tree-walker, and why?
Connections
- Programming Languages & Runtime Internals — Environments, closures and the objects the evaluator allocates on every callA tree-walker allocates an environment per call and captures it in every closure, so its allocation rate is a runtime concern that dominates its performance long before dispatch does. What those environments cost to allocate and reclaim is the runtime's subject, and it decides whether the interpreter is merely slow or unusable.