A Bytecode VM

import type { Tracer } from "../trace";import { Arithmetic, type AstNode, type BinaryOperator, type Expression, MAX_STEPS, type ProgramNode, type RunResult, RuntimeFault, type Statement } from "./tiny-language";/** The instruction set: a stack machine's, so an expression compiles to postfix and needs no registers. */export type Op = "push" | "load" | "store" | "add" | "sub" | "mul" | "div" | "neg" | "lt" | "eq" | "jump" | "jump-if-false" | "print" | "halt";export interface Instruction {  op: Op;  /** A number to push, a name to load or store, or a code index to jump to. */  arg: number | string | null;  /** The node that produced it, so a listing can point back into the tree. */  node: number;}const BINARY_OPS: Readonly<Record<BinaryOperator, Op>> = { "+": "add", "-": "sub", "*": "mul", "/": "div", "<": "lt", "==": "eq" };const SYMBOL_OF: ReadonlyMap<Op, BinaryOperator> = new Map((Object.entries(BINARY_OPS) as [BinaryOperator, Op][]).map(([symbol, op]) => [op, symbol]));/** A jump whose target is not known yet, to be patched once the code it skips is laid down. */const UNPATCHED = -1;/** * Translates a syntax tree to bytecode for a stack machine, once, so * that running it never looks at the tree again. An expression becomes * postfix: the code for the operands, then the operator, which pops them * and pushes the answer. A statement ends with the instruction that uses * the value: store, print, or a conditional jump. `if` jumps past its * body when the test is false; `while` does the same and jumps back to * the test after the body. A forward jump is emitted before its target * exists, so it is patched once the body is compiled. * * Time: O(n) for n nodes, each visited once. Space: O(n) instructions. */export class BytecodeCompiler {  private readonly code: Instruction[] = [];  constructor(private readonly tracer?: Tracer) {}  /** The whole program as instructions, ending in halt. */  compile(program: ProgramNode): Instruction[] {    for (const statement of program.body) this.statement(statement);    this.append("halt", null, program);    return [...this.code];  }  /** Appends one instruction and returns its index, so a jump can be patched later. */  private append(op: Op, arg: number | string | null, node: AstNode): number {    const index = this.code.length;    this.code.push({ op, arg, node: node.id });    // ▸ append one instruction: operands before their operator, a value before the store or print that uses it    this.tracer?.emit("compile", { index, op, arg, node: node.id, kind: node.kind });    return index;  }  /** Fills in a forward jump's target now that the code it skips has been laid down. */  private patch(index: number, target: number, node: AstNode): void {    this.code[index] = { ...this.code[index]!, arg: target };    // ▸ a forward jump was laid down before its target existed: fill the target in now that the body is compiled    this.tracer?.emit("patch", { index, target, node: node.id });  }  private statement(statement: Statement): void {    switch (statement.kind) {      case "let":        this.expression(statement.value);        this.append("store", statement.name, statement);        return;      case "print":        this.expression(statement.value);        this.append("print", null, statement);        return;      case "if": {        this.expression(statement.test);        const skip = this.append("jump-if-false", UNPATCHED, statement);        for (const inner of statement.body) this.statement(inner);        this.patch(skip, this.code.length, statement);        return;      }      case "while": {        const top = this.code.length;        this.expression(statement.test);        const exit = this.append("jump-if-false", UNPATCHED, statement);        for (const inner of statement.body) this.statement(inner);        this.append("jump", top, statement);        this.patch(exit, this.code.length, statement);        return;      }    }  }  /** Postfix: operands first, so the operator finds them on the stack. */  private expression(expression: Expression): void {    switch (expression.kind) {      case "number":        this.append("push", expression.value, expression);        return;      case "name":        this.append("load", expression.name, expression);        return;      case "unary":        this.expression(expression.operand);        this.append("neg", null, expression);        return;      case "binary":        this.expression(expression.left);        this.expression(expression.right);        this.append(BINARY_OPS[expression.op], null, expression);        return;    }  }}/** * Runs bytecode: fetch the instruction at the instruction pointer, * advance the pointer, execute. Every instruction is one of a fixed * dozen, so dispatch is one switch with no tree to inspect, and the * values an expression is building wait on a stack rather than in the * call frames of a recursive walk. A jump is the only instruction that * sets the pointer itself, and a loop is a jump backwards. * * Time: O(1) per instruction. Space: the stack's depth, which is the * deepest expression's nesting, plus the variables. */export class StackMachine {  private readonly stack: number[] = [];  private readonly variables = new Map<string, number>();  private readonly output: number[] = [];  private ip = 0;  private pointer = 0;  private steps = 0;  constructor(    private readonly code: readonly Instruction[],    private readonly tracer?: Tracer,  ) {}  /** Executes until halt; a fault stops the run and is reported, never thrown past here. */  run(): RunResult {    let fault: string | null = null;    try {      while (this.step()) {        // Each cycle is one instruction.      }    } catch (error) {      if (!(error instanceof RuntimeFault)) throw error;      fault = error.message;      // ▸ a name with no value, a division by zero, or too many instructions stops the machine      this.tracer?.emit("fault", { message: fault, ip: this.ip, steps: this.steps });      this.tracer?.emit("fault", { message: fault, pointer: this.pointer, steps: this.steps });    }    return { output: [...this.output], variables: Object.fromEntries(this.variables), steps: this.steps, fault };  }  /** One cycle: fetch, advance, execute. False once the machine has halted. */  private step(): boolean {    const instruction = this.code[this.ip];    const instruction = this.code[this.pointer];    if (instruction === undefined) throw new RuntimeFault(`no instruction at ${this.ip}`);    if (++this.steps > MAX_STEPS) throw new RuntimeFault(`still running after ${MAX_STEPS} instructions`);    const at = this.ip;    const address = this.pointer;    // ▸ read the instruction at the instruction pointer and move the pointer to the next one    this.tracer?.emit("fetch", { ip: at, op: instruction.op, arg: instruction.arg, node: instruction.node, stack: [...this.stack] });    this.tracer?.emit("fetch", { pointer: address, op: instruction.op, arg: instruction.arg, node: instruction.node, stack: [...this.stack] });    this.ip++;    this.pointer++;    const halted = this.execute(instruction);    // ▸ do it: push, pop and combine, store, print, or set the pointer for a jump    this.tracer?.emit("exec", { ip: at, op: instruction.op, arg: instruction.arg, stack: [...this.stack], next: this.ip, variables: Object.fromEntries(this.variables), output: [...this.output] });    this.tracer?.emit("exec", { pointer: address, op: instruction.op, arg: instruction.arg, stack: [...this.stack], next: this.pointer, variables: Object.fromEntries(this.variables), output: [...this.output] });    return !halted;  }  private pop(): number {    const value = this.stack.pop();    if (value === undefined) throw new RuntimeFault("the stack is empty");    return value;  }  private execute(instruction: Instruction): boolean {    const { op, arg } = instruction;    switch (op) {      case "push":        this.stack.push(arg as number);        return false;      case "load": {        const value = this.variables.get(arg as string);        if (value === undefined) throw new RuntimeFault(`${arg} is not defined`);        this.stack.push(value);        return false;      }      case "store":        this.variables.set(arg as string, this.pop());        return false;      case "neg":        this.stack.push(-this.pop());        return false;      case "jump":        this.ip = arg as number;        this.pointer = arg as number;        return false;      case "jump-if-false":        if (!Arithmetic.truthy(this.pop())) this.ip = arg as number;        if (!Arithmetic.truthy(this.pop())) this.pointer = arg as number;        return false;      case "print":        this.output.push(this.pop());        return false;      case "halt":        return true;      default: {        // The arithmetic and comparisons: the right operand was pushed last, so it comes off first.        const right = this.pop();        const left = this.pop();        this.stack.push(Arithmetic.apply(SYMBOL_OF.get(op)!, left, right));        return false;      }    }  }}