A.M. TURING AWARD HONORS INNOVATORS WHO SHAPED THE FOUNDATIONS OF PROGRAMMING LANGUAGE COMPILERS AND ALGORITHMS 

 

Columbia's Aho and Stanford's Ullman Developed Tools and Fundamental Textbooks Used by Millions of Software Programmers around the World 

ACM named Alfred Vaino Aho and Jeffrey David Ullman recipients of the 2020 ACM A.M. Turing Award for fundamental algorithms and theory underlying programming language implementation and for synthesizing these results and those of others in their highly influential books, which educated generations of computer scientists. Aho is the Lawrence Gussman Professor Emeritus of Computer Science at Columbia University. Ullman is the Stanford W. Ascherman Professor Emeritus of Computer Science at Stanford University.

Computer software powers almost every piece of technology with which we interact. Virtually every program running our world – from those on our phones or in our cars to programs running on giant server farms inside big web companies – is written by humans in a higher-level programming language and then compiled into lower-level code for execution. Much of the technology for doing this translation for modern programming languages owes its beginnings to Aho and Ullman.

Beginning with their collaboration at Bell Labs in 1967 and continuing for several decades, Aho and Ullman have shaped the foundations of programming language theory and implementation, as well as algorithm design and analysis. They made broad and fundamental contributions to the field of programming language compilers through their technical contributions and influential textbooks. Their early joint work in algorithm design and analysis techniques contributed crucial approaches to the theoretical core of computer science that emerged during this period.

The ACM A.M. Turing Award, often referred to as the “Nobel Prize of Computing,” carries a $1 million prize, with financial support provided by Google, Inc. It is named for Alan M. Turing, the British mathematician who articulated the mathematical foundation and limits of computing.

“The practice of computer programming and the development of increasingly advanced software systems underpin almost all of the technological transformations we have experienced in society over the last five decades,” explains ACM President Gabriele Kotsis. “While countless researchers and practitioners have contributed to these technologies, the work of Aho and Ullman has been especially influential. They have helped us to understand the theoretical foundations of algorithms and to chart the course for research and practice in compilers and programming language design. Aho and Ullman have been thought leaders since the early 1970s, and their work has guided generations of programmers and researchers up to the present day.”

“Aho and Ullman established bedrock ideas about algorithms, formal languages, compilers and databases, which were instrumental in the development of today’s programming and software landscape,” added Jeff Dean, Google Senior Fellow and SVP, Google AI. “They have also illustrated how these various disciplines are closely interconnected. Aho and Ullman introduced key technical concepts, including specific algorithms, that have been essential. In terms of computer science education, their textbooks have been the gold standard for training students, researchers, and practitioners.”

A Longstanding Collaboration

Aho and Ullman both earned their PhD degrees at Princeton University before joining Bell Labs, where they worked together from 1967 to 1969. During their time at Bell Labs, their early efforts included developing efficient algorithms for analyzing and translating programming languages.

In 1969, Ullman began a career in academia, ultimately joining the faculty at Stanford University, while Aho remained at Bell Labs for 30 years before joining the faculty at Columbia University. Despite working at different institutions, Aho and Ullman continued their collaboration for several decades, during which they co-authored books and papers and introduced novel techniques for algorithms, programming languages, compilers and software systems.

Influential Textbooks

Aho and Ullman co-authored nine influential books (including first and subsequent editions). Two of their most widely celebrated books include:

The Design and Analysis of Computer Algorithms (1974)
Co-authored by Aho, Ullman, and John Hopcroft, this book is considered 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. In addition to incorporating their own research contributions to algorithms, The Design and Analysis of Computer Algorithms introduced the random access machine (RAM) as the basic model for analyzing the time and space complexity of computer algorithms using recurrence relations. The RAM model also codified disparate individual algorithms into general design methods. The RAM model and general algorithm design techniques introduced in this book now form an integral part of the standard computer science curriculum.

Principles of Compiler Design (1977)
Co-authored by Aho and Ullman, this definitive book on compiler technology integrated formal language theory and syntax-directed translation techniques into the compiler design process. Often called the “Dragon Book” because of its cover design, it lucidly lays out the phases in translating a high-level programming language to machine code, modularizing the entire enterprise of compiler construction. It includes algorithmic contributions that the authors made to efficient techniques for lexical analysis, syntax analysis techniques, and code generation. The current edition of this book, Compilers: Principles, Techniques and Tools (co-authored with Ravi Sethi and Monica Lam), was published in 2007 and remains the standard textbook on compiler design. 

---

The A.M. Turing Award, the ACM's most prestigious technical award, is given for major contributions of lasting importance to computing.

This site celebrates all the winners since the award's creation in 1966. It contains biographical information, a description of their accomplishments, straightforward explanations of their fields of specialization, and text or video of their A. M. Turing Award Lecture.