Scheme in the Browser: Bringing Bob to WebAssembly

Bob, a long-running suite of Scheme implementations in Python, has just gained a new backend. The project, which began as an experiment to understand CPython-style bytecode VMs, now includes a compiler that lowers Scheme expressions directly to WebAssembly text. The new code path produces standard WASM binaries that run with existing tooling, with no separate interpreter or VM layer in the output.

The motivation was twofold: to test how a language with a real runtime—closures, garbage collection, and built-in data structures—survives lowering to WASM, and to get hands-on experience with the WASM GC extension in a non-trivial setting.

Representing Scheme Objects with WASM GC

The key design decision is how to represent Scheme values in WASM's type system. By wrapping all values in refs, the WASM runtime handles memory management automatically, removing the need for a custom garbage collector in the compiled output. The core type declarations used by Bob's wasm compiler are:

;; PAIR holds the car and cdr of a cons cell.
(type $PAIR (struct (field (mut (ref null eq))) (field (mut (ref null eq)))))

;; BOOL represents a Scheme boolean. zero -> false, nonzero -> true.
(type $BOOL (struct (field i32)))

;; SYMBOL represents a Scheme symbol. It holds an offset in linear memory
;; and the length of the symbol name.
(type $SYMBOL (struct (field i32) (field i32)))

The $PAIR type is notable because it can hold any object in either field, using a nullable reference with identity semantics. Runtime type checks are done with ref.test, which inspects the actual type behind a reference.

i31 is a clever alternative to explicit boxing for numbers. It represents a reference to an integer without heap allocation, distinguishing itself from real references with a single bit. This avoids a separate type declaration for numeric values.

The $SYMBOL type stores two numbers, which reflects a limitation of WASM: there is no built-in string type. The compiler emits all string literals and symbol names into linear memory at fixed offsets, tracking the offset and length pair for each. This layout also enables straightforward string interning, so repeated symbols are only emitted once. For a snippet like:

(write '(10 20 foo bar))

The compiler places the strings "foo" and "bar" into linear memory like so:

(data (i32.const 2048) "foo")
(data (i32.const 2051) "bar")

Code that constructs a constant list for write then references these memory locations directly. An emitted record points at address 2051 with length 3—the symbol bar, found in the middle of the generated instructions:

(struct.new $SYMBOL (i32.const 2051) (i32.const 3))

Implementing write in Raw WASM

A harder problem was implementing the write builtin, which prints recursive representations of arbitrary Scheme values, including nested lists and symbols. Two tempting shortcuts were rejected: delegating to the host runtime is impractical because WASM GC references are opaque to the outside, and writing the routine in another language (like C) before lowering to WASM fails because that language would not have a natural way to manipulate WASM GC objects.

The solution was to write write directly in WASM text, assisted by AI for some of the routine parts. Only two host functions are imported:

(import "env" "write_char" (func $write_char (param i32)))
(import "env" "write_i32" (func $write_i32 (param i32)))

One imports convert an integer to a string; the other prints a single character. Everything else, including the traversal and formatting logic, lives in the WASM module itself. For example, emitting booleans in their canonical #t/#f notation is done by checking the value and then writing the appropriate characters:

(func $emit_bool (param $b (ref $BOOL))
    (call $emit (i32.const 35)) ;; '#'
    (if (i32.eqz (struct.get $BOOL 0 (local.get $b)))
        (then (call $emit (i32.const 102))) ;; 'f'
        (else (call $emit (i32.const 116))) ;; 't'
    )
)

Project Structure and Takeaways

The full WASM compiler, WasmCompiler in bob/wasmcompiler.py, is a little over 1000 lines of Python. More than half of that count is actually embedded WASM text implementing the built-in types and functions a minimal Scheme needs, not lowering logic. The rest is a well-documented translation layer from parsed Scheme expressions to WASM instructions.

The project is a realistic example of compiling a high-level, garbage-collected language to WASM, and it demonstrates how the GC extension relieves the compiler writer from manual memory management. It also shows the practical trade-offs: string handling requires manual linear-memory management, and host interoperability is limited by the opacity of WASM GC references. For anyone curious about the limits and affordances of the current WASM toolchain, the WasmCompiler source is a good starting point.