An example of a register VM in PHP, learning resource

mathy.php

<?php

declare(strict_types=1);

namespace Mathy\Ir {
    use Mathy\Bytecode\Instruction;

    /**
     * A node in the IR expression/statement tree.
     */
    interface Ir {}

    /**
     * Marker for IR nodes usable as expressions (produce a value).
     */
    interface IrExpr extends Ir {}

    /**
     * Marker for IR nodes usable as statements (produce no value).
     */
    interface IrStmt extends Ir {}

    /**
     * A binary arithmetic operator, carrying its target opcode.
     */
    enum BinOp
    {
        case Add;
        case Sub;
        case Mul;
        case Div;

        /** The bytecode opcode this operator lowers to. */
        public function opcode(): int
        {
            return match ($this) {
                BinOp::Add => Instruction::ADD,
                BinOp::Sub => Instruction::SUB,
                BinOp::Mul => Instruction::MUL,
                BinOp::Div => Instruction::DIV,
            };
        }

        /**
         * Apply this operator to two concrete integers.
         *
         * @throws \DivisionByZeroError on division by zero (caller must guard).
         */
        public function apply(int $left, int $right): int
        {
            return match ($this) {
                BinOp::Add => $left + $right,
                BinOp::Sub => $left - $right,
                BinOp::Mul => $left * $right,
                BinOp::Div => intdiv($left, $right),
            };
        }

        /**
         * Resolve a source-level operator symbol to a BinOp.
         *
         * @throws \InvalidArgumentException if the symbol is not an operator.
         */
        public static function fromSymbol(string $symbol): self
        {
            return match ($symbol) {
                '+' => self::Add,
                '-' => self::Sub,
                '*' => self::Mul,
                '/' => self::Div,
                default => throw new \InvalidArgumentException("unknown operator '{$symbol}'"),
            };
        }
    }

    /** An integer literal. */
    final readonly class IrConst implements IrExpr
    {
        public function __construct(
            public int $value,
        ) {}
    }

    /** A variable reference, resolved against the VM environment at run time. */
    final readonly class IrVar implements IrExpr
    {
        public function __construct(
            public string $name,
        ) {}
    }

    /** A binary arithmetic expression. */
    final readonly class IrBinary implements IrExpr
    {
        public function __construct(
            public BinOp $op,
            public IrExpr $left,
            public IrExpr $right,
        ) {}
    }

    /** Arithmetic negation. */
    final readonly class IrNeg implements IrExpr
    {
        public function __construct(
            public IrExpr $operand,
        ) {}
    }

    /** A statement that prints an expression's value. */
    final readonly class IrPrint implements IrStmt
    {
        public function __construct(
            public IrExpr $expr,
        ) {}
    }
}

namespace Mathy\Optimizer {
    use Mathy\Ir\BinOp;
    use Mathy\Ir\IrBinary;
    use Mathy\Ir\IrConst;
    use Mathy\Ir\IrExpr;
    use Mathy\Ir\IrNeg;
    use Mathy\Ir\IrPrint;
    use Mathy\Ir\IrStmt;
    use Mathy\Ir\IrVar;

    /**
     * An IR-to-IR rewrite pass.
     *
     * A pass rewrites a single expression node, returning either a new
     * (simplified) node or the same node unchanged. The driver re-runs
     * passes to a fixpoint, so each pass need only perform one local step.
     */
    interface Pass
    {
        public function rewrite(IrExpr $node): IrExpr;
    }

    /**
     * Folds binary and negation nodes whose operands are all constant.
     *
     * Division and negation that would overflow or divide by zero are left
     * un-folded so the runtime (not the optimizer) reports the error.
     */
    final class ConstantFold implements Pass
    {
        public function rewrite(IrExpr $node): IrExpr
        {
            if ($node instanceof IrNeg && $node->operand instanceof IrConst) {
                if ($node->operand->value === PHP_INT_MIN) {
                    return $node; // -PHP_INT_MIN overflows; defer to runtime.
                }

                return new IrConst(-$node->operand->value);
            }

            if ($node instanceof IrBinary && $node->left instanceof IrConst && $node->right instanceof IrConst) {
                return $this->foldBinary($node->op, $node->left->value, $node->right->value) ?? $node;
            }

            return $node;
        }

