The Zeno Book Zeno 0.1 zeno-lang.org

34 Inside Zeno

Zeno was built to learn how a language is built, so the compiler is written to be read. It is a Rust program of about fifty thousand lines, with no libraries: the lexer, the parser, the checker, two engines that run programs and two that compile them are all written by hand. This chapter follows one small program through every stage, with the command that shows each.

square.zeno

function square(n: int) -> int {
    return n * n
}
print(square(7))
49

34.1 The stages

files -> lexer -> parser -> modules -> checker -+-> interpreter     zeno run
                                                +-> bytecode -> VM  zeno run --vm
                                                +-> C -> cc         zeno build
                                                +-> LLVM IR -> clang  zeno build --llvm

Each stage takes what the one before it made, and every stage after the parser works on the same syntax tree.

34.2 The lexer

The lexer turns the characters of a file into tokens, the words of the language. It looks at one character, and that is enough to decide what kind of token starts there: a digit starts a number, a quote a string, a letter a name or a keyword, # a comment.

$ zeno tokens square.zeno | head -12
   1:1   Function
   1:10  Ident("square")
   1:16  LParen
   1:17  Ident("n")
   1:18  Colon
   1:20  Ident("int")
   1:23  RParen
   1:25  Arrow
   1:28  Ident("int")
   1:32  LBrace
   1:33  Newline
   2:5   Return

A line end becomes a Newline token only where a statement can end; after + or inside brackets it is skipped, which is how a long statement goes on to the next line. The lexer reports every mistake it finds, not just the first, because after a bad character it can simply skip it and carry on. (src/lexer.rs, about 700 lines.)

34.3 The parser

The parser turns tokens into a syntax tree: the program’s shape, with each expression inside the one it belongs to. It is a recursive descent parser: one function for each kind of thing in the language (a statement, an if, an expression), each calling the others for the parts inside it. Precedence comes from which function calls which: the function for + calls the function for * to read each side, so * binds tighter without a table.

$ zeno parse square.zeno
function square(n: int) -> int
    return (n * n)
print(square(7))

zeno parse prints the tree back as text, with brackets that show how it grouped every expression. The parser stops at the first mistake, because after a syntax error it no longer knows where it is, and what follows is usually nonsense caused by the first. (src/parser.rs, about 2100 lines.)

34.4 Modules

The next stage loads every file the program imports, renames each top-level name with its module in front, and joins them into one program (Programs in Several Files). Every stage after it sees one tree, as if the program had been written in one file, so none of them had to learn about files. zeno join shows the result.

34.5 The checker

The checker walks the tree and works out a type for every expression. It is the biggest stage, nearly ten thousand lines, because it is where most of the language’s promises are kept: types, none, units, sized numbers, match covering every case, raises, owned values, private, interfaces and generics. It reports every mistake it is sure of, and marks a faulty expression so that nothing built on it is reported again.

It makes several passes, because types flow backwards as well as forwards: a parameter’s type comes from the calls, which may be below the function. Each pass notes what arrived at every untyped parameter, and the next starts from that, until a pass learns nothing new.

34.6 Two engines that run

The interpreter walks the tree. For n * n it works out the left, then the right, then multiplies. It is the simplest way to run a program, and the default for zeno run.

The VM compiles the tree to bytecode, instructions for a small stack machine, and runs those. n * n becomes "push n, push n, multiply":

$ zeno bytecode square.zeno
== main() ==
0000    1  Closure      0          ; square
0001    4  Const        0          ; <function print>
0002    |  GetLocal     0          ; square
0003    |  Const        1          ; 7
0004    |  Call         1
0005    |  Call         1
0006    |  Pop          1
0007    |  Const        2          ; none
0008    |  Return

== square(n) ==
0000    1  Required     0 0        ; "`square` needs a value for `n`"
0001    |  Enter
0002    2  GetLocal     0          ; n
0003    |  GetLocal     0          ; n
0004    |  Binary       *
0005    |  Return
0006    1  Const        1          ; none
0007    |  Return

Both engines share one file, ops.rs, for what every operator does, so what * means is written once. The VM is about twice as fast, and every test program runs on both and must print the same.

34.7 Two engines that compile

The C backend writes C, as Compiling showed. square becomes:

$ zeno build square.zeno > /dev/null
$ grep -A3 "^static int64_t z_square(int64_t z_n) {" square.c
static int64_t z_square(int64_t z_n) {
    return zeno_mul(z_n, z_n, 2, 12);
}

The LLVM backend writes LLVM’s intermediate language as text, with no LLVM library. Here the overflow check is spelled out: LLVM’s own multiply-with-overflow gives the answer and a flag, and a branch goes to Zeno’s overflow error with the line and column:

$ zeno build --llvm square.zeno > /dev/null
$ grep -A13 "define internal i64 @z_square" square.ll
define internal i64 @z_square(i64 %arg.n) {
entry:
  %t1 = call { i64, i1 } @llvm.smul.with.overflow.i64(i64 %arg.n, i64 %arg.n)
  %t2 = extractvalue { i64, i1 } %t1, 0
  %t3 = extractvalue { i64, i1 } %t1, 1
  br i1 %t3, label %overflow1, label %fits1

overflow1:
  call void @zeno_overflow(i32 2, i32 12)
  unreachable

fits1:
  ret i64 %t2
}

Both backends share the C runtime, runtime.c, which every compiled program carries: text, lists, printing, errors, the collector, the pool, and the board.

34.8 Agreement

Four ways of running one program could easily drift into four languages. They do not, because of one rule enforced by the tests: every test program is run by the interpreter, the VM, the C build and the LLVM build, in the build kinds that apply, and the outputs must be the same, byte for byte, error messages included. When a stage is changed, the tests show at once which of the others must change with it.

34.9 The files

File What it is
main.rs the zeno command
token.rs, lexer.rs characters to tokens
ast.rs, parser.rs tokens to a syntax tree
printer.rs the tree back to text, for zeno parse
modules.rs, package.rs files and packages to one tree
checker.rs types, and every check before running
value.rs, ops.rs, builtins.rs values and their operations, for both engines
interpreter.rs runs the tree
bytecode.rs, emit_bytecode.rs, vm.rs the VM
emit_c.rs, runtime.c the C backend and its runtime
emit_llvm.rs the LLVM backend
format.rs, lsp.rs, json.rs the formatter and the language server
board.rs, units.rs, ints.rs the simulated board, units, sized numbers

The docs folder of the repository has a walkthrough of each stage, written to be read beside the code, and each ends with things to try. They are the next book after this one.

No libraries, so that every part of the compiler can be read and understood by one person, which was the reason for building it. An interpreter first, because it is the shortest way to a language that runs, and then C, because C reaches every microcontroller. The interpreter stayed, as the reference every other engine is held to. (Decisions 5.1 to 5.5.)

A program goes through the lexer, the parser, the module loader and the checker, and then to one of four engines: the interpreter, the VM, C or LLVM. zeno tokens, parse, join and bytecode, and the kept .c and .ll files, show each stage. Every engine must print the same for every test program.

  1. Run zeno tokens on a file with a mistake, such as a $ in the middle of a line. How many errors does the lexer give for two such characters?

  2. Compare zeno bytecode for a while loop and for a for loop over range.

  3. Read docs/lexer.md beside src/lexer.rs, and add a token of your own.