AtlasLangimplementation

AtlasLang: Evaluating the Tree Directly

The shortest path from a parsed program to a running one is to walk the tree and evaluate as you go. It is where most languages start, it is the version whose correctness is easiest to argue, and it is the version AtlasLang deliberately did not ship — for reasons worth knowing.

The question

What is the least machinery that will actually run a parsed program?

Source→Lexing→Tokens→Parsing→AST→Semantics→Typed→IR→Optimize→Codegen→Machine code→Link→Execute
What the program is here

The typed AST as the executable form, plus an environment: a stack of scopes mapping symbols to values. Nothing is lowered, nothing is linearised, and there is no separate instruction set. The tree that the checker annotated *is* the program, and the interpreter's state is a position in that tree plus the environment stack — which is why this is the representation whose correctness is easiest to argue about.

What this phase may assume or do

A tree-walking evaluator may assume everything earlier phases established: the tree is well-formed, every identifier resolves to a declaration, every expression has a type, and every operator is defined for its operand types. It owes exactly one thing in return — that it evaluates subexpressions in the order the language specifies. AtlasLang specifies left-to-right for binary operands and short-circuit for && and ||, so an evaluator that evaluated the right operand of && unconditionally would be wrong even though every individual operation it performed was correct.

Key points

  • A tree-walking interpreter is one recursive function over node kinds, and each case is a direct statement of what a construct means.
  • Its correctness is provable by structural induction, which is a claim no lowering-and-optimizing pipeline can make as cheaply.
  • It assumes everything earlier phases established and owes exactly one thing: evaluation order, including short-circuit behaviour.
  • AtlasLang deliberately has none, because a tree cannot be analysed — no linear form, no CFG, no SSA, and therefore no optimizer.
  • The performance gap is real but is the symptom; the cause is that the tree does not answer the questions optimization needs asked.
  • The typed AST panel is exactly the representation such an evaluator would consume, so you can hand-evaluate any program and compare with the Execution panel.
  • Variable access by resolved symbol rather than by source name is what makes shadowing correct in the interpreter, just as it is in the lowering.

One function, one switch

A tree-walking interpreter is a recursive function over node kinds. eval(Number) returns its value. eval(Binary) evaluates the left child, evaluates the right child, applies the operator. eval(Identifier) looks the symbol up in the environment. eval(If) evaluates the condition and then evaluates one of the two blocks. eval(While) evaluates the condition and the body in a loop. That is the entire design, and for a language the size of AtlasLang it is perhaps two hundred lines.

The property that makes it valuable is not brevity but *transparency*. Each case is a direct statement of what the corresponding construct means, so the implementation reads as a definition of the language rather than as a strategy for executing it. When you want to know what a % b does, there is one place to look and it says so. That is why interpreters are how nearly every language starts, why they are the reference implementation when there is a faster one alongside, and why a specification written as an evaluator is a thing people do on purpose.

The recursion is also the argument for its correctness. Evaluating a node assumes only that evaluating its children is correct, so the whole evaluator is provable by structural induction over the tree — which is not a claim you can make about a pipeline that lowers to IR, optimizes and then executes bytecode.

The shape of an AtlasLang tree-walking evaluator
1function evalExpr(e, env) {
2  switch (e.kind) {
3    case 'Number': case 'String': case 'Bool':
4      return e.value
5    case 'Identifier':
6      return env.lookup(e.symbol)          // resolved by the checker, not by name
7    case 'Unary':
8      return apply(e.op, evalExpr(e.operand, env))
9    case 'Binary':
10      if (e.op === '&&')                   // control flow, not arithmetic
11        return evalExpr(e.left, env) ? evalExpr(e.right, env) : false
12      return apply(e.op, evalExpr(e.left, env), evalExpr(e.right, env))
13    case 'Call':
14      return callFn(e.callee, e.args.map(a => evalExpr(a, env)), env)
15  }
16}

Two lines carry the whole legality condition. Identifier looks up by e.symbol — the resolved symbol, never the source name — which is what makes shadowing work. And && is written as a conditional rather than as a call to apply, because evaluating both operands and then combining them would evaluate the right-hand side of a short-circuit operator that must not run.

What AtlasLang did instead, and why

