Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

4. A tree-walking interpreter first

  • Status: Accepted
  • Date: 2026-09-02

Context

Korrin needs an execution engine. The realistic options, in rough order of effort: a tree-walking interpreter (evaluate the AST directly), a bytecode compiler plus a stack VM, or lowering to an existing backend (LLVM, Cranelift, transpile to another language).

The language design is still moving. Semantics will change as the spec is written and as real programs are attempted. Whatever we build first will be rewritten in part.

Decision

Milestone 1 is a tree-walking interpreter that executes the resolved AST directly. Values are reference-counted (Rc/RefCell); there is no bytecode and no separate compile step beyond parsing and resolution.

A bytecode VM is explicitly anticipated as a later milestone. To keep that door open:

  • name resolution and static validation live in a separate resolver pass between parsing and execution — in Milestone 1 it validates (placement of return / break / super, duplicate parameters, and so on); it is the natural place to add lexical slot/depth precomputation when a VM needs it, without disturbing the interpreter;
  • the interpreter is isolated behind the korrin::run / Interpreter API, so a VM can replace it without touching callers;
  • control flow (return, break, continue) is modelled as an explicit signal enum, not host-language exceptions or panics, which maps cleanly to a VM later.

Consequences

  • Fastest path to a language that actually runs, which is what unblocks spec work, example programs, and dogfooding.
  • Slower execution than a VM — acceptable for M1, whose goal is correctness and a complete feature set, not speed.
  • Some work (the resolver's scope analysis, the signal enum) is done now partly to serve a future VM. Judged worthwhile because it also makes the interpreter clearer today.
  • A performance-focused rewrite is on the roadmap and should surprise nobody.

Alternatives considered

  • Bytecode VM from the start. Two to three times the initial work, spent optimising semantics that are still in flux.
  • Native compilation (LLVM/Cranelift). Enormous scope; wrong shape for a dynamically typed scripting language at this stage.
  • Transpile to another language. Ties Korrin's semantics and error reporting to a host that was not designed for it.

Amendment (2026-09-04): the VM has landed

Milestone 3 added the bytecode compiler and virtual machine this ADR deferred (0022, 0023, 0025). Two of the three seams named above paid off as intended: Signal was already the shape the VM wanted, and the Interpreter API stayed stable while a second engine grew beside it. The third did not: slot resolution went into the new compiler rather than into the resolver pass, which remains validation-only.

The tree-walking interpreter is not superseded. It is now the oracle the VM is tested against (0024), which makes it a permanent part of the implementation rather than a stage that was passed.