        /** Fold a binary op over two constants, or null if it must defer to runtime. */
        private function foldBinary(BinOp $op, int $left, int $right): ?IrConst
        {
            if ($op === BinOp::Div) {
                if ($right === 0) {
                    return null; // division by zero: let the VM raise it.
                }

                if ($left === PHP_INT_MIN && $right === -1) {
                    return null; // overflow: let the VM raise it.
                }
            }

            if ($op === BinOp::Mul && $this->mulOverflows($left, $right)) {
                return null;
            }

            if ($op === BinOp::Add && $this->addOverflows($left, $right)) {
                return null;
            }

            if ($op === BinOp::Sub && $this->addOverflows($left, -$right)) {
                return null;
            }

            return new IrConst($op->apply($left, $right));
        }

        /** True if $a + $b would overflow the platform int. */
        private function addOverflows(int $a, int $b): bool
        {
            if ($b > 0 && $a > (PHP_INT_MAX - $b)) {
                return true;
            }

            if ($b < 0 && $a < (PHP_INT_MIN - $b)) {
                return true;
            }

            return false;
        }

        /** True if $a * $b would overflow the platform int. */
        private function mulOverflows(int $a, int $b): bool
        {
            if ($a === 0 || $b === 0) {
                return false;
            }
            $product = $a * $b;
            // If no overflow, dividing back recovers the operand exactly.
            return intdiv($product, $b) !== $a;
        }
    }

    /**
     * Applies algebraic identities that hold in integer arithmetic:
     *   x + 0, 0 + x, x - 0            -> x
     *   x * 1, 1 * x                   -> x
     *   x * 0, 0 * x                   -> 0
     *   x / 1                          -> x
     *   -(-x)                          -> x
     */
    final class AlgebraicSimplify implements Pass
    {
        public function rewrite(IrExpr $node): IrExpr
        {
            if ($node instanceof IrNeg && $node->operand instanceof IrNeg) {
                return $node->operand->operand;
            }
            if ($node instanceof IrBinary) {
                return $this->simplifyBinary($node);
            }
            return $node;
        }

        private function simplifyBinary(IrBinary $node): IrExpr
        {
            $left = $node->left;
            $right = $node->right;

            switch ($node->op) {
                case BinOp::Add:
                    if ($this->isConst($left, 0)) {
                        return $right;
                    }
                    if ($this->isConst($right, 0)) {
                        return $left;
                    }
                    break;
                case BinOp::Sub:
                    if ($this->isConst($right, 0)) {
                        return $left;
                    }
                    break;
                case BinOp::Mul:
                    if ($this->isConst($left, 0) || $this->isConst($right, 0)) {
                        return new IrConst(0);
                    }
                    if ($this->isConst($left, 1)) {
                        return $right;
                    }
                    if ($this->isConst($right, 1)) {
                        return $left;
                    }
                    break;
                case BinOp::Div:
                    if ($this->isConst($right, 1)) {
                        return $left;
                    }
                    break;
            }
            return $node;
        }

        /** True if $node is exactly the constant $value. */
        private function isConst(IrExpr $node, int $value): bool
        {
            return $node instanceof IrConst && $node->value === $value;
        }
    }

    /**
     * Cancels an operation against its exact inverse where integer-safe:
     *   (e * k) / k  ->  e     (safe: multiply-then-divide loses nothing unless it overflowed, which fold would keep)
     */
    final class InverseCancel implements Pass
    {
        public function rewrite(IrExpr $node): IrExpr
        {
            if (!$node instanceof IrBinary || $node->op !== BinOp::Div) {
                return $node;
            }
            $left = $node->left;
            $divisor = $node->right;
            if (!$left instanceof IrBinary || $left->op !== BinOp::Mul) {
                return $node;
            }
            if (!$divisor instanceof IrConst || $divisor->value === 0) {
                return $node;
            }
            // (x * k) / k -> x ; also (k * x) / k -> x
            if ($left->right instanceof IrConst && $left->right->value === $divisor->value) {
                return $left->left;
            }
            if ($left->left instanceof IrConst && $left->left->value === $divisor->value) {
                return $left->right;
            }
            return $node;
        }
    }

    /**
     * Runs a set of passes over the IR tree to a fixpoint.
     *
     * Each expression is optimized bottom-up (children first), then every
     * pass is applied at the current node until nothing changes.
     */
    final class Optimizer
    {
        /** @var list<Pass> */
        private array $passes;

        /**
         * @param list<Pass> $passes Passes to apply; defaults to the standard set.
         */
        public function __construct(?array $passes = null)
        {
            $this->passes = $passes ?? [
                new ConstantFold(),
                new AlgebraicSimplify(),
                new InverseCancel(),
            ];
        }

        /**
         * Optimize a program.
         *
         * @param list<IrStmt> $program
         * @return list<IrStmt>
         */
        public function optimize(array $program): array
        {
            return array_map($this->stmt(...), $program);
        }

