6 ms·

I really hope this wouldn't end up like 95% of other "compiler" classes that usually just focus on parsing, rather than on emitting code, cpu architectures & op

I really hope this wouldn't end up like 95% of other "compiler" classes that usually just focus on parsing, rather than on emitting code, cpu architectures & optimizing

mhh__ 6y ago
Unlikely. Although if I ever get round to it I'd like to start an open source compiler textbook to try and centralise knowledge in this area since the field is simply too advanced to summarise in a single book these days.
- jcranmer 6y ago
  There's definitely a lack of advanced compiler textbooks, and the venerable Dragon book definitely shows its age nowadays. I've gone so far as to write an outline for what I'd want to cover, and came to the conclusion that it needs several books to adequately cover the material. And there's a lot of topics that I am personally too ignorant of to do any justice to.
  - mhh__ 6y ago
    The latter point is why I think it has to be open source rather than a single man or woman's work
  - pwdisswordfish6 6y ago
    This is the same path that led to The Art Of Computer Programming.
m12k 6y ago
Sounds like you're looking for a "Compilers 201" class.
hvidgaard 6y ago
Going from a grammar to an AST is the first and one of the hardest step IMO. And there is plenty of open source tools for exactly that and in general it is uninteresting and boring. Transforming the AST to something that can be used to emit instructions is the major thing to focus on IMO. Getting to an AST that only use very simple primitives that enables general optimizations and emitting code is hard and a different task every time.
- mhh__ 6y ago
  The semantic analysis is by far and away the hardest thing day to day. Parsing is easy
  - azhenley 6y ago
    Parsing most certainly is *not* easy for someone new to compilers. My students remind me of that all the time.
    - jcranmer 6y ago
      Lexing and parsing probably falls into the category of "obvious once you learn it, mystifying until then." (Although, that said, compiler courses could probably do well to ditch a lot of the LL(1)/LR(1) parsing theory to focus on other topics instead. You still need to teach grammars, and focus a bit on how to actually parse grammars to AST under recursive descent, including expression precedence, but you could probably excise a lot of the parser generator theory.)
      - mhh__ 6y ago
        I know embarrassingly little parser theory - I definitely couldn't write a decent parser generator without looking it up in a book for a few hours - but at least there is a theory: Semantic analysis has lots of mathematical symbology to describe it, doesn't help you write code for the most part.
        marcosdumay 6y ago
        As strange as it looks, parser theory is not very relevant on practice for writing parsers. You just use some parser generator or a parser combinators library if your language allows them, and you won't have many problems (except for maybe they being slow). It is way more relevant for optimizing parsers performance and for designing languages syntax.
        6y ago
ofrzeta 6y ago
Arguably generating code for a real CPU requires so much knowledge about that specific hardware that it's not really any longer about compilers. Therefore most compiler courses target a simpler RISC CPU because it's easier to teach the algorithms behind it.
qalmakka 6y ago
While there are (a lot) of parser generators out there, learning how to parse and validate text using a LL recursive-descent parser is still very useful, because you can easily implement one yourself and have lots of possible applications. Writing an LL parser by hand requires nothing more than a bit of theoretical knowledge and a few man-weeks. Heck, if you really wish, you can even implement your own C parser in a few weekends. Meanwhile, writing a (non-trivial, i.e. something that does more than MOV, JMP, CALL, CMP, ..) backend and optimizer requires a few decades and an investment of a few million dollars. That's why most languages nowadays either emit C (which I find is a very effective way to learn code generation, by the way) or interface with LLVM. Even for the sake of learning, writing a backend that generates actual code is the equivalent of milling your own flour in order to bake bread: fancy, but pointless. As much as people stopped milling their own flour centuries ago, people stopped writing compiler their own backends a long time ago, because it makes close to 0 sense unless you plan to cover very specific use cases. I think if you are interested in code generation, you should rather learn the math behind optimizing code and hack a bit around something existing like LLVM or GCC, because that represents better how stuff is done in practice. Writing a simple JIT compiler is also IMHO time well, but it's arguably different than writing a compiler backend.
- chrisseaton 6y ago
  > Meanwhile, writing a (non-trivial, i.e. something that does more than MOV, JMP, CALL, CMP, ..) backend and optimizer requires a few decades and an investment of a few million dollars. I think that's massively over-estimating it, based on practical experience of such compilers being built. > most languages nowadays either emit C (which I find is a very effective way to learn code generation, by the way) or interface with LLVM I think this is also not grounded in reality. I rarely see a language emitting C. LLVM is popular but not as universal as you're making out.
  - qalmakka 6y ago
    > I think that's massively over-estimating it, based on practical experience of such compilers being built. Who still writes backends from scratch nowadays (i.e. after ~2010)? The only real examples from recent times I'm aware of are Go and Cranelift: the first is backed by Google and still (arguaby) generates worse code than GCC and LLVM, the second is vastly experimental. > LLVM is popular but not as universal as you're making out If you exclude JITs (such as the CLR, JVM and JS engines, all of which have massive corporate backing behind) almost a 100% of _all_ languages that came out in the last decade use LLVM for code generation, even those coming from big players: - Swift (LLVM) - Rust (LLVM) - Zig (LLVM) - Julia (LLVM) - Pony (LLVM) - Kotlin Native (LLVM) The only other recent languages that come to my mind are Nim and Vala, and the both generate C. Outside of these, no new language has ever rolled out its own backend, unless there was a huge (Google-class) corporation behind. The only compilers I know which have their own backends and are still relevant (i.e. they are used in the real world) are: - FreePascal - GHC - OCaml - DMD (now largely supplanted by GDC and LDC) These all have been started in '90s or before, and thus had their own backends already when LLVM became popular. Everything else is JIT, or is either backed by very big companies (such as Microsoft) or uses GCC. Why would anyone waste time writing a compiler backend nowadays? It took LLVM almost 20 years to reach performance parity with GCC, and still it is sometimes problematic due to not supporting as many architectures as GCC.