implementationThis is AtlasLang's choice, not a general verdict. Ruby ran on a tree-walker until YARV in 1.9; CPython compiles to bytecode but its evaluator is still a switch over opcodes with much of the same character; and plenty of shipped DSLs and configuration languages walk trees forever because their programs are tiny and the simplicity is worth more than the speed. "Start with a tree-walker" remains good advice; "stay there" is a decision about what you need next.

AtlasLang has no tree-walking interpreter. compile() lowers the typed tree to three-address IR, converts to SSA, optimizes, emits stack bytecode and runs it on a virtual machine. The evaluator above is the version this module describes and the implementation deliberately does not contain.

The reason is that a tree-walker would have made most of this domain unteachable. There would be no IR panel, because nothing is lowered. No CFG, no SSA, no phi nodes, because control flow stays as nested tree nodes and is never a graph. No optimizer, because there is no linear form to rewrite. No register allocation and no assembly, because nothing is ever assigned to a machine resource. The pipeline explorer would have four panels instead of twelve, and eight of the modules in this guide would have nothing to point at.

That is a teaching motivation, but it maps exactly onto the real one. Languages abandon tree-walkers for the same reason: the tree is not a representation you can analyse or transform usefully. You cannot ask "which value flows to this use" of a tree without building something else first, and every optimization worth having needs that question answered. Speed is the symptom; the missing representation is the cause.

The performance story is worth stating plainly anyway. A tree-walker spends most of its time on overhead that has nothing to do with the program: a virtual call or a switch dispatch per node, a pointer chase to reach each child, an environment lookup per variable reference, and a boxed value per intermediate result. A bytecode VM replaces the tree traversal with a linear instruction fetch and replaces named lookups with slot indices, which removes most of that — the subject of [[atlaslang-bytecode]] and [[interpreter-performance]].

What each execution strategy can and cannot show youimplementation
Tree-walkingAtlasLang as built
Executable formThe typed AST itselfStack bytecode over local slots
Variable accessEnvironment lookup by symbolSlot index — an array offset
Control flowNested tree nodes; host recursion and loopsNumeric jump targets in a flat instruction list
Can it be analysed?Not usefully — no linear form, no CFGYes: blocks, dominance, SSA, data flow
Can it be optimized?Only by rewriting the treeEight passes to a fixed point
Implementation sizeRoughly one recursive functionTen files
Correctness argumentStructural induction over the treeOne argument per stage, plus per-pass legality conditions

Where you can still see the tree being the program

Even without an interpreter in the implementation, the typed AST is on screen at /compilers/pipeline, and it is exactly the representation the evaluator above would consume. Every field the evaluator needs is populated: symbol on each identifier, so a lookup goes to the right declaration; type on each expression, so the operator to apply is determined; and the tree structure itself, which is the evaluation order.

That is the useful exercise. Type a small program, look at the Typed AST panel, and evaluate it by hand top to bottom. Then look at the Execution panel and compare the printed output. If they agree — and they will — you have demonstrated the thing that matters: the tree-walker and the compiled pipeline are two implementations of the same language, and the whole of the pipeline between them exists to make the second one analysable and fast, not to make it mean something different.

The place where hand-evaluation is most instructive is short-circuit evaluation. Load the shortcircuit example — if (a != 0 && 10 / a > 1) with a zero — and walk the tree. The left operand is false, so a correct evaluator never touches the division. Now look at the IR panel and see that the compiler expressed the same rule by lowering && into two blocks and a branch. Two implementations, one semantics, and the semantics came from the tree.

How it works

The steps, in the order the compiler takes them.

  • Evaluate an expression by switching on its node kind and recursing into children in the order the language specifies.
  • Literals return their value; identifiers look up the resolved symbol in the environment stack.
  • Binary operators evaluate both operands and apply — except && and ||, which are written as conditionals so the right operand can be skipped.
  • Statements are executed in sequence: a Let evaluates its initializer and binds, an Assign evaluates and rebinds, a Print evaluates and emits.
  • An If evaluates the condition and then executes one block; a While re-evaluates the condition each iteration.
  • Entering a block pushes a scope onto the environment; leaving it pops, which is what restores an outer binding after a shadowing one.
  • A call binds arguments into a fresh scope and executes the body, using the host language's stack for the call stack — including, unavoidably, its stack depth limit.
  • A return propagates out of the body, usually as a host-language exception or a sentinel, because a tree walk has no jump.

