7 ms·

Why Learn Compilers (2021)

118 points by ingve 3y ago

hayst4ck 3y ago
I remember understanding error messages a lot better after taking compilers.
- dietr1ch 3y ago
  The real discovery to me seems that you are actually supposed to read through the errors, and that it's ok to not understand them completely. As a TA I got to see huge jumps in productivity and independence on students that read a couple more lines and reasoned instead of bailing out at the first ugly line.
nayuki 3y ago
> And because compilers are largely deterministic closed-system problems -- for each input, there is one and only output Not even close! Optimization and code generation is a fantastically hard problem full of heuristics and tradeoffs. There is definitely more than one way to compile C source code to x86 binary code. There is even more than one way to compile TypeScript to JavaScript if you consider things like whitespace, indentation, and constant folding. The rest of the article is alright.
- mathisfun123 3y ago
  +1 Ya that's a hilariously naive take (the quoted line not your response) given PGO, to say nothing of MLGO.
- ehaliewicz2 3y ago
  Pretty sure he means given a single compiler.
- WalterBright 3y ago
  The compiler is deterministic - for the same inputs, you'll get the same outputs. Unless you've got memory corruption in it.
  - burjui 3y ago
    Or unless you iterate over randomized hashtables to produce some output, e.g. function sections in an executable. Though that doesn't change the semantics and is basically rearranging coins in your pocket.
  - eru 3y ago
    Many optimizers (and other algorithms used in compilers) can benefit from some random bits. Though, of course, in practice you can use pseudo-random bits and fix the seed.
    - WalterBright 3y ago
      Having a compiler produce different code for the same source is a recipe for "I can't reproduce your bug and can't fix it".
- mfranc42 3y ago
  He probably meant that a compiler is a pure function for a given source file and a set of flags. Of course, if you change a compiler or flags, you can get something radically different, but you shouldn't get something radically different because it's Tuesday, midnight, your username starts with n, you have more than 3 hard drives, or because it reads some bytes from /dev/urandom. It's bit of a stretch, sure, but I don't expect my performance problems to go away by recompiling stuff over and over again without changing either the code or flags and expecting the optimizer to make a better decision next time. It doesn't work that way.
  - mathisfun123 3y ago
    >and expecting the optimizer to make a better decision next time. It doesn't work that way But in practice it does work exactly that way because of PGO and if we're precluding PGO then the observation is as banal as "programs that have no side-effects are pure". Like I get that the post is trying to paint some beautiful picture about how compiler passes are abstract beautiful transformations of representations of programs but it's not a useful picture at all.
    - slavapestov 3y ago
      > Like I get that the post is trying to paint some beautiful picture about how compiler passes are abstract beautiful transformations of representations of programs but it's not a useful picture at all. It is actually a very useful picture especially to a beginner. PGO is an edge case and not used a whole lot in practice. Many compilers do not support it at all, even production compilers. Someone learning to write a compiler does not need to think about PGO. And besides, a compiler with PGO is still a pure function of source + flags + profile.
      - mathisfun123 3y ago
        >PGO is an edge case and not used a whole lot in practice. Many compilers do not support it at all, even production compilers. Both clang and gcc support `-fprofile-generate`. Beyond that generic infrastructure, in my area (DL compilers) if you're not doing PGO/autotuning you're not serious. >Someone learning to write a compiler does not need to think about PGO. That's like saying someone learning to write a compiler doesn't need to think about optimization at all - sure maybe the first time. But then every time after that it should be at the forefront of your mind.
