15 ms·

Turing Award goes to Aho and Ullman

459 points by jonstewart 6y ago

jonstewart 6y ago
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.
deleted 6y ago
[deleted]
enriquto 6y ago
Maybe link to the source? https://awards.acm.org/about/2020-turing https://awards.acm.org/about/2020-turing
nabla9 6y ago
I love the Dragon Book (Compilers: Principles, Techniques, and Tools by Aho, Sethi, Ullman). https://en.wikipedia.org/wiki/Compilers:_Principles,_Techniques,_and_Tools https://en.wikipedia.org/wiki/Compilers:_Principles,_Techniq...
jjice 6y ago
Good for them. The Dragon Book is a great compiler guide, despite some understandable criticisms I've heard about it not teaching blessing edge technique at the time. I'm using it right now for my compiler course, and it still holds up to a solid extent. Just out of curiosity though, why wasn't Sethi (co-author) included? Was he just an author and not involved in as much research as Aho and Ullman?
- pbhowmic 6y ago
  Good question. Why not?
- comeonseriously 6y ago
  Maybe because, while HN is talking about The Dragon Book, the actual reference[0] refers to https://en.wikipedia.org/wiki/Principles_of_Compiler_Design https://en.wikipedia.org/wiki/Principles_of_Compiler_Design which did not include Sethi (although there is a blurb about it in the paragraph). [0]https://awards.acm.org/about/2020-turing https://awards.acm.org/about/2020-turing
  - jjice 6y ago
    Thank you for pointing that out. I guess I had tunnel vision because of my personal experience.
- gnulinux 6y ago
  The original Dragon Book (sometimes referred to as the "Green Dragon Book") was written by Aho and Ullman.
- mhh__ 6y ago
  The dragon book still has some gems but great might be pushing it these days
algo_trader 6y ago
Wikipedia: Jeffrey Ullman.... was the Ph.D. advisor of Sergey Brin The greats know how to recognize greats ;)
- rvz 6y ago
  > Jeffrey Ullman.... was the Ph.D. advisor of Sergey Brin And? What is that supposed to mean?
  - chrisseaton 6y ago
    A PhD advisor is the academic who guides your PhD work. Sergey Brin is a co-founder of Google. They're pointing out how connected many people in computer science.
    - rvz 6y ago
      > They're pointing out how connected many people in computer science. Your last sentence is mostly relevant to my point. The parent shouldn't be easily blinded and in awe of listing just only 'one example' and then proclaiming they're 'recognising greats'. Let's have more examples of other 'greats' connected to or even advised by Jeffrey Ullman rather than mentioning only one 'great'. Even if it is the co-founder of Google.
rurban 6y ago
Needed some time. Knuth won it 1974, Hopcroft 1986 already. Wonder why so late
- quantified 6y ago
  Well, many worthy candidates to consider over the years. Hope these two have plenty of time left on this earth to enjoy the award.
- stueynz 6y ago
  That was my thought too... I didn’t do computers course so never had the joy of reading the dragon book... but Data Structures & Algorithms was the text book for second year CompSci...
noisy_boy 6y ago
Alfred Aho is the "a" in awk[0] (Peter Weinberger and Brian Kernighan being "w" and "k"). [0]: https://en.wikipedia.org/wiki/AWK https://en.wikipedia.org/wiki/AWK
- credit_guy 6y ago
  The book "The AWK Programming Language" by Aho, Weinberger and Kernighan is a real gem. Chapter 6 is "Little Languages", it shows you how to write interpreters and compilers using AWK. In particular it even shows how to start a bootstrap: you write a compiler to a subset of AWK that writes down C code. You don't need to read all the 5 chapters before, only Chapter 1 is enough.
  - deleted 6y ago
    [deleted]
  - dfjsk 6y ago
    Generally when a compiler produces C code (or assembly, or whatever) it is described as emitting C code. "A compiler for a subset of AWK that emits C code"
- zests 6y ago
  Also: https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm
