Turing Lecture 2021: Abstractions, Their Algorithms, and Their Compilers

Computational thinking is an essential skill in the information age. We will talk about the core of computational thinking: abstractions and their uses. We begin with a taxonomy of abstractions based on their intended purpose and identify four different kinds of abstractions that are commonly used in computing. We look at three areas of computer science in which abstractions play a vital role. Compiler design is one of the first areas of computer science where powerful abstractions led to important improvements in the technology. More recently, the need to deal with increasingly large datasets has led to the development of new abstractions and increased the importance of old ones. Finally, we examine an abstraction that supports quantum computation and its potential for new computing capabilities. We close with some problems regarding computing abstractions that may lead to advances in the future.

Alfred Aho

Alfred V. Aho is the Lawrence Gussman Professor Emeritus of Computer Science at Columbia University. Aho is well known for his many papers and books on algorithms and data structures, programming languages, compilers, and the foundations of computer science. His research interests have included programming languages, compilers, algorithms, software engineering, and quantum computation. He’s a recipient of the ACM A. M. Turing Award and the IEEE John von Neumann Medal. Aho is a Member of the U.S. National Academy of Engineering and of the American Academy of Arts and Sciences. He is a Fellow of the American Association for the Advancement of Science, ACM, Bell Labs, IEEE, and the Royal Society of Canada. Aho has served as Vice President of the Computing Sciences Research Center at Bell Labs, the lab that invented UNIX, C, and C++. Professor Aho also served as General Manager of the Information Sciences and Technologies Research Laboratory at Bellcore (Telcordia).

Jeffrey Ullman

Jeffrey Ullman is the Stanford W. Ascherman Professor of Engineering (Emeritus) in the Department of Computer Science at Stanford University and CEO of Gradiance Corp. Prior to his appointment at Stanford, he was a member of the technical staff of Bell Laboratories, and on the faculty of Princeton University between. He later served as chair of the Stanford Computer Science Department. Ullman was elected to the National Academy of Engineering, the American Academy of Arts and Sciences, the National Academy of Sciences, and has held Guggenheim and Einstein Fellowships. He has received the SIGMOD Contributions Award, the ACM Karl V. Karlstrom Outstanding Educator Award, the Knuth Prize, the SIGMOD E. F. Codd Innovations Award, the IEEE von Neumann Medal, the NEC C&C Foundation Prize, and the ACM A.M. Turing Award. He is the author of 16 books, including books on database systems, data mining, compilers, automata theory, and algorithms.