The Compiler

#42: the compiler itself. CC0.

The 42nd CC0 demo is the compiler itself. .ax compiles .ax to WebAssembly. The compiler that built demos #1 through #41 is itself public domain. The ouroboros eats its tail.

The Ouroboros

Self-Compilation (PROVED)
.ax source code is compiled to WebAssembly by a compiler written in .ax. The compiler compiles itself, reaching a fixed point: the output of compiling the compiler with itself is byte-for-byte identical to the compiler. deep_ouroboros.wasm = ~310KB. Zero external dependencies.
~310KB
Total compiler size
tokenizer.ax (288L) + parser.ax (628L) + wasm_emit.ax (~4700L). One WASM file.
Fixed point
Self-identical compilation
Compiler compiles itself. Output = input. The loop closes.
Zero JS
WASI toolchain
wasmtime runs the compiler. No node. No npm. No webpack. Pure WASM.
3 ops
meet(*), complement(~), add(+)
The entire language is built from 3 operations on a ring.

The Pipeline

.ax source flows through 4 stages, each written in .ax:

tokenizer.ax
288 lines
Characters to tokens. charCode dispatch, zero allocation.
parser.ax
628 lines
Tokens to AST. Recursive descent, 27 node types.
wasm_emit.ax
~4700 lines
AST to WASM binary. 9 analysis passes.
evaluator.ax
~1070 lines
Runtime interpreter. REPL, meta-eval, ouroboros.

Source-level include directive expands files before tokenization. Test prelude dissolves boilerplate: one line replaces twelve.

The compiler has 9 analysis passes. Each pass tightens type information.

The Cunningham Filtration

Cunningham Filtration (PROVED)
Twin Cunningham map c(x) = 2x + 1 from seeds {1, 2} generates {1, 2, 3, 5, 7, 11} -- the first six chain elements. Two closure conditions complete the rest: 2^2 + 3^2 = 13, and 2 + 3 + 5 + 7 = 17. 17 is the unique prime p > 13 satisfying finality (5*7 = 1 mod p), Fermat (phi(p) = 2^4 = 16), and chain sum (2+3+5+7 = p).
c(1) = 3
Chain from 1
1 -> 3 -> 7 -> 15 (composite). Generates 3, 7.
c(2) = 5
Chain from 2
2 -> 5 -> 11 -> 23 -> 47 -> 95. Generates 5, 11.
13 = 2^2+3^2
Sum of squares
Sum of squares of the first two chain primes.
17 = 2+3+5+7
Chain sum
5*7 = 1 mod 17. phi(17) = 16 = 2^4.

Twin Cunningham chains from just two seeds produce six primes. Two closure conditions complete the seven. The compiler that compiles itself is built on the chain that generates itself.

Seed (try 1 or 2):

Try It: Live .ax Compiler

Type .ax code below. The evaluator (itself written in .ax, compiled to WASM) executes it in your browser:

let f = fn(x) = x * x in f(42)

The Ouroboros Test

Three levels of self-reference. L1: arithmetic. L2: function definition. L3: the evaluator evaluates itself evaluating code. The snake eats its own tail.

See it live: the REPL at /repl interprets .ax using the evaluator, and Try It above does the same.

Self-Hosting Compilers: CRT vs Proprietary

SizeGCC: 15M+ lines. LLVM: 30M+ lines. V8: 4M+ lines.deep_ouroboros.wasm: ~310KB. ~5600 lines of .ax. One file.Dependenciesnpm install: 200+ packages. cmake: 50+ deps.Zero. .ax compiles .ax. No package manager.Self-hostingGCC compiles itself (multi-stage bootstrap).ax compiles itself to WASM. Fixed point in 1 generation.RuntimeNode.js: 70MB. Python: 30MB.wasmtime: 40MB. Or any browser. WASM is universal.LicenseGPL (GCC), Apache (LLVM), BSD (V8)CC0. Public domain. No license. No restrictions. Forever.CostMSVC: Visual Studio license. Xcode: Apple hardware.$0. Runs in any browser. Runs under wasmtime. Runs anywhere.

Source code · Public domain (CC0)

Report issue

.ax source compiled to WASM via self-hosting compiler. Zero HTML authored.