How does a compiler compile itself?

Folio, the language I launched yesterday, has a compiler written in Folio. Here's how it works, in seven short parts.

1. It's 71,287 lines of Folio

folio.exe is built from machine.folio (51,159 lines: the native compiler and its runtime), folio.folio (7,988: the command line), compiler.folio (5,457: the front end) and 8 smaller files.

2. The front end: words, a tree, names

compiler.folio turns source into tokens, parses them into a tree by recursive descent, and works out what every name means. It's held to Folio's JavaScript engine byte for byte, so a program means the same thing, and fails with the same message, on every Folio engine.

3. An assembler of its own

machine.folio writes x86-64 itself: one Folio function per instruction, a ModRM encoder, labels, and jumps filled in once everything has its place. Folio's + becomes addsd, the bytes F2 0F 58 C1.

4. Every value is 8 bytes

A number is just its double. Text, lists and records are NaNs that arithmetic never makes: the top 16 bits say what kind it is (0xFFF9 is text) and the low 48 bits say where it lives. So a + b is one addsd and one check for NaN.

5. The whole file, byte by byte

No assembler, no linker. machine.folio writes the PE32+ header for Windows (MZ, PE, x86-64) or an ELF file for Linux, and the runtime that goes in it: a conservative garbage collector, text, dictionaries, and numbers shown exactly as JavaScript shows them.

6. The chicken and the egg

The first folio.exe has to come from somewhere. node bootstrap.mjs runs machine.folio on Folio's JavaScript engine, once. From then on, Folio builds Folio.

7. The proof: a fixed point

folio.exe compiles its own source into exactly its own bytes. Yesterday's 1.12 release rebuilt itself in 8.9 s into the same 32,392,192 bytes, the same SHA-256, and the Linux and Windows builds build each other byte for byte. The release workflow checks this on every release.

The design notes behind all of it (DESIGN.md, sections 13 and 25) and the source: github.com/samyyy2423/folio

There's a one-minute video version on LinkedIn.