Lessons from Writing a Compiler

https://borretti.me/article/lessons-writing-compiler

by zetalyrae • 4 years ago

246 86 4 years ago

borretti.me

_dain_• 4 years ago

What does the Austral language bring to the table? Are there code examples?

tekknolagi• 4 years ago

You might enjoy a read through the programming language's website. I certainly did.

https://austral.github.io/

The spec has some nice code snippets:

https://austral.github.io/spec/

zetalyrae14• 4 years ago

You can think of it as either "Rust: The Good Parts" or "Modern Ada". It's a minimal language with linear types, capability-based security, an Ada-inspired module system, and strong typing. And it's designed with simplicity as the overriding goal: it's small enough that it fits in your head, and avoids becoming the Vasa[0].

By way of example: the borrow checker in the Rust compiler is 24.7k lines of code[1]. Austral's equivalent is 600 lines, because it's simply doing less. The linear type system is designed so that the rules fit in a page of text, and you learn them once and apply them everywhere, rather than fighting against an ever-changing, opaque pile of heuristics. It's much more like a normal type system and much less like static analysis.

There are a few example programs in the compiler repository[2] and the website[3].

[0] https://www.stroustrup.com/P0977-remember-the-vasa.pdf

[1] https://twitter.com/zetalyrae/status/1540883027743559682

[2] https://github.com/austral/austral/tree/master/examples

[3] https://austral.github.io/examples/

tialaramex6• 4 years ago

Linear types are interesting, however I don't buy "Rust: The Good Parts".

In particular type inference (Rust has this, Austral does not) is a real quality of life improvement. If there's only one possible type X could be, what value is produced by insisting that I figure out how to spell that type to talk about X? This feels unimportant when X's type is an integer, but when it's an array of functions which return other functions that take an array of functions and return an integer, figuring out how to write what I'm doing is tiresome. The compiler knows, and I know, don't waste my time.

I presume that providing inference interferes with the ambition to have a small specification, because offering inference means either different implementations could have different inference rules, or else, those rules must be set out in full in the specification. However the quality of life improvement is real.

Gadiguibou• 4 years ago

It's really similar to the language I'm writing a compiler for atm :). (I also like the syntax and choice of keywords.)

I haven't heard much from the usefulness of linear types in real world scenarios and would like to learn more from someone with a bit more experience.

- Is it enough to grow to do things like concurrency?

- Are non-linear types allowed?

- Are references possible?

- In which case, does it fall back to a GC? ref counting?

tester756• 4 years ago

The prototypical compilers textbook is:

Dragon Book?

astrange3• 4 years ago

Yes, which is why it's a bad book and you shouldn't tell people to read it. Actual compilers tend to handwrite their parsers rather than using theory; parser generators aren't good at recovery and error messages.

zabzonk2• 4 years ago

I agree it is a bad book, but you don't seem to be explaining why.

zetalyrae14• 4 years ago

I think writing a parser by hand should be reserved for when

1. You have users.

2. You can demonstrate a marked improvement in performance and/or error reporting with the hand-written parser.

Otherwise, deriving a parser from a grammar should absolutely be the default. Writing parsers by hand is error-prone, causes security vulnerabilities[0], and is very tedious work.

[0] http://langsec.org/

defen• 4 years ago

Actual compilers tend to handwrite their parsers rather than using theory; parser generators aren't good at recovery and error messages.

The linked article recommends using a parser generator. However in my experience I agree with you, parser generators aren't great in practice, which makes me hesitant to read the rest of the post.

titzer• 4 years ago

Just write recursive descent, except for the infix operator precedence, and then use a tiny stack that you either push to or pop from (shift/reduce, ala LR) based on the relative precedence.

Pretty much all compilers that have fast parsers that also give good error messages are hand-written recursive descent.

mrslave• 4 years ago

It's a fine book and you should not tell people to read it.

It belongs in a first compilers course where you learn about how scanners and parsers work, not just "configure this then call `yylex`". So yeah, it nerds out about finite state machines for a little too long for most audiences. And you know your audience. Your audience wants to write a compiler today, so you are correct not to recommend this book.

dan-robertson• 4 years ago

Regarding parsing techniques: https://notes.eatonphil.com/parser-generators-vs-handwritten...

