5 ms·

It was just a few days ago when I mentioned how often I see the dragon book held up as a punching bag. It seems that at some point the book, along with K&R, ha

by cxr 6y ago

It was just a few days ago when I mentioned how often I see the dragon book held up as a punching bag. It seems that at some point the book, along with K&R, have become the target for unsubstantiated criticism. I've pressed for details, and I've seen others do the same, but it never ends in anything concrete—just an implicit appeal to the new conventional wisdom that they do more harm than good. Reminds me of how "truth" gets synthesized on Reddit. Here's a counterexample: Russ Cox has a series on regular expressions, beginning with Regular Expression Matching Can Be Simple And Fast <https://swtch.com/~rsc/regexp/regexp1.html https://swtch.com/~rsc/regexp/regexp1.html>. In the last several years, it has become very well-received. In it, he lays out the case for Thompson NFAs, and also laments in some places about how the approach is not more widely known, having become a sort of lost knowledge. (See also Jonathan Blow's <https://www.youtube.com/watch?v=ZSRHeXYDLko https://www.youtube.com/watch?v=ZSRHeXYDLko>.) For all the criticism of the dragon book, though, you'd think that would mean enough people have read it that someone would have pointed out that Thompson is cited in Chapter 3, where his approach is described in some detail. I think that what's actually going on is that, like The Art Of Computer Programming, the dragon book is widely referenced and rarely read. Now, enter the 21st century meme factory. Having said that, the most recent comment I saw that was being casually dismissive of the dragon book—ironically for its "second-rate methods" that have "held back" compiler development—did motivate me into digging the book out, which itself led to me to spending an hour or so chasing down the source of McCarthy's "ho, ho, you're confusing theory with practice" quip, since the origin story of Lisp's eval is also told in Chapter 11 of the dragon book. <https://hypothes.is/a/pQs39pAhEeupnAuO5qfOeQ https://hypothes.is/a/pQs39pAhEeupnAuO5qfOeQ>

jnwatson 6y ago
I took a compilers class around the dragon book. I think the valid criticism is the sequence of the book. An undergraduate compiler class can only cover perhaps half the book. IMHO, the number of students that would benefit from learning about AST transformation and code gen vastly outnumbers the folks that would benefit from learning about finite automata transformation (and I took a dedicated course in that). There simply aren’t that many folks working on regex engines.
- marktangotango 6y ago
  > There simply aren’t that many folks working on regex engines. Yes that's true but there are A LOT of leetcode/hankerrank problems that are trivially solvable when one has a solid grasp of DFA and state machines in general!
- vishnugupta 6y ago
  I second this based on my experience. My masters thesis was in code generation for Haskell where in I spent fair bit of time learning tree pattern matching, AST manipulation, register allocation etc. One can achieve a non trivial speed up by understanding these different phases of code generation. Another reason, in the context of compilers, is that there’s not much to be gained by micro-optimizing lexing and parsing. After all, a code is compiled just once and executed multiple times. So you know where much of the fun lies. The undergrads unfortunately usually miss out on the meatier part of the compiler course.
  - fanf2 6y ago
    It used to be the case that lexing was the hottest part of a compiler, because it had to touch every byte of source and subsequent phases did not have so much data to crunch. But that stopped being true in the 1990s as optimizing compilers became mainstream technology.
- criddell 6y ago
  > An undergraduate compiler class can only cover perhaps half the book. When I took a compilers course that used this book, the professor had his own syllabus and would use the dragon book in support of his plan. We jumped around quite a bit and certainly didn't use all of the book. That course was one of my favorites and had a huge impact on me. I haven't written any compilers, but have used a lot of the concepts (especially state machines) over the years.
- jll29 6y ago
  > There simply aren’t that many folks working on regex engines. You'd be surprised: there's even a dedicated annual international conference on implementation of automata that has been going since 1996: <https://link.springer.com/conference/wia https://link.springer.com/conference/wia> There are constantly new algorithms, libraries, tools and applications around regular languages and regular relations (an extension of regular expression that is more elegant, symmetric, expressive and takes a lot of the ugliness of regexes out). Simplifying somewhat, finite state transducers are NFAs "with output". See e.g. FOMA at <https://fomafst.github.io/ https://fomafst.github.io/>.
spekcular 6y ago
> I've pressed for details, and I've seen others do the same, but it never ends in anything concrete—just an implicit appeal to the new conventional wisdom that they do more harm than good. Really? Merits of the criticism aside (I don't know anything about compilers, so I'm not capable of judging), the received wisdom seems to be that the Dragon book spends far too much time on parsing and not enough time on other, more important aspects of modern compiler development. See, for instance, this blog post by a professor about teaching a compilers course: http://danghica.blogspot.com/2020/04/teaching-compilers.html http://danghica.blogspot.com/2020/04/teaching-compilers.html. Or this blog post (and the one it links in the first paragraph): https://semantic-domain.blogspot.com/2020/02/thought-experiment-introductory.html https://semantic-domain.blogspot.com/2020/02/thought-experim....
- hardwaregeek 6y ago
  Exactly. I don't have the book in front of me, but I remember its typechecking section being hilariously short and imperative focused. Also in general the book doesn't focus on implementation at all. That's okay in some respects; it's probably stayed more relevant and useful due to not talking about implementation. But it makes it possible to read a bunch of the book and still have no clue how to write code to build a compiler.