- armchairhacker 3y ago
  There are multiple valid ways to compile a source with the same semantics, but a decent compiler should absolutely be deterministic. Imagine libraries which compile fine 99% of the time, but produce the wrong semantics every 1%: - Bug in your program? Could be a dependency of a dependency built wrong, better do a full clean and rebuild. - All of your pre-release tests passed? The code you shipped doesn't work, because you hit that unlucky 1%. Imagine how bad this would be back when software was released on CDs... - Have 70 dependencies which are like this (not hard in the webscale era)? Now your CI needs to retry every build up to 10 times, because every build has a ~63.4% chance of failing. And there's still ~1% chance your CI fails anyways because you got 10 unlucky builds in a row. I'm sure there are more stories of these kinds of issues...
  - eru 3y ago
    > There are multiple valid ways to compile a source with the same semantics, but a decent compiler should absolutely be deterministic. Imagine libraries which compile fine 99% of the time, but produce the wrong semantics every 1%: That's not the only kind of non-determinism, you know? Lots of algorithms benefits from access to random bits, too.
    - armchairhacker 3y ago
      The context is > for each input, there is one and only output A randomized algorithm which uses non-determinism but produces the same output is OK. Also, psuedo-randomness is OK as long as the same program compiled in the same version of the compiler always gets the same seed. But if the algorithm can produce different output causing the same program to compile to different assembly, that's a problem. Unless you can formally prove that every possible variation will have the same behavior, but formal methods + non-determinism is hard, so it usually isn't worth it. Even random hash order in hashmaps can create problems: see https://github.com/rust-lang/rust/issues/84447 https://github.com/rust-lang/rust/issues/84447 and https://github.com/rust-lang/rust/pull/82272#issuecomment-825124318 https://github.com/rust-lang/rust/pull/82272#issuecomment-82..., though this is a very small issue in the diagnostic reporter and not a case of 2 valid programs with different semantics.
- nayuki 3y ago
  So, the downvotes and replies warrants a follow-up comment. I support deterministic compilers due to deterministic builds. For a given input source code, compiler executable, and command-line flags, it should always produce the same binary, regardless of the time of day, random number generator, I/O, threading, environment, etc. My refutation of the article is that he made it sound like a compiler is like computing Fibonacci numbers - here are all the valid inputs, here is how each one maps to its one and only correct output answer, so fill in the code to accomplish that. Also in the previous paragraph he wrote: > Because the most basic compiler architecture is standard, you have limited boundaries and degrees of freedom when designing one. This might sound restricting, but actually, it's freeing because you get to play in a predictable sandbox.
xwowsersx 3y ago
What are some good resources/courses/books for learning compilers, especially in a hands-on way? "Crafting Interpreters" seems to be well-liked, is that a decent place to start? Appreciate any other tips.
- eru 3y ago
  You might like https://smunix.github.io/dev.stephendiehl.com/fun/index.html https://smunix.github.io/dev.stephendiehl.com/fun/index.html
- ogennadi 3y ago
  A PL researcher recommended [1] precisely cuz it avoids parsing and focuses on interpretation. [1] https://cs.brown.edu/courses/cs173/2012/book/ https://cs.brown.edu/courses/cs173/2012/book/
- azhenley 3y ago
  I wrote a tutorial series for my students: Let’s make a Teeny Tiny compiler. It’s much smaller than Crafting Interpreters, so I’d recommend it before you go there to test the waters. https://austinhenley.com/blog/teenytinycompiler1.html https://austinhenley.com/blog/teenytinycompiler1.html
  - ludicast 3y ago
    Very well done. Took a brief glance through your series and seems to cover most of the important deets.
  - xwowsersx 3y ago
    This looks very nice. Thank you!
- urthor 3y ago
  My suggestion is Crafting Interpreters + a different programming language to Java. YMMV, but it's hard to genuinely learn from Crafting Interpreters. All the code is already written for you.
