{ "cells": [ { "cell_type": "markdown", "id": "2de06185", "metadata": {}, "source": [ "---\n", "title: \"Crafting Interpreters: A Runnable, Semantics-First Cheat Sheet (Python)\"\n", "pubDate: 2026-04-15T13:00:00+03:00\n", "description: \"Notebook companion to Crafting Interpreters. Chapters are distilled into a core semantic idea and presented via a runnable Python micro-example. Sections conclude with an end-to-end tree-walk and bytecode VM executions of the same tiny program.\"\n", "category: \"lab\"\n", "tags:\n", " - python\n", " - programming-languages\n", " - interpreters\n", " - compilers\n", " - virtual-machines\n", "---" ] }, { "cell_type": "markdown", "id": "2ae85aa3", "metadata": {}, "source": [ "# Crafting Interpreters Cheat Sheet\n", "\n", "A notebook companion for *Crafting Interpreters*. Each chapter is self-contained, with a definition cell and a runnable cell right below it.\n", "\n", "This is a conceptual companion, not a line-by-line reproduction of the book's implementations. Some chapters use smaller substitute mechanisms when that keeps the core idea cleaner in notebook form. For example, where the book uses a Pratt parser for expression parsing, this notebook may use a smaller hand-written parser that demonstrates precedence and associativity directly without reproducing the exact architecture. " ] }, { "cell_type": "markdown", "id": "b9e0d44c", "metadata": {}, "source": [ "**Download & run locally:** [crafting-interpreters-cheat-sheet.ipynb](/notebooks/crafting-interpreters-cheat-sheet.ipynb)" ] }, { "cell_type": "markdown", "id": "e6612bf5", "metadata": {}, "source": [ "### Notebook usage\n", "\n", "- Run cells top to bottom.\n", "- Each chapter appears as `implementation -> example`.\n", "- The notebook targets Python 3.10+ because several examples use `match` / `case`.\n" ] }, { "cell_type": "markdown", "id": "63c11508", "metadata": {}, "source": [ "## Chapter 4. Scanning\n", "\n", "Lexing turns characters into tokens so later phases can reason about symbols.\n", "\n", "*Note*: the book implements a manual scanner with explicit state and lookahead; this version uses a compact regex-based tokenizer to illustrate tokenization." ] }, { "cell_type": "code", "execution_count": 1, "id": "cce7f8d3", "metadata": {}, "outputs": [], "source": [ "def ch4_scanning() -> None:\n", " import re\n", " token = re.compile(r\"(?P\\d+)|(?P[A-Za-z_]\\w*)|(?P[=+;])|(?P\\s+)\")\n", " def scan(s: str): return [(m.lastgroup, m.group()) for m in token.finditer(s) if m.lastgroup != \"WS\"]\n", " print(scan(\"var x=1+2;\"))\n" ] }, { "cell_type": "code", "execution_count": 2, "id": "f2c1072e", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[('ID', 'var'), ('ID', 'x'), ('OP', '='), ('NUM', '1'), ('OP', '+'), ('NUM', '2'), ('OP', ';')]\n" ] } ], "source": [ "ch4_scanning()\n" ] }, { "cell_type": "markdown", "id": "c5680a9b", "metadata": {}, "source": [ "## Chapter 5. Representing Code\n", "\n", "ASTs turn code into data, which makes evaluation a tree walk.\n" ] }, { "cell_type": "code", "execution_count": 3, "id": "f30bbfcc", "metadata": {}, "outputs": [], "source": [ "def ch5_ast() -> None:\n", " def ev(e):\n", " match e:\n", " case (\"lit\", v): return v\n", " case (\"+\", a, b): return ev(a) + ev(b)\n", " case _: raise ValueError(e)\n", " expr = (\"+\", (\"lit\", 1), (\"+\", (\"lit\", 2), (\"lit\", 3)))\n", " print(ev(expr))\n" ] }, { "cell_type": "code", "execution_count": 4, "id": "878879f9", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "6\n" ] } ], "source": [ "ch5_ast()\n" ] }, { "cell_type": "markdown", "id": "fe715e3b", "metadata": {}, "source": [ "## Chapter 6. Parsing Expressions\n", "\n", "Parsing chooses structure and precedence.\n", "\n", "*Note*: Crafting Interpreters uses a Pratt parser here; this notebook instead uses a tiny recursive-descent precedence parser so the shape of parsing remains explicit in a smaller cell." ] }, { "cell_type": "code", "execution_count": 5, "id": "edc4be41", "metadata": {}, "outputs": [], "source": [ "def ch6_structure() -> None:\n", " import re\n", "\n", " token_re = re.compile(r\"\\d+|[()+*]\")\n", " toks = token_re.findall(\"1+2*3+(4*5)\")\n", " i = 0\n", "\n", " def peek():\n", " return toks[i] if i < len(toks) else None\n", "\n", " def eat(tok=None):\n", " nonlocal i\n", " t = peek()\n", " if tok is not None and t != tok:\n", " raise SyntaxError((tok, t))\n", " i += 1\n", " return t\n", "\n", " def primary():\n", " t = peek()\n", " if t is None:\n", " raise SyntaxError(\"unexpected EOF\")\n", " if t.isdigit():\n", " eat()\n", " return (\"lit\", int(t))\n", " if t == \"(\":\n", " eat(\"(\")\n", " e = expr()\n", " eat(\")\")\n", " return e\n", " raise SyntaxError(t)\n", "\n", " def term():\n", " e = primary()\n", " while peek() == \"*\":\n", " eat(\"*\")\n", " e = (\"*\", e, primary())\n", " return e\n", "\n", " def expr():\n", " e = term()\n", " while peek() == \"+\":\n", " eat(\"+\")\n", " e = (\"+\", e, term())\n", " return e\n", "\n", " ast = expr()\n", " if peek() is not None:\n", " raise SyntaxError(f\"trailing token {peek()}\")\n", "\n", " def ev(e):\n", " match e:\n", " case (\"lit\", v): return v\n", " case (\"+\", a, b): return ev(a) + ev(b)\n", " case (\"*\", a, b): return ev(a) * ev(b)\n", " case _: raise ValueError(e)\n", "\n", " print(toks)\n", " print(ast)\n", " print(ev(ast))\n" ] }, { "cell_type": "code", "execution_count": 6, "id": "741662af", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "['1', '+', '2', '*', '3', '+', '(', '4', '*', '5', ')']\n", "('+', ('+', ('lit', 1), ('*', ('lit', 2), ('lit', 3))), ('*', ('lit', 4), ('lit', 5)))\n", "27\n" ] } ], "source": [ "ch6_structure()\n" ] }, { "cell_type": "markdown", "id": "729a8605", "metadata": {}, "source": [ "## Chapter 7. Evaluating Expressions\n", "\n", "Evaluation is runtime meaning with dynamic checks.\n" ] }, { "cell_type": "code", "execution_count": 7, "id": "0880a27e", "metadata": {}, "outputs": [], "source": [ "def ch7_eval_semantics() -> None:\n", " def ev(e):\n", " match e:\n", " case (\"lit\", v): return v\n", " case (\"+\", a, b):\n", " x, y = ev(a), ev(b)\n", " if type(x) != type(y): raise TypeError(\"no mixed +\")\n", " return x + y\n", " case _: raise ValueError(e)\n", " print(ev((\"+\", (\"lit\", 1), (\"lit\", 2))))\n", " try: ev((\"+\", (\"lit\", 1), (\"lit\", \"s\")))\n", " except Exception as ex: print(type(ex).__name__, str(ex))\n" ] }, { "cell_type": "code", "execution_count": 8, "id": "3446b887", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "3\n", "TypeError no mixed +\n" ] } ], "source": [ "ch7_eval_semantics()\n" ] }, { "cell_type": "markdown", "id": "7753af45", "metadata": {}, "source": [ "## Chapter 8. Statements and State\n", "\n", "Statements introduce mutation through environments.\n", "\n", "Note: this uses a single flat environment; the book introduces nested environments aligned with block structure." ] }, { "cell_type": "code", "execution_count": 9, "id": "cf8cb49f", "metadata": {}, "outputs": [], "source": [ "def ch8_state() -> None:\n", " env: dict[str, object] = {}\n", " def eval_(e):\n", " match e:\n", " case (\"lit\", v): return v\n", " case (\"var\", n): return env[n]\n", " case _: raise ValueError(e)\n", " def exec_(s):\n", " match s:\n", " case (\"var\", n, e): env[n] = eval_(e)\n", " case (\"set\", n, e): env[n] = eval_(e)\n", " case _: raise ValueError(s)\n", " exec_((\"var\", \"x\", (\"lit\", 0)))\n", " exec_((\"set\", \"x\", (\"lit\", 3)))\n", " print(env)\n" ] }, { "cell_type": "code", "execution_count": 10, "id": "a5e14355", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "{'x': 3}\n" ] } ], "source": [ "ch8_state()\n" ] }, { "cell_type": "markdown", "id": "01b4f014", "metadata": {}, "source": [ "## Chapter 9. Control Flow\n", "\n", "Control flow is who runs next.\n" ] }, { "cell_type": "code", "execution_count": 11, "id": "fc220708", "metadata": {}, "outputs": [], "source": [ "def ch9_control_flow() -> None:\n", " prog = [(\"inc\", \"x\"), (\"jnlt\", \"x\", 3, 0)] # jump to 0 while x < 3\n", " env, pc = {\"x\": 0}, 0\n", " while pc < len(prog):\n", " op, *a = prog[pc]\n", " if op == \"inc\":\n", " env[a[0]] += 1\n", " pc += 1\n", " elif op == \"jnlt\":\n", " name, bound, target = a\n", " pc = target if env[name] < bound else pc + 1\n", " else:\n", " raise ValueError(op)\n", " print(env[\"x\"])\n" ] }, { "cell_type": "code", "execution_count": 12, "id": "00df84fe", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "3\n" ] } ], "source": [ "ch9_control_flow()\n" ] }, { "cell_type": "markdown", "id": "8aa2d575", "metadata": {}, "source": [ "## Chapter 9. Syntactic Sugar\n", "\n", "Surface syntax often desugars into a smaller core.\n", "\n", "Note: this models control flow with explicit jumps; I think the book first implements structured control flow in the AST interpreter before lowering." ] }, { "cell_type": "code", "execution_count": 13, "id": "54d9bf9a", "metadata": {}, "outputs": [], "source": [ "def ch9_sugar() -> None:\n", " def desugar(stmt):\n", " match stmt:\n", " case (\"for\", init, cond, step, body):\n", " return [init, (\"while\", cond, body + [step])]\n", " case _:\n", " return [stmt]\n", "\n", " def run(block):\n", " env = {}\n", "\n", " def ev(e):\n", " match e:\n", " case (\"lit\", v): return v\n", " case (\"var\", n): return env[n]\n", " case (\"+\", a, b): return ev(a) + ev(b)\n", " case (\"<\", a, b): return ev(a) < ev(b)\n", " case _: raise ValueError(e)\n", "\n", " def exec_block(xs):\n", " for s in xs:\n", " exec_stmt(s)\n", "\n", " def exec_stmt(s):\n", " match s:\n", " case (\"var\", n, e): env[n] = ev(e)\n", " case (\"set\", n, e): env[n] = ev(e)\n", " case (\"print\", e): print(ev(e))\n", " case (\"while\", c, b):\n", " while ev(c):\n", " exec_block(b)\n", " case _: raise ValueError(s)\n", "\n", " exec_block(block)\n", "\n", " sugared = (\n", " \"for\",\n", " (\"var\", \"i\", (\"lit\", 0)),\n", " (\"<\", (\"var\", \"i\"), (\"lit\", 3)),\n", " (\"set\", \"i\", (\"+\", (\"var\", \"i\"), (\"lit\", 1))),\n", " [(\"print\", (\"var\", \"i\"))],\n", " )\n", "\n", " core = desugar(sugared)\n", " print(core)\n", " run(core)\n" ] }, { "cell_type": "code", "execution_count": 14, "id": "58fb69ab", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[('var', 'i', ('lit', 0)), ('while', ('<', ('var', 'i'), ('lit', 3)), [('print', ('var', 'i')), ('set', 'i', ('+', ('var', 'i'), ('lit', 1)))])]\n", "0\n", "1\n", "2\n" ] } ], "source": [ "ch9_sugar()\n" ] }, { "cell_type": "markdown", "id": "f7ae6da5", "metadata": {}, "source": [ "## Chapter 10. Functions\n", "\n", "Functions are first-class values and closures capture scope.\n" ] }, { "cell_type": "code", "execution_count": 15, "id": "18c04af2", "metadata": {}, "outputs": [], "source": [ "def ch10_functions() -> None:\n", " class Env(dict):\n", " def __init__(self, parent=None):\n", " super().__init__()\n", " self.parent = parent\n", "\n", " def get(self, name):\n", " if name in self:\n", " return self[name]\n", " if self.parent is not None:\n", " return self.parent.get(name)\n", " raise NameError(name)\n", "\n", " def ev(e, env):\n", " match e:\n", " case (\"lit\", v):\n", " return v\n", " case (\"var\", n):\n", " return env.get(n)\n", " case (\"+\", a, b):\n", " return ev(a, env) + ev(b, env)\n", " case (\"fun\", params, body):\n", " return (\"closure\", params, body, env)\n", " case (\"call\", fn_expr, arg_exprs):\n", " tag, params, body, closed = ev(fn_expr, env)\n", " call_env = Env(closed)\n", " for p, a in zip(params, arg_exprs):\n", " call_env[p] = ev(a, env)\n", " return ev(body, call_env)\n", " case _:\n", " raise ValueError(e)\n", "\n", " env = Env()\n", " env[\"makeAdder\"] = ev(\n", " (\"fun\", [\"n\"], (\"fun\", [\"x\"], (\"+\", (\"var\", \"x\"), (\"var\", \"n\")))),\n", " env,\n", " )\n", " env[\"add5\"] = ev((\"call\", (\"var\", \"makeAdder\"), [(\"lit\", 5)]), env)\n", " print(env[\"add5\"][0], ev((\"call\", (\"var\", \"add5\"), [(\"lit\", 2)]), env))\n" ] }, { "cell_type": "code", "execution_count": 16, "id": "c57b683e", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "closure 7\n" ] } ], "source": [ "ch10_functions()\n" ] }, { "cell_type": "markdown", "id": "efa9be25", "metadata": {}, "source": [ "## Chapter 11. Resolving and Binding\n", "\n", "Lexical scope can be resolved ahead of time.\n", "\n", "*Note*: this is a minimal resolver sketch; the book performs a full pre-pass over the AST" ] }, { "cell_type": "code", "execution_count": 17, "id": "a473b266", "metadata": {}, "outputs": [], "source": [ "def ch11_resolution() -> None:\n", " scopes: list[set[str]] = []\n", "\n", " def resolve_expr(e):\n", " match e:\n", " case (\"lit\", _):\n", " return e\n", " case (\"var\", name):\n", " for dist, scope in enumerate(reversed(scopes)):\n", " if name in scope:\n", " return (\"var_at\", dist, name)\n", " return (\"global\", name)\n", " case (\"+\", a, b):\n", " return (\"+\", resolve_expr(a), resolve_expr(b))\n", " case _:\n", " raise ValueError(e)\n", "\n", " def resolve_stmt(s):\n", " match s:\n", " case (\"var\", name, init):\n", " out = (\"var\", name, resolve_expr(init))\n", " if scopes:\n", " scopes[-1].add(name)\n", " return out\n", " case (\"print\", e):\n", " return (\"print\", resolve_expr(e))\n", " case (\"block\", body):\n", " scopes.append(set())\n", " out = (\"block\", [resolve_stmt(x) for x in body])\n", " scopes.pop()\n", " return out\n", " case _:\n", " raise ValueError(s)\n", "\n", " prog = (\"block\", [\n", " (\"var\", \"x\", (\"lit\", \"global\")),\n", " (\"block\", [\n", " (\"var\", \"x\", (\"lit\", \"local\")),\n", " (\"print\", (\"var\", \"x\")),\n", " ]),\n", " (\"print\", (\"var\", \"x\")),\n", " ])\n", "\n", " resolved = resolve_stmt(prog)\n", " print(resolved)" ] }, { "cell_type": "code", "execution_count": 18, "id": "17c61e09", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "('block', [('var', 'x', ('lit', 'global')), ('block', [('var', 'x', ('lit', 'local')), ('print', ('var_at', 0, 'x'))]), ('print', ('var_at', 0, 'x'))])\n" ] } ], "source": [ "ch11_resolution()\n" ] }, { "cell_type": "markdown", "id": "4dbc4b79", "metadata": {}, "source": [ "## Chapter 12. Classes\n", "\n", "Classes package state and behavior into objects.\n" ] }, { "cell_type": "code", "execution_count": 19, "id": "127613c8", "metadata": {}, "outputs": [], "source": [ "def ch12_classes() -> None:\n", " def lookup_method(cls, name):\n", " methods = cls[\"methods\"]\n", " if name in methods:\n", " return methods[name]\n", " raise KeyError(name)\n", "\n", " def bind(method, this):\n", " return lambda *args: method(this, *args)\n", "\n", " def new(cls, *args):\n", " obj = {\"class\": cls, \"fields\": {}}\n", " init = cls[\"methods\"].get(\"init\")\n", " if init is not None:\n", " bind(init, obj)(*args)\n", " return obj\n", "\n", " def getprop(obj, name):\n", " if name in obj[\"fields\"]:\n", " return obj[\"fields\"][name]\n", " return bind(lookup_method(obj[\"class\"], name), obj)\n", "\n", " Point = {\n", " \"name\": \"Point\",\n", " \"methods\": {\n", " \"init\": lambda this, x, y: this[\"fields\"].update({\"x\": x, \"y\": y}),\n", " \"norm2\": lambda this: this[\"fields\"][\"x\"] ** 2 + this[\"fields\"][\"y\"] ** 2,\n", " },\n", " }\n", "\n", " p = new(Point, 3, 4)\n", " print(getprop(p, \"norm2\")())\n" ] }, { "cell_type": "code", "execution_count": 20, "id": "38090b20", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "25\n" ] } ], "source": [ "ch12_classes()\n" ] }, { "cell_type": "markdown", "id": "9d39a7b3", "metadata": {}, "source": [ "## Chapter 12. Prototypes\n", "\n", "Prototype delegation is object lookup by chain walk.\n" ] }, { "cell_type": "code", "execution_count": 21, "id": "6a8a1274", "metadata": {}, "outputs": [], "source": [ "def ch12_prototypes() -> None:\n", " proto = {\"to_s\": lambda self: f\"{self['x']},{self['y']}\"}\n", " obj = {\"__proto__\": proto, \"x\": 1, \"y\": 2}\n", " def get(o, k): return o[k] if k in o else get(o[\"__proto__\"], k)\n", " print(get(obj, \"to_s\")(obj))\n" ] }, { "cell_type": "code", "execution_count": 22, "id": "d4f3ca05", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "1,2\n" ] } ], "source": [ "ch12_prototypes()\n" ] }, { "cell_type": "code", "execution_count": null, "id": "e3151f70", "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "id": "3f9d2512", "metadata": {}, "source": [ "## Chapter 13. Inheritance\n", "\n", "Inheritance is method lookup with reuse.\n" ] }, { "cell_type": "code", "execution_count": 23, "id": "80e2d2ab", "metadata": {}, "outputs": [], "source": [ "def ch13_inheritance() -> None:\n", " def lookup_method(cls, name):\n", " if name in cls[\"methods\"]:\n", " return cls[\"methods\"][name]\n", " if cls[\"super\"] is not None:\n", " return lookup_method(cls[\"super\"], name)\n", " raise KeyError(name)\n", "\n", " def bind(method, this):\n", " return lambda *args: method(this, *args)\n", "\n", " def new(cls):\n", " return {\"class\": cls, \"fields\": {}}\n", "\n", " def getprop(obj, name):\n", " return bind(lookup_method(obj[\"class\"], name), obj)\n", "\n", " A = {\n", " \"name\": \"A\",\n", " \"super\": None,\n", " \"methods\": {\n", " \"m\": lambda this: \"A\",\n", " },\n", " }\n", "\n", " B = {\n", " \"name\": \"B\",\n", " \"super\": A,\n", " \"methods\": {\n", " \"m\": lambda this: \"B->\" + lookup_method(B[\"super\"], \"m\")(this),\n", " },\n", " }\n", "\n", " b = new(B)\n", " print(getprop(b, \"m\")())\n" ] }, { "cell_type": "code", "execution_count": 24, "id": "a081cc87", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "B->A\n" ] } ], "source": [ "ch13_inheritance()\n" ] }, { "cell_type": "markdown", "id": "1cfc76a1", "metadata": {}, "source": [ "## End-to-End Shared Program\n", "\n", "A single tiny AST program is used by both execution models below. The surface language is intentionally small: `+`, `<`, `if`, `while`, `print`, vars, and assignment.\n" ] }, { "cell_type": "code", "execution_count": 25, "id": "cba3a149", "metadata": {}, "outputs": [], "source": [ "# Mini language AST\n", "# Expr: (\"lit\", v) | (\"var\", name) | (\"+\", a, b) | (\"<\", a, b)\n", "# Stmt: (\"var\", name, expr) | (\"set\", name, expr) | (\"print\", expr)\n", "# | (\"if\", cond, then_block, else_block) | (\"while\", cond, body_block)\n", "\n", "DEMO_PROG = [\n", " (\"var\", \"i\", (\"lit\", 0)),\n", " (\"var\", \"acc\", (\"lit\", 0)),\n", " (\"while\", (\"<\", (\"var\", \"i\"), (\"lit\", 5)), [\n", " (\"set\", \"acc\", (\"+\", (\"var\", \"acc\"), (\"var\", \"i\"))),\n", " (\"set\", \"i\", (\"+\", (\"var\", \"i\"), (\"lit\", 1))),\n", " ]),\n", " (\"if\", (\"<\", (\"var\", \"acc\"), (\"lit\", 10)),\n", " [(\"print\", (\"var\", \"acc\"))],\n", " [(\"print\", (\"+\", (\"var\", \"acc\"), (\"lit\", 100)))],\n", " ),\n", "]\n" ] }, { "cell_type": "markdown", "id": "edbc5e64", "metadata": {}, "source": [ "## End-to-End After II.A\n", "\n", "Run the shared AST program through a tiny tree-walk interpreter. This is the semantic target for the tree-walk half of the book.\n" ] }, { "cell_type": "code", "execution_count": 26, "id": "6146b2a9", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "110\n" ] } ], "source": [ "def run_treewalk(prog):\n", " env = {}\n", "\n", " def ev(e):\n", " match e:\n", " case (\"lit\", v): return v\n", " case (\"var\", n): return env[n]\n", " case (\"+\", a, b):\n", " x, y = ev(a), ev(b)\n", " if type(x) != type(y): raise TypeError(\"no mixed +\")\n", " return x + y\n", " case (\"<\", a, b):\n", " x, y = ev(a), ev(b)\n", " return x < y\n", " case _: raise ValueError(e)\n", "\n", " def exec_block(block):\n", " for s in block: exec_stmt(s)\n", "\n", " def exec_stmt(s):\n", " match s:\n", " case (\"var\", n, e): env[n] = ev(e)\n", " case (\"set\", n, e): env[n] = ev(e)\n", " case (\"print\", e): print(ev(e))\n", " case (\"if\", c, t, f): exec_block(t if ev(c) else f)\n", " case (\"while\", c, b):\n", " while ev(c): exec_block(b)\n", " case _: raise ValueError(s)\n", "\n", " exec_block(prog)\n", "\n", "run_treewalk(DEMO_PROG) # expected: 110\n" ] }, { "cell_type": "markdown", "id": "ab6fb850", "metadata": {}, "source": [ "# III.A Bytecode Virtual Machine" ] }, { "cell_type": "markdown", "id": "bd57c6ac", "metadata": {}, "source": [ "## Chapter 14. Chunks of Bytecode\n", "\n", "Bytecode separates instructions from literals.\n" ] }, { "cell_type": "code", "execution_count": 27, "id": "6246e116", "metadata": {}, "outputs": [], "source": [ "def ch14_chunks() -> None:\n", " const = [1, 2]\n", " code = [(\"CONST\", 0), (\"CONST\", 1), (\"ADD\",), (\"RET\",)]\n", " for i, ins in enumerate(code):\n", " op, *a = ins\n", " print(i, op, const[a[0]] if op == \"CONST\" else \"\")\n" ] }, { "cell_type": "code", "execution_count": 28, "id": "c6458964", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "0 CONST 1\n", "1 CONST 2\n", "2 ADD \n", "3 RET \n" ] } ], "source": [ "ch14_chunks()\n" ] }, { "cell_type": "markdown", "id": "56b02a74", "metadata": {}, "source": [ "## Chapter 15. A Virtual Machine\n", "\n", "A VM gives semantics by a stack execution model.\n" ] }, { "cell_type": "code", "execution_count": 29, "id": "16a4ca1a", "metadata": {}, "outputs": [], "source": [ "def ch15_vm() -> None:\n", " const = [1, 2]\n", " code = [(\"CONST\", 0), (\"CONST\", 1), (\"ADD\",), (\"RET\",)]\n", " stack, ip = [], 0\n", " while True:\n", " op, *a = code[ip]; ip += 1\n", " if op == \"CONST\": stack.append(const[a[0]])\n", " elif op == \"ADD\": stack.append(stack.pop() + stack.pop())\n", " elif op == \"RET\": print(stack.pop()); break\n", " else: raise ValueError(op)\n" ] }, { "cell_type": "code", "execution_count": 30, "id": "44f48450", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "3\n" ] } ], "source": [ "ch15_vm()\n" ] }, { "cell_type": "markdown", "id": "cd4416c4", "metadata": {}, "source": [ "## Chapter 15. Register Sketch\n", "\n", "Register code makes dataflow explicit.\n" ] }, { "cell_type": "code", "execution_count": 31, "id": "123fd6db", "metadata": {}, "outputs": [], "source": [ "def ch15_register_bytecode() -> None:\n", " const = [1, 2]; r = [0, 0]\n", " r[0] = const[0]; r[1] = const[1]\n", " r[0] = r[0] + r[1]\n", " print(r[0])\n" ] }, { "cell_type": "code", "execution_count": 32, "id": "aa8779dd", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "3\n" ] } ], "source": [ "ch15_register_bytecode()\n" ] }, { "cell_type": "markdown", "id": "fcaea928", "metadata": {}, "source": [ "## Chapter 16. Scanning on Demand\n", "\n", "Lazy lexing produces tokens only when needed.\n" ] }, { "cell_type": "code", "execution_count": 33, "id": "52346e05", "metadata": {}, "outputs": [], "source": [ "def ch16_lazy_scan() -> None:\n", " import re\n", " pat = re.compile(r\"\\d+|[()+*]\")\n", " def scan(s: str):\n", " for m in pat.finditer(s): yield m.group()\n", " it = scan(\"1+(2*3)\")\n", " print(next(it), list(it))\n" ] }, { "cell_type": "code", "execution_count": 34, "id": "fa6700de", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "1 ['+', '(', '2', '*', '3', ')']\n" ] } ], "source": [ "ch16_lazy_scan()\n" ] }, { "cell_type": "markdown", "id": "ce12c2dd", "metadata": {}, "source": [ "## Chapter 17. Compiling Expressions\n", "\n", "Compilation lowers ASTs into bytecode.\n" ] }, { "cell_type": "code", "execution_count": 35, "id": "fbc4a2b0", "metadata": {}, "outputs": [], "source": [ "def ch17_compile() -> None:\n", " def compile_(e, const, code):\n", " match e:\n", " case (\"lit\", v):\n", " const.append(v); code.append((\"CONST\", len(const) - 1))\n", " case (\"+\", a, b):\n", " compile_(a, const, code); compile_(b, const, code); code.append((\"ADD\",))\n", " case _: raise ValueError(e)\n", " const, code = [], []\n", " compile_((\"+\", (\"lit\", 1), (\"lit\", 2)), const, code); code.append((\"RET\",))\n", " print(const, code)\n" ] }, { "cell_type": "code", "execution_count": 36, "id": "05a7a612", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[1, 2] [('CONST', 0), ('CONST', 1), ('ADD',), ('RET',)]\n" ] } ], "source": [ "ch17_compile()\n" ] }, { "cell_type": "markdown", "id": "09d6580f", "metadata": {}, "source": [ "## Chapter 18. Types of Values\n", "\n", "Tagged values make operations precise.\n" ] }, { "cell_type": "code", "execution_count": 37, "id": "af50abe7", "metadata": {}, "outputs": [], "source": [ "def ch18_tagged_values() -> None:\n", " def add(a, b):\n", " ta, va = a; tb, vb = b\n", " if ta != tb: raise TypeError(\"type mismatch\")\n", " return (ta, va + vb)\n", " print(add((\"num\", 1), (\"num\", 2)))\n" ] }, { "cell_type": "code", "execution_count": 38, "id": "1f1d598f", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "('num', 3)\n" ] } ], "source": [ "ch18_tagged_values()\n" ] }, { "cell_type": "markdown", "id": "b6507d4b", "metadata": {}, "source": [ "## Chapter 19. Strings\n", "\n", "Interning canonicalizes equal strings.\n" ] }, { "cell_type": "code", "execution_count": 39, "id": "5e836653", "metadata": {}, "outputs": [], "source": [ "def ch19_interning() -> None:\n", " pool: dict[str, str] = {}\n", " def intern(s: str) -> str: pool.setdefault(s, s); return pool[s]\n", " a = intern(\"hi\" * 1); b = intern(\"h\" + \"i\")\n", " print(a is b, a == b, len(pool))\n" ] }, { "cell_type": "code", "execution_count": 40, "id": "8d857fdc", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "True True 1\n" ] } ], "source": [ "ch19_interning()\n" ] }, { "cell_type": "markdown", "id": "04f114d1", "metadata": {}, "source": [ "## Chapter 20. Hash Tables\n", "\n", "Hash tables trade simple lookup for collision handling.\n" ] }, { "cell_type": "code", "execution_count": 41, "id": "06e9e8b4", "metadata": {}, "outputs": [], "source": [ "def ch20_hashtable() -> None:\n", " def hput(t, k, v):\n", " i = hash(k) % len(t)\n", " while t[i] and t[i][0] != k: i = (i + 1) % len(t)\n", " t[i] = (k, v)\n", " def hget(t, k):\n", " i = hash(k) % len(t)\n", " while t[i] and t[i][0] != k: i = (i + 1) % len(t)\n", " return None if not t[i] else t[i][1]\n", " t = [None] * 8; hput(t, \"a\", 1); hput(t, \"b\", 2); print(hget(t, \"b\"))\n" ] }, { "cell_type": "code", "execution_count": 42, "id": "cdf7dce0", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "2\n" ] } ], "source": [ "ch20_hashtable()\n" ] }, { "cell_type": "markdown", "id": "74776f97", "metadata": {}, "source": [ "## Chapter 21. Global Variables\n", "\n", "Globals are shared mutable name/value storage.\n" ] }, { "cell_type": "code", "execution_count": 43, "id": "df361bcf", "metadata": {}, "outputs": [], "source": [ "def ch21_globals() -> None:\n", " globals_: dict[str, int] = {}\n", " def setg(k: str, v: int) -> None: globals_[k] = v\n", " def getg(k: str) -> int: return globals_[k]\n", " setg(\"x\", 1); setg(\"x\", getg(\"x\") + 2)\n", " print(getg(\"x\"))\n" ] }, { "cell_type": "code", "execution_count": 44, "id": "1bf31eb4", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "3\n" ] } ], "source": [ "ch21_globals()\n" ] }, { "cell_type": "markdown", "id": "6b34a3ed", "metadata": {}, "source": [ "## Chapter 22. Local Variables\n", "\n", "Locals are usually fast stack slots.\n" ] }, { "cell_type": "code", "execution_count": 45, "id": "764bd64b", "metadata": {}, "outputs": [], "source": [ "def ch22_locals() -> None:\n", " stack = [None] * 4\n", " def fn(a: int, b: int) -> int:\n", " base = 0\n", " stack[base], stack[base + 1] = a, b\n", " stack[base + 2] = stack[base] + stack[base + 1]\n", " return stack[base + 2]\n", " print(fn(1, 2))\n" ] }, { "cell_type": "code", "execution_count": 46, "id": "196d76ee", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "3\n" ] } ], "source": [ "ch22_locals()\n" ] }, { "cell_type": "markdown", "id": "ea901e38", "metadata": {}, "source": [ "## Chapter 23. Jumping Back and Forth\n", "\n", "Jumps are control flow as data with patching.\n" ] }, { "cell_type": "code", "execution_count": 47, "id": "a8b8e027", "metadata": {}, "outputs": [], "source": [ "def ch23_patch_jumps() -> None:\n", " code = [(\"JMP_IF_FALSE\", None), (\"THEN\",), (\"JMP\", None), (\"ELSE\",), (\"HALT\",)]\n", " code[0] = (\"JMP_IF_FALSE\", 3)\n", " code[2] = (\"JMP\", 4)\n", " print(code)\n" ] }, { "cell_type": "code", "execution_count": 48, "id": "a1e102db", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[('JMP_IF_FALSE', 3), ('THEN',), ('JMP', 4), ('ELSE',), ('HALT',)]\n" ] } ], "source": [ "ch23_patch_jumps()\n" ] }, { "cell_type": "markdown", "id": "1cb2b095", "metadata": {}, "source": [ "## Chapter 24. Calls and Functions\n", "\n", "Calls require frames and return addresses.\n" ] }, { "cell_type": "code", "execution_count": 49, "id": "98dcd0f2", "metadata": {}, "outputs": [], "source": [ "def ch24_calls_frames() -> None:\n", " prog = [(\"CALL\", \"f\"), (\"PRINT\",), (\"HALT\",)]\n", " funcs = {\"f\": [(\"PUSH\", 3), (\"RET\",)]}\n", " stack, call, pc, code = [], [], 0, prog\n", " while True:\n", " op, *a = code[pc]; pc += 1\n", " if op == \"CALL\": call.append((code, pc)); code, pc = funcs[a[0]], 0\n", " elif op == \"PUSH\": stack.append(a[0])\n", " elif op == \"RET\": code, pc = call.pop()\n", " elif op == \"PRINT\": print(stack.pop())\n", " elif op == \"HALT\": break\n", " else: raise ValueError(op)\n" ] }, { "cell_type": "code", "execution_count": 50, "id": "9dcaee5d", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "3\n" ] } ], "source": [ "ch24_calls_frames()\n" ] }, { "cell_type": "markdown", "id": "fe7a1f3d", "metadata": {}, "source": [ "## Chapter 25. Closures\n", "\n", "Closures extend the lifetime of captured locals.\n" ] }, { "cell_type": "code", "execution_count": 51, "id": "b8830869", "metadata": {}, "outputs": [], "source": [ "def ch25_closures() -> None:\n", " class Cell:\n", " def __init__(self, value):\n", " self.value = value\n", "\n", " class Env(dict):\n", " def __init__(self, parent=None):\n", " super().__init__()\n", " self.parent = parent\n", "\n", " def lookup_binding(self, name):\n", " if name in self:\n", " return self[name]\n", " if self.parent is not None:\n", " return self.parent.lookup_binding(name)\n", " raise NameError(name)\n", "\n", " def read(binding):\n", " return binding.value if isinstance(binding, Cell) else binding\n", "\n", " def ev(e, env):\n", " match e:\n", " case (\"lit\", v):\n", " return v\n", " case (\"var\", n):\n", " return read(env.lookup_binding(n))\n", " case (\"set\", n, rhs):\n", " binding = env.lookup_binding(n)\n", " if not isinstance(binding, Cell):\n", " raise TypeError(f\"{n} is not assignable\")\n", " binding.value = ev(rhs, env)\n", " return binding.value\n", " case (\"+\", a, b):\n", " return ev(a, env) + ev(b, env)\n", " case (\"fun\", params, body):\n", " return (\"closure\", params, body, env)\n", " case (\"call\", fn, args):\n", " tag, params, body, closed = ev(fn, env)\n", " call_env = Env(closed)\n", " for p, a in zip(params, args):\n", " call_env[p] = Cell(ev(a, env))\n", " return ev(body, call_env)\n", " case (\"seq\", xs):\n", " v = None\n", " for x in xs:\n", " v = ev(x, env)\n", " return v\n", " case _:\n", " raise ValueError(e)\n", "\n", " def make_counter():\n", " activation = Env()\n", " activation[\"n\"] = Cell(0)\n", " return ev(\n", " (\"fun\", [], (\"seq\", [\n", " (\"set\", \"n\", (\"+\", (\"var\", \"n\"), (\"lit\", 1))),\n", " (\"var\", \"n\"),\n", " ])),\n", " activation,\n", " )\n", "\n", " env = Env()\n", " env[\"c\"] = make_counter()\n", " print(ev((\"call\", (\"var\", \"c\"), []), env), ev((\"call\", (\"var\", \"c\"), []), env))\n" ] }, { "cell_type": "code", "execution_count": 52, "id": "6a5fe2f8", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "1 2\n" ] } ], "source": [ "ch25_closures()\n" ] }, { "cell_type": "markdown", "id": "ba2e5e49", "metadata": {}, "source": [ "## Chapter 25. Loop Variable Capture\n", "\n", "Loop captures need snapshotting when you want value capture.\n" ] }, { "cell_type": "code", "execution_count": 53, "id": "d84c2077", "metadata": {}, "outputs": [], "source": [ "def ch25_loop_var() -> None:\n", " class Cell:\n", " def __init__(self, value):\n", " self.value = value\n", "\n", " shared = Cell(0)\n", " late = []\n", " for i in range(3):\n", " shared.value = i\n", " late.append(lambda cell=shared: cell.value)\n", "\n", " snap = []\n", " for i in range(3):\n", " cell = Cell(i)\n", " snap.append(lambda cell=cell: cell.value)\n", "\n", " print([f() for f in late], [f() for f in snap])\n" ] }, { "cell_type": "code", "execution_count": 54, "id": "b64128b0", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[2, 2, 2] [0, 1, 2]\n" ] } ], "source": [ "ch25_loop_var()\n" ] }, { "cell_type": "markdown", "id": "6f7d26a1", "metadata": {}, "source": [ "## Chapter 26. Garbage Collection\n", "\n", "Tracing GC defines reachability semantics.\n" ] }, { "cell_type": "code", "execution_count": 55, "id": "6688aea9", "metadata": {}, "outputs": [], "source": [ "def ch26_gc_tracing() -> None:\n", " heap, roots = {1: [2, 3], 2: [], 3: [2], 4: []}, [1]\n", " marked: set[int] = set()\n", " def mark(o: int) -> None:\n", " if o in marked: return\n", " marked.add(o)\n", " for r in heap.get(o, []): mark(r)\n", " for r in roots: mark(r)\n", " for o in list(heap):\n", " if o not in marked: del heap[o]\n", " print(sorted(heap))\n" ] }, { "cell_type": "code", "execution_count": 56, "id": "06bbda8a", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[1, 2, 3]\n" ] } ], "source": [ "ch26_gc_tracing()\n" ] }, { "cell_type": "markdown", "id": "52c4671a", "metadata": {}, "source": [ "## Chapter 27. Classes and Instances\n", "\n", "Instances carry fields and a pointer to behavior.\n" ] }, { "cell_type": "code", "execution_count": 57, "id": "4779f9bf", "metadata": {}, "outputs": [], "source": [ "def ch27_instances() -> None:\n", " def new(cls):\n", " return {\"class\": cls, \"fields\": {}}\n", "\n", " Point = {\n", " \"name\": \"Point\",\n", " \"super\": None,\n", " \"methods\": {\n", " \"norm2\": lambda this: this[\"fields\"][\"x\"] ** 2 + this[\"fields\"][\"y\"] ** 2,\n", " },\n", " }\n", "\n", " p = new(Point)\n", " p[\"fields\"][\"x\"] = 3\n", " p[\"fields\"][\"y\"] = 4\n", " print(p[\"class\"][\"methods\"][\"norm2\"](p))\n" ] }, { "cell_type": "code", "execution_count": 58, "id": "711336a2", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "25\n" ] } ], "source": [ "ch27_instances()\n" ] }, { "cell_type": "markdown", "id": "95ba1aa8", "metadata": {}, "source": [ "## Chapter 28. Methods and Initializers\n", "\n", "Initializers and binding shape object construction.\n" ] }, { "cell_type": "code", "execution_count": 59, "id": "18427d4f", "metadata": {}, "outputs": [], "source": [ "def ch28_init_bind() -> None:\n", " def bind(method, this):\n", " return lambda *args: method(this, *args)\n", "\n", " def new(cls, *args):\n", " obj = {\"class\": cls, \"fields\": {}}\n", " init = cls[\"methods\"].get(\"init\")\n", " if init is not None:\n", " bind(init, obj)(*args)\n", " return obj\n", "\n", " def getprop(obj, name):\n", " if name in obj[\"fields\"]:\n", " return obj[\"fields\"][name]\n", " return bind(obj[\"class\"][\"methods\"][name], obj)\n", "\n", " C = {\n", " \"name\": \"C\",\n", " \"super\": None,\n", " \"methods\": {\n", " \"init\": lambda this, x: this[\"fields\"].update({\"x\": x}),\n", " \"get\": lambda this: this[\"fields\"][\"x\"],\n", " },\n", " }\n", "\n", " o = new(C, 7)\n", " print(getprop(o, \"get\")())\n" ] }, { "cell_type": "code", "execution_count": 60, "id": "7590075d", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "7\n" ] } ], "source": [ "ch28_init_bind()\n" ] }, { "cell_type": "markdown", "id": "93cc5c22", "metadata": {}, "source": [ "## Chapter 29. Superclasses\n", "\n", "super starts lookup one link up the chain.\n" ] }, { "cell_type": "code", "execution_count": 61, "id": "aa0864a0", "metadata": {}, "outputs": [], "source": [ "def ch29_super_lookup() -> None:\n", " def lookup_method(cls, name):\n", " if name in cls[\"methods\"]:\n", " return cls[\"methods\"][name]\n", " if cls[\"super\"] is not None:\n", " return lookup_method(cls[\"super\"], name)\n", " raise KeyError(name)\n", "\n", " def bind(method, this):\n", " return lambda *args: method(this, *args)\n", "\n", " def new(cls):\n", " return {\"class\": cls, \"fields\": {}}\n", "\n", " A = {\n", " \"name\": \"A\",\n", " \"super\": None,\n", " \"methods\": {\n", " \"m\": lambda this: \"A\",\n", " },\n", " }\n", "\n", " B = {\n", " \"name\": \"B\",\n", " \"super\": A,\n", " \"methods\": {\n", " \"m\": lambda this: \"B->\" + lookup_method(B[\"super\"], \"m\")(this),\n", " },\n", " }\n", "\n", " b = new(B)\n", " print(bind(lookup_method(B, \"m\"), b)())\n" ] }, { "cell_type": "code", "execution_count": 62, "id": "57c5773d", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "B->A\n" ] } ], "source": [ "ch29_super_lookup()\n" ] }, { "cell_type": "markdown", "id": "96323933", "metadata": {}, "source": [ "## Chapter 30. Optimization\n", "\n", "Optimizations are semantics-preserving rewrites.\n" ] }, { "cell_type": "code", "execution_count": 63, "id": "26ae83df", "metadata": {}, "outputs": [], "source": [ "def ch30_optimize_fold() -> None:\n", " def ev(e):\n", " match e:\n", " case (\"lit\", v): return v\n", " case (\"+\", a, b): return ev(a) + ev(b)\n", " case (\"*\", a, b): return ev(a) * ev(b)\n", " case _: raise ValueError(e)\n", "\n", " def fold(e):\n", " match e:\n", " case (\"+\", a, b):\n", " a, b = fold(a), fold(b)\n", " return (\"lit\", ev((\"+\", a, b))) if a[0] == b[0] == \"lit\" else (\"+\", a, b)\n", " case (\"*\", a, b):\n", " a, b = fold(a), fold(b)\n", " return (\"lit\", ev((\"*\", a, b))) if a[0] == b[0] == \"lit\" else (\"*\", a, b)\n", " case _:\n", " return e\n", "\n", " expr = (\"+\", (\"lit\", 1), (\"*\", (\"lit\", 2), (\"lit\", 3)))\n", " folded = fold(expr)\n", " print(expr, \"=>\", folded, ev(expr), ev(folded))\n" ] }, { "cell_type": "code", "execution_count": 64, "id": "14f0e373", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "('+', ('lit', 1), ('*', ('lit', 2), ('lit', 3))) => ('lit', 7) 7 7\n" ] } ], "source": [ "ch30_optimize_fold()\n" ] }, { "cell_type": "markdown", "id": "5213f474", "metadata": {}, "source": [ "## End-to-End After III.A\n", "\n", "Compile the same AST program to bytecode and run it on a tiny stack VM. This keeps the same semantic target but moves the execution model into the VM world.\n" ] }, { "cell_type": "code", "execution_count": 65, "id": "1b057db8", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "110\n" ] } ], "source": [ "# Bytecode ops: CONST k, GET slot, SET slot, ADD, LT, JIF_FALSE addr, JMP addr, PRINT, HALT\n", "\n", "def compile_to_bytecode(prog):\n", " consts = []\n", " code = []\n", " slots = {} # name -> int\n", "\n", " def slot(name):\n", " if name not in slots: slots[name] = len(slots)\n", " return slots[name]\n", "\n", " def emit(*ins): code.append(tuple(ins)); return len(code) - 1\n", " def patch(at, target):\n", " op, _ = code[at]\n", " code[at] = (op, target)\n", "\n", " def cconst(v):\n", " consts.append(v)\n", " emit(\"CONST\", len(consts) - 1)\n", "\n", " def cexpr(e):\n", " match e:\n", " case (\"lit\", v): cconst(v)\n", " case (\"var\", n): emit(\"GET\", slot(n))\n", " case (\"+\", a, b): cexpr(a); cexpr(b); emit(\"ADD\")\n", " case (\"<\", a, b): cexpr(a); cexpr(b); emit(\"LT\")\n", " case _: raise ValueError(e)\n", "\n", " def cblock(block):\n", " for s in block: cstmt(s)\n", "\n", " def cstmt(s):\n", " match s:\n", " case (\"var\", n, e):\n", " cexpr(e); emit(\"SET\", slot(n))\n", " case (\"set\", n, e):\n", " cexpr(e); emit(\"SET\", slot(n))\n", " case (\"print\", e):\n", " cexpr(e); emit(\"PRINT\")\n", " case (\"if\", c, t, f):\n", " cexpr(c)\n", " jif = emit(\"JIF_FALSE\", None)\n", " cblock(t)\n", " jmp = emit(\"JMP\", None)\n", " patch(jif, len(code))\n", " cblock(f)\n", " patch(jmp, len(code))\n", " case (\"while\", c, b):\n", " loop_start = len(code)\n", " cexpr(c)\n", " jif = emit(\"JIF_FALSE\", None)\n", " cblock(b)\n", " emit(\"JMP\", loop_start)\n", " patch(jif, len(code))\n", " case _: raise ValueError(s)\n", "\n", " cblock(prog)\n", " emit(\"HALT\")\n", " return consts, code, slots\n", "\n", "def run_vm(consts, code, slots):\n", " stack = []\n", " globals_ = [None] * len(slots)\n", " ip = 0\n", "\n", " while True:\n", " op, *a = code[ip]; ip += 1\n", " if op == \"CONST\":\n", " stack.append(consts[a[0]])\n", " elif op == \"GET\":\n", " stack.append(globals_[a[0]])\n", " elif op == \"SET\":\n", " globals_[a[0]] = stack.pop()\n", " elif op == \"ADD\":\n", " b = stack.pop(); a0 = stack.pop()\n", " if type(a0) != type(b): raise TypeError(\"no mixed +\")\n", " stack.append(a0 + b)\n", " elif op == \"LT\":\n", " b = stack.pop(); a0 = stack.pop()\n", " stack.append(a0 < b)\n", " elif op == \"JIF_FALSE\":\n", " cond = stack.pop()\n", " if not cond: ip = a[0]\n", " elif op == \"JMP\":\n", " ip = a[0]\n", " elif op == \"PRINT\":\n", " print(stack.pop())\n", " elif op == \"HALT\":\n", " return\n", " else:\n", " raise ValueError(op)\n", "\n", "consts, code, slots = compile_to_bytecode(DEMO_PROG)\n", "run_vm(consts, code, slots) # expected: 110\n" ] } ], "metadata": { "kernelspec": { "display_name": ".venv", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.13.2" } }, "nbformat": 4, "nbformat_minor": 5 }