9 ms·
Lessons from Writing a Compiler
- _dain_ 4y agoWhat does the Austral language bring to the table? Are there code examples?
- tekknolagi 4y agoYou might enjoy a read through the programming language's website. I certainly did. https://austral.github.io/ https://austral.github.io/ The spec has some nice code snippets: https://austral.github.io/spec/ https://austral.github.io/spec/
- zetalyrae 4y agoYou 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 https://www.stroustrup.com/P0977-remember-the-vasa.pdf [1]: https://twitter.com/zetalyrae/status/1540883027743559682 https://twitter.com/zetalyrae/status/1540883027743559682 [2]: https://github.com/austral/austral/tree/master/examples https://github.com/austral/austral/tree/master/examples [3]: https://austral.github.io/examples/ https://austral.github.io/examples/
- tialaramex 4y agoLinear 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.
- zetalyrae 4y agoIt's about readability. You write the types for documentation, and to make it easier for people doing a code walkthrough to simulate what is happening in their heads. IDEs can add type annotations not present in the code, but there are many contexts (source control diffs, or code in a PDF, or code in a website) where that kind of software type annotation is not available. I find that in OCaml, which has type inference for everything (function arguments, function return type, local variables, expressions) I end up writing the types almost everywhere, for two reasons. The first is documentation: it helps me to read and understand code I wrote ages ago. But the second is that type inference often goes haywire, because the compiler doesn't know ahead of time whether the code you wrote is in error. So when you make a mistake, like forgetting to pass the right number of arguments to a curried function, the compiler will happily propagate that mistake around, even propagating the erroneously-inferred types to other functions. And you get these incomprehensible type error messages that come from places that are very separate from where the mistake actually happened. And then I find myself taking a random walk through the code, adding type annotations to constrain the inference until I find my mistake. So why not skip the middle step, and require annotations? Often, however, it isn't obvious what the type of an expression is going to be, and it's easier to construct the value level than the type level. For those cases you could simply force a type error to find out the type and write it in the text. The simplicity reason is not that inference rules vary by compiler (the rules can be put in the spec), it's that type inference (as opposed to one-directional type propagation) can be complex to implement, and for simple extensions to an H-M type system it can become undecidable.
- tialaramex 4y agoComing from mostly C and Java (where I didn't have inference) and Python (dynamic types, no real annotation when I was writing it) I found Rust's degree of inference (Constants, function signatures, structures must spell their types, but other types can be inferred if unambiguous) very satisfying, and I don't fancy going back. Never written any OCaml in anger, and it has been decades since I wrote more ML of any sort, so perhaps in OCaml I'd find there's too much inference for my taste.
- Gadiguibou 4y agoIt'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?
- zetalyrae 4y ago1. I think it's good enough for concurrency. A big selling point of linear types is that, since there can only be a single reference to a linear value at any time, concurrency is trivial. You just send linear values through other threads on a channel, and they're consumed (from the point of view of the sending thread). 2. The set of types is divided into two universes: the Free universe (i.e. unrestricted) types like bool, int, records and unions containing other free types; and the Linear universe, containing linear types. So non-linear types are allowed and are the default for anything that's not a resource with a particular lifecycle (i.e., anything other than memory, file handles, socket handles, that kind of thing). 3. References are possible and they work like borrowing in Rust. 4. No refcounting or GC, it's done at compile time like in Rust.
- tester756 4y ago>The prototypical compilers textbook is: Dragon Book?
- deleted 4y ago[deleted]
- astrange 4y agoYes, 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.
- zabzonk 4y agoI agree it is a bad book, but you don't seem to be explaining why.
- astrange 4y agoThe article says exactly what I'd say. It spends far too much time explaining the frontend (parsing theory) which isn't the difficult or important part of the compiler, and it somehow makes it sound scary and mathematical. The rest isn't covered enough and doesn't have enough practical real-world advice.
- necheffa 4y agoAs someone who has had to clean up (with backwards compatibility) after people who YOLO'd custom grammars rather than actually taking the time to respect the mathematics of parsing and design ambiguity out up front... I cannot disagree with you more.
- astrange 4y agoI mean, I think you should read a book on parsing theory, just not that one. I like "Parsing Techniques: A Practical Guide" but there might be a newer better one. But clang and gcc both have handwritten recursive-descent parsers for C/C++. (C++ parsing of course is undecidable, or at least used to be.)
- tsegratis 4y agoThat 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_clarence 4y agoI’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 https://legacy.cs.indiana.edu/~dyb/pubs/nano-jfp.pdf
- tsegratis 4y agoDid you choose "No destructors" because of their effect on static analysis? -- Why are they an anti feature?
- zetalyrae 4y agoDestructors, 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-linear-types https://austral.github.io/spec/rationale-error-handling 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.
- hardwaregeek 4y agoI’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.
- deleted 4y ago[deleted]
- TazeTSchnitzel 4y agoThe 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_clarence 4y agoJust use Arc
- the_clarence 4y agoOCaml 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 4y agoAfter 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).
- ArrayBoundCheck 4y ago
- ki_ 4y agoThe big font is difficult to read (for me) edit: nvm, i can just zoom out to 50%;
- ahaferburg 4y agoOr use reader mode.
- danybittel 4y 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_clarence 4y agoInteresting 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)
- renox 4y agoWhat's Austral story for integer overflow? Division errors are explained but not the other errors, I guess that they abort too?
- zetalyrae 4y agoInteger arithmetic traps on overflow -- and that includes the often forgotten "divide by INT_MIN" case: https://github.com/austral/austral/blob/01a6327815d1f9cc10975b75b2b24f42428ac6b2/lib/builtin/Pervasive.aum#L129 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.
- renox 4y agoThanks 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..
- DylanSp 4y agoVery 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 4y 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.