Language Implementation Strategies

There are many ways to make a program run.

Learning Objectives

Describe tree-walk and AST interpreters, bytecode interpreters, stack and register VMs, native compilers, compilers to portable IR, transpilers, source interpreters, compile-then-run workflows and hybrid execution.

Explain AOT, JIT, adaptive/tiered, tracing and method-based compilation.

Weigh start-up time against steady-state performance, portability against deployment cost, and compare performance fairly.

Choose a strategy for a given language and deployment.

Plain-Language Explanation

There are many ways to make a program run. You can read the program's tree and do what each node says (simple, slow). You can first translate it into compact instructions for an imaginary machine and run those (faster, still portable). You can translate it into real machine code before shipping (fast, but tied to one platform), or while it runs, only for the parts that matter (fast after a warm-up). Real systems mix these.

Precise Technical Explanation

Evaluates the AST recursively: evaluate(Binary) evaluates both children, then applies the operator. Easy to write and debug; slow because each step chases pointers through a tree and re-dispatches on node types.

A tree-walk interpreter over an AST (as opposed to a parse tree). Advanced AST interpreters rewrite nodes as they learn about types ("self-optimising AST interpreters", e.g. Truffle) and can be partially evaluated into machine code.

Compiles the AST once into a linear sequence of compact instructions, then runs a dispatch loop: fetch, decode, execute. Better cache locality and less per-step overhead than walking a tree.

Stack-based virtual machine Instructions take operands from an operand stack and push results (ADD pops two, pushes one). Compact code, simple compilers: JVM, CPython, CLR's CIL, WebAssembly, MiniLang (Module 9).

Register-based virtual machine Instructions name virtual registers explicitly (ADD r0, r1, r2): fewer, larger instructions. Lua 5, Dalvik and V8's Ignition (an accumulator-plus-registers design) are register-based (Module 10).

Compiler to native machine code AOT compilers (GCC, Clang, rustc, Go) produce machine code for one target architecture and OS ABI. Best start-up and predictable performance; requires one build per target.

Compiler to portable intermediate representation javac (class files), the C# compiler (CIL assemblies) and WebAssembly toolchains emit a portable format; a runtime on each platform finishes the job.

Transpilation / source-to-source compilation Compiling to another high-level language: TypeScript → JavaScript, Kotlin/JS, Nim → C. The target language's implementation then runs the result.

Interpretation of source text Truly executing raw text each time (classic shells, early BASICs) is rare today: even shells parse each command into a tree before running it.

Two visible steps (javac then java, gcc then ./a.out) versus one (python script.py, node app.js, java File.java source launch — which compiles in memory).

Interpreter for cold code, JIT for hot code, AOT for start-up-critical code — HotSpot, .NET with ReadyToRun plus tiered JIT, V8.

Ahead-of-time (AOT) compilation Compilation before execution: native compilers,.NET Native AOT, GraalVM native-image, Android's ART (AOT on install plus JIT).

Just-in-time (JIT) compilation Compilation during execution, using run-time knowledge (observed types, hot paths) — Module 16.

Adaptive and tiered compilation Code moves through tiers as it gets hotter: interpreter → baseline compiler (fast to compile, modest code) → optimising compiler (slow to compile, fast code). HotSpot's C1/C2,.NET tier 0/tier 1, V8's Ignition/Sparkplug/Maglev/TurboFan.