- deleted 6y ago
  [deleted]
pthreads 6y ago
Can someone recommend me a good online course in automata theory (or even a book). I tried Ullman's course on edX (or Coursera, don't remember). But I found it a bit difficult to follow -- seemed a bit dry and monotonous, to me at least. Had the same experience with Ullman's book (first edition at least). I have enough theoretical background in CS and am not averse to reading dense material.
- deleted 6y ago
  [deleted]
- joshmarlow 6y ago
  I'm assuming this was the Ullman book you took a look at - https://www.amazon.com/Introduction-Automata-Languages-Computation-Addison-Wesley/dp/020102988X/ https://www.amazon.com/Introduction-Automata-Languages-Compu... If not, it's good but pretty dense. If you didn't like that, then I would recommend this one - https://www.amazon.com/Introduction-Theory-Computation-Michael-Sipser/dp/113318779X https://www.amazon.com/Introduction-Theory-Computation-Micha... Sipser has a lot less notation and more english explanations of the concepts. I picked it up and read most of it after graduating - it's pretty easy to follow (though if I recall, I think some of the terminology around Turing complete languages differed slightly from the Ullman text).
  - llimllib 6y ago
    I love sipser, it’s one of the few textbooks I kept after college
  - pthreads 6y ago
    Thanks for the Sipser recommendation. Picked it up yesterday and already liking it.
- brudgers 6y ago
  My interest in the topic carried me through Ulman’s Corsera course...the second time back when such things were free. Which is only relevant in the sense that what changes is our relationship to the material over time. Our interests evolve. Same our expectations. Ulman wrote the book. It’s hard to do better than that in many of the ways that matter.
kazinator 6y ago
I've amusingly noticed that my 1988 edition of the book does not mention tail calls whatsoever, except in one early chapter where it is in relation to the implementation of some parsing. Index: [...] Tail recursion 52-53 On pages 52-53, they show how, in a token matching procedure that takes no arguments, and returns nothing, the recursive self call can be manually replaced by a backwards goto: "[w]e can speed up a program by replacing tail recursion by iteration. For a procedure without parameters, a tail-recursive call can be simply replaced by a jump to the beginning of the procedure." There is no mention about the possibility of compilers doing this for you, or that there are other reasons for tail calls, like eliminating stack growth. The rest of the book is mum about tail calls.
- deleted 6y ago
  [deleted]
markus_zhang 6y ago
Contrary to the opinion of many HN posters, I actually believe the front-end (lexing, parsing, semantic analysis) is more important to most software engineers. Consider: You don't get to work on the back-end for most of the careers out there. But Lexing and parsing are very valuable if you want to parse something, say a configuration file. These kinds of things are more often seen in day-in-day work than code generation and optimization.
- chrisseaton 6y ago
  I think they should split university courses - a course about parsing (no need to even mention compilers) and a course about compilers that starts from an AST. Many the former a requirement and the latter an elective.
  - cestith 6y ago
    under 40 days ago someone posted to HN a SIGPLAN story about teaching compiler from the final phase to the first phase of processing the translations. https://news.ycombinator.com/item?id=26237368 https://news.ycombinator.com/item?id=26237368 It gives you an AST you can assume is valid and has you do the work to rename variables and methods. Then it gives you an AST and has you develop your target code (in the case of the specific class, LLVM IR). Then the AST is checked for valid semantics. Then the course has you check a source program for syntactic validity and generate an AST. It gives people the advantage of understanding what the AST is for on a deeper level before deciding how to represent it. I think this sort of class and a separate parsing class could be stellar together.
  - kingaillas 6y ago
    My university did that... sort of. There was a required "Theory of Computation" course using the Ullman & Hopcroft textbook "Introduction to Automata Theory, Languages, and Computation". A newer textbook could also be Sipser's "Introduction to the Theory of Computation".
- Koshkin 6y ago
  As a side note, "lexing" is jargon that has never been in use by authors of books on compilers.
