Skip to content

Aho and Ullman: The Dragon Book

Abstract

Alfred Aho (born 1941) and Jeffrey Ullman (born 1942) met at Princeton, worked together at Bell Labs from 1967, and wrote the books that told two generations of computer scientists what algorithms and compilers were: The Design and Analysis of Computer Algorithms (1974, with Hopcroft) and Principles of Compiler Design (1977), the “Dragon Book,” whose cover Ullman sketched as a joke at the expense of his own subject. Their parsing theory became yacc; Aho’s string-matching algorithm became fgrep and his pattern-action language became AWK; Ullman’s students included Sergey Brin. They shared the 2020 Turing Award.

The AWK Programming Language cover
The cover of The AWK Programming Language (1988), the manual for the language Aho wrote with Weinberger and Kernighan. Image: Alfred Aho, public domain (text and simple geometry), via Wikimedia Commons.

Princeton, 1965

Jeffrey David Ullman was born in New York on 22 November 1942, the son of an advertising man who had discovered “you can’t actually get a job as an English major,” and took a BS in engineering mathematics at Columbia in 1963. He did not consider leaving the city for graduate school; Princeton was the nearest place with a fellowship, at $2,000 a year against the NSF’s $1,800, so he went there. A summer spent on automata theory turned him into a theoretician, and in his third year a new faculty member arrived, John Hopcroft, who had spent the same summer proving a theorem Ullman had to tell him Seymour Ginsburg had already proved. The two agreed that finite automata and context-free languages were “interesting subjects and useful subjects at the same time,” and Ullman finished his PhD in 1966, went to Bell Labs, and started writing a book with Hopcroft when Hopcroft came to the Labs on sabbatical.

Alfred Vaino Aho was born on 9 August 1941 in Timmins, Ontario, a mining town in the Canadian north, took a BASc in engineering physics at Toronto in 1963 and a Princeton PhD in 1967 under Hopcroft, on indexed grammars, a class between context-free and context-sensitive. He joined Bell Labs the same year.

Bell Labs and yacc

The two shared Doug McIlroy’s department, the group that produced Unix. “I didn’t do anything of that magnitude,” Ullman said, “but Al and I, we were both in that group, and we got interested in parsing.” Their two-volume The Theory of Parsing, Translation, and Compiling (early 1970s) was, in Ullman’s judgment, “more of the theory than the pragmatics,” and it sold reasonably. What sold better was an idea in one of their Bell Labs memos on LR parsing: Steve Johnson read it and said “Hey, we can actually build this.” Johnson wrote the code, and the result was yacc, Yet Another Compiler-Compiler, the Unix command that turned a grammar into a parser and was, for decades, how compilers were started. Michael Lesk’s lex did the same for lexical analysis. “To us it was just a paper to write,” Ullman said.

Aho’s own tools followed. With Margaret Corasick he published “Efficient String Matching” in Communications of the ACM in June 1975, an algorithm that finds every occurrence of every word in a dictionary in one pass over the text; it became fgrep. His egrep did the same for full regular expressions. In 1977, with Peter Weinberger and Brian Kernighan, he wrote AWK, the language whose programs are lists of pattern–action pairs applied to each line of input, and whose name is the authors’ initials. The three wrote its book in 1988.

The Dragon on the Cover

Ullman left the Labs for Princeton in 1969 and Aho stayed, and they kept writing together. The Design and Analysis of Computer Algorithms (1974), with Hopcroft (Hopcroft and Tarjan), was the first graduate textbook to treat algorithm design as a discipline with named techniques and a standard way of analysing them, and the framework it laid down is the one the field’s curriculum still uses. Then they decided they had “gone overboard with the theory” of parsing and that there were practical things to tell, yacc among them. Principles of Compiler Design came out from Addison-Wesley in 1977.

Bill Greener, the editor, asked whether they had an idea for the cover. Ullman was, he admitted later, “a little bit cynical about the real value of what we were writing,” so he sketched a knight fighting a dragon with the weapons the book taught, LR parsing and the rest, and asked that the back cover show Don Quixote tilting at a windmill with the same labels: “basically sort of saying it’s propaganda that you need all this great stuff that we’re going to teach you about, but you don’t really, it’s just all nonsense.” Greener “looked pretty scared,” but had the Addison-Wesley artists do it. “It turned out that in fact these tools were useful, so with the second edition, we dropped the back cover.” The front stayed. The green Dragon Book of 1977 became the red one, Compilers: Principles, Techniques, and Tools, with Ravi Sethi in 1986, and the purple one with Monica Lam in 2006, and the dragon, “a metaphor for conquering complexity,” is the cover by which the subject is known (The Compiler).

Stanford and the Database Turn

At Princeton Ullman hired Catriel Beeri, who taught a course on relational database theory, and “for sort of the last half of my time at Princeton, we were trying to develop a theory of relational databases.” He moved to Stanford in 1979, chaired the department from 1990 to 1994, and wrote the database books: Principles of Database and Knowledge-Base Systems (1988–89), Database Systems: The Complete Book (2002, with Hector Garcia-Molina and Jennifer Widom), and Mining of Massive Datasets (2014, with Jure Leskovec and Anand Rajaraman). His students included Widom and Sergey Brin, of whom he said that the key to advising was “to get out of their way and get them the resources if they need them. In Sergey’s case, what he needed was disk.” Ullman bought him disks to hold a copy of the web. He became emeritus in 2003 and received the Knuth Prize in 2000.

Aho stayed at Bell Labs until 1991, moved to Columbia in 1995 as Lawrence Gussman Professor and twice chaired its department, and went back to the Labs from 1997 to 2002 as vice president of the Computing Sciences Research Center. He received the IEEE von Neumann Medal in 2003; Ullman and Hopcroft shared it in 2010.

The Award and the Letter

The ACM gave Aho and Ullman the 2020 Turing Award, announced in March 2021, “for developing the fundamental algorithms and theory underlying programming language implementation and for synthesizing these results and those of others in their highly influential books, which have educated generations of computer scientists.” The Turing interviews that followed were conducted for Aho by Ken Thompson and for Ullman, in April 2024, by Hansen Hsu of the Computer History Museum.

The announcement drew an open letter. In 2011 Ullman had posted on his website that he would not help Iranian students apply to Stanford, citing the Iranian government’s position on Israel. In 2021 a group called CSForInclusion called the remarks discriminatory and inflammatory and criticised the ACM’s choice; Stanford said Ullman had been expressing personal views and had no role in admissions; the ACM reaffirmed its commitment to inclusion and left the award standing.

Dead End: The Back Cover

Ullman’s Don Quixote was a joke about his own field, and by the second edition the joke had been dropped because it had stopped being true: LR parsing and the rest were, in fact, how every compiler was built. The reverse happened to yacc. “It’s pretty much deprecated at this point,” Ullman said in 2024, “but for decades people would use it.” Most production compilers now use hand-written parsers, and the generated-parser approach the Dragon Book made canonical survives mainly in teaching and in yacc’s descendants. The theory was right and the tool was retired; the book is in its fourth decade.

📚 Sources