6 ms·

I never took a compilers course in college and came to regret that. Ten years later I started reading the Dragon Book, and realized how I could trivially modify

I never took a compilers course in college and came to regret that. Ten years later I started reading the Dragon Book, and realized how I could trivially modify the NFA regular expression search algorithm to solve a problem I’d seen in digital forensics and eDiscovery. The writing is extremely clear and easy to follow, and I now tell all interns to be sure to take a compilers course before they graduate. Well-earned!

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.
ChuckMcM 6y ago
Agreed, of all the CS classes I took in college, the compilers class has been the most useful in my career. Still have the copy of the "dragon book" from that class.
forinti 6y ago
Although I really enjoyed compilers in college I never thought I would build one for practical reasons. I ended up using the knowledge for two very interesting projects. One was a template engine in Java for turning variables into clauses in SQL queries. The other was an interpreter for PL/SQL that helps to extract procedures and functions in order to do partial updates of packages in production (the user chooses which procedures to send to production and doesn't have to update the whole package).
- 0xfaded 6y ago
  My first job had me write a biology protocol description to robot commands compiler. It wasn't Turing complete, but it did need to allocate and assign "registers", which were the physical spaces available for the 96 well sample plates.
grok22 6y ago
Weird, I remember the book as being too dense and cryptic without sufficient explanatory text for a compilers course when I originally read it...maybe I am mis-remembering. I will have to find a copy and take another look.

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.

ChuckMcM 6y ago

Agreed, of all the CS classes I took in college, the compilers class has been the most useful in my career. Still have the copy of the "dragon book" from that class.

forinti 6y ago

Although I really enjoyed compilers in college I never thought I would build one for practical reasons. I ended up using the knowledge for two very interesting projects. One was a template engine in Java for turning variables into clauses in SQL queries. The other was an interpreter for PL/SQL that helps to extract procedures and functions in order to do partial updates of packages in production (the user chooses which procedures to send to production and doesn't have to update the whole package).

0xfaded 6y ago
My first job had me write a biology protocol description to robot commands compiler. It wasn't Turing complete, but it did need to allocate and assign "registers", which were the physical spaces available for the 96 well sample plates.

grok22 6y ago

Weird, I remember the book as being too dense and cryptic without sufficient explanatory text for a compilers course when I originally read it...maybe I am mis-remembering. I will have to find a copy and take another look.