zscheme

A high-performance Scheme implementation written in Zig, designed for embedding in applications.

Features

• Fast register-based bytecode VM with tagged pointer value representation (61-bit fixnums, headerless 16-byte cons cells)
• AOT compiler — Scheme to Zig to native code via LLVM. Competitive with Chez Scheme.
• R5RS compliant (259/259 tests passing, interpreter AND AOT)
• R7RS-small support (802/811 — the remaining 9 are documented non-goals: rational literals and one libm ULP)
• Hygienic macros via syntax-rules with full ellipsis support
• First-class continuations (call/cc, dynamic-wind)
• Proper tail calls as required by the Scheme standard
• Full Unicode character classification and case conversion (via zg)
• Generational mark-sweep GC with typed arenas (pairs, floats, closures) and shadow stack for AOT code
• Native value types for zero-boxing embedding (custom types compile to stack-allocated Zig structs in AOT)
• Source-level debugger — breakpoints, stepping (into/over/out), stack traces, frame locals, eval-in-frame; designed for DAP integration in host editors, zero overhead when inactive (-Ddebugger gate)
• #doc reader extension — attach docstrings to defined functions, queryable at runtime via (zscheme meta)
• Embeddable with clean Zig API — selective library loading for sandboxing
• Standalone REPL and script execution

Building

Requires Zig 0.16 or later.

# Debug build
zig build
# Release build (optimized)
zig build -Doptimize=ReleaseFast
# Run tests
zig build test

Dev tools (optional)

simgrep (code-duplication search) and zigmap (codemap generator) are useful while hacking on zscheme. They are tools, not project dependencies — bootstrap them once with:

scripts/setup-tools.sh # clone (if missing) and build both
scripts/setup-tools.sh -u # also `git pull --ff-only` first

This drops simgrep/ and zigmap/ at the project root.

Usage

REPL

./zig-out/bin/zscheme

> (define (fib n)
 (if (< n 2) n (+ (fib (- n 1)) (fib (- n 2)))))
