Build a Complete Mini-Language and Runtime

This module turns everything into one project: a small language with two working back ends that agree with each other, a verifier, a debugger trace, tests, benchmarks and safety limits — the same design as the course's own MiniLang implementation, which you…

Learning Objectives

Build MiniLang end to end in labs: goals and grammar, lexer with positions, parser and AST, expressions and statements, environments, functions, recursion and closures; a bytecode compiler, instruction set, disassembler, verifier and stack VM with frames and locals; errors with stack traces; modules, objects and memory management (with clearly marked limitations); a debugger/trace mode, REPL, test runner, benchmarks, sandbox and budget; documentation and a versioned bytecode format.

Meet the capstone requirements with tests and measurements.

Plain-Language Explanation

Precise Technical Explanation

Define language goals and grammar Goal: a small, dynamically typed, lexically scoped language with first-class functions, safe to run untrusted code in a browser. Grammar: the course overview's EBNF.

Create lexer with source positions Module 3; tokens with kind, lexeme, literal and span.

Create parser and AST Module 4; recursive descent with panic-mode recovery; AST nodes with ids and spans.

Implement expressions and statements Module 6; evaluate and execute.

Implement environments and scope Module 7; environment chains and static checks (duplicate locals, self-referencing initialisers, top-level return).

Add functions and recursion Function values, calls with arity checks, return via a host exception, depth limit.

Functions capture their defining environment (tree-walker) or upvalues (VM).

Add bytecode compiler Module 8; locals resolved to slots, upvalues to indices, globals to names; jumps patched.