whartung 3y ago
If no other reason, compilers are just great fun and really satisfying to write. Watching your compiler take a simple expression and spit out a bunch of code referencing locals, referencing globals, type conversions and coercions, function calls, managing precedence. This little thing created all this code. It’s exciting. Especially the first time, it’s magic. It’s a lot of fun. Once I wrote a DSL for a rule system, compiled down into Java source. Later, I wrote another higher level rule system that generated the DSL. At one point I think there was a USENET .sig line that read “Will write code that writes code that writes code for food.” Indeed.
quickthrower2 3y ago
Helps if your company pays you to just do compilers full time and nothing else; not even a colleague to need to talk to!
freilanzer 3y ago
Writing a compiler is still on my list since a few years, but everytime I start I get stuck in the parser. It just doesn't seem to click with me. On the next couple of weekends I'll start again with Flix (flix.dev) and maybe Crafting Interpreters. Wish me luck.
- Georgelemental 3y ago
  In my compilers class in university, the prof skipped over parsing entirely—our source code was Racket S-expressions.
  - freilanzer 3y ago
    Good, it's not the most important or interesting part imo. I also had an entire course about parsing, just not about compilers, and I don't see why many professors give it such an amount of attention.
- jjice 3y ago
  Something to consider is a parser generator for your language. They get a lot of flack online these days for some reason from people saying "a recursive descent parser is faster and not that hard", but they're generally time consuming if you just want to get something going. PLY (or maybe it's SLY now) for Python is really great.
- drdude 3y ago
  During my 2015 Compilers class, it was indeed the worst step and hardest to get right. We spent (my and my team mate) about 60%+ of the time making that parser actually parse. The lexing, tokenizing, etc is nothing compared to it. In another project, I used Antlr to avoid the headaches, but there are definitely better alternatives out there (some one mentioned Sly in the comments). Right now, if I want to mess with some transformation passes for an existing language, I would just look for LLVM and Clang for C for example (readily made front end, and backend with hackable middle end). P.S. I am a hobbyist at this stage and you can consider me knowing nothing about LLVM. My advice is based on my friends' (same colleague) who works for nVidia for their CUDA compiler using LLVM. Another reason for me to be interested in LLVM is that I used JVM languages (Scala, Java) for the past 20+ years and with GraalVM and its polyglot support for LLVM based languages; whose support was added using LLVM. my rusty two cents (Rust is awesome too ;)).

118 points by ingve 3y ago

hayst4ck 3y ago

I remember understanding error messages a lot better after taking compilers.

dietr1ch 3y ago
The real discovery to me seems that you are actually supposed to read through the errors, and that it's ok to not understand them completely. As a TA I got to see huge jumps in productivity and independence on students that read a couple more lines and reasoned instead of bailing out at the first ugly line.

nayuki 3y ago

> And because compilers are largely deterministic closed-system problems -- for each input, there is one and only output Not even close! Optimization and code generation is a fantastically hard problem full of heuristics and tradeoffs. There is definitely more than one way to compile C source code to x86 binary code. There is even more than one way to compile TypeScript to JavaScript if you consider things like whitespace, indentation, and constant folding. The rest of the article is alright.

mathisfun123 3y ago
+1 Ya that's a hilariously naive take (the quoted line not your response) given PGO, to say nothing of MLGO.
ehaliewicz2 3y ago
Pretty sure he means given a single compiler.
WalterBright 3y ago
The compiler is deterministic - for the same inputs, you'll get the same outputs. Unless you've got memory corruption in it.
- burjui 3y ago
  Or unless you iterate over randomized hashtables to produce some output, e.g. function sections in an executable. Though that doesn't change the semantics and is basically rearranging coins in your pocket.
- eru 3y ago
  Many optimizers (and other algorithms used in compilers) can benefit from some random bits. Though, of course, in practice you can use pseudo-random bits and fix the seed.
  - WalterBright 3y ago
    Having a compiler produce different code for the same source is a recipe for "I can't reproduce your bug and can't fix it".
