SCM023

A hand-crafted Scheme engine featuring a bytecode compiler and virtual machine.

SCM023 is a from-scratch Scheme implementation built to learn more about compiler and interpreter engineering, and to build performance-critical software - a bytecode compiler, a tail-call-dispatch virtual machine, first-class continuations, and a self-hosted bootstrap layer written in Scheme itself.

Note

SCM023 is not fully standard-compliant and is still missing many standard library features. Development has been targeting R3RS as the closest reference standard. See Current limitations below.

Features

Special forms: and, or, quote, quasiquote, unquote, unquote-splicing, define, lambda, begin, cond, else, if, set!, let, letrec, let*, delay

Some of these support multiple valid forms - define, let, lambda, if, and cond in particular each accept more than one shape.

Notable procedures: load, call/cc, force, apply

Architecture

SCM023 compiles source directly to bytecode ahead of execution - there's no tree-walking step at runtime. The pipeline looks like this:

Memory-mapped source file → Lexer → CstGen → AstGen → Compiler → Vm

• Lexer tokenizes the memory-mapped source file.
• CstGen builds a concrete syntax tree from the token stream.
• AstGen lowers the CST into an abstract syntax tree.
• Compiler walks the AST and produces bytecode.

The compiler is recursive: each procedure gets its own SubCompiler, which can itself spawn further SubCompilers for nested procedures. Each SubCompiler builds a control-flow graph (CFG) for its procedure, which is then lowered into a procedure prototype (the actual bytecode) by CodeGen.

Once compiled, the root procedure prototype is handed to the Vm, which enters its evaluation loop and runs the program.

Dispatch design

Both the Lexer and the Vm use tail-call dispatch rather than a central dispatch loop (such as a while wrapping a switch). Each token handler / opcode handler tail-calls directly into the next one. This avoids a single large indirect branch that the CPU's branch predictor has to reason about on every iteration, and instead spreads dispatch across many smaller, more predictable indirect jumps - improving branch prediction and reducing dispatch overhead in the hot loop.

Bytecode format

Each bytecode instruction is a fixed 2 bytes, packed as tightly as possible so more instructions fit per cache line. Combined with the tail-call VM design, this keeps the hot execution path small and cache-friendly.

The VM also performs tail-call optimization at the bytecode level - a Scheme tail call compiles to a tail-call instruction that reuses the current call frame rather than growing the stack, so tail-recursive Scheme code runs in constant stack space.

(disassemble <procedure>)

SCM023 exposes a disassemble procedure - specific to this runtime - for inspecting the compiled bytecode of any procedure:

>>> (disassemble call-with-input-file)
Disassembly of procedure at 0x79c609e00340:
  0000 (push-local 0)
  0002 (push-global 39)
  0004 (call 1)
  0006 (set-local! 2)
  0008 (push-local 2)
  000a (push-local 1)
  000c (call-void 1)
  000e (push-local 2)
  0010 (push-global 41)
  0012 (tail-call 1)

Note the final instruction: tail-call rather than call, reflecting that call-with-input-file's last operation is in tail position.

Compiler optimizations

The compiler currently performs minimal optimization, notably unreachable code elimination on the CFG. Constant folding is deliberately not performed, for a couple of reasons:

1. SCM023 supports an incremental compiler that works across REPL invocations, so "constants" from a prior compilation unit aren't necessarily fixed for all future ones.
2. In Scheme, arithmetic operators like + are ordinary procedures, not syntax - they can be redefined or shadowed at runtime. It's therefore unsafe to assume that + in source code will still mean + by the time that code actually runs.

Bootstrapping

The core of the runtime is implemented in C++. Some builtins are native functions written directly in C++; others are assembled by combining native functions to bootstrap the rest of the standard library in Scheme itself. The REPL itself is implemented in SCM023's own Scheme.

Value representation

SCM023 uses a fairly typical NaN-boxing scheme: every value is packed into a single 8-byte word. Numbers (64-bit floats), booleans, the null value, EOF, an internal unbound sentinel, characters, native function pointers, and GC-managed pointers all fit into this one 8-byte representation. This keeps every stack value the same size regardless of type.

Garbage collection

SCM023 uses a copying garbage collector, currently single-generation. A copying collector was chosen for a few reasons:

Scheme (and functional languages generally) allocate heavily and briefly. Most Scheme code generates a large volume of short-lived objects - cons cells, closures, intermediate values - so an allocator optimized for fast, frequent allocation matters more here than in a typical imperative language.