lordleft 6y ago
Aho was my CS Theory professor at undergrad. He was incredibly polite and in my opinion, quite compassionate towards his beleaguered CS students. Cheers to him and Ullman.
- sebastian_z 6y ago
  Agreed! (as a former MS student)
- vlads 6y ago
  Same. Aho was one of the nicest professors of my undergrad studies. He was also one of the few who actually taught well, and who placed a heavy emphasis on understanding the basics and then being able to build on top of that.
- bradneuberg 6y ago
  Alfred Aho taught my Software Engineering I and II courses at Columbia University when I was an undergrad, and they were my favorite Computer Science courses. He was a great, compassionate teacher, with a mix of theoretical and real world instruction. Really a highlight for me. Glad to hear he won the Turing Award.
cjohansson 6y ago
Reading one of their books now, great stuff, compilers are fascinating, I wish I had discovered that earlier
neonate 6y ago
https://archive.is/kamx6 https://archive.is/kamx6
shadeslayer_ 6y ago
One of the enduring memories of bumbling through my first few months as an undergrad was coming upon a torn, well-read copy of the Dragon Book in the institute library. To date, it remains one of the best pieces of CS literature I have read. Seven years down the line, it feels strangely warm to read those names again.
- pvarangot 6y ago
  The Dragon book is great! That book opened my mind onto how compilers "do it" when I was a starting college. That being said, their book on Data Structures and Algorithms is severely underrated. It doesn't go in depth like more classical texts like Cormen and doesn't condense infinite knowledge in each paragraph like Knuth does, but it's a very nice read that goes from simple data structures to secondary memory and it's really easy to read.
  - tsjq 6y ago
    The book by Aho, Hopkroft , Ullman ?
    - pvarangot 6y ago
      Yes, that one.
- hn_throwaway_99 6y ago
  I've been out of college for a looking time. I'm not a particularly nostalgic person, but there are a couple books I still have from college, and the Dragon Book is still one I like to read.
eyeundersand 6y ago
Prof. Ullman's opinion on the Middle East: https://web.archive.org/web/20120806135022/http://infolab.stanford.edu/~ullman/pub/iranian.html https://web.archive.org/web/20120806135022/http://infolab.st...
- closetnerd 6y ago
  Just read some of his comments about Iran on his wiki. It shouldn’t impact the recognition of his achievements. Ironically though I was disheartened to see that a student reaching out to him was shot down because of his (valid) views on the Iranian government.
  - eyeundersand 6y ago
    I agree that his views should have no bearing on his achievements, and for what it’s worth I found myself disagreeing more with his tone.
- laichzeit0 6y ago
  No one cares. Cancel culture is an advanced form of trolling.
cambalache 6y ago
The prize didnt go to React creators? Well, maybe next year.
pjmorris 6y ago
Back in the dark ages when 'Data Structures and Algorithms' was our state of the art textbook, we called the author trio of Aho, Hopcroft, and Ullman the 'Three Wise Men.' Glad to see Aho and Ullman get more serious recognition.
smortaz 6y ago
thank you aho & ullman. your dragon book got me hooked & started a 40 year career in compilers/languages. first job, an algol68 compiler on burroughs hw back in the middle ages.
a-dub 6y ago
masters of the real "string theory"
garfieldnate 6y ago
Is it possible in the future that incremental compilation methods will become basic compiler knowledge? I think it would be an amazing step forward if the default compiler design would always result in IDE-inspectable code. Language Server Protocol is amazing, but it's only half the story.
amelius 6y ago
What's today's equivalent of the "Dragon book"? I guess it should cover new stuff such as JIT compilation, concurrent garbage collection, optimizations that are part of LLVM, and modern type systems.
- kindofajsdev 6y ago
  If this exists, I would love to read it.
