LetItCrash

Compilers for the practicing programmer

LLM-authored, human-reviewed

Algorithms & theory

The first compiler for Rust was written in OCaml. Facebook’s Hack - the language that powers much of HHVM, the runtime for a good share of the modern web - is written in OCaml. That is not a coincidence. Compilers process trees, and functional languages - immutable data, pattern matching, recursion as the default - give compiler writers the tools they need. If you have worked through this site’s ladder, you already know most of the skills inside a compiler. The point is practical: a well-rounded system architect - a concurrency expert, a polyglot, a “right language for the job” person - should understand how languages become machines.

The claim: the runtime model is compiler knowledge

This site teaches the runtime model of two languages. The functional JavaScript vs. functional Elixir article shows how V8 compiles JavaScript and how the BEAM compiles Erlang: one runtime rewards staying on a single fast thread, while the other rewards spreading work across cheap processes. The BEAM article explains a virtual machine designed for telephone switches. These are compiler stories in runtime form. Choosing a language for a task is predicting how that task will behave under a given compiler. You cannot decide whether the BEAM is the right tool for a compute-bound job without knowing what the BEAM optimizes for. You cannot know that without knowing how it translates your code. The transfer the interviewers promised - that compiler knowledge makes you a better programmer - is real and specific: compilers turn the abstract skills this site drills (trees, recursion, pattern matching, substitution) into the shape of real systems.

The pipeline, in one picture

Compiler reference texts divide the work into a small number of phases. A modern textbook states the whole shape in a sentence:

Compilers analyze their input, construct a semantic representation, and synthesize their output from it. This analysis-synthesis paradigm is very powerful and widely applicable.

Analysis turns source text into meaning; synthesis turns meaning into output. Between them sits the pipeline that every compiler shares. Every stage is an algorithm:

  • Lexing turns a string into tokens. This is the shunting yard exercise’s first half, and the site’s Evaluate RPN - a tokenizer that reads “3 + 4 2” as `[‘“3”‘, “+”, “4”, ““, “2”]` is a lexer in miniature.
  • Parsing turns tokens into a tree. The grammar of an expression - precedence, associativity, parentheses - is the same problem the shunting yard algorithm solves with two stacks, and the tree it builds is a syntax tree: the encoding article calls this exact shape a “tuple tree,” and it is the structure this site’s binary trees article describes.
  • Tree walking turns the tree into behavior. An interpreter is a tree walker with an evaluator at each node; the site’s lambda calculus section is precisely that - beta-reduction is an evaluator, and the whole lambda calculus section is a running interpreter for the smallest language that exists.

The strongest books in the field use this split to organize their teaching. The Go-based introduction explains its own structure by what it leaves out: “Instead of writing about building a tree-walking interpreter and turning it into a virtual machine, I would only write about the tree-walking part.” The tree-walking part is the part this site has been teaching all along.

The front end is pattern matching on text

Parsing is pattern matching on a token stream. That is the connection that makes compilers familiar. The reference implementation of a parser is recursive descent: one function per grammar rule, with each function matching the next token against the shapes it knows. The site’s pattern matching article teaches exactly this reflex - “the = sign is not what you thought, and every Elixir function you read from now on is a set of patterns waiting to match.” A parser makes that sentence literal: the pattern is the grammar rule, the match is the token, and recursion grows the tree. The encoding article makes the representation legible - a syntax tree stored as tuples, or as an array with children-as-indices, is the same tree in the language’s primitive clothes. Parsing is not separate from the algorithm practice this site teaches. It is that practice applied to a token stream.

The back end is a tree walk

If the front end is pattern matching, the back end is recursion. An interpreter evaluates a syntax tree by walking it: evaluate the children, then combine the results. The site’s /lambda section states the idea plainly - a lambda term is a tree, and beta-reduction is the evaluator that walks it, substituting and reducing until a normal form is reached. The lambda calculus article calls the reduction rule “the only rule” of the calculus. In its role as an evaluator, that rule does what every tree-walking interpreter does. Compilation is the next step: the same walk, with a different output. Instead of producing a value, each node produces code. The evaluator and the compiler share the tree; they differ in what the walk emits.

The functional connection is the main point. A tree walk on immutable data needs no defensive copying because the tree cannot change under you. The walk is safe by construction. Pattern matching dispatches on node shape. Recursion is the walk itself. The three skills this site drills from the first ladder step are exactly the three skills a compiler’s back end needs. That is why compiler writers reach for languages that make those skills native.

Why OCaml: the language-choice lesson

Rust’s bootstrap and Hack’s implementation are the industry’s two most visible votes for this thesis. Before Rust could compile itself, a compiler written in OCaml compiled it - a functional language whose pattern matching, algebraic data types, and immutability made the tree munching tractable. Hack chose OCaml outright, and its hack/src is a working argument that a large, industrial-strength compiler can be built in a language most working programmers would not have picked for “systems” work. Both teams chose the language for the task’s shape. The task is tree munching, so the language that makes tree munching natural wins, whatever its reputation.

The architect’s lesson is the orchestration article’s lesson, stated more sharply: choose the language for the workload. The BEAM is oriented toward concurrency, which is why Erlang and Elixir are not the languages compiler writers reach for - not because they cannot, but because a compiler’s workload is not a telephone switch’s workload. The same reasoning that says “Elixir for the conductor, Rust for the computation” says “OCaml for the compiler.” Understand a compiler as a tree-walking program, and you can make that call instead of inheriting it. The reading Elixir article applies the same principle at the syntax level; this article applies it at the architectural level.

What the architect takes away

A well-rounded architect does not need to build a compiler. They need to know what one is, because the compiler shapes the language’s performance profile and ergonomics. Knowing that V8 JITs hot loops and the BEAM preempts processes is compiler knowledge. So is knowing that parsing is pattern matching and evaluation is a tree walk. So is knowing that a language was designed for the tree-munching workload. Each fact tells you when a language will be the right tool and when it will fight you. That is the skill this site’s ladder was building toward.

Where to go next

Rust’s first compiler was OCaml because tree munching fits a functional language like a glove, and Hack is OCaml today for the same reason. Keep this point: compilers are not separate from the algorithms you already practice. They are parsing - which is pattern matching - and evaluation - which is a tree walk. Language choice means choosing the tool that fits the workload. Once you know that, “when to use a different language” stops being a fashion question and becomes an engineering one.

← Back to articles

Exercises