- deleted 6y ago
  [deleted]
kingaillas 6y ago
As others noted, the Dragon Book spends far too much time on parsing, and not nearly enough on optimizations. To be fair, the first edition of the book is from 1986. It looks like the 2nd edition (2006) adds 3 chapters on data flow analysis, parallelization. I don't happen to have that version of the book so I don't know how good the material is. I took compilers in grad school in the early 90's. Even then, we mostly skipped parsing because that was considered covered in another class (Theory of Computation, a class that covered regular expression, finite automata, Turing machines, P vs NP, those sorts of topics). The professor spent as much time as he could on optimizations, since that was his research focus. He then went onto write his own compiler book (Engineering a Compiler; Cooper & Torczon) so you can compare the table of contents (https://www.elsevier.com/books/engineering-a-compiler/cooper/978-0-12-088478-0 https://www.elsevier.com/books/engineering-a-compiler/cooper...) and see what current compiler researchers feel are important topics to cover in a textbook. Not throwing the Dragon Book under the bus, but it probably is in the "cited widely but rarely read" category as you have noted, just from its position as being first/early. An anecdote from me - I had the occasion to write a parser for a work project a few years ago. Rather than reach for flex/bison or any theory I had from compiler courses... I went with the new-to-me method of a parser combinator. This was awesome and I might even describe as fun. Granted the target language I was parsing was much simpler than a programming language, but I hope that is covered in today's compilers courses. I remember really tedious parsing homework problems back in the day.
- mcguire 6y ago
  My impression (it's been a very long time since my compilers class) was that it didn't spend too much time on parsing; rather, it spent too much time on how to implement parser generators. I've spent a lot of time parsing things in my life, but rather much less on the details of LR parsers.
  - Taniwha 6y ago
    I was doing compiler design back in the late 70s/early 80s and writing your own compiler generator was quite common at the time - it wasn't until things like bison/yacc became available which not only did an excellent job but also allowed one to hack on them and/or the result (for example my Algol68 compiler needed to be able to be able to decide how to resolve some shift/reduce conflicts on the fly ... that's how you do changeable operator precedence)
wglb 6y ago
They are good books. (I started the first one when writing a compiler). The valid criticisms of them relate to improvements in parsing, and in optimization, which has progressed significantly in the years that they were written. Fun fact: On the compiler we wrote, Jeanne Musinski PhD, a student of Ullman was on our team. She wrote the parser, and actually discovered an improvement in error recovery during our project and published a paper after conferring with Ullman.
1vuio0pswjnm7 6y ago
I also see this sort of commentary regarding lex and yacc, the programs used in the dragon book. I always muse that the commentators probably have no idea how much software they currently use that, unbeknownst to them, has lex/flex and/or yacc/bison dependencies.
tester34 6y ago
>I think that what's actually going on is that, like The Art Of Computer Programming, the dragon book is widely referenced and rarely read. Now, enter the 21st century meme factory. In my opinion this book is "hard to read" in the sense it's dense in math formality There's a lot of good concepts but I bet you could write it times shorter.

by cxr 6y ago

jnwatson 6y ago

I took a compilers class around the dragon book. I think the valid criticism is the sequence of the book. An undergraduate compiler class can only cover perhaps half the book. IMHO, the number of students that would benefit from learning about AST transformation and code gen vastly outnumbers the folks that would benefit from learning about finite automata transformation (and I took a dedicated course in that). There simply aren’t that many folks working on regex engines.

marktangotango 6y ago
> There simply aren’t that many folks working on regex engines. Yes that's true but there are A LOT of leetcode/hankerrank problems that are trivially solvable when one has a solid grasp of DFA and state machines in general!
vishnugupta 6y ago
I second this based on my experience. My masters thesis was in code generation for Haskell where in I spent fair bit of time learning tree pattern matching, AST manipulation, register allocation etc. One can achieve a non trivial speed up by understanding these different phases of code generation. Another reason, in the context of compilers, is that there’s not much to be gained by micro-optimizing lexing and parsing. After all, a code is compiled just once and executed multiple times. So you know where much of the fun lies. The undergrads unfortunately usually miss out on the meatier part of the compiler course.
- fanf2 6y ago
  It used to be the case that lexing was the hottest part of a compiler, because it had to touch every byte of source and subsequent phases did not have so much data to crunch. But that stopped being true in the 1990s as optimizing compilers became mainstream technology.