        /** Optimize a single statement. */
        private function stmt(IrStmt $node): IrStmt
        {
            if ($node instanceof IrPrint) {
                return new IrPrint($this->expr($node->expr));
            }

            return $node;
        }

        /** Optimize an expression: children first, then passes to a fixpoint. */
        private function expr(IrExpr $node): IrExpr
        {
            $node = $this->descend($node);

            do {
                $before = $node;
                foreach ($this->passes as $pass) {
                    $node = $pass->rewrite($node);
                }
                // If a pass exposed new structure, re-optimize children.
                if ($node !== $before) {
                    $node = $this->descend($node);
                }
            } while ($node !== $before);

            return $node;
        }

        /** Recurse into a node's children, rebuilding it with optimized ones. */
        private function descend(IrExpr $node): IrExpr
        {
            return match (true) {
                $node instanceof IrBinary => new IrBinary(
                    $node->op,
                    $this->expr($node->left),
                    $this->expr($node->right),
                ),
                $node instanceof IrNeg => new IrNeg($this->expr($node->operand)),
                default => $node, // IrConst, IrVar: nothing to descend into.
            };
        }
    }
}

namespace Mathy\Lisp {
    use InvalidArgumentException;
    use Mathy\Ir\BinOp;
    use Mathy\Ir\IrBinary;
    use Mathy\Ir\IrConst;
    use Mathy\Ir\IrExpr;
    use Mathy\Ir\IrNeg;
    use Mathy\Ir\IrPrint;
    use Mathy\Ir\IrStmt;
    use Mathy\Ir\IrVar;

    /** A node in the Lisp-surface AST. */
    interface LispNode {}

    /** A number literal, e.g. `10` or `-2`. */
    final readonly class LispNum implements LispNode
    {
        public function __construct(
            public int $value,
        ) {}
    }

    /** A symbol, e.g. `+`, `print`, `neg`, or a variable name. */
    final readonly class LispSym implements LispNode
    {
        public function __construct(
            public string $name,
        ) {}
    }

    /** A parenthesized list, e.g. `(+ 1 2)`. */
    final readonly class LispList implements LispNode
    {
        /** @param list<LispNode> $items */
        public function __construct(
            public array $items,
        ) {}

        /**
         * Fetch the item at $index, asserting its presence.
         *
         * @throws InvalidArgumentException if the index is absent.
         */
        public function at(int $index): LispNode
        {
            return $this->items[$index] ?? throw new InvalidArgumentException("missing list element at index {$index}");
        }

        /** Number of items in the list. */
        public function count(): int
        {
            return \count($this->items);
        }
    }

    /**
     * Parses fully-parenthesized prefix syntax into a Lisp AST.
     *
     * Grammar: atoms are numbers or symbols; everything else is a
     * space-separated list wrapped in parentheses.
     */
    final class LispParser
    {
        /** @var list<string> */
        private array $tokens = [];
        private int $pos = 0;

        /**
         * Parse a whole program: a sequence of top-level forms.
         *
         * @return list<LispNode>
         */
        public function parse(string $src): array
        {
            $this->tokens = $this->tokenize($src);
            $this->pos = 0;

            $forms = [];
            while ($this->pos < \count($this->tokens)) {
                $forms[] = $this->form();
            }
            return $forms;
        }

        /**
         * Split source into `(`, `)`, and atom tokens.
         *
         * @return list<string>
         */
        private function tokenize(string $src): array
        {
            $spaced = str_replace(['(', ')'], [' ( ', ' ) '], $src);
            $parts = preg_split('/\s+/', trim($spaced), flags: PREG_SPLIT_NO_EMPTY);
            if ($parts === false) {
                throw new InvalidArgumentException('failed to tokenize source');
            }
            return array_values($parts);
        }

        /** Peek at the current token, or null at end of input. */
        private function peek(): ?string
        {
            return $this->tokens[$this->pos] ?? null;
        }

        /** Parse one form: an atom or a `( ... )` list. */
        private function form(): LispNode
        {
            $tok = $this->peek() ?? throw new InvalidArgumentException('unexpected end of input');

            if ($tok === '(') {
                return $this->list();
            }
            if ($tok === ')') {
                throw new InvalidArgumentException('unexpected )');
            }
            $this->pos++;
            return $this->atom($tok);
        }

        /** Parse a `( form* )` list, assuming the cursor is on `(`. */
        private function list(): LispList
        {
            $this->pos++; // consume '('

            $items = [];
            while (true) {
                $tok = $this->peek() ?? throw new InvalidArgumentException('unterminated list');
                if ($tok === ')') {
                    break;
                }
                $items[] = $this->form();
            }
            $this->pos++; // consume ')'
            return new LispList($items);
        }