norswap 6y ago
Lecturer here - we will definitely cover some other topics, including semantic analysis (type checking, etc), code generation, basic optimizations, ... I still expect parsing will be the major part of the course, maybe 50%? There are some good reasons for that too. Parsing has a rich (and interesting) theoretical background that you don't really have with basic semantic analysis (unless you go to symbolic execution) and optimizations. It's more of an engineering-only angle (which we cover), while parsing has both aspects. Background in parsing is also more likely to serve most the average student in practice :) I also think it's less easy to figure out on your own.
- setr 6y ago
  > Lecturer here - we will definitely cover some other topics, including semantic analysis (type checking, etc), code generation, basic optimizations, ... How is this being updated? I've noted that all current videos were posted on Feb 1, but I guess there's more coming up? Also the video times are a little weird -- I assumed this was being pulled from your normal classes, but the video lengths range from 10 min to 30 min kind of randomly. I suppose my main question is: whats the background to this course?
  - norswap 6y ago
    This is the content for the first two weeks. It will updated regularly - probably every week starting from next week (I'd put it all out if I had it, but planning and recording these things is an ongoing process!) As for the context, this is the UCLouvain master compiler class. We currently can't have in-person classes in Belgium (because Covid obviously). Since we're no longer bound by the usual 2h lecture format (and it's the first time I'm giving the class), I figure I might as well go with a timing that is natural, and that depends on the material, what I have to say etc. If anything, I'm thinking of moving towards more consistently shorter videos, as the ~30 minutes videos are both harder for me to make and for the students to consume. Sessions that include live coding or code reviews will probably still be longer.

I really hope this wouldn't end up like 95% of other "compiler" classes that usually just focus on parsing, rather than on emitting code, cpu architectures & optimizing

mhh__ 6y ago

Unlikely. Although if I ever get round to it I'd like to start an open source compiler textbook to try and centralise knowledge in this area since the field is simply too advanced to summarise in a single book these days.

jcranmer 6y ago
There's definitely a lack of advanced compiler textbooks, and the venerable Dragon book definitely shows its age nowadays. I've gone so far as to write an outline for what I'd want to cover, and came to the conclusion that it needs several books to adequately cover the material. And there's a lot of topics that I am personally too ignorant of to do any justice to.
- mhh__ 6y ago
  The latter point is why I think it has to be open source rather than a single man or woman's work
- pwdisswordfish6 6y ago
  This is the same path that led to The Art Of Computer Programming.

m12k 6y ago

Sounds like you're looking for a "Compilers 201" class.

hvidgaard 6y ago

Going from a grammar to an AST is the first and one of the hardest step IMO. And there is plenty of open source tools for exactly that and in general it is uninteresting and boring. Transforming the AST to something that can be used to emit instructions is the major thing to focus on IMO. Getting to an AST that only use very simple primitives that enables general optimizations and emitting code is hard and a different task every time.

mhh__ 6y ago
The semantic analysis is by far and away the hardest thing day to day. Parsing is easy
- azhenley 6y ago
  Parsing most certainly is *not* easy for someone new to compilers. My students remind me of that all the time.
  - jcranmer 6y ago
    Lexing and parsing probably falls into the category of "obvious once you learn it, mystifying until then." (Although, that said, compiler courses could probably do well to ditch a lot of the LL(1)/LR(1) parsing theory to focus on other topics instead. You still need to teach grammars, and focus a bit on how to actually parse grammars to AST under recursive descent, including expression precedence, but you could probably excise a lot of the parser generator theory.)
    - mhh__ 6y ago
      I know embarrassingly little parser theory - I definitely couldn't write a decent parser generator without looking it up in a book for a few hours - but at least there is a theory: Semantic analysis has lots of mathematical symbology to describe it, doesn't help you write code for the most part.
      - marcosdumay 6y ago
        As strange as it looks, parser theory is not very relevant on practice for writing parsers. You just use some parser generator or a parser combinators library if your language allows them, and you won't have many problems (except for maybe they being slow). It is way more relevant for optimizing parsers performance and for designing languages syntax.
        6y ago

ofrzeta 6y ago

Arguably generating code for a real CPU requires so much knowledge about that specific hardware that it's not really any longer about compilers. Therefore most compiler courses target a simpler RISC CPU because it's easier to teach the algorithms behind it.

qalmakka 6y ago

While there are (a lot) of parser generators out there, learning how to parse and validate text using a LL recursive-descent parser is still very useful, because you can easily implement one yourself and have lots of possible applications. Writing an LL parser by hand requires nothing more than a bit of theoretical knowledge and a few man-weeks. Heck, if you really wish, you can even implement your own C parser in a few weekends. Meanwhile, writing a (non-trivial, i.e. something that does more than MOV, JMP, CALL, CMP, ..) backend and optimizer requires a few decades and an investment of a few million dollars. That's why most languages nowadays either emit C (which I find is a very effective way to learn code generation, by the way) or interface with LLVM. Even for the sake of learning, writing a backend that generates actual code is the equivalent of milling your own flour in order to bake bread: fancy, but pointless. As much as people stopped milling their own flour centuries ago, people stopped writing compiler their own backends a long time ago, because it makes close to 0 sense unless you plan to cover very specific use cases. I think if you are interested in code generation, you should rather learn the math behind optimizing code and hack a bit around something existing like LLVM or GCC, because that represents better how stuff is done in practice. Writing a simple JIT compiler is also IMHO time well, but it's arguably different than writing a compiler backend.

chrisseaton 6y ago
> Meanwhile, writing a (non-trivial, i.e. something that does more than MOV, JMP, CALL, CMP, ..) backend and optimizer requires a few decades and an investment of a few million dollars. I think that's massively over-estimating it, based on practical experience of such compilers being built. > most languages nowadays either emit C (which I find is a very effective way to learn code generation, by the way) or interface with LLVM I think this is also not grounded in reality. I rarely see a language emitting C. LLVM is popular but not as universal as you're making out.
- qalmakka 6y ago
  > I think that's massively over-estimating it, based on practical experience of such compilers being built. Who still writes backends from scratch nowadays (i.e. after ~2010)? The only real examples from recent times I'm aware of are Go and Cranelift: the first is backed by Google and still (arguaby) generates worse code than GCC and LLVM, the second is vastly experimental. > LLVM is popular but not as universal as you're making out If you exclude JITs (such as the CLR, JVM and JS engines, all of which have massive corporate backing behind) almost a 100% of _all_ languages that came out in the last decade use LLVM for code generation, even those coming from big players: - Swift (LLVM) - Rust (LLVM) - Zig (LLVM) - Julia (LLVM) - Pony (LLVM) - Kotlin Native (LLVM) The only other recent languages that come to my mind are Nim and Vala, and the both generate C. Outside of these, no new language has ever rolled out its own backend, unless there was a huge (Google-class) corporation behind. The only compilers I know which have their own backends and are still relevant (i.e. they are used in the real world) are: - FreePascal - GHC - OCaml - DMD (now largely supplanted by GDC and LDC) These all have been started in '90s or before, and thus had their own backends already when LLVM became popular. Everything else is JIT, or is either backed by very big companies (such as Microsoft) or uses GCC. Why would anyone waste time writing a compiler backend nowadays? It took LLVM almost 20 years to reach performance parity with GCC, and still it is sometimes problematic due to not supporting as many architectures as GCC.

norswap 6y ago

Lecturer here - we will definitely cover some other topics, including semantic analysis (type checking, etc), code generation, basic optimizations, ... I still expect parsing will be the major part of the course, maybe 50%? There are some good reasons for that too. Parsing has a rich (and interesting) theoretical background that you don't really have with basic semantic analysis (unless you go to symbolic execution) and optimizations. It's more of an engineering-only angle (which we cover), while parsing has both aspects. Background in parsing is also more likely to serve most the average student in practice :) I also think it's less easy to figure out on your own.

setr 6y ago
> Lecturer here - we will definitely cover some other topics, including semantic analysis (type checking, etc), code generation, basic optimizations, ... How is this being updated? I've noted that all current videos were posted on Feb 1, but I guess there's more coming up? Also the video times are a little weird -- I assumed this was being pulled from your normal classes, but the video lengths range from 10 min to 30 min kind of randomly. I suppose my main question is: whats the background to this course?
- norswap 6y ago
  This is the content for the first two weeks. It will updated regularly - probably every week starting from next week (I'd put it all out if I had it, but planning and recording these things is an ongoing process!) As for the context, this is the UCLouvain master compiler class. We currently can't have in-person classes in Belgium (because Covid obviously). Since we're no longer bound by the usual 2h lecture format (and it's the first time I'm giving the class), I figure I might as well go with a timing that is natural, and that depends on the material, what I have to say etc. If anything, I'm thinking of moving towards more consistently shorter videos, as the ~30 minutes videos are both harder for me to make and for the students to consume. Sessions that include live coding or code reviews will probably still be longer.