criddell 6y ago
> An undergraduate compiler class can only cover perhaps half the book. When I took a compilers course that used this book, the professor had his own syllabus and would use the dragon book in support of his plan. We jumped around quite a bit and certainly didn't use all of the book. That course was one of my favorites and had a huge impact on me. I haven't written any compilers, but have used a lot of the concepts (especially state machines) over the years.
jll29 6y ago
> There simply aren’t that many folks working on regex engines. You'd be surprised: there's even a dedicated annual international conference on implementation of automata that has been going since 1996: <https://link.springer.com/conference/wia https://link.springer.com/conference/wia> There are constantly new algorithms, libraries, tools and applications around regular languages and regular relations (an extension of regular expression that is more elegant, symmetric, expressive and takes a lot of the ugliness of regexes out). Simplifying somewhat, finite state transducers are NFAs "with output". See e.g. FOMA at <https://fomafst.github.io/ https://fomafst.github.io/>.

spekcular 6y ago

> I've pressed for details, and I've seen others do the same, but it never ends in anything concrete—just an implicit appeal to the new conventional wisdom that they do more harm than good. Really? Merits of the criticism aside (I don't know anything about compilers, so I'm not capable of judging), the received wisdom seems to be that the Dragon book spends far too much time on parsing and not enough time on other, more important aspects of modern compiler development. See, for instance, this blog post by a professor about teaching a compilers course: http://danghica.blogspot.com/2020/04/teaching-compilers.html http://danghica.blogspot.com/2020/04/teaching-compilers.html. Or this blog post (and the one it links in the first paragraph): https://semantic-domain.blogspot.com/2020/02/thought-experiment-introductory.html https://semantic-domain.blogspot.com/2020/02/thought-experim....

hardwaregeek 6y ago
Exactly. I don't have the book in front of me, but I remember its typechecking section being hilariously short and imperative focused. Also in general the book doesn't focus on implementation at all. That's okay in some respects; it's probably stayed more relevant and useful due to not talking about implementation. But it makes it possible to read a bunch of the book and still have no clue how to write code to build a compiler.
deleted 6y ago
[deleted]

kingaillas 6y ago

As others noted, the Dragon Book spends far too much time on parsing, and not nearly enough on optimizations. To be fair, the first edition of the book is from 1986. It looks like the 2nd edition (2006) adds 3 chapters on data flow analysis, parallelization. I don't happen to have that version of the book so I don't know how good the material is. I took compilers in grad school in the early 90's. Even then, we mostly skipped parsing because that was considered covered in another class (Theory of Computation, a class that covered regular expression, finite automata, Turing machines, P vs NP, those sorts of topics). The professor spent as much time as he could on optimizations, since that was his research focus. He then went onto write his own compiler book (Engineering a Compiler; Cooper & Torczon) so you can compare the table of contents (https://www.elsevier.com/books/engineering-a-compiler/cooper/978-0-12-088478-0 https://www.elsevier.com/books/engineering-a-compiler/cooper...) and see what current compiler researchers feel are important topics to cover in a textbook. Not throwing the Dragon Book under the bus, but it probably is in the "cited widely but rarely read" category as you have noted, just from its position as being first/early. An anecdote from me - I had the occasion to write a parser for a work project a few years ago. Rather than reach for flex/bison or any theory I had from compiler courses... I went with the new-to-me method of a parser combinator. This was awesome and I might even describe as fun. Granted the target language I was parsing was much simpler than a programming language, but I hope that is covered in today's compilers courses. I remember really tedious parsing homework problems back in the day.

mcguire 6y ago
My impression (it's been a very long time since my compilers class) was that it didn't spend too much time on parsing; rather, it spent too much time on how to implement parser generators. I've spent a lot of time parsing things in my life, but rather much less on the details of LR parsers.
- Taniwha 6y ago
  I was doing compiler design back in the late 70s/early 80s and writing your own compiler generator was quite common at the time - it wasn't until things like bison/yacc became available which not only did an excellent job but also allowed one to hack on them and/or the result (for example my Algol68 compiler needed to be able to be able to decide how to resolve some shift/reduce conflicts on the fly ... that's how you do changeable operator precedence)

wglb 6y ago

They are good books. (I started the first one when writing a compiler). The valid criticisms of them relate to improvements in parsing, and in optimization, which has progressed significantly in the years that they were written. Fun fact: On the compiler we wrote, Jeanne Musinski PhD, a student of Ullman was on our team. She wrote the parser, and actually discovered an improvement in error recovery during our project and published a paper after conferring with Ullman.

1vuio0pswjnm7 6y ago

I also see this sort of commentary regarding lex and yacc, the programs used in the dragon book. I always muse that the commentators probably have no idea how much software they currently use that, unbeknownst to them, has lex/flex and/or yacc/bison dependencies.

tester34 6y ago

>I think that what's actually going on is that, like The Art Of Computer Programming, the dragon book is widely referenced and rarely read. Now, enter the 21st century meme factory. In my opinion this book is "hard to read" in the sense it's dense in math formality There's a lot of good concepts but I bet you could write it times shorter.