scumcity 6y ago
Dragon book is solid, but just a regurgitation of Knuth, etc. Hardly worth a Turing Award. The bar lowers more every year, sigh.
- svat 6y ago
  This is trolling, but as most of the HN comments here mention the dragon book and a careless reader may get the same impression, let me reply seriously anyway, and point out that the Turing award is not for that: https://awards.acm.org/about/2020-turing https://awards.acm.org/about/2020-turing It is for their pioneering research work in algorithms and theory related to compilers (some of which indeed went into some of their books later). Also, even if you consider only books, they wrote nine books, and neither of the two mentioned as most influential is "the dragon book". The first mentioned is the book by Aho, Hopcraft and Ullman: Design and Analysis of Computer Algorithms (1974) > a classic in the field and was one of the most cited books in computer science research for more than a decade. It became the standard textbook for algorithms courses throughout the world when computer science was still an emerging field. This predates other major algorithms textbooks like say Kleinberg and Tardos (2005), Skiena (1st ed 1997), CLRS (1st ed 1990), or Sedgewick (1st ed 1983). Easily the standard textbook for more than a decade (and still used in some universities; it's still in print in some countries). > Principles of Compiler Design (1977) This is the "green dragon book", not to be confused with Compilers: Principles, Techniques, and Tools (1986, 2nd ed 2006) aka the "red dragon book" and the one people usually mean by "dragon book". This book is not even mentioned in the award citation. (Their automata book was widely used too.) So the idea that the award was given solely or even primarily for the dragon book seems entirely inaccurate. The Wikipedia pages on Aho and Ullman give some idea of their work: indexed grammars, nested-stack automata, egrep, fgrep / Aho-Corasick algorithm, the algorithms that went into yacc and lex, AWK (Aho), and "one of the founders of the field of database theory" (Ullman). [Edit: Shortened my very long comment.]
rswier 6y ago
Here are the course notes from an AT&T Compiler Construction Course by "Aho, Sethi, et. al." https://archive.org/details/CompilerConstructionCourse_Dec83 https://archive.org/details/CompilerConstructionCourse_Dec83
karulont 6y ago
“Alfred Vaino Aho” this a the first time I looked it up in full (with the middle name) it seems like a Finnish or maybe Estonian name. I am wondering if he has Finnish or Estonian heritage.
- selimthegrim 6y ago
  Finnish I think
musicale 6y ago
For teaching (and indeed writing) compilers, I greatly prefer Niklaus Wirth's simple recursive descent approach (and associated texts) to the encyclopedic bulk and complexity of the Dragon book! However, I like Automata Theory, Languages and Computation. It's a book that has grown on me over the years. As an aside, I think it's kind of interesting and cool to give the Turing award this year for writing textbooks! It's a type of deep scholarship that seems underappreciated and rarely rewarded.
DSingularity 6y ago
Yay a supporter of apartheid wins a Turing!
- echelon 6y ago
  I tried googling it and didn't find anything. Is this still the opinion they hold?
  - DSingularity 6y ago
    Only Ullman — he never renounced his views.
- dragonwriter 6y ago
  That about as relevant as saying “someone who can’t code fizzbuzz won a Nobel Peace Prize”.
  - DSingularity 6y ago
    Only to people who don’t mind adoring someone for their technical feats while ignoring their unethical positions.
    - miltondts 6y ago
      A person is a very complex, multi faceted system. If we don't like one particular aspect of that person, must we condemn everything that he does?
      - DSingularity 6y ago
        If that one thing is severe, yeah absolutely!
        randomsearch 6y ago
        Why?
ratnakar007 6y ago
bob
lincpa 6y ago
It is time for the computer software and hardware system to be updated. The Grand Unified Programming Theory: The Pure Function Pipeline Data Flow with principle-based Warehouse/Workshop Model https://github.com/linpengcheng/PurefunctionPipelineDataflow https://github.com/linpengcheng/PurefunctionPipelineDataflow
seanhunter 6y ago
Thoroughly deserved. My "Dragon Book" story is I went for a haircut in a pretty high-end salon. As a guy who was used to getting cheap haircuts in bargain places, I was feeling very out of place, which only became worse when they seated me next to a very glamourous-looking woman who was having a bunch of different highlighting and colouring things done to her hair. Then I noticed the book she was reading - the dragon book. We ended up having a fantastic conversation.