Tracing JIT overview Records the operations along a hot *path* through a loop (a trace), compiles that linear trace with guards, and exits to the interpreter when a guard fails (LuaJIT, PyPy's meta-tracing).

Method-based JIT overview Compiles whole functions/methods, with inlining of callees (HotSpot,.NET, V8).

Dynamic language implementation challenges Types are unknown until run time; properties can be added and removed; functions can be replaced; eval exists. Implementations rely on type feedback, inline caches, hidden classes and deoptimisation.

Static language runtime challenges Generics instantiation, reflection, dynamic class loading, interface dispatch and the need to preserve debuggability and safety still require runtime machinery even when types are known.

Startup time versus steady-state performance An interpreter starts immediately; a JIT pays compilation cost before code is fast (warm-up); AOT pays ahead of time. Short-lived processes (CLI tools, serverless functions) favour fast start-up; long-running servers favour peak throughput.

Portability, deployment, and runtime dependency trade-offs Portable IR needs a runtime installed (or bundled); native binaries need per-platform builds; containers ship the runtime with the app.

Comparing performance fairly Use the same algorithm and input, warm up JIT-based systems, repeat measurements, report medians and spread, state versions and hardware, and measure what users experience (latency distributions, start-up, memory) — not only one micro-benchmark.

When to choose each strategy Strategy worth considering Teaching, prototyping a language, configuration language

Embeddable scripting, portable distribution CLI tools, system software, embedded targets

Long-running services in a managed language Hybrid with tiered JIT Sandboxed portable modules Reusing another ecosystem

Examples to compare. C: commonly compiled to native code before running. Java: compiled to class-file bytecode, then interpreted and JIT-compiled by a JVM. Python: CPython compiles source to implementation-specific bytecode and executes it in its VM; details vary by version and implementation. JavaScript: engines parse and execute through several internal tiers that vary by engine and release. C#: commonly compiled to CLI assemblies containing IL and metadata, then executed by a .NET runtime (JIT); deployment can also involve AOT options (ReadyToRun, Native AOT). WebAssembly: validated modules executed by a conforming runtime that chooses its own compilation strategy.

Why It Matters in Real Systems

Strategy decides cold-start latency, peak throughput, memory footprint, debuggability and deployment shape — the first questions in any runtime choice.

Key Terms

Selecting the code that implements the next node or instruction

One execution mode (interpreter, baseline, optimised) Period before JIT-compiled code reaches steady state Recorded linear path through hot code

Diagram, Execution Trace or State Transition

Text equivalent: a tiered runtime starts in the interpreter, promotes hot code to a baseline compiler and then to an optimising compiler, and falls back to the interpreter (deoptimises) when an assumption made during optimisation stops holding.

flowchart LR
  I[Interpreter: counts calls and types] -->|hot| B[Baseline JIT]
  B -->|hotter + stable types| O[Optimising JIT]
  O -->|assumption fails| D[Deoptimise]
  D --> I

Syntax or Instruction Format

No dedicated source syntax; this is a runtime or architecture concept.

Complete Example

The same MiniLang program executed by both of the course's back ends, measured on the build machine. The tree-walk interpreter counts AST nodes it visits; the VM counts instructions it executes. Counts are deterministic; times are one real run (Node.js 24, Windows 11; 2 warm-up runs, median of 7):

Output (one real run; times vary between machines and runs):

import { interpret, compile, runVm } from "file:///D:/Projects/EngineerHub/src/cs/tracks/runtimes/minilang/minilang.ts";

const src = `
fun fib(n) { if (n < 2) return n; return fib(n - 1) + fib(n - 2); }
print(fib(20));`;

function median(xs) { const s = [...xs].sort((a, b) => a - b); return s[Math.floor(s.length / 2)]; }
function measure(run) {
  for (let i = 0; i < 2; i++) run();                     // warm-up: let V8 compile our interpreters
  const times = [];
  let last;
  for (let i = 0; i < 7; i++) { const t = performance.now(); last = run(); times.push(performance.now() - t); }
  return { last, ms: median(times) };
}

const tree = measure(() => interpret(src, { maxSteps: 10_000_000 }));
const script = compile(src).script;                      // compile once, run many times
const vm = measure(() => runVm(script, { maxSteps: 10_000_000 }));
console.log("tree-walk:", tree.last.output[0], "| AST nodes visited:", tree.last.steps, "| median", tree.ms.toFixed(1), "ms");
console.log("bytecode VM:", vm.last.output[0], "| instructions executed:", vm.last.executed, "| median", vm.ms.toFixed(1), "ms");
console.log("same answer:", tree.last.output[0] === vm.last.output[0]);

tree-walk: 6765 | AST nodes visited: 240801 | median 66.0 ms
bytecode VM: 6765 | instructions executed: 262694 | median 14.8 ms
same answer: true

Line-by-Line Explanation

Both back ends are run several times; the first runs warm up V8 itself (our interpreters are JavaScript, JIT-compiled by V8 — a runtime inside a runtime).

The VM run reuses one compiled script: compilation is paid once, like a cached .pyc.

Steps and instructions are *different units* — an AST node and a bytecode instruction do different amounts of work — so compare times, not counts.

Expected Output

6765 from both back ends (fib(20)); counts are deterministic; times are not.

Step-by-Step Runtime Behavior

The tree-walker recursively evaluates nodes and keeps environments as hash maps; the VM executes a flat byte array, keeps locals in stack slots and looks up only globals by name.

Common Misconceptions

"A JIT is always faster." Not for short runs, where compile time dominates.

"Bytecode VMs are always faster than tree-walkers." Usually, but a well-optimised AST interpreter can beat a naive bytecode VM.

"Register VMs are always faster than stack VMs." Fewer instructions, but larger ones; results depend on the implementation.

Common Bugs and Failure Modes

Benchmarking without warm-up; benchmarking dead code the optimiser removes; comparing different algorithms; reporting one run.

Corrected or Safer Patterns

Warm up, repeat, report median and spread, check the result is used, state versions — as the example does.

Debugging and Inspection Techniques

Instruction and node counters (as above); -XX:+PrintCompilation (HotSpot); --trace-opt (Node); DOTNET_TieredCompilation settings (.NET).

Performance Considerations

Dispatch overhead, memory locality, value representation and name lookup dominate interpreter speed; Modules 9, 10 and 25 attack each.

Security Considerations

A JIT needs writable-then-executable memory, enlarging the attack surface; some environments forbid JITs (iOS for third-party apps, hardened server configurations) and run interpreters only.

Portability and Version Caveats

Tier names and thresholds change frequently (V8 added Sparkplug in 2021 and Maglev in 2023). Describe roles, not version-specific names, unless you name the version.

Real-World Use Cases

Choosing Native AOT for a .NET CLI tool; enabling a JIT-less mode for a locked-down device; embedding Lua for game scripting; shipping WebAssembly for portable plug-ins.

Best Practices

Start with a tree-walker to pin down semantics, then add a bytecode back end and differential-test them (as this course does).

Exercises

E1 · Beginner. Why is the second MiniLang run faster than the first in the example's warm-up?

Answer: Our interpreters are JavaScript code; V8 interprets them at first and JIT-compiles them once they are hot, so early runs include V8's own warm-up.

E2 · Intermediate. A CLI tool runs for 50 ms. Which strategy fits best, and why?

Answer: AOT (native) or an interpreter with fast start-up; a JIT would spend much of the 50 ms compiling code that barely runs afterwards.

E3 · Advanced challenge. Design a fair benchmark comparing CPython and a JVM on JSON parsing.

Answer: Same input files and equivalent libraries; separate start-up time from steady-state throughput; warm up the JVM; repeat many iterations in fresh and warmed processes; report medians and percentiles, memory, versions, flags and hardware; verify outputs match.

Quiz

? What does tiered compilation do?
+ Moves code from cheaper to more optimising execution modes as it gets hotter. :: Interpreter → baseline → optimising.
- Compiles everything with the best optimiser first. :: That would delay start-up.
- Splits code into files. :: Unrelated.
- Runs only interpreted code. :: Tiers include compiled code.

? Which strategy produces machine code before the program runs?
+ AOT compilation :: Ahead of time.
- JIT compilation :: During execution.
- Tree-walk interpretation :: No machine code is generated.
- Tracing :: Tracing is a JIT technique.

? Which are needed to compare runtime performance fairly? (select all that apply)
+ Warm-up for JIT-based systems :: Otherwise you measure compilation.
+ Repetitions and medians :: Single runs are noisy.
- Different algorithms for each language :: Compare like with like.
+ Stating versions and hardware :: Results are environment-specific.

Summary and Key Takeaways

Implementations interpret trees, interpret bytecode, compile ahead of time, compile just in time — usually several at once. Choose by start-up needs, peak performance, portability and deployment constraints, and measure fairly.