        /** Classify a bare atom as a number or a symbol. */
        private function atom(string $tok): LispNode
        {
            if (preg_match('/^-?\d+$/', $tok) === 1) {
                return new LispNum((int) $tok);
            }
            return new LispSym($tok);
        }
    }

    /** Lowers a Lisp AST into shared Mathy IR. */
    final class LispLowering
    {
        /**
         * Lower a list of top-level forms to IR statements.
         *
         * @param list<LispNode> $forms
         * @return list<IrStmt>
         */
        public function lower(array $forms): array
        {
            return array_map($this->stmt(...), $forms);
        }

        /** Lower one top-level form, which must be a statement. */
        private function stmt(LispNode $node): IrStmt
        {
            if (!$node instanceof LispList) {
                throw new InvalidArgumentException('top-level form must be a list');
            }
            $head = $node->at(0);
            if (!$head instanceof LispSym || $head->name !== 'print') {
                throw new InvalidArgumentException('expected a (print ...) statement');
            }
            if ($node->count() !== 2) {
                throw new InvalidArgumentException('print takes exactly one argument');
            }
            return new IrPrint($this->expr($node->at(1)));
        }

        /** Lower an expression form to an IR expression. */
        private function expr(LispNode $node): IrExpr
        {
            if ($node instanceof LispNum) {
                return new IrConst($node->value);
            }
            if ($node instanceof LispSym) {
                return new IrVar($node->name);
            }
            if ($node instanceof LispList) {
                return $this->call($node);
            }
            throw new InvalidArgumentException('unrecognized expression node');
        }

        /** Lower a `( op arg... )` call. */
        private function call(LispList $node): IrExpr
        {
            $head = $node->at(0);
            if (!$head instanceof LispSym) {
                throw new InvalidArgumentException('list head must be a symbol');
            }

            if ($head->name === 'neg') {
                if ($node->count() !== 2) {
                    throw new InvalidArgumentException('neg takes exactly one argument');
                }
                return new IrNeg($this->expr($node->at(1)));
            }

            if ($node->count() !== 3) {
                throw new InvalidArgumentException("operator '{$head->name}' takes exactly two arguments");
            }
            return new IrBinary(BinOp::fromSymbol($head->name), $this->expr($node->at(1)), $this->expr($node->at(2)));
        }
    }
}

namespace Mathy\CLang {
    use InvalidArgumentException;
    use Mathy\Ir\BinOp;
    use Mathy\Ir\IrBinary;
    use Mathy\Ir\IrConst;
    use Mathy\Ir\IrExpr;
    use Mathy\Ir\IrNeg;
    use Mathy\Ir\IrPrint;
    use Mathy\Ir\IrStmt;
    use Mathy\Ir\IrVar;

    /** A node in the C-surface AST. */
    interface CNode {}

    /** A number literal. */
    final readonly class CNum implements CNode
    {
        public function __construct(
            public int $value,
        ) {}
    }

    /** A variable reference. */
    final readonly class CVar implements CNode
    {
        public function __construct(
            public string $name,
        ) {}
    }

    /** A unary minus, e.g. `-x`. */
    final readonly class CUnary implements CNode
    {
        public function __construct(
            public CNode $operand,
        ) {}
    }

    /** An infix binary expression, e.g. `a + b`. */
    final readonly class CBinary implements CNode
    {
        public function __construct(
            public string $op,
            public CNode $left,
            public CNode $right,
        ) {}
    }

    /** A `print(expr);` statement. */
    final readonly class CPrint implements CNode
    {
        public function __construct(
            public CNode $expr,
        ) {}
    }

    /**
     * A recursive-descent parser for a tiny C-like expression language.
     *
     * Grammar (precedence climbing):
     *   program := stmt*
     *   stmt    := 'print' '(' expr ')' ';'
     *   expr    := term (('+' | '-') term)*
     *   term    := unary (('*' | '/') unary)*
     *   unary   := '-' unary | primary
     *   primary := NUMBER | IDENT | '(' expr ')'
     */
    final class CParser
    {
        /** @var list<string> */
        private array $tokens = [];
        private int $pos = 0;

        /**
         * Parse a whole program into a list of statements.
         *
         * @return list<CPrint>
         */
        public function parse(string $src): array
        {
            $this->tokens = $this->tokenize($src);
            $this->pos = 0;

            $stmts = [];
            while ($this->pos < \count($this->tokens)) {
                $stmts[] = $this->stmt();
            }
            return $stmts;
        }

