5 ms·

Compilers are complicated things -- too much to attempt to cover in a single quarter. There is a followup course, CS243 which focuses on the optimization aspec

Compilers are complicated things -- too much to attempt to cover in a single quarter. There is a followup course, CS243 which focuses on the optimization aspect. http://suif.stanford.edu/~courses/cs243/ http://suif.stanford.edu/~courses/cs243/

wtetzner 11y ago
Right, but while parsing is important, it's the least interesting aspect of implementing a compiler. It would be better if more time was spend on starting with an AST and generating code. Then at the end of the course, implement a parser to generate the AST.
- mafribe 11y ago
  That's exactly how I used to teach compilers. But the weaker students had a really hard time understanding the purpose of ASTs ("why don't you give the program to the code generator as a string?") no matter how often I pointed out why ASTs are a better data structure than strings from the POV of efficient code generation. And some students complained about this "unnatural" sequence of explaining compilers in the course evaluations. So I changed to teaching compilers in the standard order, lexing -> parsing -> type-checking -> code gen -> optimisation. No complaints any more. There is another dimension to this. While code gen and optimisations are more interesting than lexing/parsing almost no student will ever again write a code generator, let alone optimisations. OTOH, most programmers need to write little lexers and little parsers for little languages all the time. That's why a bit of facility with lexing/parsing and associated tools is hightly useful.
  - sklogic 11y ago
    You should have done it in a homoiconic language like Scheme, where nobody would be puzzled by a notion of an AST.
    - mafribe 11y ago
      Then my students would have been puzzled by Scheme, which they don't know. Incidentally, Scheme has a syntax too, so you need lexing and parsing to handle Scheme. The only advantage is that Scheme's syntax is simple. Moreover the problem of language representation doesn't go away. You still need to represent programs. The real problem is to understand that there are two level: programs and representations of programs. Avoiding to confuse the two is the real challenge, and it remains a challenge in Scheme.
      - sklogic 11y ago
        Sorry, I'm under a slow-ban here (currently like 2 posts in 6 hours allowance), so I'll answer to all your posts at once here. > Then my students would have been puzzled by Scheme, which they don't know. Maybe they're not ready for a compilers course then? You could have saved a lot of time and effort for them this way. > Incidentally, Scheme has a syntax too, so you need lexing and parsing to handle Scheme. It can have as much syntax as you want. Nobody cares - there is already a parser, ready to use, and you don't have to roll out your own. > The real problem is to understand that there are two level: programs and representations of programs. This is the most important takeaway from a compilers course. It makes sense to get there as soon as possible. Also, I'm a bit skeptical about your assessment of your students, from your words it sounds like you're teaching in a lunatics asylum. > https://news.ycombinator.com/reply?id=11281976 https://news.ycombinator.com/reply?id=11281976 > you need a platform independent memory model Sorry, this is a wishful thinking. A truly efficient concurrent language is always very much platform-specific (think of Occam on one side of the spectrum and OpenCL and Cuda on another). > nobody really knows what exactly the memory model is Really? I've seen a number of Coq/HOL/ACL2 precise memory models of certain architectures. > https://news.ycombinator.com/reply?id=11282014 https://news.ycombinator.com/reply?id=11282014 > idealised compilers have a beautiful pipeline structure A very practical compiler can also be built as a beautiful and simple pipeline. > By this reasoning, any computable problem is trivially simple, because I can translate it into ARM/x86/MIPS/... machine code, and machine code is just a linear list of trivial commands, i.e. I can "turn it into a laughably simple chain". You did not get it at all. You cannot translate "any code" into a linear trivial sequence with each step being nothing but some primitive form of term rewriting of a single input tree into a single output tree. A trivial proof for how badly wrong you are: you do not need a Turing-complete language to write a compiler. Now try to apply this to your "any computable problem" reasoning. > if you chain enough simple things, the result stops being simple. Incorrect. Such a chain is as simple as its most complex building block. Complexity does not add up. > Look for example at modern JIT compilers, tracing or otherwise. Firstly, we're talking about the proper compilers here. JIT is a totally different beast, it got a very severe performance constraint. Secondly, even JIT can be structured this way, and most of the existing JITs are idiotically, needlessly overcomplicated. > They are not simple by any stretch of the imagination. Sorry, but no, they are. Yes, the non-Turing-complete property breaks there, as well as with any other interpreter, but a Turing-complete subset of a JIT compiler can be very easily isolated. > https://news.ycombinator.com/reply?id=11279390 https://news.ycombinator.com/reply?id=11279390 > Optimisations are easy only if you can accept the optimisation process to be slow, and/or the resulting code buggy. And this is nothing but a FUD. Firstly, nanopass compilers are not any slower than the fused ones. In some cases they're faster, due to some of the nice properties of the immutability. Also, you can fuse some passes automatically, while still keeping your code trivial. Secondly, the simpler your passes are, the easier it is to reason about their correctness. Compare it to the notoriously shitty instcombine pass in LLVM, as it is an example of the opposite approach (the one you're apparently advocating).