How it breaks

What the engineer observes when it goes wrong — not what goes wrong internally.

  • Evaluating both operands of && before combining them, so a != 0 && 10 / a > 1 divides by zero when a is zero — the program is wrong and every individual operation was right.
  • Looking variables up by source name instead of by resolved symbol, so an inner let x and an outer x share storage and the wrong value is read after the block ends.
  • Deep recursion in the interpreted program exhausting the *host* stack, producing a host-level stack overflow rather than a language-level error the user can act on.
  • Evaluating a While condition once and caching it, or re-entering a block without pushing a fresh scope, both of which produce loops that behave subtly wrongly rather than obviously so.
  • A return implemented by returning a sentinel that some statement handler forgets to propagate, so the function continues executing after it returned.
  • Performance that is acceptable on examples and unusable on real input, discovered late, because a tree-walker's overhead is per node and therefore invisible on small programs.

When it helps

  • Starting a language, where a working evaluator on day two is worth more than an architecture on day thirty.
  • A reference implementation next to a faster one, where the tree-walker is what you differential-test the optimizing path against — see [[differential-testing]].
  • Configuration languages, template languages and small DSLs, where programs are short and simplicity outlives speed.
  • Explaining semantics: an evaluator case is the clearest possible statement of what a construct means, which is why specifications are sometimes written as one.

When it hurts

  • Anything needing optimization, because the tree is not a representation you can usefully analyse and every transformation has to be a tree rewrite.
  • Hot loops and long-running programs, where per-node dispatch, pointer chasing and environment lookups dominate the actual work.
  • Languages with deep recursion, where the interpreted call stack is the host call stack and the limit is not yours to set.
  • Teaching the middle and back ends of a compiler, which is the specific reason AtlasLang does not have one.

What it costs

Every one of these is paid by something.

  • A tree-walker buys an implementation you can read in an afternoon and pays with an execution model that cannot be analysed, which forecloses every optimization at once.
  • Using the host language's call stack buys a trivial implementation of function calls and pays by making the interpreted stack depth limit someone else's decision.
  • Environment lookup by symbol buys correct scoping with no lowering step and pays a lookup per variable reference, which is one of the largest per-node costs.
  • Keeping the tree as the executable form buys perfect correspondence with the source — every runtime error can point at a real span — and pays the entire performance gap.
  • Skipping it, as AtlasLang did, buys eleven more representations to teach and to optimize, and pays with ten files instead of one and a correctness argument that has to be made stage by stage.

What else you could do

What a different compiler or language does instead, and when that is better.

  • Compile to bytecode and interpret that, which is what AtlasLang does: a linear instruction stream, slot-indexed locals and a dispatch loop — [[atlaslang-bytecode]] and [[bytecode-compiler]].
  • A closure-compiling interpreter, which walks the tree once and produces a nested closure per node, removing the dispatch switch while keeping the tree shape. A real and underused middle ground.
  • Threaded code, where each node becomes a pointer to its handler and dispatch is an indirect jump rather than a switch — see [[dispatch-loop]].
  • Compiling to native code ahead of time, which removes the interpreter entirely at the cost of everything in the back half of this domain — [[aot-compilation]].
  • A partial evaluator or a JIT built on top of a tree-walker, which is how several production language implementations got fast without abandoning the evaluator as the semantics of record.

See it for yourself

The flag, dump or tool that shows you this directly.

  • /compilers/pipeline — the Typed AST panel is exactly what a tree-walking evaluator would consume, with symbol and type populated on every node.
  • Hand-evaluate a small program from that panel and compare with the Execution panel; they agree, which is the point.
  • Load the shortcircuit example and walk it by hand, then look at the IR panel to see the same rule expressed as two blocks and a branch.
  • For a real one: python -c "import ast; print(ast.dump(ast.parse(open('f.py').read())))" prints the tree CPython compiles from, and python -m dis f.py prints what it compiled it to.
  • Ruby before 1.9 is the canonical shipped tree-walker; its replacement by YARV is a well-documented account of exactly this trade.

