How the Compiler Works

You don't need to know how the compiler is built to use Tessera, but a rough picture helps when you wonder why something behaves the way it does. This appendix is that picture.

The pipeline

The compiler is written in OCaml, with no dependencies beyond the standard distribution. A program goes through these stages:

1. Lexing and parsing turn the source into a syntax tree. Newlines end statements, so the parser also decides where an expression continues onto the next line.
2. Modules are loaded: every use is resolved to a file next to the program, a dependency from tessera.toml, or the standard library, which is built into the compiler. Git dependencies are fetched and checked against tessera.lock here.
3. Type checking infers the types inside every function, checks every call against its signature, checks that matches are exhaustive, and enforces the capability rules: authority followed through every type and kept out of dyn values, no ambient I/O, dependencies within their caps. It collects every error rather than stopping at the first, and attaches fixes where it can.
4. Running or compiling. From the checked program, one of two backends takes over.

Everything up to here is shared, which is why both backends accept exactly the same programs and report exactly the same errors.

The interpreter

tessera run walks the checked syntax tree directly. It starts instantly, which makes it the right tool for trying things, for tests and for scripts. Tasks run as coroutines, and the capability operations are implemented in OCaml.

The native backend

tessera build goes further:

1. Lowering turns the checked program into a small intermediate representation in which every type is concrete: each generic function is instantiated for the types it's used with, and interfaces become direct calls, so generic code costs nothing extra.
2. Ownership inserts reference counting: each value is retained and released exactly where needed, and a value's last use moves it instead. This, with copy-on-write, is what makes value semantics cheap (chapter 4).
3. Code generation writes C. Value types such as numbers and small structs become plain C values; strings, lists and maps become reference-counted objects. Pipelines of pure closures are fused into single loops, and pure calls are reused where the result can't differ (chapter 12).
4. The C compiler builds the C together with the runtime, which provides tasks as fibers on a thread per core, the event loop for sockets and timers, TLS through OpenSSL, and the operating-system sandbox.

You can see the C for yourself:

$ tessera build main.tsr --emit-c -o hello
$ ls
hello.c
main.tsr
$ grep -c "" hello.c
4477

That C file is the whole program, runtime included, and it needs nothing beyond libc (plus OpenSSL if the program uses TLS). The server for this book is deployed exactly that way: the generated C is committed, and the deployment only needs a C compiler.

Built binaries are cached by the exact C, compiler flags and compiler version, so building an unchanged program again takes milliseconds.

Why two backends behave the same

A program shouldn't behave differently depending on how you run it. So the specification pins down everything that could differ: integers wrap the same way, floats avoid fused multiply-add, maps iterate in insertion order, concurrent output is ordered by start order, and --seed gives the same random numbers. The compiler's own test suite runs every test program in both backends, and the native ones also under AddressSanitizer and ThreadSanitizer.

Tessera in Tessera

Tessera compiles itself. The whole path from source to C (the lexer, the parser, the module loader, the type checker, lowering and its passes, C generation and the check, caps and build commands) also exists in Tessera, in selfhost/ in the compiler's repository, about 20,000 lines of it. Each part was checked against the OCaml compiler before the next was written: both run on every Tessera file in the repository, on edge cases written for each step and on every example in this book, and they must agree on every token, syntax tree, type, diagnostic and line of C.

The proof that the compiler is complete is the bootstrap. The OCaml compiler builds the Tessera compiler; that compiler builds itself; the result builds itself again. The last two emit exactly the same C, about 368,000 lines, which is also what the OCaml compiler emits for it. sh selfhost/bootstrap.sh runs it.

The self-hosted compiler is a Tessera program like any other, so it holds only the authority it is given. tessera caps on it shows it can read and write files, read a fixed list of environment variables and run the C compiler and a few file tools during a build; checking, lowering and generating C are pure functions. Its standard library and runtime headers are embedded from the compiler's source tree, through embed roots in its tessera.toml, so the compiled compiler doesn't read those sources when it runs. The OCaml compiler stays, as the way to build Tessera from scratch, and still runs the interpreter, the formatter and the language server.

A note on performance

Native Tessera code is C, compiled by the system's C compiler with optimizations, so for straightforward numeric and string code most of the speed is the C compiler's work. Where Tessera pays a price, the price comes from the language's guarantees: reference counting on shared values, bounds checks on indexing, and the occasional copy when a shared value is changed. The compiler works to make those rare, by moving values on their last use, updating in place when nothing else holds a value, and hoisting checks out of loops.

The interpreter is much slower than native code, as interpreters are, but fast enough for tests, scripts and trying things out. When speed matters, tessera run --native or tessera build is one flag away, and bench blocks (chapter 11) will tell you what you gained.