4 ms·
Compiler Construction: The Art of Niklaus Wirth (2000) [pdf]
- userbinator 9y agoGenerate good code from the beginning; don't generate bad code and optimize later Unfortunately this is something that no compiler I know of does, as evidenced by their -O0 being far worse than even what a naive Asm programmer (human) could do, and it's one of the things that irks me about compilers. Dataflow-directed, "work backwards" techniques might be the solution to this, but once again I don't know of any compilers that do it. On the other hand, his points about using recursive-descent parsing seem to agree with the majority of widely-used compilers. However, this is factually incorrect: I even think that the availability of powerful bottom-up parser generators such as Yacc are responsible for the cryptic syntax of C. Dennis Ritchie's first C compiler used recursive descent. Yacc itself was written in C, so it could not have come before. You can see the sources yourself here: https://news.ycombinator.com/item?id=5748672 https://news.ycombinator.com/item?id=5748672
- chubot 9y agoI agree he is wrong on that point. The recursive descent is easy to see here: http://minnie.tuhs.org/cgi-bin/utree.pl?file=V6/usr/source/c/c02.c http://minnie.tuhs.org/cgi-bin/utree.pl?file=V6/usr/source/c... Search for statement() and forstmt(). (This site has a more modern, easier-to-read version of the Github files, which at least has #defines rather than hard-coded ints!!!) But a large part of it is also Dijikstra's shunting yard algorithm: http://minnie.tuhs.org/cgi-bin/utree.pl?file=V6/usr/source/c/c00.c http://minnie.tuhs.org/cgi-bin/utree.pl?file=V6/usr/source/c... Read an expression and return a pointer to its tree. It's the classical bottom-up, priority-driven scheme. The initflg prevents the parse from going past "," or ":" because those delimitesrs are special in initializer (and some other) expressions. tree() Related post: Code for the Shunting Yard Algorithm, and More http://www.oilshell.org/blog/2017/04/22.html http://www.oilshell.org/blog/2017/04/22.html
- seanmcdirmid 9y agoPrecedence parsing is surprisingly robust and error tolerant, as well as being bottom up. Sans braces, it can be used for much of your expression syntax depending on how overloaded your terminals are.
- vidarh 9y agoYou can use it for braces too, with some relatively simple additional rules. Braces the way they're used in most languages are "just" a special case of parentheses: You need to recurse, and the closing parenthesis/brace needs to trigger reduce all the way to a single value. If you're willing to sacrifice a bit more generality you can parse a lot more. E.g. my (very much in-progress and incomplete) Ruby compiler uses precedence parsing with tweaks to parse most of the Ruby grammar, including blocks (do/end, {/}), array indices and initializers (foo[1], vs [1,2,3]) and more. It's been hell to adjust the priorities, and it's not correct yet, but I also think it can be cleaned up quite a bit more. The biggest pain point, actually, is tidying up the generated tree to remove superfluous nodes and flaten various bits, and that's where I'll need to do the most work to simplify. There are of course ugly parts of this with Ruby that ruined my originally quite nice and clean generic shunting yard code. E.g. if "foo" is a local variable "foo [1]" should parse as "foo.[](1)" (that is '[]' is a method name), while if "foo" is not a local variable, it is implicitly a method call, and "foo [1]" should parse as "foo([1])" with "self" as implicit receiver. I've for now resolved that by having a few "artificial" terminals to handle this and a few other ambiguities that are picked based on context and resolved later, but I'm really not happy about it. Worst case is I "surrender" and convert it to a recursive descent like the higher levels of the grammar, but I want to see what I can do with the current one first. Currently the full parser, which still lacks some parts of Ruby is about 1600 lines of Ruby (including the lexical tokenizer and some generic parser/scanner utility classes), which I'm distinctly displeased about - it's much smaller than MRI, but not as much smaller as I think should be possible, especially since it's still missing pieces; granted there's a lot of comments, but I think parsing Ruby in Ruby should be doable in <1000 lines of Ruby code using recursive descent + precedence parsing despite Ruby's many idiosyncracies. Less if you exclude the code for a decent generic parser library. I think that says a lot of the simplicity of applying both recursive descent and precedence parsing..
- mojuba 9y ago> Unfortunately this is something that no compiler I know of does Turbo Pascal (and Delphi), originally influenced by Wirth's books did exactly that. It was an incredibly fast compiler that generated surprizingly decent binaries.
- e12e 9y agoI've seen people imply that latest generation c compilers (gcc,clang etc) generate quite a lot better code than these previous generation compilers. Partly I guess turbo Pascal didn't to much auto vectorization for example. Unsure about loop unrolling. I'm sure it helped that Pascal had a IMNHO saner calling convention (more like the current amd64 convention) - so would utilise register for passing arguments rather than always using the stack.
- Narishma 9y agoI doubt vectorization (automatic or not) was relevant during Turbo Pascal's era.
- e12e 9y agoTrue, but it's relevant today (since around 1996 with the mmx instruction set). And if some people are arguing today that you can have single pass, fast and simple, and get ~max performance on modern architecture. I'm not saying you can't, I'm just saying that "as fast machine code as early 90s era c compilers" might not translate to as fast as today's c++ compilers machine code.
- vidarh 9y ago>> Generate good code from the beginning; don't generate bad code and optimize later > Unfortunately this is something that no compiler I know of does, You're probably right compared to modern compilers. What you need to compare to are the compilers of the era, which were truly abysmal. It's not that the Wirth compilers generated fantastic code (e.g. at least one of Wirths students explored adding much more aggressive optimization to his Oberon compiler), but they generated code that was a great deal better than a lot of non-Wirth style compilers at the time. Some compilers of the time even depended on peephole optimizer passes because the code they generated was so bad that even simple 2-3 instruction peephole passes were enough to drastically improve the code. There was little reason for this. E.g. most of the time it was a matter of as basic stuff as passing on information about the registers to use rather than the dumb/naive approach of generating everything using scratch registers that you move things to/from. I remember back in my asm days that I once had the C source for a GUI component I wanted to use, but the code the C compiler I had available generated was so awful that in exasperation I compiled it, disassembled it, and proceeded to manually clean it up. I deleted about half the instructions of about several thousand lines of compiler output, with very minimal fixups.
- sitkack 9y agoI did something similar, I was a novice C programmer, and had a problem that could have used some `rot` instructions that weren't available, so I used the emit asm flag to generate stubs and wrote the function in asm, it would have taken me ages to do it from scratch, but fixing up the output of the C compiler took about an hour of experimentation.
- lboasso 9y agoWirth's compilers generated reasonably good code: 80% of the performance of optimizing compilers with 20% of the effort. The first Java client jit compiler, was developed by Robert Griesemer (former PhD student of Wirth). The design of the compiler is described in the paper "A compiler for the java hotspot virtual machine", published in the same book: "The School of Niklaus Wirth: The Art of Simplicity".
- gsg 9y agoThis is nonsense. Modern compilers don't work by generating the results you see with -O0 and then optimising; the poor quality of -O0 code is the result of skipping register allocation. > Dataflow-directed, "work backwards" techniques might be the solution Destination driven code generation is a known technique. It doesn't generate good enough results to have gotten much attention (better than what you get from -O0, though).
- lboasso 9y agoI wrote a simple self-hosting compiler to showcase Niklaus Wirth's approach to writing compilers: https://github.com/lboasso/oberonc https://github.com/lboasso/oberonc Single pass compilers have their advantages.
- sitkack 9y ago"The School of Niklaus Wirth" [0] contains this essay and many others on how simplicity can be an essential quality of a system. I vastly under appreciated how well Wirthian languages are designed, even after toying with the excellent offshoot, Modula3 [1]. In my youth I was too concerned with raw performance and syntax. In my old age I am concerned about semantics and maintainability. [0] https://www.amazon.com/School-Niklaus-Wirth-Art-Simplicity/dp/1558607234 https://www.amazon.com/School-Niklaus-Wirth-Art-Simplicity/d... [1] https://github.com/modula3/cm3 https://github.com/modula3/cm3
- lboasso 9y agoI own a copy of "The School of Niklaus Wirth" :) I really appreciate the pragmatism of Wirth's designs and his quest for simplicity.
- pedrow 9y agoAs a matter of interest do we know when this was written? The PDF has a date of 2007 but the latest reference is Wirth's book, published in 1996.
- vidarh 9y agoThis looks to be the original publication [1]: Hanspeter Mössenböck: Compiler Construction - The Art of Niklaus Wirth. Chapter in: Böszörmeny et al.(eds): The School of Niklaus Wirth, dpunkt.verlag 2000, pp.55-68 An extensive list of Mössenböck's publications can be found here[2] [1] http://ssw.jku.at/Research/Papers/Moe00b.html http://ssw.jku.at/Research/Papers/Moe00b.html [2] http://ssw.jku.at/Research/Papers/ http://ssw.jku.at/Research/Papers/ (while this from the page looks like it's for his institute, it looks like all of them have him as at least co-author, and they include papers from his past institutions including his time at ETHZ with Wirth; e.g. a favourite of mine of his earlier paper is this collaboration with Marc M. Brandis on generating SSA forms for structured languages in a single pass [3] from '94 - as a confessed Niklaus Wirth fanboy I read most of the papers that came out of his research group in the early 90's..) [3] http://ssw.jku.at/Research/Papers/Moe94.html http://ssw.jku.at/Research/Papers/Moe94.html EDIT: I of course had to check, and Amazon (at least in the UK) has the book this is from (The School of Niklaus Wirth: The Art of Simplicity ), though it's expensive... I just had to share this hilarious find from one of the reviews: "For me, this book is one to keep forever. I enjoyed every page (apart from the section written by Dijkstra since it was handwritten..)." EDIT2: And having been seduced into buying this book, I can confirm Dijkstra's contribution (On the transitive closure of a well founded relation; dedicated to Niklaus Wirth) is in fact included in his handwritten form. I wish I had handwriting like that (but not enough to put in the effort).
- sctb 9y agoThanks for sleuthing! We've updated the title.
- tom_mellior 9y ago> in: Böszörmeny et al.(eds): The School of Niklaus Wirth I used to have that book somewhere. All of it was nicely typeset, except for Dijkstra's chapter, which was facsimile copies of (nicely) handwritten text.
- mojuba 9y ago> Don't let the compiler repair poor programming style ... This includes some cases of common subexpression elimination, loop invariant code motion and copy propagation Unfortunately in languages like C++ these inefficiencies often originate from inline function expansion rather than the programmer and thus are absolutely necessary. > Strive for short compilation times I wish designers of Swift heard this... Swift's build times can be horrifically slow for no good reason, it seems. I think slow build times have become a new norm pretty much like e.g. graphics display boot up times, i.e. someone at some point convinced the users that it's the way it should be and as a new norm no vendor strives to improve it.
- fao_ 9y ago> someone at some point convinced the users that it's the way it should be and as a new norm no vendor strives to improve it. People tend to defend slow boot up times with arguments that boil down to the aphorism: Better the code be correct than fast. Unfortunately most modern software out there is neither, which is where the whole argument falls apart.