Plausible wrong readings

Stated the way a confident engineer states them.

  • "AtlasLang runs by walking the tree." It does not. It lowers to IR, optimizes and runs bytecode on a VM. This lesson describes the version it deliberately does not have.
  • "Tree-walking is the beginner version." It is the version whose correctness is easiest to argue and is frequently kept as the reference implementation for exactly that reason.
  • "Interpreters are slow because interpretation is slow." A tree-walker is slow because of per-node dispatch, pointer chasing and name lookups. A bytecode interpreter is also an interpreter and is far faster.
  • "You could optimize the tree instead of lowering it." You can rewrite a tree, and some compilers do. What you cannot do is ask it which definition reaches a use without building a different representation first.

Misconceptions

The claim, and what is actually true.

A tree-walking interpreter is not a real implementation.
It is a complete implementation of the language and frequently the one that defines what the language means. Shipping languages have run on them for years.
The reason to compile is speed.
Speed is the visible reason. The structural reason is that a tree cannot answer the questions optimization requires — which definition reaches this use, which blocks dominate which — without first becoming something else.
You can add an optimizer to a tree-walker later.
You can add tree rewrites. Anything requiring data-flow reasoning requires building a linear form and a CFG first, which is most of the work of compiling.

Go deeper

The same idea at increasing depth. Stop wherever it stops being useful.

overview

The simplest way to run a parsed program is to walk its tree and do what each node says: a number node yields its number, a plus node evaluates both sides and adds, an if node evaluates its condition and runs one branch. That is a complete implementation, it is short, and it is where most languages begin. AtlasLang skipped it because a tree is not something you can analyse or optimize.

practical

If you are building a language, write this first. You will have something running in a day, and it becomes the reference you test everything else against. Two things to get right from the start, because both are silent when wrong: look variables up by the symbol the resolver produced rather than by name, and write && and || as conditionals rather than as operator applications. Then decide, based on how large real programs get, whether you ever need more.

advanced

The tree-walker is worth keeping even after you have something faster, and not for nostalgia. It is the reference semantics: when the optimizing path disagrees with it, the optimizing path is wrong, and having a second implementation makes that a testable proposition rather than an argument. That is the whole basis of [[differential-testing]] applied to your own compiler — generate programs, run both, compare, and any divergence is a real bug with a minimal reproducer attached. Several production language teams maintain exactly this, and the cost of keeping a two-hundred-line evaluator in sync with the language is small against the cost of a miscompilation that nothing detected.

How much this depends on

Nothing in this domain is true of every compiler. These say how much.

implementationAtlasLang has no tree-walking interpreter; src/compilers/sim/ lowers to IR and runs bytecode on a stack VM. The evaluator in this lesson is written as pseudocode to describe the alternative honestly rather than to describe the code. Everything said about the typed AST, symbols and short-circuit lowering is true of the implementation; the evaluator itself is not in it.
simplifiedThe sketch omits what a real evaluator spends most of its code on: a value representation that can carry every type, error propagation with source spans, return unwinding, host stack-depth protection and an environment that is faster than a chain of hash maps. Those four make a toy evaluator into a usable one and roughly quadruple its size.
typicalMainstream dynamic language implementations mostly moved from tree-walking to bytecode — Ruby at 1.9, and CPython long before — while plenty of small DSLs and configuration languages stay with tree-walkers permanently because their programs are short. Neither is a default; the crossover is decided by program size and by whether anyone needs it to be fast.

If you were asked this in an interview

  • What is the one obligation a tree-walking evaluator has that its individual node cases do not obviously imply?
  • Why did AtlasLang lower to IR rather than walk the tree, and what would have been unteachable otherwise?
  • You have a tree-walker and you now want an optimizer. What has to be built first, and why?

Connections

DSAbinary-treedfsrecursionstack
Domains that do not exist yet
  • Programming Languages & Runtime Internals — Value representation, boxing and the cost of an environment lookup at run time
    A tree-walker's performance is decided almost entirely by how values are represented and how variable lookup is implemented — boxing, tagged unions, inline caches on environments. Those are runtime concerns; this lesson stops at why the tree cannot be optimized instead.