mfranc42 3y ago
He probably meant that a compiler is a pure function for a given source file and a set of flags. Of course, if you change a compiler or flags, you can get something radically different, but you shouldn't get something radically different because it's Tuesday, midnight, your username starts with n, you have more than 3 hard drives, or because it reads some bytes from /dev/urandom. It's bit of a stretch, sure, but I don't expect my performance problems to go away by recompiling stuff over and over again without changing either the code or flags and expecting the optimizer to make a better decision next time. It doesn't work that way.
- mathisfun123 3y ago
  >and expecting the optimizer to make a better decision next time. It doesn't work that way But in practice it does work exactly that way because of PGO and if we're precluding PGO then the observation is as banal as "programs that have no side-effects are pure". Like I get that the post is trying to paint some beautiful picture about how compiler passes are abstract beautiful transformations of representations of programs but it's not a useful picture at all.
  - slavapestov 3y ago
    > Like I get that the post is trying to paint some beautiful picture about how compiler passes are abstract beautiful transformations of representations of programs but it's not a useful picture at all. It is actually a very useful picture especially to a beginner. PGO is an edge case and not used a whole lot in practice. Many compilers do not support it at all, even production compilers. Someone learning to write a compiler does not need to think about PGO. And besides, a compiler with PGO is still a pure function of source + flags + profile.
    - mathisfun123 3y ago
      >PGO is an edge case and not used a whole lot in practice. Many compilers do not support it at all, even production compilers. Both clang and gcc support `-fprofile-generate`. Beyond that generic infrastructure, in my area (DL compilers) if you're not doing PGO/autotuning you're not serious. >Someone learning to write a compiler does not need to think about PGO. That's like saying someone learning to write a compiler doesn't need to think about optimization at all - sure maybe the first time. But then every time after that it should be at the forefront of your mind.
armchairhacker 3y ago
There are multiple valid ways to compile a source with the same semantics, but a decent compiler should absolutely be deterministic. Imagine libraries which compile fine 99% of the time, but produce the wrong semantics every 1%: - Bug in your program? Could be a dependency of a dependency built wrong, better do a full clean and rebuild. - All of your pre-release tests passed? The code you shipped doesn't work, because you hit that unlucky 1%. Imagine how bad this would be back when software was released on CDs... - Have 70 dependencies which are like this (not hard in the webscale era)? Now your CI needs to retry every build up to 10 times, because every build has a ~63.4% chance of failing. And there's still ~1% chance your CI fails anyways because you got 10 unlucky builds in a row. I'm sure there are more stories of these kinds of issues...
- eru 3y ago
  > There are multiple valid ways to compile a source with the same semantics, but a decent compiler should absolutely be deterministic. Imagine libraries which compile fine 99% of the time, but produce the wrong semantics every 1%: That's not the only kind of non-determinism, you know? Lots of algorithms benefits from access to random bits, too.
  - armchairhacker 3y ago
    The context is > for each input, there is one and only output A randomized algorithm which uses non-determinism but produces the same output is OK. Also, psuedo-randomness is OK as long as the same program compiled in the same version of the compiler always gets the same seed. But if the algorithm can produce different output causing the same program to compile to different assembly, that's a problem. Unless you can formally prove that every possible variation will have the same behavior, but formal methods + non-determinism is hard, so it usually isn't worth it. Even random hash order in hashmaps can create problems: see https://github.com/rust-lang/rust/issues/84447 https://github.com/rust-lang/rust/issues/84447 and https://github.com/rust-lang/rust/pull/82272#issuecomment-825124318 https://github.com/rust-lang/rust/pull/82272#issuecomment-82..., though this is a very small issue in the diagnostic reporter and not a case of 2 valid programs with different semantics.
nayuki 3y ago
So, the downvotes and replies warrants a follow-up comment. I support deterministic compilers due to deterministic builds. For a given input source code, compiler executable, and command-line flags, it should always produce the same binary, regardless of the time of day, random number generator, I/O, threading, environment, etc. My refutation of the article is that he made it sound like a compiler is like computing Fibonacci numbers - here are all the valid inputs, here is how each one maps to its one and only correct output answer, so fill in the code to accomplish that. Also in the previous paragraph he wrote: > Because the most basic compiler architecture is standard, you have limited boundaries and degrees of freedom when designing one. This might sound restricting, but actually, it's freeing because you get to play in a predictable sandbox.