        /**
         * Split source into number, identifier, and punctuation tokens.
         *
         * @return list<string>
         */
        private function tokenize(string $src): array
        {
            $matches = [];
            $result = preg_match_all('/\d+|[A-Za-z_]\w*|[()+\-*\/;]/', $src, $matches);
            if ($result === false) {
                throw new InvalidArgumentException('failed to tokenize source');
            }
            /** @var list<string> $tokens */
            $tokens = $matches[0] ?? [];
            return $tokens;
        }

        /** Peek at the current token without consuming it. */
        private function peek(): ?string
        {
            return $this->tokens[$this->pos] ?? null;
        }

        /**
         * Consume the current token, requiring it to equal $expected if given.
         *
         * @throws InvalidArgumentException on end of input or mismatch.
         */
        private function eat(?string $expected = null): string
        {
            $tok = $this->peek() ?? throw new InvalidArgumentException('unexpected end of input');
            if ($expected !== null && $tok !== $expected) {
                throw new InvalidArgumentException("expected '{$expected}', got '{$tok}'");
            }
            $this->pos++;
            return $tok;
        }

        /** Parse `print ( expr ) ;`. */
        private function stmt(): CPrint
        {
            $this->eat('print');
            $this->eat('(');
            $expr = $this->expr();
            $this->eat(')');
            $this->eat(';');
            return new CPrint($expr);
        }

        /** Parse additive: term (('+'|'-') term)*. */
        private function expr(): CNode
        {
            $node = $this->term();
            while (true) {
                $op = $this->peek();

                if ($op === '+' || $op === '-') {
                    $this->eat();
                    $node = new CBinary($op, $node, $this->term());
                } else {
                    break;
                }
            }

            return $node;
        }

        /** Parse multiplicative: unary (('*'|'/') unary)*. */
        private function term(): CNode
        {
            $node = $this->unary();
            while (true) {
                $op = $this->peek();

                if ($op === '*' || $op === '/') {
                    $this->eat();
                    $node = new CBinary($op, $node, $this->unary());
                } else {
                    break;
                }
            }

            return $node;
        }

        /** Parse a unary minus chain, then a primary. */
        private function unary(): CNode
        {
            if ($this->peek() === '-') {
                $this->eat();
                return new CUnary($this->unary());
            }

            return $this->primary();
        }

        /** Parse a number, identifier, or parenthesized subexpression. */
        private function primary(): CNode
        {
            $tok = $this->peek() ?? throw new InvalidArgumentException('unexpected end of input');

            if ($tok === '(') {
                $this->eat('(');
                $node = $this->expr();
                $this->eat(')');
                return $node;
            }

            if (preg_match('/^\d+$/', $tok) === 1) {
                $this->eat();
                return new CNum((int) $tok);
            }

            if (preg_match('/^[A-Za-z_]\w*$/', $tok) === 1) {
                $this->eat();
                return new CVar($tok);
            }

            throw new InvalidArgumentException("unexpected token '{$tok}'");
        }
    }

    /** Lowers a C AST into shared Mathy IR. */
    final class CLowering
    {
        /**
         * Lower a list of C statements to IR statements.
         *
         * @param list<CPrint> $stmts
         * @return list<IrStmt>
         */
        public function lower(array $stmts): array
        {
            return array_map($this->stmt(...), $stmts);
        }

        /** Lower one statement. */
        private function stmt(CNode $node): IrStmt
        {
            if ($node instanceof CPrint) {
                return new IrPrint($this->expr($node->expr));
            }
            throw new InvalidArgumentException('expected a print statement');
        }

        /** Lower an expression node. */
        private function expr(CNode $node): IrExpr
        {
            return match (true) {
                $node instanceof CNum => new IrConst($node->value),
                $node instanceof CVar => new IrVar($node->name),
                $node instanceof CUnary => new IrNeg($this->expr($node->operand)),
                $node instanceof CBinary => new IrBinary(
                    BinOp::fromSymbol($node->op),
                    $this->expr($node->left),
                    $this->expr($node->right),
                ),
                default => throw new InvalidArgumentException('not an expression: ' . $node::class),
            };
        }
    }
}

namespace Mathy\Bytecode {
    use InvalidArgumentException;

    /** A compiled unit: instructions plus an integer pool and a name pool. */
    final class Chunk
    {
        /** @var list<Instruction> */
        public array $code = [];
        /** @var list<int> */
        public array $constants = [];
        /** @var list<string> */
        public array $names = [];

