Alfred V Aho

ACM A. M. Turing Award (2020)
ACM Fellows (1996)
2020 ACM A.M. Turing Award

ACM A. M. Turing Award

USA - 2020

citation

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.

Computer software powers almost every piece of technology we interact with. 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, under the hood, owes its beginnings to this year's Turing Award winners.

Alfred V. Aho is the Lawrence Gussman Professor Emeritus of Computer Science at Columbia University and Jeffrey D. Ullman is the Stanford W. Ascherman Professor Emeritus of Computer Science at Stanford University. Aho and Ullman began their productive and creative collaboration in 1967 at Bell Labs, which they both joined after finishing their PhDs at Princeton University. While at Bell Labs, they developed efficient algorithms for analyzing and translating programming languages, and they continued their close collaboration after Ullman moved to academia in 1969. Their joint and individual research contributions over the span of several decades have shaped the foundations of programming language theory and implementation, as well as algorithm design and analysis.

Aho and Ullman made broad and fundamental contributions to the field of programming language compilers through their technical contributions and influential textbooks. Aho and Ullman contributed to formal language theory and invented efficient algorithms for lexical analysis, syntax analysis, code generation, and code optimization. For example, in an early paper, Aho and Ullman showed how it was possible to make Knuth's LR(k) parsing algorithm work with simple grammars that technically did not meet the requirements of an LR(k) grammar; this idea led to the YACC parser-generator, which for many years was the preferred method for quickly building a parser. They developed efficient algorithms for data-flow analysis that exploited the structure of "gotoless" programs, which were at the time just becoming the norm. As the field of relational databases was opening up, their paper (with Catriel Beeri) on "lossless joins" explained what the normal forms defined by Codd, Fagin, and others were attempting to do with regard to design of databases and gave a methodology for determining when it was possible to break a relation into smaller components without losing information.

Their research, along with that of others, formed the basis of their two-volume series on parsing and compiling, which led to their definitive book on compiler technology, Principles of Compiler Design, published in 1977. This "Dragon Book" (nicknamed after its colorful cover) and its subsequent editions with Ravi Sethi, and later with Sethi and Monica Lam, became the bibles of compiler design. These books lucidly lay out the phases in translating a high-level programming language to machine code, modularizing the entire enterprise of compiler construction. Their fundamental algorithms have been incorporated into commercial compilers and popular compiler construction tools, such as Lex and YACC, which are routinely used by millions worldwide to automate building components of programming language compilers.

The impact of their work since the 1970s is so profound and so pervasive that it is easily taken for granted. Anyone who has programmed in C or any of its derivatives; anyone who has used Unix tools, such as AWK, fgrep, Lex, and YACC; anyone who has taken a compiler course; or anyone who has built a compiler by just reading the Dragon Book has been touched by the work of Aho and Ullman.

Their early joint work in algorithm design and analysis techniques contributed crucial approaches to the theoretical core of computer science that emerged in this period. In its focus on basic methods for processing graphs, strings, and sequences, this algorithmic work was tightly integrated with their research on programming languages as well. Their foundational book with John Hopcroft, The Design and Analysis of Computer Algorithms, published in 1974, created the conceptual framework not just for teaching algorithms in the standard computer science curriculum for decades, but also for presenting and analyzing new algorithms developed by the research community. In addition to incorporating their own results, the book codified a range of disparate algorithms into a set of general design methods, including divide-and-conquer, recursion, dynamic programming, and others that have long since entered the standard toolbox of computer scientists.

The Dragon Book and their foundational algorithms book, along with their subsequent books on data structures and algorithms, and on theoretical foundations of computer science, sit on the shelves of all researchers and practitioners of computing to this day.

For fundamental algorithms and theory underlying programming language implementation and for synthesizing those results and other state-of-the art results in their highly influential books, which educated generations of computer scientists, Aho and Ullman have been selected to receive the recognition conferred by the ACM A.M. Turing Award.

Press Release

ACM Fellows

USA - 1996

citation

For contributions to Interconnection Networks, High-Performance Computer Architecture, System Reliability, and Scheduling Techniques.

2020 ACM A.M. Turing Award

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 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.

Biographical Background

Alfred Vaino Aho
Alfred Aho is the Lawrence Gussman Professor Emeritus at Columbia University. He joined the Department of Computer Science at Columbia in 1995. Prior to Columbia, Aho was Vice President of Computing Sciences Research at Bell Laboratories where he worked for more than 30 years. A graduate of the University of Toronto, Aho earned his Master’s and PhD degrees in Electrical Engineering/Computer Science from Princeton University.

Aho’s honors include the IEEE John von Neumann Medal and the NEC C&C Foundation C&C Prize. He is a member of the US National Academy of Engineering, the American Academy of Arts and Sciences, and the Royal Society of Canada. He is a Fellow of ACM, IEEE, Bell Labs, and the American Association for the Advancement of Science.

Jeffrey David Ullman
Jeffrey Ullman is the Stanford W. Ascherman Professor Emeritus at Stanford University and CEO of Gradiance Corporation, an online learning platform for various computer science topics. He joined the faculty at Stanford in 1979. Prior to Stanford, he served on the faculty of Princeton University from 1969 to 1979, and was a member of the technical staff at Bell Labs from 1966 to 1969. A graduate of Columbia University, Ullman earned his PhD in Computer Science from Princeton University.

Ullman’s honors include receiving the IEEE John von Neumann Medal, the NEC C&C Foundation C&C Prize, the Donald E. Knuth Prize, and the ACM Karl V. Karlstrom Outstanding Educator Award. He is a member of the US National Academy of Engineering, the National Academy of Sciences, and the American Academy of Arts and Sciences, and is an ACM Fellow.