mhh__2• 4 years ago

I think engineering a compiler is a better book.

The dragon book has a few places which are really good and then a few places which were an afterthought shoved in there later like SSA (which is really important).

We are due a new batch of compiler books. As the utility of investment in compilers has decreased we are stuck with books mostly expecting x86 to die and be replaced with potentially statically schedulable machines so a lot of time is spent on algorithms that are really really fuzzy on a modern core.

Muchnick is a still a Bible for optimizations but it's written in a bizarre pseudo-language which means many algorithms are rather inpenetrable.

JITs are not very well covered in the literature. There's a lot of subtle variations in how they design their IRs these days.

sivakon• 4 years ago

so what’s the quintessential book for learning compilers (practical book)!

tsegratis3• 4 years ago

That was a useful write up, thanks

It's more unusual to find writeups on implementation of semantics or typchecking, but as you say, more important

Keeping the env flat, and like a relational database (for typechecking) sounds like an idea i will take

the_clarence5• 4 years ago

I’ve always wondered why Rust creates a unique id per atom and keeps track of type information in a hashmap using that unique id as key (instead of storing the type information within the atoms themselves). I guess it is to keep things flat, or reuse the same structure for different passes.

Other approaches like the nanopass approach creates different structs for each pass: https://legacy.cs.indiana.edu/~dyb/pubs/nano-jfp.pdf

tsegratis3• 4 years ago

Did you choose "No destructors" because of their effect on static analysis? -- Why are they an anti feature?

zetalyrae14• 4 years ago

Destructors, exception handling, and the type system are all tied together, so I'm not sure where to begin explaining. These two sections in the rationale provide a complete explanation:

https://austral.github.io/spec/rationale-linear-types

https://austral.github.io/spec/rationale-error-handling

But basically: there are no destructors because there is no exception handling, and therefore no stack unwinding. The reason there's no exception handling is that the semantics (and implementation) of exception handling are incredibly complicated, and they make the code harder to reason about.

A design goal in Austral is "no hidden control flow". If it's not on the source code, it isn't happening.

Linear types are also not compatible with exception handling (which is why Rust uses affine types, sort of).

In place of destructors you have functions that consume linear values. These are ordinary functions and have to be called explicitly, calls to them are not inserted by the compiler.

For example, imagine that File is a linear type that holds a file handle. You might have something like:

    let f: File := openFile("foo.txt");
    -- code etc etc.
    closeFile(f);

Here, closeFile is a "destructor" in the sense that it takes a value of a linear type and returns nothing. It's not a destructor in the C++ sense because the call is not inserted for you at the end of a block or during stack unwinding.

tsegratis3• 4 years ago

Okay, nice

Overall I'm impressed with your clarity of design -- coming from a language designer of many years, for whatever that is worth ;)

tialaramex6• 4 years ago

But, what happens if I have a Bunch of things and now I'm done with it?

In a language like C++ or Rust, if those things happen to be Files then when they're destroyed because I was done with the whole Bunch, the files get closed. [ This also means, although it would usually only happen intentionally in Rust, that you can leak the open files, that's what Rust's Box::leak does for example, but if it didn't exist you could do it yourself ]

I haven't written any Austral, but, if I have a Bunch of Files, am I now responsible for taking all the Files back out of the Bunch to closeFile them or else my program won't compile somehow? That seems like it'd suck for performance.

Or maybe I just can't put Files in a Bunch because they're Linear? That seems like an annoying limitation.

Or maybe I need to tell the Bunch to call closeFile on the Files when I get rid of the Bunch?

ArrayBoundCheck• 4 years ago

I dislike zig for lack of destructors and "no hidden control flow". I'll probably dislike your language too but is there one big thing difference from zig and austral?

hardwaregeek• 4 years ago

I’d update this to Just Use Rust cause now you get the benefit of a decent package ecosystem and most of the benefits of OCaml. There are some messy lifetimes but something like Rowan and a couple arenas solves this.

As for parsing I think treesitter is pretty solid. You get the benefits of a parser generator but also a fast incremental CST parser.

TazeTSchnitzel• 4 years ago

The extra work required to deal with the lifetime of a graph is pretty unfriendly for a beginner. It's one of the few things for which, though I would be willing to use Rust myself, I might not recommend it to someone else.