        /** Append an instruction. */
        public function emit(Instruction $inst): void
        {
            $this->code[] = $inst;
        }

        /** Intern an integer constant, returning its pool index. */
        public function constant(int $value): int
        {
            $i = array_search($value, $this->constants, true);
            if ($i !== false) {
                return $i;
            }
            $this->constants[] = $value;
            return \count($this->constants) - 1;
        }

        /** Intern a variable name, returning its pool index. */
        public function name(string $value): int
        {
            $i = array_search($value, $this->names, true);
            if ($i !== false) {
                return $i;
            }
            $this->names[] = $value;
            return \count($this->names) - 1;
        }
    }

    /**
     * A single encoded instruction.
     *
     * Layout: [ op:8 | A:8 | B:8 | C:8 ], or A plus a 16-bit Bx field.
     */
    final readonly class Instruction
    {
        /** A Bx : R[A] = K[Bx] */
        public const int LOADK = 0;
        /** A B : R[A] = R[B] */
        public const int MOVE = 1;
        /** A B C : R[A] = R[B] + R[C] */
        public const int ADD = 2;
        /** A B C : R[A] = R[B] - R[C] */
        public const int SUB = 3;
        /** A B C : R[A] = R[B] * R[C] */
        public const int MUL = 4;
        /** A B C : R[A] = R[B] / R[C] */
        public const int DIV = 5;
        /** A B : R[A] = -R[B] */
        public const int NEG = 6;
        /** A sBx : R[A] = sBx (immediate int) */
        public const int LOADI = 7;
        /** A : print R[A] */
        public const int PRINT = 8;
        /** A Bx : R[A] = env[names[Bx]] */
        public const int LOADV = 9;

        private function __construct(
            public int $code,
        ) {}

        /** Assert an operand fits in an unsigned 8-bit field. */
        private static function u8(int $v, string $field): int
        {
            if ($v < 0 || $v > 0xFF) {
                throw new InvalidArgumentException("operand {$field}={$v} out of 8-bit range");
            }
            return $v;
        }

        /** Assert a value fits in an unsigned 16-bit field. */
        private static function u16(int $v, string $field): int
        {
            if ($v < 0 || $v > 0xFFFF) {
                throw new InvalidArgumentException("field {$field}={$v} out of 16-bit range");
            }
            return $v;
        }

        /** Assert a value fits in a signed 16-bit field. */
        private static function s16(int $v, string $field): int
        {
            if ($v < -0x8000 || $v > 0x7FFF) {
                throw new InvalidArgumentException("field {$field}={$v} out of signed 16-bit range");
            }
            return $v;
        }

        /** iABC: three register operands. */
        public static function makeABC(int $op, int $a, int $b, int $c): self
        {
            return new self(
                self::u8($op, 'op') | (self::u8($a, 'A') << 8) | (self::u8($b, 'B') << 16) | (self::u8($c, 'C') << 24),
            );
        }

        /** iAB: two operands, C unused. */
        public static function makeAB(int $op, int $a, int $b): self
        {
            return new self(self::u8($op, 'op') | (self::u8($a, 'A') << 8) | (self::u8($b, 'B') << 16));
        }

        /** iA: one operand. */
        public static function makeA(int $op, int $a): self
        {
            return new self(self::u8($op, 'op') | (self::u8($a, 'A') << 8));
        }

        /** iABx: unsigned 16-bit Bx (e.g. constant or name index). */
        public static function makeABx(int $op, int $a, int $bx): self
        {
            return new self(self::u8($op, 'op') | (self::u8($a, 'A') << 8) | (self::u16($bx, 'Bx') << 16));
        }

        /** iAsBx: signed 16-bit Bx (e.g. immediate value). */
        public static function makeAsBx(int $op, int $a, int $sbx): self
        {
            return self::makeABx($op, $a, self::s16($sbx, 'sBx') + 0x8000);
        }

        /** Decode the opcode. */
        public function op(): int
        {
            return $this->code & 0xFF;
        }

        /** Decode operand A. */
        public function a(): int
        {
            return ($this->code >> 8) & 0xFF;
        }

        /** Decode operand B. */
        public function b(): int
        {
            return ($this->code >> 16) & 0xFF;
        }

        /** Decode operand C. */
        public function c(): int
        {
            return ($this->code >> 24) & 0xFF;
        }

        /** Decode the unsigned 16-bit Bx field. */
        public function bx(): int
        {
            return ($this->code >> 16) & 0xFFFF;
        }

        /** Decode the signed 16-bit Bx field. */
        public function sbx(): int
        {
            return $this->bx() - 0x8000;
        }
    }
}

