ACM Turing Award 2020
Alfred Vaino Aho and Jeffrey David Ullman were declared the 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.” 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. The Association for Computing Machinery (ACM) A.M. Turing Award, christened the “Nobel Prize of Computing,” is named in honour of Alan Turing, the British mathematician, who articulated the mathematical foundation and the limits of computing. The Turing Award recognizes contributions that have a lasting impact on computing and it is ACM’s most prestigious technical award.
Aho and Ullman earned their doctoral degrees at Princeton University, a year apart before joining the famed Bell Labs, where they worked together from 1967 to 1969. During this short period, they kickstarted a collaboration that would last a lifetime and revolutionise the world at large. Their early innovative research in formal languages and compiler theory led to key algorithms for modern compilers and string-pattern matching tools. Compilers are programs that translate source code from a high-level programming language to a lower level language (assembly language, object code, or machine code), and thereby help create an executable program.
Aho and Ullman made a wide range of contributions to programming language compilers, formal language theory and invented efficient algorithms for lexical analysis, syntax analysis, code generation, code optimisation, text processing applications, and programming language translation. They helped build the YACC parser-generator, a staple method for quickly building parsers for programming languages, by making Knuth’s LR(k) parsing algorithm work with simple grammars that technically did not meet the requirements of an LR(k) grammar. Their code generation algorithms influenced the design of retargetable C compilers, which further facilitated the porting of the UNIX operating system from minicomputers to supercomputers.
Ullman was one of the founders of database theory and made crucial contributions to data mining and data integration. He was instrumental in developing a theory of algorithms for the modern “MapReduce” style of parallel programming. He pioneered the field of join processing in map-reduce environments that has had tremendous impact on big data processing in parallel and distributed architectures. Aho built popular and fundamental Unix tools like Lex and grep. He also invented the Aho–Corasick algorithm, alongside Margaret Corasick. It is a string-matching algorithm that constructs an automation for finding words in an input string that are contained in a dictionary. Aho and Corasick collaborated with Peter Weinberger and Brian Kernighan, to create the AWK programming language, a scripting language that begated dynamic, “problem-focused” languages like Perl, Python, Javascript, and Ruby.
Ullman and Aho have also been brilliant expositors and have authored terrific textbooks that have been the Magna Carta in their fields. They penned the definitive treatise on compiler technology, Principles of Compiler Design (1977) and nicknamed the “Dragon Book” for its colourful cover. It beautifully elucidates the phases in translating a high-level programming language to machine code, modularizing the entire enterprise of compiler construction. It still remains the prescribed textbook on compiler design. Ullman also penned the Principles of Database Systems (1988), a comprehensive description of the theory and principles of database systems. Along with another Turing Awardee, John Hopcroft, Ullman and Aho wrote the classic, The Design and Analysis of Computer Algorithms (1974), which is a standard textbook for algorithms courses throughout the world, when computer science was still in its infancy.
Ullman left Bell Labs after three years and was part of the faculty at Princeton and Stanford while Aho plied his trade at Bell Labs for over three decades before transitioning to conventional university academia. The pioneering work they carried out at Bell Labs is reminiscent of a glorious time when industry heartily funded truly blue-sky research. Till date, Bell Labs has 9 Nobel Prizes and 5 Turing Awards, to its credit.
Both Ullman and Aho have built an illustrious body of research in a wide array of computer science disciplines like automata, formal languages, language theory, compilers, data structures, algorithms, database theory, and graph theory They have also published numerous research papers that have garnered thousands of citations and authored books that have trained generations of computer scientists. They have been admitted to the ranks of many esteemed societies, academies, fellowships, and have earned numerous accolades like the IEEE John von Neumann Medal “for outstanding achievements in computer-related science and technology.” Their pioneering contributions, both individually and jointly, have helped shape and power the modern day world. Their theory underlies the programs that enable instantaneous internet search results and Internet of Things (IoT) ecosystem.
The prize is not without its controversies and Ullman has been accused of holding xenophobic and discriminatory views against students and researchers from Iran. The links here, here and here contain a better description of the nuances of the allegations against Ullman. This also reiterates the fact that prizes, no matter how prestigious, don’t serve as tests of character.