Virtual-memory-arena infrastructure was already in place. The compiler already relies on an arena-centric architecture built on virtual memory, and a copying collector was a natural fit to reuse that same infrastructure - bump-pointer allocation into a reserved region is both simple and very fast, which lines up well with the allocation pattern above.

Copying collectors don't scan garbage at all. Since collection works by tracing and relocating only the live set into a fresh space, the cost of a collection scales with how much data survives, not with how much garbage exists. For a language producing lots of short-lived garbage, this is a good match - dead objects are simply never visited or copied.

Examples

A quick tour of each special form and notable procedure, shown as REPL interactions.

quote

>>> (quote (1 2 3))
$1 = (1 2 3)
>>> '(a b c)
$2 = (a b c)

quasiquote, unquote, unquote-splicing

>>> (quasiquote (1 (unquote (+ 1 1)) (unquote-splicing (list 3 4))))
$1 = (1 2 3 4)
>>> `(1 ,(+ 1 1) ,@(list 3 4))
$2 = (1 2 3 4)

and / or

>>> (and 1 2 3)
$1 = 3
>>> (and 1 #f 3)
$2 = #f
>>> (or #f #f 5)
$3 = 5

if

>>> (if (> 3 2) 'yes 'no)
$1 = yes

cond / else

>>> (cond ((= 1 2) 'a)
          ((= 1 1) 'b)
          (else 'c))
$1 = b

define

>>> (define x 10)
$1 = ()
>>> x
$2 = 10
>>> (define (square n) (* n n))
$3 = ()
>>> (square 5)
$4 = 25
>>> (define (add . args) (apply + args))
$5 = ()
>>> (add 1 2 3 4)
$6 = 10

lambda

>>> ((lambda (x y) (+ x y)) 3 4)
$1 = 7
>>> (define add (lambda args (apply + args)))
$2 = ()
>>> (add 1 2 3 4)
$3 = 10
>>> (define my-apply (lambda (proc . args) (apply proc args)))
$4 = ()
>>> (my-apply + 1 2 3 4)
$5 = 10

begin

>>> (begin (display "computing... ") (+ 1 2))
computing... $1 = 3

set!

>>> (define counter 0)
$1 = ()
>>> (set! counter (+ counter 1))
$2 = ()
>>> counter
$3 = 1

let

>>> (let ((x 1) (y 2)) (+ x y))
$1 = 3

let*

>>> (let* ((x 1) (y (+ x 1))) (+ x y))
$1 = 3

letrec

>>> (letrec ((even? (lambda (n) (if (zero? n) #t (odd? (- n 1)))))
             (odd?  (lambda (n) (if (zero? n) #f (even? (- n 1))))))
      (even? 10))
$1 = #t

delay / force

>>> (define p (delay (begin (display "evaluated! ") (+ 1 2))))
$1 = ()
>>> (force p)
evaluated! $2 = 3
>>> (force p)
$3 = 3

Note the second force doesn't re-evaluate - the promise's value is memoized after the first force.

load

>>> (load "examples/data-example.scm")

call/cc

>>> (call/cc (lambda (k) (+ 1 (k 42))))
$1 = 42

Implementation note: call/cc is implemented via stack copying rather than a heap-allocated call stack. This makes invoking a continuation relatively expensive, but it was a deliberate trade-off - it keeps regular (non-continuation) calls fast, since the VM's call stack stays a native-like, contiguous stack rather than a chain of heap-allocated frames that every call would have to pay for.

apply

>>> (apply / '(4 2))
$1 = 2

Running

SCM023 is a command-line application. The CWD (current-working-directory) must be the in the root of the released folder structure. If working off the repository directly, the CWD must be the root of the repository.

Usage

If you want to execute a source file directly:

./scm023 examples/data-example.scm

If you want to enter the REPL:

./scm023

Building

Building is a standard CMake workflow:

git clone https://github.com/connellr023/scm023
cd scm023
CXX=clang++ cmake -B build -DCMAKE_BUILD_TYPE=Release
cmake --build build

Final application bundling is done with CPack:

cpack --config build/CPackConfig.cmake

Supported platforms:

• Linux
• MacOS
• Windows

Supported compilers:

• GCC >= 16
• Clang >= 20

Performance

SCM023 is tuned to be lightweight, not just functionally complete:

• Cold start (including runtime bootstrapping): <10ms
• Idle memory footprint: hundreds of KB

Current limitations

SCM023 is not fully standard-compliant, and targets R3RS as the closest reference standard rather than fully implementing any single revision. Standard library coverage is partial - many common procedures aren't implemented yet.

License

Free software under the Apache 2.0 License.

Copyright (C) 2026, connellr023@github