namespace Mathy\Compiler {
    use InvalidArgumentException;
    use Mathy\Bytecode\Chunk;
    use Mathy\Bytecode\Instruction;
    use Mathy\Ir\IrBinary;
    use Mathy\Ir\IrConst;
    use Mathy\Ir\IrExpr;
    use Mathy\Ir\IrNeg;
    use Mathy\Ir\IrPrint;
    use Mathy\Ir\IrStmt;
    use Mathy\Ir\IrVar;

    /**
     * Lowers a list of IR statements into a single Chunk.
     *
     * Uses a simple stack-style register allocator: each expression result
     * lands in the next free register, and registers are freed as operands
     * are consumed.
     */
    final class Compiler
    {
        private Chunk $chunk;
        private int $next = 0;

        public function __construct()
        {
            $this->chunk = new Chunk();
        }

        /**
         * @param list<IrStmt> $program
         */
        public function compile(array $program): Chunk
        {
            $this->chunk = new Chunk();
            $this->next = 0;
            foreach ($program as $stmt) {
                $this->stmt($stmt);
                $this->next = 0; // registers are scratch between statements
            }
            return $this->chunk;
        }

        /** Reserve the next free register. */
        private function alloc(): int
        {
            return $this->next++;
        }

        /** Compile a statement. */
        private function stmt(IrStmt $node): void
        {
            if ($node instanceof IrPrint) {
                $r = $this->expr($node->expr);
                $this->chunk->emit(Instruction::makeA(Instruction::PRINT, $r));
                return;
            }
            throw new InvalidArgumentException('not a statement: ' . $node::class);
        }

        /** Compile an expression, returning the register holding its result. */
        private function expr(IrExpr $node): int
        {
            return match (true) {
                $node instanceof IrConst => $this->constExpr($node),
                $node instanceof IrVar => $this->varExpr($node),
                $node instanceof IrNeg => $this->negExpr($node),
                $node instanceof IrBinary => $this->binaryExpr($node),
                default => throw new InvalidArgumentException('not an expression: ' . $node::class),
            };
        }

        /** Load a constant into a fresh register. */
        private function constExpr(IrConst $node): int
        {
            $dst = $this->alloc();
            // Small values fit in a signed immediate; larger ones go to the pool.
            if ($node->value >= -0x8000 && $node->value <= 0x7FFF) {
                $this->chunk->emit(Instruction::makeAsBx(Instruction::LOADI, $dst, $node->value));
                return $dst;
            }

            $k = $this->chunk->constant($node->value);
            $this->chunk->emit(Instruction::makeABx(Instruction::LOADK, $dst, $k));
            return $dst;
        }

        /** Load a variable's value into a fresh register. */
        private function varExpr(IrVar $node): int
        {
            $dst = $this->alloc();
            $n = $this->chunk->name($node->name);
            $this->chunk->emit(Instruction::makeABx(Instruction::LOADV, $dst, $n));
            return $dst;
        }

        /** Compile a negation in place. */
        private function negExpr(IrNeg $node): int
        {
            $src = $this->expr($node->operand);
            $this->chunk->emit(Instruction::makeAB(Instruction::NEG, $src, $src));
            return $src;
        }

        /** Compile a binary op, reusing the left register for the result. */
        private function binaryExpr(IrBinary $node): int
        {
            $left = $this->expr($node->left);
            $right = $this->expr($node->right);
            $this->chunk->emit(Instruction::makeABC($node->op->opcode(), $left, $left, $right));
            $this->next = $right; // free the right operand's register
            return $left;
        }
    }
}

namespace Mathy\Vm {
    use Mathy\Bytecode\Chunk;
    use Mathy\Bytecode\Instruction;
    use RuntimeException;

    /** Thrown when execution hits an invalid operation or malformed chunk. */
    final class VmError extends RuntimeException {}

    /** Executes a chunk against a flat register file and a variable environment. */
    final class Vm
    {
        /** @var array<int, int> */
        private array $r = [];