sklogic 11y ago
My point is exactly the opposite - compilers are easy, probably easier than pretty much anything else. And courses like this do not help by pretending this is a complex topic and by obscuring what matters with unimportant minutiae (like parsing and such).
- mafribe 11y ago
  compilers are easy No. Modern, industrial-strength compilers are some of the most complicated pieces of technology we have. Indeed almost every part of the compiler pipeline, in particular parsing, type-inference, and optimisations, are active areas of research.
  - nickpsecurity 11y ago
    None of what you ssid means writing compilers is hard: just that the first ones or techniques are hard to do. Once it's done, it's another building block that can be chained together to solve similar problems. Using a ML or LISP with right primitives makes that even easier. Designing the right language and implementing modularly makes that easier. So, I'd say the industrial ones are as tough as they are because they support hard-to-compile languages with many dark corners while bring implemented in the same languages themselves. Make problem hard for yourself then it's hard. Make it easier then it's... still work but only a tiny fraction of what you alluded to.
  - agumonkey 11y ago
    It's far from trivial, but it is presented as more complex than it should. The parsing point is valid, when in AST land the rewrite / transform / optimize part, which could be seen as the most important one, seems more enjoyable and composable than the parsing stage which is often covered in great details (courses making you write BNF state matrices?).
  - astrange 11y ago
    Compilers are not really complicated compared to plenty of other hard topics. They're large, but they always separate out into different passes that you just run one after the other. You don't have to manage the program as a whole. And optimizations don't even matter anyway. x86 runs your -O1 program as fast as your -O3, and nobody has put a real accurate model of an x86 into a production compiler for the last decade.

wtetzner 11y ago

Right, but while parsing is important, it's the least interesting aspect of implementing a compiler. It would be better if more time was spend on starting with an AST and generating code. Then at the end of the course, implement a parser to generate the AST.

