Alfred Vaino Aho (born August 9, 1941) is a Canadian
computer scientist
A computer scientist is a person who is trained in the academic study of computer science.
Computer scientists typically work on the theoretical side of computation, as opposed to the hardware side on which computer engineers mainly focus (al ...
best known for his work on
programming language
A programming language is a system of notation for writing computer programs. Most programming languages are text-based formal languages, but they may also be graphical. They are a kind of computer language.
The description of a programming ...
s,
compiler
In computing, a compiler is a computer program that translates computer code written in one programming language (the ''source'' language) into another language (the ''target'' language). The name "compiler" is primarily used for programs that ...
s, and related algorithms, and his textbooks on the art and science of computer programming.
Aho was elected into the
National Academy of Engineering
The National Academy of Engineering (NAE) is an American nonprofit, non-governmental organization. The National Academy of Engineering is part of the National Academies of Sciences, Engineering, and Medicine, along with the National Academy ...
in 1999 for his contributions to the fields of algorithms and programming tools.
He and his long-time collaborator
Jeffrey Ullman
Jeffrey David Ullman (born November 22, 1942) is an American computer scientist and the Stanford W. Ascherman Professor of Engineering, Emeritus, at Stanford University. His textbooks on compilers (various editions are popularly known as the dr ...
are the recipients of the 2020
Turing Award
The ACM A. M. Turing Award is an annual prize given by the Association for Computing Machinery (ACM) for contributions of lasting and major technical importance to computer science. It is generally recognized as the highest distinction in compu ...
, generally recognized as the highest distinction in
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
.
Career
Aho received a B.A.Sc. (1963) in Engineering Physics from the
University of Toronto
The University of Toronto (UToronto or U of T) is a public research university in Toronto, Ontario, Canada, located on the grounds that surround Queen's Park. It was founded by royal charter in 1827 as King's College, the first institution ...
, then an M.A. (1965) and Ph.D. (1967) in Electrical Engineering/Computer Science from
Princeton University
Princeton University is a private university, private research university in Princeton, New Jersey. Founded in 1746 in Elizabeth, New Jersey, Elizabeth as the College of New Jersey, Princeton is the List of Colonial Colleges, fourth-oldest ins ...
. He conducted research at
Bell Labs
Nokia Bell Labs, originally named Bell Telephone Laboratories (1925–1984),
then AT&T Bell Laboratories (1984–1996)
and Bell Labs Innovations (1996–2007),
is an American industrial research and scientific development company owned by mult ...
from 1967 to 1991, and again from 1997 to 2002 as Vice President of the Computing Sciences Research Center. Since 1995, he has held the Lawrence Gussman Professorship in
Computer Science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
at
Columbia University
Columbia University (also known as Columbia, and officially as Columbia University in the City of New York) is a private research university in New York City. Established in 1754 as King's College on the grounds of Trinity Church in Manhatt ...
. He served as chair of the department from 1995 to 1997, and again in the spring of 2003.
In his PhD thesis Aho created
indexed grammar Indexed grammars are a generalization of context-free grammars in that nonterminals are equipped with lists of ''flags'', or ''index symbols''.
The language produced by an indexed grammar is called an indexed language.
Definition
Modern definition ...
s and the
nested-stack automaton as vehicles for extending the power of
context-free languages
In formal language theory, a context-free language (CFL) is a language generated by a context-free grammar (CFG).
Context-free languages have many applications in programming languages, in particular, most arithmetic expressions are generated by ...
, but retaining many of their decidability and closure properties. One application of indexed grammars is modelling parallel rewriting systems, particularly in biological applications.
After graduating from Princeton, Aho joined the Computing Sciences Research Center at Bell Labs where he devised efficient
regular expression
A regular expression (shortened as regex or regexp; sometimes referred to as rational expression) is a sequence of characters that specifies a search pattern in text. Usually such patterns are used by string-searching algorithms for "find" or ...
and string-pattern matching algorithms that he implemented in the first versions of the
Unix
Unix (; trademarked as UNIX) is a family of multitasking, multiuser computer operating systems that derive from the original AT&T Unix, whose development started in 1969 at the Bell Labs research center by Ken Thompson, Dennis Ritchie, and ot ...
tools
egrep
grep is a command-line utility for searching plain-text data sets for lines that match a regular expression. Its name comes from the ed command ''g/re/p'' (''globally search for a regular expression and print matching lines''), which has the sam ...
and
fgrep
grep is a command-line utility for searching plain-text data sets for lines that match a regular expression. Its name comes from the ed command ''g/re/p'' (''globally search for a regular expression and print matching lines''), which has the sam ...
. The
fgrep
algorithm has become known as the
Aho–Corasick algorithm; it is used by several bibliographic search-systems, including the one developed by Margaret J. Corasick, and by other string-searching applications.
At Bell Labs, Aho worked closely with
Steve Johnson and
Jeffrey Ullman
Jeffrey David Ullman (born November 22, 1942) is an American computer scientist and the Stanford W. Ascherman Professor of Engineering, Emeritus, at Stanford University. His textbooks on compilers (various editions are popularly known as the dr ...
to develop efficient algorithms for analyzing and translating programming languages. Steve Johnson used the bottom-up LALR parsing algorithms to create the syntax-analyzer generator
yacc
Yacc (Yet Another Compiler-Compiler) is a computer program for the Unix operating system developed by Stephen C. Johnson. It is a Look Ahead Left-to-Right Rightmost Derivation (LALR) parser generator, generating a LALR parser (the part of a com ...
,
and
Michael E. Lesk and
Eric Schmidt
Eric Emerson Schmidt (born April 27, 1955) is an American businessman and software engineer known for being the CEO of Google from 2001 to 2011, executive chairman of Google from 2011 to 2015, executive chairman of Alphabet Inc. from 2015 to 20 ...
used Aho's regular-expression pattern-matching algorithms to create the lexical-analyzer generator
lex
Lex or LEX may refer to:
Arts and entertainment
* ''Lex'', a daily featured column in the ''Financial Times''
Games
* Lex, the mascot of the word-forming puzzle video game ''Bookworm''
* Lex, the protagonist of the word-forming puzzle video ga ...
. The lex and yacc tools and their derivatives have been used to develop the front ends of many of today's programming language compilers.
Aho and Ullman wrote a series of textbooks on compiling techniques that codified the theory relevant to compiler design. Their 1977 textbook ''
Principles of Compiler Design
''Principles of Compiler Design'', by Alfred Aho and Jeffrey Ullman, is a classic textbook on compilers for computer programming languages. Both of the authors won the 2020 Turing award for their work on compilers.
It is often called the "green ...
'' had a green dragon on the front cover and became known as "the green dragon book". In 1986 Aho and Ullman were joined by
Ravi Sethi
Ravi Sethi (born 1947) is an Indian computer scientist retired from executive roles at Bell Labs and Avaya Labs. He also serves as a member of the National Science Foundation's Computer and Information Science and Engineering (CISE) Advisory Co ...
to create a new edition, "the red dragon book" (which was briefly shown in the 1995 movie ''
Hackers
A hacker is a person skilled in information technology who uses their technical knowledge to achieve a goal or overcome an obstacle, within a computerized system by non-standard means. Though the term ''hacker'' has become associated in popu ...
''), and in 2006 also by
Monica Lam
Monica Sin-Ling Lam is an American computer scientist. She is a professor in the Computer Science Department at Stanford University.
Professional biography
Monica Lam received a B.Sc. from University of British Columbia in 1980 and a Ph.D. in ...
to create "the
purple dragon book". The dragon books are used for university courses as well as industry references.
In 1974, Aho,
John Hopcroft
John Edward Hopcroft (born October 7, 1939) is an American theoretical computer scientist. His textbooks on theory of computation (also known as the Cinderella book) and data structures are regarded as standards in their fields. He is the IBM Pro ...
, and Ullman wrote the ''Design and Analysis of Computer Algorithms'', codifying some of their early research on algorithms. This book became one of the most highly cited books in computer science for several decades and helped to stimulate the creation of algorithms and
data structure
In computer science, a data structure is a data organization, management, and storage format that is usually chosen for efficient access to data. More precisely, a data structure is a collection of data values, the relationships among them, a ...
s as a central course in the computer science curriculum.
Aho is also widely known for his co-authorship of the
AWK programming language
AWK (''awk'') is a domain-specific language designed for text processing and typically used as a data extraction and reporting tool. Like sed and grep, it is a filter, and is a standard feature of most Unix-like operating systems.
The AWK lang ...
with
Peter J. Weinberger
Peter Jay Weinberger (born August 6, 1942) is a computer scientist best known for his early work at Bell Labs. He now works at Google.
Weinberger was an undergraduate at Swarthmore College, graduating in 1964. He received his PhD in mathemati ...
and
Brian Kernighan
Brian Wilson Kernighan (; born 1942) is a Canadian computer scientist.
He worked at Bell Labs and contributed to the development of Unix alongside Unix creators Ken Thompson and Dennis Ritchie. Kernighan's name became widely known through co-au ...
(the "A" stands for "Aho"). Aho's research interests include programming languages, compilers, algorithms, and
quantum computing
Quantum computing is a type of computation whose operations can harness the phenomena of quantum mechanics, such as superposition, interference, and entanglement. Devices that perform quantum computations are known as quantum computers. Though ...
. He is part of the Language and Compilers research-group at Columbia University.
Overall, his works have been cited 81,040 times and he has an
h-index
The ''h''-index is an author-level metric that measures both the productivity and citation impact of the publications, initially used for an individual scientist or scholar. The ''h''-index correlates with obvious success indicators such as winn ...
of 66, as of May 8, 2019.
Aho has received many prestigious honors, including the
IEEE
The Institute of Electrical and Electronics Engineers (IEEE) is a 501(c)(3) professional association for electronic engineering and electrical engineering (and associated disciplines) with its corporate office in New York City and its operation ...
's
John von Neumann Medal
The IEEE John von Neumann Medal was established by the IEEE Board of Directors in 1990 and may be presented annually "for outstanding achievements in computer-related science and technology." The achievements may be theoretical, technological, or ...
and membership in the
National Academy of Engineering
The National Academy of Engineering (NAE) is an American nonprofit, non-governmental organization. The National Academy of Engineering is part of the National Academies of Sciences, Engineering, and Medicine, along with the National Academy ...
. He was elected a Fellow of the
American Academy of Arts and Sciences
The American Academy of Arts and Sciences (abbreviation: AAA&S) is one of the oldest learned societies in the United States. It was founded in 1780 during the American Revolution by John Adams, John Hancock, James Bowdoin, Andrew Oliver, and ...
in 2003.
He holds honorary doctorates from the
University of Waterloo
The University of Waterloo (UWaterloo, UW, or Waterloo) is a public research university with a main campus in Waterloo, Ontario
Waterloo is a city in the Canadian province of Ontario. It is one of three cities in the Regional Municipality ...
,
from the
University of Helsinki
The University of Helsinki ( fi, Helsingin yliopisto, sv, Helsingfors universitet, abbreviated UH) is a public research university located in Helsinki, Finland since 1829, but founded in the city of Turku (in Swedish ''Åbo'') in 1640 as the ...
,
and from the
University of Toronto
The University of Toronto (UToronto or U of T) is a public research university in Toronto, Ontario, Canada, located on the grounds that surround Queen's Park. It was founded by royal charter in 1827 as King's College, the first institution ...
.
He is a Fellow of the
American Association for the Advancement of Science
The American Association for the Advancement of Science (AAAS) is an American international non-profit organization with the stated goals of promoting cooperation among scientists, defending scientific freedom, encouraging scientific respons ...
,
ACM,
Bell Labs
Nokia Bell Labs, originally named Bell Telephone Laboratories (1925–1984),
then AT&T Bell Laboratories (1984–1996)
and Bell Labs Innovations (1996–2007),
is an American industrial research and scientific development company owned by mult ...
, and
IEEE
The Institute of Electrical and Electronics Engineers (IEEE) is a 501(c)(3) professional association for electronic engineering and electrical engineering (and associated disciplines) with its corporate office in New York City and its operation ...
.
[
Aho has twice served as chair of the Advisory Committee for the Computer and Information Science and Engineering Directorate of the National Science Foundation. He is a past president of the ACM Special Interest Group on Algorithms and Computability Theory. Aho, Hopcroft, and Ullman were co-recipients of the 2017 ]C&C Prize
The NEC C&C Prize ( ja, C&C賞) is an award given by the NEC Corporation "in recognition of outstanding contributions to research and development and/or pioneering work in the fields of semiconductors, computers, telecommunications and their integr ...
awarded by NEC
is a Japanese multinational corporation, multinational information technology and electronics corporation, headquartered in Minato, Tokyo. The company was known as the Nippon Electric Company, Limited, before rebranding in 1983 as NEC. It prov ...
Corporation. He and Ullman were named recipients of the 2020 Turing Award
The ACM A. M. Turing Award is an annual prize given by the Association for Computing Machinery (ACM) for contributions of lasting and major technical importance to computer science. It is generally recognized as the highest distinction in compu ...
on March 31, 2021.[ACM Turing Award Honors Innovators Who Shaped the Foundations of Programming Language Compilers and Algorithms](_blank)
Retrieved March 31, 2021.
Teaching
Aho has taught at Columbia University in New York City since 1995. He won the Great Teacher Award from the Society of Columbia Graduates in 2003.
Books
*A. V. Aho and J. D. Ullman, ''The Theory of Parsing, Translation, and Compiling, Vol. 1, Parsing.'' Prentice Hall, 1972.
*A. V. Aho (ed.) ''Currents in the Theory of Computing.'' Prentice Hall, 1973.
*A. V. Aho and J. D. Ullman, ''The Theory of Parsing, Translation, and Compiling, Vol. 2, Compiling.'' Prentice-Hall, 1973.
*A. V. Aho, J. E. Hopcroft, J. D. Ullman, ''The Design and Analysis of Computer Algorithms.'' Addison-Wesley, 1974.
*A. V. Aho and J. D. Ullman, ''Principles of Compiler Design.'' Addison-Wesley, 1977.
*A. V. Aho, J. E. Hopcroft, J. D. Ullman, ''Data Structures and Algorithms.'' Addison-Wesley, 1983.
*A. V. Aho, R. Sethi, J. D. Ullman, '' Compilers: Principles, Techniques, and Tools.'' Addison-Wesley, Reading MA 1986.
*A. V. Aho, B. W. Kernighan, and P. J. Weinberger, ''The AWK Programming Language.'' Addison-Wesley, 1988.
*A. V. Aho and J. D. Ullman,
Foundations of Computer Science
'' W. H. Freeman/Computer Science Press, 1992.
**A. V. Aho and J. D. Ullman, ''Foundations of Computer Science, C Edition.'' W. H. Freeman, 1995.
*A. V. Aho, M. S. Lam, R. Sethi, and J. D. Ullman, '' Compilers: Principles, Techniques, and Tools, Second Edition.'' Addison-Wesley, 2007.
References
External links
*
Alfred V Aho
at the ACM Digital Library
{{DEFAULTSORT:Aho, Alfred
1941 births
Canadian computer scientists
Canadian people of Finnish descent
Columbia University faculty
Columbia School of Engineering and Applied Science faculty
Fellows of the Association for Computing Machinery
Fellow Members of the IEEE
American people of Finnish descent
Living people
Princeton University School of Engineering and Applied Science alumni
Programming language designers
Scientists at Bell Labs
Theoretical computer scientists
Turing Award laureates
University of Toronto alumni
People from Timmins
Scientists from Ontario
Fellows of the American Academy of Arts and Sciences
Members of the United States National Academy of Engineering
Canadian textbook writers