Compilers, How They Work, And Writing Them From Scratch

Source: Compilers, How They Work, And Writing Them From Scratch, Adam McDaniel (kiwi), 23:53, uploaded 2024-06-01, category Other / Unclear, playlist index 547.

Adam McDaniel begins with four questions: how computers compute, how programming languages work inside, how to create a language, and how to design an elegant compiler. He answers them by moving through two virtual machines and then through Sage, a compiler and language he has worked on since high school. The route runs from eight symbols and a tape of small integers to an operating system, a PowerPoint app, and AES encryption running in a browser.

From human source code to machine instructions

McDaniel describes a compiler as a program that transforms source code into machine code. A parser reads the source, an intermediate representation gives the program a more manageable form, and a code generator produces the target instructions. The familiar language is designed around human abstractions. Machine code consists of binary instructions that a processor can execute directly.

He explains the gap through a caveman. The programmer writes a novel in a language with a large vocabulary and flexible grammar. The computer understands a small set of grunts and gestures. A direct translation would force the compiler to map every comfortable human construction straight into a primitive machine operation, which would make the compiler hard to build and harder to reason about. An intermediate language reduces the distance in stages. Translating English into a small language with simpler grammar is easier before translating that language into the caveman’s gestures.

The first machine has two parts in its brain: a list of numbers and a pointer to the one number under consideration. Each cell holds a value from 0 to 255, with arithmetic wrapping around at either end. Eight symbols provide the whole vocabulary. Addition and subtraction change the current value. Angle brackets move the pointer. A dot prints the current value, and a comma replaces it with an input value. Square brackets repeat a block whilst the current value remains non-zero.

The demonstration adds the first two numbers in the list and prints the result. McDaniel says that this machine is Turing complete, so it can perform any computable task in principle, including piloting a rocket to the Moon. Its practical limits arrive quickly. Adding larger numbers takes longer, even though a modern computer can operate on a 64-bit value in one instruction. The machine has no functions for reusable subroutines and no way to call specialised operations supplied by another machine. It can compute, although its small vocabulary makes ordinary software unpleasant.

The Sage virtual machine

The second machine keeps the tape-based model and adds the parts needed for real programs. McDaniel calls it the Sage virtual machine. Its main memory stores 64-bit values. A smaller register or accumulator provides short-term working space. Extra bookkeeping tracks movement around the tape, and a call stack records where execution should return after a function call.

The Sage VM can set register values, move by several cells, load memory into the register, and store register values back into memory. DF treats the current memory value as a new pointer, whilst refer reverses that jump. offset and index let programs work with pointer values without depending on the VM’s private representation of a pointer. McDaniel connects these operations to familiar memory functions such as malloc and free.

Arithmetic works element by element across the register and main memory. Add, subtract, multiply, and divide leave the main memory unchanged. Negation and a test for non-negative values supply more basic operations. Function, call, and return instructions provide subroutines. while, if, else, and end provide loops and branches. The video passes over bitwise arithmetic, Boolean logic, and floating-point instructions because they follow the same pattern.

The richer machine supports high-level features such as algebraic data types, pattern matching, and polymorphic functions. McDaniel has used it to implement a shell, a PowerPoint application, and AES encryption and decryption. It also produces portable code that can later be mapped onto real processors. This is the first important separation in the video: a virtual machine can give a language a stable target whilst another compiler handles the hardware-specific work.

A ladder of intermediate representations

Sage VM code remains simpler than a high-level language, so a second compiler can translate it into x86-64 assembly. McDaniel shows equivalent Sage VM and x86-64 programs. The assembly is longer, yet each Sage instruction expands to roughly three to five x86-64 instructions. The translation stays local enough to inspect.

The high-level source does not go straight to the VM. The Sage compiler first parses the input, lowers it into Sage assembly, which McDaniel calls Sage IR, and then lowers the IR into Sage VM code. The final step can target x86-64 assembly or another machine language. Each representation removes some human convenience and leaves a smaller problem for the next stage.

Sage IR adds global variables, automatic tape allocation, a stack for function arguments and local variables, and a frame pointer for managing stack frames. General-purpose registers provide temporary space without repeated stack operations. Named functions and foreign-function calls give the IR a usable interface to the outside world. Instructions such as “load effective address” make it easier to calculate the address of a local variable before the compiler reduces the operation to the VM’s smaller vocabulary.

The resulting Sage VM code is difficult to read. McDaniel uses that awkwardness to show how much work the IR performs on behalf of the programmer. User-visible registers and internal registers map to special tape locations. Stack operations and global variables become tape manipulation that the high-level program never has to see. The same property makes the VM a possible platform for obfuscated machine code because reverse engineering the original structure becomes difficult.