Define an instruction set 30 instructions (Module 8's table), documented with stack effects.

disassembleText: offsets, lines, operands, constants, jump targets, nested functions.

Write bytecode verifier Module 8; opcodes, operands, jump boundaries, stack depth on all paths, no falling off the end.

Build stack VM Module 9; dispatch loop over a byte array.

Add call frames and locals Module 11; frames window the value stack; slot 0 is the first parameter.

Add runtime errors and stack traces Errors carry spans; traces list frames with lines — identical in both back ends (the differential tests check full error texts).

Add modules and imports Not implemented in MiniLang: design sketch — import "name"; compiles a module once, runs it in its own global table, and binds an object of its exports; cache by name; detect cycles. (A good extension exercise.) Add a simple object model

Not implemented: design sketch — class declarations creating closures for methods and an instance field table; method lookup by name with an inline cache per call site.

Add a basic garbage collector or explicit arena/pool (clearly mark educational limitations)

MiniLang relies on the host JavaScript engine's garbage collector for closures and upvalues — an educational limitation: it does not manage its own heap. Module 14's exercise sketches a mark-sweep collector for it.

Add a debugger/trace mode interpret(src, { trace: true }) and runVm(script, { trace: true }) record every step; the visualizers add breakpoints and stepping.

Keep one global table across inputs; compile each line as a script; print errors and continue (the course's playground behaves this way per run).

Add test runner and conformance tests Golden programs with expected outputs and errors, run on both back ends; verifier tests with malformed bytecode; fuzzing.

Compare the tree-walker and the VM on the same programs with warm-up and repeats (below).

Add a sandbox and instruction budget Budgets, depth limits, a single safe native function, verification before every VM run (Module 24).

Document language semantics The semantics table in the course overview.

Package a release and version the bytecode format Serialise compiled chunks with a header (magic number, format version); refuse unknown versions; verify after loading (below).

Capstone requirements A documented grammar Lexer and parser tests Step-through execution trace

Runtime error messages with source locations Tests for scope, closures, recursion, arithmetic, branches and errors Invalid bytecode validation tests

Performance comparison with the tree-walk interpreter Clear limitations and security notes Reproducible build and run instructions

Why It Matters in Real Systems

Building a complete language once makes every production runtime legible: you will recognise the lexer, parser, compiler, verifier, VM, frames and limits in each of them.

Key Terms

Simple implementation defining expected behaviour Program plus expected output

Number in a serialised file identifying its layout Deliberate simplification, documented

Diagram, Execution Trace or State Transition

Text equivalent: the same AST feeds a tree-walk interpreter and a bytecode compiler; bytecode is verified before the VM runs it and can be serialised with a versioned header; differential tests compare both back ends' outputs.

flowchart LR
  SRC[source] --> LEX[lexer] --> PAR[parser + static checks] --> AST
  AST --> TW[tree-walk interpreter]
  AST --> CMP[bytecode compiler] --> BC[bytecode] --> VER[verifier] --> VM[stack VM]
  BC --> SER[serialise: magic + version] --> LOAD[load + verify]
  TW --> CMPR{outputs equal?}
  VM --> CMPR

Syntax or Instruction Format

MiniLang source (grammar in the course overview); bytecode (Module 8); serialised format (below): MLBC magic, format version byte, then JSON-encoded chunks for readability in this teaching version.

Complete Example

A capstone-style program exercising recursion, closures, loops, short-circuits and errors (both back ends):

The last line was deliberately written with a call that has two arguments to print, which MiniLang's grammar does not allow — the error above is a syntax error reported with its position, and nothing ran: syntax errors stop the whole program before execution. The corrected program:

Versioned bytecode serialisation with verification on load, and the tree-walker versus VM benchmark required by the capstone (Node.js 24; times are one real run with warm-up, median of 7):

fun makeAccumulator(start) {
  let total = start;
  fun add(n) { total = total + n; return total; }
  return add;
}
fun fib(n) { if (n < 2) return n; return fib(n - 1) + fib(n - 2); }

let acc = makeAccumulator(100);
let i = 1;
while (i <= 5) { acc(fib(i)); i = i + 1; }
print("accumulated: " + str(acc(0)));
print(nil or "default", false and missing);

Syntax error [line 12:23]: Expect ')' after value. (found ',')

fun makeAccumulator(start) {
  let total = start;
  fun add(n) { total = total + n; return total; }
  return add;
}
fun fib(n) { if (n < 2) return n; return fib(n - 1) + fib(n - 2); }

let acc = makeAccumulator(100);
let i = 1;
while (i <= 5) { acc(fib(i)); i = i + 1; }
print("accumulated: " + str(acc(0)));
print(nil or "default");
print(false and missing);

accumulated: 112
default
false

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

const FORMAT_VERSION = 1;
function serialise(fn) {
  const enc = (f) => ({ name: f.name, arity: f.arity, upvalueCount: f.upvalueCount, code: f.chunk.code, names: f.chunk.names, lines: f.chunk.lines,
    constants: f.chunk.constants.map((c) => (isFnProto(c) ? { fn: enc(c) } : { v: c })) });
  return Buffer.concat([Buffer.from("MLBC"), Buffer.from([FORMAT_VERSION]), Buffer.from(JSON.stringify(enc(fn)))]);
}
function load(bytes) {
  if (bytes.subarray(0, 4).toString() !== "MLBC") throw new Error("not MiniLang bytecode");
  if (bytes[4] !== FORMAT_VERSION) throw new Error(`unsupported bytecode format version ${bytes[4]} (this VM supports ${FORMAT_VERSION})`);
  const dec = (o) => ({ name: o.name, arity: o.arity, upvalueCount: o.upvalueCount,
    chunk: { code: o.code, names: o.names, lines: o.lines, spans: o.code.map(() => null), constants: o.constants.map((c) => ("fn" in c ? dec(c.fn) : c.v)) } });
  const fn = dec(JSON.parse(bytes.subarray(5).toString()));
  const errors = verify(fn);
  if (errors.length) throw new Error("verification failed: " 
…

serialised: 429 bytes, header 4d4c424301
loaded and run: 2584
load(version 2): unsupported bytecode format version 2 (this VM supports 1)
load(tampered): verification failed: unknown opcode 99
fib(18): tree-walk 33.0 ms, bytecode VM 8.7 ms (median of 7 after warm-up) → VM 3.8× faster on this run

Line-by-Line Explanation

First program: the syntax error is reported before anything runs — note that *no* output appears, because the whole program is parsed (and rejected) before execution starts.

Fixed program: acc accumulates fib(1)…fib(5) = 1 + 1 + 2 + 3 + 5 = 12 on top of 100; str converts the number for concatenation; short-circuits as in Module 6.

Release: the header 4d4c4243 01 is MLBC plus version 1; loading checks magic, version and then *verifies* the decoded code, so a future format or tampered bytes are refused before execution.

Benchmark: same program, same warm-up and repeat policy for both back ends, median reported, the ratio labelled as this run.

Step-by-Step Runtime Behavior

Release flow: compile → serialise (header + payload) → ship → load: check magic → check version → decode → verify → run with limits.

Common Misconceptions

"Serialising bytecode makes it safe to load." Loading must verify — files can be tampered with.

"A language is done when it runs one program." Tests, errors, limits and documentation are the work.

Common Bugs and Failure Modes

Back ends drifting apart without differential tests, unversioned caches, unverified loads, missing limits, undocumented semantics.

Corrected or Safer Patterns

Differential tests in CI, format versions, verification on load, limits by default, a semantics document.

Debugging and Inspection Techniques

Every tool from the course: tokens, AST printer, disassembler, verifier, traces, differential and fuzz tests.

Performance Considerations

Measure both back ends; optimise the VM only after the profile (Module 25).

Security Considerations

Untrusted source and bytecode must pass through the parser/verifier and run with budgets; keep the host API minimal.

Portability and Version Caveats

The teaching serialisation uses JSON for readability; a production format would be binary, with explicit endianness and sizes.

Real-World Use Cases

Configuration and rule languages, game scripting, educational languages, embedded DSLs.

Best Practices

Two back ends plus differential tests, verify everything you load, limit everything you run, document everything you decide.

Exercises

E1 · Beginner. Why did the first capstone program print nothing at all?

Answer: It contained a syntax error; MiniLang parses the entire program before executing, so a syntax error anywhere stops execution before the first statement runs.

E2 · Intermediate. Add a % operator to MiniLang. Which parts of the implementation change?

Answer: Lexer (new token), parser (factor level), AST printer (operator label), tree-walker (arith), compiler (new opcode or reuse), instruction table, disassembler and verifier (stack effect), VM handler, tests on both back ends and the documentation.

E3 · Advanced challenge. Design import for MiniLang.

Answer: Syntax import "name"; binds a global name to a module object; the runtime keeps a module cache; on first import, compile the module's source, run it with its own globals table, collect its top-level bindings as exports, store the module object in the cache *before* running (to handle cycles) and bind it; verify module bytecode on load; report cycles where a binding is missing.

Quiz

? Why does the release loader verify bytecode after checking the version?
+ Files can be corrupted or tampered with; only verified code may run. :: Version checks alone do not ensure well-formedness.
- To make loading slower. :: Safety, not speed.
- Because JSON requires it. :: Unrelated.
- To compile the code again. :: It does not recompile.

? Which capstone requirement catches drift between the two back ends?
+ Differential tests comparing their outputs and errors :: Any difference is a bug.
- The AST printer :: Useful for debugging, not for drift.
- The disassembler :: Shows bytecode only.
- The benchmark :: Measures speed only.

? Which are documented educational limitations of MiniLang? (select all that apply)
+ It relies on the host's garbage collector :: No own heap.
+ It has no modules or classes (design sketches only) :: Extension exercises.
- It has no bytecode verifier :: It has one.
+ Its serialisation format is JSON for readability :: Not a production format.

Summary and Key Takeaways

A complete mini-language combines a positioned lexer, a recovering parser, static checks, a tree-walk interpreter, a bytecode compiler, disassembler, verifier and VM with frames, closures, traces, limits, tests, benchmarks, documentation and a versioned, verified bytecode format — with its simplifications clearly documented.