> (fib 10)
55
> (map (lambda (x) (* x x)) '(1 2 3 4 5))
(1 4 9 16 25)

Running Scripts

./zig-out/bin/zscheme script.scm [args...]

Command-line arguments after the script name are available in *args* as a list of strings.

AOT Compilation

Compile Scheme to native code via Zig:

# Generate Zig source
./zig-out/bin/zscheme --emit-zig program.scm > generated.zig
# Build as standalone binary
zig build-exe generated.zig --dep zscheme -Mzscheme=src/root.zig

The AOT compiler passes the same R7RS suite as the interpreter (802/811) — the two execution modes are gated to agree byte-for-byte on a differential corpus. Unsupported forms (call/cc in non-escape position, dynamic-wind, guard, case-lambda) fall back to embedded bytecode automatically. Optimizations include whole-program type inference (scalar and vector-element types via a union-find constraint solver), unboxed fixnum/float fast paths with exactness-preserving dispatch, native mutual recursion, cons-recursive optimization, CPS defunctionalization, and module-level global caching.

See examples/callback/ for a full embedding example with VM, mixed, and pure-AOT build modes.

Performance

Benchmarked on Apple M1 Pro using the R7RS benchmark suite. All benchmarks use identical algorithms and iteration counts.

AOT Compiler vs Chez Scheme

The AOT backend compiles Scheme to Zig, then to native code via LLVM. 27 benchmarks from the R7RS suite.

Geometric mean: 0.78x (AOT/Chez, <1.0 = AOT faster). AOT wins 13 of 27 benchmarks. Chez Scheme (--optimize-level 2) is a mature native-code compiler with decades of development; beating it on geomean is a strong result.

Float-heavy benchmarks (sumfp, mbrot, fibfp) benefit from unboxed f64 fast paths. Integer-heavy benchmarks (fib, tak, ack) benefit from zero-cost fixnum arithmetic (tag 000).

VM Interpreter vs Lua 5.4

zscheme wins 14 of 16 benchmarks, geometric mean 0.39x (2.5x faster). zscheme excels on list-heavy code (7-11x faster on destruc, diviter, divrec, primes) thanks to dedicated pair arenas with headerless 16-byte cons cells.

AOT vs VM

The AOT compiler provides 13x geometric mean speedup over the bytecode interpreter (20 benchmarks), with individual speedups ranging from 4.3x (destruc) to 54.4x (cpstak).

See bench/HISTORY.md for full optimization history.

Embedding

zscheme is designed as an embeddable library. Add it as a Zig dependency, pick only the libraries you need, and optionally extend it with custom Scheme or Zig code.

Minimal setup

conststd=@import("std");constzs=@import("zscheme");// Construct an Io handle once and pass it to Memory.varthreaded:std.Io.Threaded=.init(allocator,.{});deferthreaded.deinit();constio=threaded.io();varmem=zs.Memory.init(allocator,io);defermem.deinit();varvm=zs.Vm.init(&mem);defervm.deinit();// Register only the libraries you need (sandboxed — no file I/O, no eval)tryvm.registerLibrary(zs.lib.scheme.base.library);tryvm.registerLibrary(zs.lib.scheme.write.library);// Or register everything: try zs.registerAll(&vm);constresult=tryvm.interpret("(+ 1 2 3)");std.debug.print("{}\n",.{result.asFixnum().?});// 6

Native Zig primitives

Register Zig functions as Scheme primitives:

fnprim_timestamp(vm_ptr:*anyopaque,args:[]constzs.Value)anyerror!zs.Value{if(args.len!=0)returnerror.ArityError;constmem=zs.Vm.getMemory(vm_ptr);constts=std.Io.Clock.now(.real,mem.io);constns:i64=@intCast(ts.nanoseconds);returnzs.Value.makeFixnum(ns)orelseerror.Overflow;}constclosure=trymem.makeNativeClosure(&prim_timestamp);tryvm.defineGlobal("timestamp-ns",closure);

Calling Scheme from Zig

_=tryvm.interpret("(define (double x) (* x 2))");constdouble=vm.globals.get("double").?;constresult=tryvm.callAndRun(double,&.{zs.Value.makeFixnum(21).?});std.debug.print("{}\n",.{result.asFixnum().?});// 42

Native value types

Register custom value types that work seamlessly in both the VM interpreter and AOT compiler.

VM path — values are heap-allocated and GC-managed, accessed via nativeData():

constVec2=struct{x:f32,y:f32};fnprim_make_vec2(vm_ptr:*anyopaque,args:[]constzs.Value)anyerror!zs.Value{constx:f32=@floatCast(zs.runtime.toF64(args[0]));consty:f32=@floatCast(zs.runtime.toF64(args[1]));constv=Vec2{.x=x,.y=y};returnzs.Vm.getMemory(vm_ptr).makeNativeValue(0,std.mem.asBytes(&v));}fnprim_vec2_x(vm_ptr:*anyopaque,args:[]constzs.Value)anyerror!zs.Value{constdata=args[0].nativeData(Vec2,0)orelsereturnerror.TypeError;returnzs.Vm.getMemory(vm_ptr).makeFloat(@floatCast(data.x));}

Operator overloading — register operators so +, -, *, / work with native types:

mem.registerNativeOps(0,.{.add=&prim_vec2_add,// (+ vec2 vec2) → vec2.mul=&prim_vec2_scale,// (* vec2 scalar) → vec2.format=&formatVec2,// (display vec2) → "#<vec2 3.0 4.0>"});

(define v (+ (make-vec2 1.0 2.0) (make-vec2 3.0 4.0)))
(display v) ; → #<vec2 4.0 6.0>
(vec2-x (* v 2.0)) ; → 8.0

AOT path — the same Scheme code compiles to direct Zig function calls with zero boxing. The codegen reads a .zon descriptor file that lists each type's Zig name, size, and function signatures:

// engine.zon — passed to `zscheme --emit-zig --native-types=engine.zon`.{.module="engine",// generated code does `@import("engine")`.types=.{.{.name="vec2",.zig_type_name="Vec2",.size=8,.functions=.{.{.scheme_name="make-vec2",.zig_name="makeVec2",.params=.{.f64_t,.f64_t},.ret=.{.custom=0}},.{.scheme_name="vec2-x",.zig_name="vec2X",.params=.{.{.custom=0}},.ret=.f64_t},.{.scheme_name="vec2-add",.zig_name="vec2Add",.params=.{.{.custom=0},.{.custom=0}},.ret=.{.custom=0},.overloads=.add},},},},}

;; AOT: compiles to native.vec2X(native.vec2Add(a, b)) — zero boxing, zero GC
(define (sum-x a b) (vec2-x (+ a b)))

The companion engine.zig file provides the Zig types and functions, plus mechanical pack_T / unpack_T boundary helpers (~12 lines per type).

See examples/native-types/ for a full runnable example — zig build native-types-example builds and runs it.

Custom Scheme libraries

Embed Scheme source files as proper R7RS libraries:

_=tryvm.interpret(@embedFile("math.scm"));_=tryvm.interpret(@embedFile("app.scm"));

;; math.scm
(define-library (example math)
 (import (scheme base))
 (export square factorial)
 (begin
 (define (square x) (* x x))
 (define (factorial n)
 (if (<= n 1) 1 (* n (factorial (- n 1)))))))

Available libraries

Docstrings with #doc

The #doc reader extension attaches documentation to exported functions. Docstrings are stored in the library table at compile time and queryable at runtime via (zscheme meta):

(define-library (example math)
 (import (scheme base))
 (export square)
 (begin
 (define (square x)
 #doc "Return the square of x."
 (* x x))))
(import (example math) (zscheme meta))
(symbol-doc '(example math) 'square) ; → "Return the square of x."
(symbol-doc '(example math) 'nonexistent) ; → #f

Docstrings are dropped from bytecode — functions behave identically at runtime.

Omitting a library means its functionality is unavailable — useful for sandboxing untrusted code. Only scheme.base is required for basic operation.

A full working example with VM, mixed, and pure-AOT build modes is in examples/callback/.

What's Implemented

R5RS (complete)

• All special forms: lambda, if, set!, cond, case, and, or, let, let*, letrec, begin, do, delay, quasiquote
• syntax-rules macros with hygiene
• call/cc and dynamic-wind
• eval with scheme-report-environment
• All standard procedures (~170 primitives)

R7RS-small (mostly complete)

• define-library and module system with import modifiers
• guard exception handling with with-exception-handler, raise, error
• define-record-type
• let-values, let*-values, letrec*
• case-lambda
• let-syntax, letrec-syntax
• Bytevector operations and bytevector ports
• Full Unicode character classification and case conversion
• Vector quasiquote (`#(,x ,@xs))
• Multiple return values (values, call-with-values)
• String and file ports

Not Yet Implemented

• Rational numbers (1/2, 10/2 literals, exact division)
• Bignums (integers limited to 61 bits)
• Complex numbers
• make-parameter / parameterize
• delay-force (iterative forcing)
• define-values
• syntax-case
• Datum labels (#0=, #0#)

License

MIT License. See LICENSE for details.