xwowsersx 3y ago

What are some good resources/courses/books for learning compilers, especially in a hands-on way? "Crafting Interpreters" seems to be well-liked, is that a decent place to start? Appreciate any other tips.

eru 3y ago
You might like https://smunix.github.io/dev.stephendiehl.com/fun/index.html https://smunix.github.io/dev.stephendiehl.com/fun/index.html
ogennadi 3y ago
A PL researcher recommended [1] precisely cuz it avoids parsing and focuses on interpretation. [1] https://cs.brown.edu/courses/cs173/2012/book/ https://cs.brown.edu/courses/cs173/2012/book/
azhenley 3y ago
I wrote a tutorial series for my students: Let’s make a Teeny Tiny compiler. It’s much smaller than Crafting Interpreters, so I’d recommend it before you go there to test the waters. https://austinhenley.com/blog/teenytinycompiler1.html https://austinhenley.com/blog/teenytinycompiler1.html
- ludicast 3y ago
  Very well done. Took a brief glance through your series and seems to cover most of the important deets.
- xwowsersx 3y ago
  This looks very nice. Thank you!
urthor 3y ago
My suggestion is Crafting Interpreters + a different programming language to Java. YMMV, but it's hard to genuinely learn from Crafting Interpreters. All the code is already written for you.

whartung 3y ago

If no other reason, compilers are just great fun and really satisfying to write. Watching your compiler take a simple expression and spit out a bunch of code referencing locals, referencing globals, type conversions and coercions, function calls, managing precedence. This little thing created all this code. It’s exciting. Especially the first time, it’s magic. It’s a lot of fun. Once I wrote a DSL for a rule system, compiled down into Java source. Later, I wrote another higher level rule system that generated the DSL. At one point I think there was a USENET .sig line that read “Will write code that writes code that writes code for food.” Indeed.

quickthrower2 3y ago

Helps if your company pays you to just do compilers full time and nothing else; not even a colleague to need to talk to!

freilanzer 3y ago

Writing a compiler is still on my list since a few years, but everytime I start I get stuck in the parser. It just doesn't seem to click with me. On the next couple of weekends I'll start again with Flix (flix.dev) and maybe Crafting Interpreters. Wish me luck.

Georgelemental 3y ago
In my compilers class in university, the prof skipped over parsing entirely—our source code was Racket S-expressions.
- freilanzer 3y ago
  Good, it's not the most important or interesting part imo. I also had an entire course about parsing, just not about compilers, and I don't see why many professors give it such an amount of attention.
jjice 3y ago
Something to consider is a parser generator for your language. They get a lot of flack online these days for some reason from people saying "a recursive descent parser is faster and not that hard", but they're generally time consuming if you just want to get something going. PLY (or maybe it's SLY now) for Python is really great.
drdude 3y ago
During my 2015 Compilers class, it was indeed the worst step and hardest to get right. We spent (my and my team mate) about 60%+ of the time making that parser actually parse. The lexing, tokenizing, etc is nothing compared to it. In another project, I used Antlr to avoid the headaches, but there are definitely better alternatives out there (some one mentioned Sly in the comments). Right now, if I want to mess with some transformation passes for an existing language, I would just look for LLVM and Clang for C for example (readily made front end, and backend with hackable middle end). P.S. I am a hobbyist at this stage and you can consider me knowing nothing about LLVM. My advice is based on my friends' (same colleague) who works for nVidia for their CUDA compiler using LLVM. Another reason for me to be interested in LLVM is that I used JVM languages (Scala, Java) for the past 20+ years and with GraalVM and its polyglot support for LLVM based languages; whose support was added using LLVM. my rusty two cents (Rust is awesome too ;)).