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.
Run
zeno tokenson 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?Compare
zeno bytecodefor awhileloop and for aforloop overrange.Read
docs/lexer.mdbesidesrc/lexer.rs, and add a token of your own.