mafribe 11y ago
That's exactly how I used to teach compilers. But the weaker students had a really hard time understanding the purpose of ASTs ("why don't you give the program to the code generator as a string?") no matter how often I pointed out why ASTs are a better data structure than strings from the POV of efficient code generation. And some students complained about this "unnatural" sequence of explaining compilers in the course evaluations. So I changed to teaching compilers in the standard order, lexing -> parsing -> type-checking -> code gen -> optimisation. No complaints any more. There is another dimension to this. While code gen and optimisations are more interesting than lexing/parsing almost no student will ever again write a code generator, let alone optimisations. OTOH, most programmers need to write little lexers and little parsers for little languages all the time. That's why a bit of facility with lexing/parsing and associated tools is hightly useful.
- sklogic 11y ago
  You should have done it in a homoiconic language like Scheme, where nobody would be puzzled by a notion of an AST.
  - mafribe 11y ago
    Then my students would have been puzzled by Scheme, which they don't know. Incidentally, Scheme has a syntax too, so you need lexing and parsing to handle Scheme. The only advantage is that Scheme's syntax is simple. Moreover the problem of language representation doesn't go away. You still need to represent programs. The real problem is to understand that there are two level: programs and representations of programs. Avoiding to confuse the two is the real challenge, and it remains a challenge in Scheme.
    - sklogic 11y ago
      Sorry, I'm under a slow-ban here (currently like 2 posts in 6 hours allowance), so I'll answer to all your posts at once here. > Then my students would have been puzzled by Scheme, which they don't know. Maybe they're not ready for a compilers course then? You could have saved a lot of time and effort for them this way. > Incidentally, Scheme has a syntax too, so you need lexing and parsing to handle Scheme. It can have as much syntax as you want. Nobody cares - there is already a parser, ready to use, and you don't have to roll out your own. > The real problem is to understand that there are two level: programs and representations of programs. This is the most important takeaway from a compilers course. It makes sense to get there as soon as possible. Also, I'm a bit skeptical about your assessment of your students, from your words it sounds like you're teaching in a lunatics asylum. > https://news.ycombinator.com/reply?id=11281976 https://news.ycombinator.com/reply?id=11281976 > you need a platform independent memory model Sorry, this is a wishful thinking. A truly efficient concurrent language is always very much platform-specific (think of Occam on one side of the spectrum and OpenCL and Cuda on another). > nobody really knows what exactly the memory model is Really? I've seen a number of Coq/HOL/ACL2 precise memory models of certain architectures. > https://news.ycombinator.com/reply?id=11282014 https://news.ycombinator.com/reply?id=11282014 > idealised compilers have a beautiful pipeline structure A very practical compiler can also be built as a beautiful and simple pipeline. > By this reasoning, any computable problem is trivially simple, because I can translate it into ARM/x86/MIPS/... machine code, and machine code is just a linear list of trivial commands, i.e. I can "turn it into a laughably simple chain". You did not get it at all. You cannot translate "any code" into a linear trivial sequence with each step being nothing but some primitive form of term rewriting of a single input tree into a single output tree. A trivial proof for how badly wrong you are: you do not need a Turing-complete language to write a compiler. Now try to apply this to your "any computable problem" reasoning. > if you chain enough simple things, the result stops being simple. Incorrect. Such a chain is as simple as its most complex building block. Complexity does not add up. > Look for example at modern JIT compilers, tracing or otherwise. Firstly, we're talking about the proper compilers here. JIT is a totally different beast, it got a very severe performance constraint. Secondly, even JIT can be structured this way, and most of the existing JITs are idiotically, needlessly overcomplicated. > They are not simple by any stretch of the imagination. Sorry, but no, they are. Yes, the non-Turing-complete property breaks there, as well as with any other interpreter, but a Turing-complete subset of a JIT compiler can be very easily isolated. > https://news.ycombinator.com/reply?id=11279390 https://news.ycombinator.com/reply?id=11279390 > Optimisations are easy only if you can accept the optimisation process to be slow, and/or the resulting code buggy. And this is nothing but a FUD. Firstly, nanopass compilers are not any slower than the fused ones. In some cases they're faster, due to some of the nice properties of the immutability. Also, you can fuse some passes automatically, while still keeping your code trivial. Secondly, the simpler your passes are, the easier it is to reason about their correctness. Compare it to the notoriously shitty instcombine pass in LLVM, as it is an example of the opposite approach (the one you're apparently advocating).

sklogic 11y ago

My point is exactly the opposite - compilers are easy, probably easier than pretty much anything else. And courses like this do not help by pretending this is a complex topic and by obscuring what matters with unimportant minutiae (like parsing and such).

mafribe 11y ago
compilers are easy No. Modern, industrial-strength compilers are some of the most complicated pieces of technology we have. Indeed almost every part of the compiler pipeline, in particular parsing, type-inference, and optimisations, are active areas of research.
- nickpsecurity 11y ago
  None of what you ssid means writing compilers is hard: just that the first ones or techniques are hard to do. Once it's done, it's another building block that can be chained together to solve similar problems. Using a ML or LISP with right primitives makes that even easier. Designing the right language and implementing modularly makes that easier. So, I'd say the industrial ones are as tough as they are because they support hard-to-compile languages with many dark corners while bring implemented in the same languages themselves. Make problem hard for yourself then it's hard. Make it easier then it's... still work but only a tiny fraction of what you alluded to.
- agumonkey 11y ago
  It's far from trivial, but it is presented as more complex than it should. The parsing point is valid, when in AST land the rewrite / transform / optimize part, which could be seen as the most important one, seems more enjoyable and composable than the parsing stage which is often covered in great details (courses making you write BNF state matrices?).
- astrange 11y ago
  Compilers are not really complicated compared to plenty of other hard topics. They're large, but they always separate out into different passes that you just run one after the other. You don't have to manage the program as a whole. And optimizations don't even matter anyway. x86 runs your -O1 program as fast as your -O3, and nobody has put a real accurate model of an x86 into a production compiler for the last decade.