459 points by jonstewart 6y ago

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.

deleted 6y ago

[deleted]

enriquto 6y ago

Maybe link to the source? https://awards.acm.org/about/2020-turing https://awards.acm.org/about/2020-turing

nabla9 6y ago

I love the Dragon Book (Compilers: Principles, Techniques, and Tools by Aho, Sethi, Ullman). https://en.wikipedia.org/wiki/Compilers:_Principles,_Techniques,_and_Tools https://en.wikipedia.org/wiki/Compilers:_Principles,_Techniq...

jjice 6y ago

Good for them. The Dragon Book is a great compiler guide, despite some understandable criticisms I've heard about it not teaching blessing edge technique at the time. I'm using it right now for my compiler course, and it still holds up to a solid extent. Just out of curiosity though, why wasn't Sethi (co-author) included? Was he just an author and not involved in as much research as Aho and Ullman?

pbhowmic 6y ago
Good question. Why not?
comeonseriously 6y ago
Maybe because, while HN is talking about The Dragon Book, the actual reference[0] refers to https://en.wikipedia.org/wiki/Principles_of_Compiler_Design https://en.wikipedia.org/wiki/Principles_of_Compiler_Design which did not include Sethi (although there is a blurb about it in the paragraph). [0]https://awards.acm.org/about/2020-turing https://awards.acm.org/about/2020-turing
- jjice 6y ago
  Thank you for pointing that out. I guess I had tunnel vision because of my personal experience.
gnulinux 6y ago
The original Dragon Book (sometimes referred to as the "Green Dragon Book") was written by Aho and Ullman.
mhh__ 6y ago
The dragon book still has some gems but great might be pushing it these days

algo_trader 6y ago

Wikipedia: Jeffrey Ullman.... was the Ph.D. advisor of Sergey Brin The greats know how to recognize greats ;)

rvz 6y ago
> Jeffrey Ullman.... was the Ph.D. advisor of Sergey Brin And? What is that supposed to mean?
- chrisseaton 6y ago
  A PhD advisor is the academic who guides your PhD work. Sergey Brin is a co-founder of Google. They're pointing out how connected many people in computer science.
  - rvz 6y ago
    > They're pointing out how connected many people in computer science. Your last sentence is mostly relevant to my point. The parent shouldn't be easily blinded and in awe of listing just only 'one example' and then proclaiming they're 'recognising greats'. Let's have more examples of other 'greats' connected to or even advised by Jeffrey Ullman rather than mentioning only one 'great'. Even if it is the co-founder of Google.

rurban 6y ago

Needed some time. Knuth won it 1974, Hopcroft 1986 already. Wonder why so late

quantified 6y ago
Well, many worthy candidates to consider over the years. Hope these two have plenty of time left on this earth to enjoy the award.
stueynz 6y ago
That was my thought too... I didn’t do computers course so never had the joy of reading the dragon book... but Data Structures & Algorithms was the text book for second year CompSci...

noisy_boy 6y ago

Alfred Aho is the "a" in awk[0] (Peter Weinberger and Brian Kernighan being "w" and "k"). [0]: https://en.wikipedia.org/wiki/AWK https://en.wikipedia.org/wiki/AWK

credit_guy 6y ago
The book "The AWK Programming Language" by Aho, Weinberger and Kernighan is a real gem. Chapter 6 is "Little Languages", it shows you how to write interpreters and compilers using AWK. In particular it even shows how to start a bootstrap: you write a compiler to a subset of AWK that writes down C code. You don't need to read all the 5 chapters before, only Chapter 1 is enough.
- deleted 6y ago
  [deleted]
- dfjsk 6y ago
  Generally when a compiler produces C code (or assembly, or whatever) it is described as emitting C code. "A compiler for a subset of AWK that emits C code"
zests 6y ago
Also: https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm
deleted 6y ago
[deleted]