the_clarence5• 4 years ago

Just use Arc

the_clarence5• 4 years ago

OCaml really messes with you if you try to prototype as you can’t have two modules that depend on one another. Rust is def. much better.

smasher164• 4 years ago

After reading through the Austral site, I have to say that the reasoning for its various features is very well articulated. This language ticks a lot of boxes. The only feedback I have to offer is to not skimp on the FFI, because the easier it is to call into C and C++ code, the easier the language will be to adopt (at least for the domain it seems to be targeting).

ki_• 4 years ago

The big font is difficult to read (for me)

edit: nvm, i can just zoom out to 50%;

ahaferburg• 4 years ago

Or use reader mode.

danybittel• 4 years ago

"Investing time in writing a good end-to-end test runner was a huge boon.."

I'd like to hear some details (features) of the test runner.

the_clarence5• 4 years ago

Interesting post! Personally I discovered all of these things by just making up some language and trying to compile it. I realized that parsing things was hard because of line breaks and words and whitespaces, so I wrote a lexer without knowning that it was a lexer and later realized that I had reinvented the wheel. Then I needed to store the spot in the source where each token had originated from, learned that it’s usually called span, and on and on. At some point I realized it was hard to figure out how to parse an expression without documenting the grammar, and then I learned about BNF. It’s actually not too hard to figure everything yourself and then read about how people usually solve a problem if you get stuck. Learn by doing.

Another good way to learn is to check the compiler of a language you already know and use. Then you grasp common terms like “kind” and “ty” and “span” that you can reuse.

You then realize things like: it’s better to have expressions be statements, as long as they don’t return a value. Otherwise you end up duplicating code for parsing statements and expressions (for example, for function calls)

because importing the Error module would be a circular dependency. This is a problem as new types of errors are added.

This is really only a problem with OCaml, which is why it’s not a great language to write any big program in IMO (as you can’t easily prototype or split your logic into many modules easily without hitting dependency cycles)

renox2• 4 years ago

What's Austral story for integer overflow? Division errors are explained but not the other errors, I guess that they abort too?

zetalyrae14• 4 years ago

Integer arithmetic traps on overflow -- and that includes the often forgotten "divide by INT_MIN" case:

https://github.com/austral/austral/blob/01a6327815d1f9cc1097...

You have to use a different set of operators to get modular arithmetic semantics. So, the choice is not a flag you flip at build time, but a choice of operators.

renox2• 4 years ago

Thanks for your answer.

You have to use a different set of operators to get modular arithmetic semantics. So, the choice is not a flag you flip at build time, but a choice of operators.

Like Zig I think.

As for 'panic at overflow' I think that Erlang/Elixir is the same so there are probably a lot of 'design patterns'/libraries to get inspiration from there.

One note, your language allow usage of 'named parameters' as in "return File(handle => ptr);" so this means that the name of the parameter is part of the API and must be chosen carefully.. ptr isn't a very good name, handle would be a better name, but then of course you have "return File(handle => handle);" which is a classic problem of named parameters..

DylanSp2• 4 years ago

Very good article. The focus on end-to-end testing, especially during early iteration, rings true to me; when I wrote a toy language/interpreter, I used a lot of unit tests for the individual stages. They definitely helped find and prevent bugs, but they took a lot of time to write, and they're closely coupled to the internal data structures.

deterministic• 4 years ago

Writing a parser by hand is tricky and not worth the alleged performance increases

Not my experience at all. It is easy and fun. And I can actually debug the parser instead of staring at generated noise/tables. And the performance is usually x2 or more, making it worth it for compiling large projects. Background: I am the maintainer of a high performance JIT optimising compiler for a Haskell like rules language used in production by commercial companies around the world.

And yes tests are absolutely necessary to maintain a commercial optimising compiler. I use a test suite of more than 9000 tests. The result is zero bugs in production the last 5+ years. The upfront cost is absolutely worth it because I can make massive changes to the internals of the compiler and still confidently release the result into production.

As for type checking: you typically won’t find any useful stuff in compiler books. However there is a massive amount of information available on type checking and type systems online. It is a huge research area and kinda the foundation of computer science. There are whole books dedicated to type checking and type systems alone.

Lessons from Writing a Compiler

Related Stories