4 ms·

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

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).

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).