pthreads 6y ago

Can someone recommend me a good online course in automata theory (or even a book). I tried Ullman's course on edX (or Coursera, don't remember). But I found it a bit difficult to follow -- seemed a bit dry and monotonous, to me at least. Had the same experience with Ullman's book (first edition at least). I have enough theoretical background in CS and am not averse to reading dense material.

deleted 6y ago
[deleted]
joshmarlow 6y ago
I'm assuming this was the Ullman book you took a look at - https://www.amazon.com/Introduction-Automata-Languages-Computation-Addison-Wesley/dp/020102988X/ https://www.amazon.com/Introduction-Automata-Languages-Compu... If not, it's good but pretty dense. If you didn't like that, then I would recommend this one - https://www.amazon.com/Introduction-Theory-Computation-Michael-Sipser/dp/113318779X https://www.amazon.com/Introduction-Theory-Computation-Micha... Sipser has a lot less notation and more english explanations of the concepts. I picked it up and read most of it after graduating - it's pretty easy to follow (though if I recall, I think some of the terminology around Turing complete languages differed slightly from the Ullman text).
- llimllib 6y ago
  I love sipser, it’s one of the few textbooks I kept after college
- pthreads 6y ago
  Thanks for the Sipser recommendation. Picked it up yesterday and already liking it.
brudgers 6y ago
My interest in the topic carried me through Ulman’s Corsera course...the second time back when such things were free. Which is only relevant in the sense that what changes is our relationship to the material over time. Our interests evolve. Same our expectations. Ulman wrote the book. It’s hard to do better than that in many of the ways that matter.

kazinator 6y ago

I've amusingly noticed that my 1988 edition of the book does not mention tail calls whatsoever, except in one early chapter where it is in relation to the implementation of some parsing. Index: [...] Tail recursion 52-53 On pages 52-53, they show how, in a token matching procedure that takes no arguments, and returns nothing, the recursive self call can be manually replaced by a backwards goto: "[w]e can speed up a program by replacing tail recursion by iteration. For a procedure without parameters, a tail-recursive call can be simply replaced by a jump to the beginning of the procedure." There is no mention about the possibility of compilers doing this for you, or that there are other reasons for tail calls, like eliminating stack growth. The rest of the book is mum about tail calls.

deleted 6y ago
[deleted]

markus_zhang 6y ago

Contrary to the opinion of many HN posters, I actually believe the front-end (lexing, parsing, semantic analysis) is more important to most software engineers. Consider: You don't get to work on the back-end for most of the careers out there. But Lexing and parsing are very valuable if you want to parse something, say a configuration file. These kinds of things are more often seen in day-in-day work than code generation and optimization.

chrisseaton 6y ago
I think they should split university courses - a course about parsing (no need to even mention compilers) and a course about compilers that starts from an AST. Many the former a requirement and the latter an elective.
- cestith 6y ago
  under 40 days ago someone posted to HN a SIGPLAN story about teaching compiler from the final phase to the first phase of processing the translations. https://news.ycombinator.com/item?id=26237368 https://news.ycombinator.com/item?id=26237368 It gives you an AST you can assume is valid and has you do the work to rename variables and methods. Then it gives you an AST and has you develop your target code (in the case of the specific class, LLVM IR). Then the AST is checked for valid semantics. Then the course has you check a source program for syntactic validity and generate an AST. It gives people the advantage of understanding what the AST is for on a deeper level before deciding how to represent it. I think this sort of class and a separate parsing class could be stellar together.
- kingaillas 6y ago
  My university did that... sort of. There was a required "Theory of Computation" course using the Ullman & Hopcroft textbook "Introduction to Automata Theory, Languages, and Computation". A newer textbook could also be Sipser's "Introduction to the Theory of Computation".
Koshkin 6y ago
As a side note, "lexing" is jargon that has never been in use by authors of books on compilers.

lordleft 6y ago

Aho was my CS Theory professor at undergrad. He was incredibly polite and in my opinion, quite compassionate towards his beleaguered CS students. Cheers to him and Ullman.