An example language feature makes the difference clear. A small Sage program defines an Option type with an unwrap method. The method throws an error for an empty value and returns the contained value otherwise. The main function creates an option containing 5, unwraps it, and prints the result. The Sage IR is longer than the source, yet its stack operations and branches remain legible. The VM version has already discarded most of that shape.

Variables, structures, and generic lists

McDaniel then follows ordinary values through the IR. A function that assigns 5 to x pushes the constant onto the stack, pushes the value for the variable, prints it, tears down the stack frame, and exits. In the outer scope, the compiler stores the function pointer in a register before calling it. The compiler mangles the function name, although this example contains only one function to identify.

Structures expose the compiler’s memory rules. A Position contains integer fields x and y. A Vector contains two Position fields, start and end. The compiler allocates fields in alphabetical order and stores them consecutively without padding or alignment. The two positions are pushed together, with the end position stored before the start because the compiler follows that field order. The IR ends up shorter than the source because the type declarations carry enough information for the compiler to lay out the values.

The generic linked list shows tagged values and pointers. A list is either nil or cons; a cons value contains a pointer to the next element and a value of type T. Each list value occupies three cells because the largest variant needs two fields and one cell stores the tag. The empty list receives tag 1, whilst cons receives tag 0. The compiler allocates nodes on the stack, stores the address of the previous node in the new node’s next field, and builds the list containing 1, 2, and 3.

Generic code creates a separate problem. When a polymorphic function is used with int, the compiler generates a version for integers. When the same function is used with a tuple of two integers, it generates another version with the appropriate value size. McDaniel calls this process monomorphisation, with each specialised copy called a monomorph. The two functions may look almost identical, although their stack layouts differ. Calling the wrong copy can crash the program or produce an incorrect result. He describes this as one of the hardest parts of his compiler.

Type checking and the limits of decidability

Translation is only part of the job. A type checker has to establish that a program is well typed, and it must reach an answer in finite time. If checking can loop forever, the compiler cannot report an error reliably and may hang or crash instead. McDaniel treats decidability as a design constraint that has to be built into the type system.

Sage groups its terms into expressions, constants, and types. Constants are expressions, and types are constants, so each category includes the next one. The compiler infers an expected type from the context in which an expression appears. It then compares the inferred type with that expectation. Sage uses structural equality: two types with different names count as equal when their structures match. The checker therefore compares the shape of the values rather than trusting names alone.

A language with somewhere to go

The final demonstrations show what the layers buy. McDaniel presents an operating system whose user space is written in Sage. It boots into a shell written in the Sage source language and compiled for RISC-V. The shell launches a Sage PowerPoint application, which presents material about the operating system before returning to the shell to navigate the file system.

The Sage compiler and VM also run in a browser through a static site hosted on GitHub Pages. The web interface exposes the compilation stages and executes the resulting code. A JavaScript-interoperability backend lets Sage call supported JavaScript functions such as eval. The prepared examples include “hello world”, factorial, a hash map written from scratch, canvas drawings, and AES encryption and decryption in the browser.

The source leaves the viewer with a method rather than a single compiler trick. A parser, an intermediate representation, and a code generator form the basic architecture. The useful design choice is to make each lowering step small enough to inspect. A high-level program becomes IR, IR becomes VM code, and VM code becomes machine instructions. The compiler stays understandable because each stage solves a narrower translation problem.

Limits of the source

The video is a worked explanation of McDaniel’s Sage system, with demonstrations of code and a web interface. It does not provide formal references, benchmark methods, or a full specification of the language and virtual machine. Exact instruction names, memory layouts, type rules, and generated code depend on the diagrams and source shown during the video. The captions contain automatic-recognition errors around technical terms, including Sumerian, Sage, RISC-V, monomorphisation, and pointer operations. I have normalised those terms where the surrounding explanation makes the intended word clear.

The description identifies this upload as a reupload with improved audio mixing. It links to the Sage compiler, its browser demo, McDaniel’s website and blog, and his Dune shell project. Those links provide the source’s own routes into the implementation. They do not supply the external evidence needed to turn the video’s claims about performance, portability, or completeness into an independent assessment.

Further reading / references

• Sage compiler, the compiler discussed in the video.
• Sage browser demo, the web interface used for the compilation and execution examples.
• Adam McDaniel’s blog, which the description links as further material on programming and compilers.
• Dune shell, the shell project mentioned in the description.