        /**
         * Run every instruction in the chunk.
         *
         * @param array<string, int> $env Variable bindings for LOADV.
         */
        public function run(Chunk $chunk, array $env = []): void
        {
            $this->r = [];

            foreach ($chunk->code as $pc => $inst) {
                match ($inst->op()) {
                    Instruction::LOADK => $this->set($inst->a(), $this->konst($chunk, $inst->bx())),
                    Instruction::LOADI => $this->set($inst->a(), $inst->sbx()),
                    Instruction::LOADV => $this->set($inst->a(), $this->lookup($chunk, $inst->bx(), $env)),
                    Instruction::MOVE => $this->set($inst->a(), $this->get($inst->b())),
                    Instruction::ADD => $this->set($inst->a(), $this->get($inst->b()) + $this->get($inst->c())),
                    Instruction::SUB => $this->set($inst->a(), $this->get($inst->b()) - $this->get($inst->c())),
                    Instruction::MUL => $this->set($inst->a(), $this->get($inst->b()) * $this->get($inst->c())),
                    Instruction::DIV => $this->set($inst->a(), $this->div(
                        $this->get($inst->b()),
                        $this->get($inst->c()),
                    )),
                    Instruction::NEG => $this->set($inst->a(), -$this->get($inst->b())),
                    Instruction::PRINT => $this->emit($this->get($inst->a())),
                    default => throw new VmError("unknown opcode {$inst->op()} at pc {$pc}"),
                };
            }
        }

        /** Read a register, failing if it was never written. */
        private function get(int $reg): int
        {
            if (!array_key_exists($reg, $this->r)) {
                throw new VmError("read of uninitialized register r{$reg}");
            }
            return $this->r[$reg];
        }

        /** Write a register. */
        private function set(int $reg, int $value): void
        {
            $this->r[$reg] = $value;
        }

        /** Read an integer constant from the pool. */
        private function konst(Chunk $chunk, int $index): int
        {
            if (!array_key_exists($index, $chunk->constants)) {
                throw new VmError("constant index {$index} out of range");
            }
            return $chunk->constants[$index];
        }

        /**
         * Resolve a variable: pool index -> name -> environment value.
         *
         * @param array<string, int> $env
         */
        private function lookup(Chunk $chunk, int $index, array $env): int
        {
            if (!array_key_exists($index, $chunk->names)) {
                throw new VmError("name index {$index} out of range");
            }
            $name = $chunk->names[$index];
            if (!array_key_exists($name, $env)) {
                throw new VmError("undefined variable '{$name}'");
            }
            return $env[$name];
        }

        /** Integer division, guarding against a zero divisor and overflow. */
        private function div(int $a, int $b): int
        {
            if ($b === 0) {
                throw new VmError('division by zero');
            }
            if ($a === PHP_INT_MIN && $b === -1) {
                throw new VmError('division overflow');
            }
            return intdiv($a, $b);
        }

        /** Print a value, separated from execution for a clean side-effect seam. */
        private function emit(int $value): void
        {
            echo $value, PHP_EOL;
        }
    }
}

namespace Mathy\Example {
    use Mathy\CLang\CLowering;
    use Mathy\CLang\CParser;
    use Mathy\Compiler\Compiler;
    use Mathy\Lisp\LispLowering;
    use Mathy\Lisp\LispParser;
    use Mathy\Optimizer\Optimizer;
    use Mathy\Vm\Vm;

    $compiler = new Compiler();
    $optimizer = new Optimizer();
    $vm = new Vm();

    $cSrc = 'print((a + 5) * 1 + 0);';
    $cAst = new CParser()->parse($cSrc);
    $cIr = new CLowering()->lower($cAst);
    $cOptimizedIr = $optimizer->optimize($cIr);
    $cChunk = $compiler->compile($cOptimizedIr);

    echo 'Code      : ', $cSrc, PHP_EOL;
    echo 'Variables : ["a" => 3]', PHP_EOL;
    echo 'Output    : ';
    $vm->run($cChunk, ['a' => 3]);
    echo PHP_EOL;

    $cSrc2 = 'print((a * 10) / 10);';
    $cAst2 = new CParser()->parse($cSrc2);
    $cIr2 = new CLowering()->lower($cAst2);
    $cOptimizedIr2 = $optimizer->optimize($cIr2);
    $cChunk2 = $compiler->compile($cOptimizedIr2);
    echo 'Code      : ', $cSrc2, PHP_EOL;
    echo 'Variables : ["a" => 7]', PHP_EOL;
    echo 'Output    : ';
    $vm->run($cChunk2, ['a' => 7]);
    echo PHP_EOL;

    $lispSrc = '(print (* (+ 10 5) -2))';
    $lispAst = new LispParser()->parse($lispSrc);
    $lispIr = new LispLowering()->lower($lispAst);
    $lispOptimizedIr = $optimizer->optimize($lispIr);
    $lispChunk = $compiler->compile($lispOptimizedIr);
    echo 'Code      : ', $lispSrc, PHP_EOL;
    echo 'Output    : ';
    $vm->run($lispChunk);
    echo PHP_EOL;
}