sebastian_z 6y ago
Agreed! (as a former MS student)
vlads 6y ago
Same. Aho was one of the nicest professors of my undergrad studies. He was also one of the few who actually taught well, and who placed a heavy emphasis on understanding the basics and then being able to build on top of that.
bradneuberg 6y ago
Alfred Aho taught my Software Engineering I and II courses at Columbia University when I was an undergrad, and they were my favorite Computer Science courses. He was a great, compassionate teacher, with a mix of theoretical and real world instruction. Really a highlight for me. Glad to hear he won the Turing Award.

cjohansson 6y ago

Reading one of their books now, great stuff, compilers are fascinating, I wish I had discovered that earlier

neonate 6y ago

https://archive.is/kamx6 https://archive.is/kamx6

shadeslayer_ 6y ago

One of the enduring memories of bumbling through my first few months as an undergrad was coming upon a torn, well-read copy of the Dragon Book in the institute library. To date, it remains one of the best pieces of CS literature I have read. Seven years down the line, it feels strangely warm to read those names again.

pvarangot 6y ago
The Dragon book is great! That book opened my mind onto how compilers "do it" when I was a starting college. That being said, their book on Data Structures and Algorithms is severely underrated. It doesn't go in depth like more classical texts like Cormen and doesn't condense infinite knowledge in each paragraph like Knuth does, but it's a very nice read that goes from simple data structures to secondary memory and it's really easy to read.
- tsjq 6y ago
  The book by Aho, Hopkroft , Ullman ?
  - pvarangot 6y ago
    Yes, that one.
hn_throwaway_99 6y ago
I've been out of college for a looking time. I'm not a particularly nostalgic person, but there are a couple books I still have from college, and the Dragon Book is still one I like to read.

eyeundersand 6y ago

Prof. Ullman's opinion on the Middle East: https://web.archive.org/web/20120806135022/http://infolab.stanford.edu/~ullman/pub/iranian.html https://web.archive.org/web/20120806135022/http://infolab.st...

closetnerd 6y ago
Just read some of his comments about Iran on his wiki. It shouldn’t impact the recognition of his achievements. Ironically though I was disheartened to see that a student reaching out to him was shot down because of his (valid) views on the Iranian government.
- eyeundersand 6y ago
  I agree that his views should have no bearing on his achievements, and for what it’s worth I found myself disagreeing more with his tone.
laichzeit0 6y ago
No one cares. Cancel culture is an advanced form of trolling.

cambalache 6y ago

The prize didnt go to React creators? Well, maybe next year.

pjmorris 6y ago

Back in the dark ages when 'Data Structures and Algorithms' was our state of the art textbook, we called the author trio of Aho, Hopcroft, and Ullman the 'Three Wise Men.' Glad to see Aho and Ullman get more serious recognition.

smortaz 6y ago

thank you aho & ullman. your dragon book got me hooked & started a 40 year career in compilers/languages. first job, an algol68 compiler on burroughs hw back in the middle ages.

a-dub 6y ago

masters of the real "string theory"

garfieldnate 6y ago

Is it possible in the future that incremental compilation methods will become basic compiler knowledge? I think it would be an amazing step forward if the default compiler design would always result in IDE-inspectable code. Language Server Protocol is amazing, but it's only half the story.

amelius 6y ago

What's today's equivalent of the "Dragon book"? I guess it should cover new stuff such as JIT compilation, concurrent garbage collection, optimizations that are part of LLVM, and modern type systems.

kindofajsdev 6y ago
If this exists, I would love to read it.

scumcity 6y ago

Dragon book is solid, but just a regurgitation of Knuth, etc. Hardly worth a Turing Award. The bar lowers more every year, sigh.

svat 6y ago
This is trolling, but as most of the HN comments here mention the dragon book and a careless reader may get the same impression, let me reply seriously anyway, and point out that the Turing award is not for that: https://awards.acm.org/about/2020-turing https://awards.acm.org/about/2020-turing It is for their pioneering research work in algorithms and theory related to compilers (some of which indeed went into some of their books later). Also, even if you consider only books, they wrote nine books, and neither of the two mentioned as most influential is "the dragon book". The first mentioned is the book by Aho, Hopcraft and Ullman: Design and Analysis of Computer Algorithms (1974) > a classic in the field and was one of the most cited books in computer science research for more than a decade. It became the standard textbook for algorithms courses throughout the world when computer science was still an emerging field. This predates other major algorithms textbooks like say Kleinberg and Tardos (2005), Skiena (1st ed 1997), CLRS (1st ed 1990), or Sedgewick (1st ed 1983). Easily the standard textbook for more than a decade (and still used in some universities; it's still in print in some countries). > Principles of Compiler Design (1977) This is the "green dragon book", not to be confused with Compilers: Principles, Techniques, and Tools (1986, 2nd ed 2006) aka the "red dragon book" and the one people usually mean by "dragon book". This book is not even mentioned in the award citation. (Their automata book was widely used too.) So the idea that the award was given solely or even primarily for the dragon book seems entirely inaccurate. The Wikipedia pages on Aho and Ullman give some idea of their work: indexed grammars, nested-stack automata, egrep, fgrep / Aho-Corasick algorithm, the algorithms that went into yacc and lex, AWK (Aho), and "one of the founders of the field of database theory" (Ullman). [Edit: Shortened my very long comment.]

rswier 6y ago

Here are the course notes from an AT&T Compiler Construction Course by "Aho, Sethi, et. al." https://archive.org/details/CompilerConstructionCourse_Dec83 https://archive.org/details/CompilerConstructionCourse_Dec83

karulont 6y ago

“Alfred Vaino Aho” this a the first time I looked it up in full (with the middle name) it seems like a Finnish or maybe Estonian name. I am wondering if he has Finnish or Estonian heritage.

selimthegrim 6y ago
Finnish I think

musicale 6y ago

For teaching (and indeed writing) compilers, I greatly prefer Niklaus Wirth's simple recursive descent approach (and associated texts) to the encyclopedic bulk and complexity of the Dragon book! However, I like Automata Theory, Languages and Computation. It's a book that has grown on me over the years. As an aside, I think it's kind of interesting and cool to give the Turing award this year for writing textbooks! It's a type of deep scholarship that seems underappreciated and rarely rewarded.

DSingularity 6y ago

Yay a supporter of apartheid wins a Turing!

echelon 6y ago
I tried googling it and didn't find anything. Is this still the opinion they hold?
- DSingularity 6y ago
  Only Ullman — he never renounced his views.
dragonwriter 6y ago
That about as relevant as saying “someone who can’t code fizzbuzz won a Nobel Peace Prize”.
- DSingularity 6y ago
  Only to people who don’t mind adoring someone for their technical feats while ignoring their unethical positions.
  - miltondts 6y ago
    A person is a very complex, multi faceted system. If we don't like one particular aspect of that person, must we condemn everything that he does?
    - DSingularity 6y ago
      If that one thing is severe, yeah absolutely!
      - randomsearch 6y ago
        Why?

ratnakar007 6y ago

bob

lincpa 6y ago

It is time for the computer software and hardware system to be updated. The Grand Unified Programming Theory: The Pure Function Pipeline Data Flow with principle-based Warehouse/Workshop Model https://github.com/linpengcheng/PurefunctionPipelineDataflow https://github.com/linpengcheng/PurefunctionPipelineDataflow

seanhunter 6y ago

Thoroughly deserved. My "Dragon Book" story is I went for a haircut in a pretty high-end salon. As a guy who was used to getting cheap haircuts in bargain places, I was feeling very out of place, which only became worse when they seated me next to a very glamourous-looking woman who was having a bunch of different highlighting and colouring things done to her hair. Then I noticed the book she was reading - the dragon book. We ended up having a fantastic conversation.