Editing Alfred Aho

{{Short description|Canadian computer scientist (born 1941)}}
{{Use mdy dates|date=April 2021}}
{{Infobox scientist
| name              = Alfred Aho
| birth_name        = Alfred Vaino Aho
| image             = 
| image_size        = 
| caption           = Alfred Aho in 2018
| birth_date        = {{birth date and age|1941|08|09}}
| birth_place       = [[Timmins]], Ontario, Canada
| death_date        = 
| death_place       = 
| nationality       = Canadian<br />American
| field             = [[Computer science]]
| work_institution  = [[Columbia University]]
| education         = {{ubl |[[University of Toronto]] ([[Bachelor of Applied Science|BASc]]) |[[Princeton University]] ([[Master of Arts|MA]], [[Doctor of Philosophy|PhD]])}}
| thesis_title      = Indexed Grammars: An Extension of Context Free Grammars
| thesis_year       = 1968
| doctoral_advisor  = [[John Hopcroft]]<ref name="mathgene">{{MathGenealogy |id=82019 |title=Alfred Vaino Aho}}</ref>
| doctoral_students = {{Plainlist|
* [[Krysta Svore]]
* [[Gaurav Kc]]
* [[Marc Eaddy]]
* [[Marcio Buss]]
}}
| known_for         = {{Plainlist|
* [[Awk]] programming language
* ''[[Principles of Compiler Design]]''
* ''[[Compilers: Principles, Techniques, and Tools]]''
* [[Aho-Corasick algorithm]]
}}
| prizes            = {{Plainlist|
* Bell Labs Fellow (1984)
* [[American Association for the Advancement of Science|FAAAS]] (1986)
* [[IEEE Fellow]] (1988)
* [[Association for Computing Machinery|FACM]] (1996)
* IEEE [[John von Neumann Medal]] (2003)
* NAE Member
* NAS Member
* [[Turing Award]] (2020)}}
}}

'''Alfred Vaino Aho''' (born August 9, 1941) is a Canadian [[computer scientist]] best known for his work on [[programming language]]s, [[compiler]]s, and related algorithms, and his textbooks on the art and science of computer programming.<ref>{{Cite journal | doi = 10.1145/2582611| title = A front row seat to ''Communications''<nowiki>'</nowiki> editorial transformation| journal = Communications of the ACM| volume = 57| issue = 4| pages = 5| year = 2014| last1 = Aho | first1 = A. | author-link1 = Alfred Aho| last2 = Gottlob | first2 = G. | s2cid = 21553189| author-link2 = Georg Gottlob}}</ref><ref>{{cite book |first1=A.V. |last1=Aho |chapter=Algorithms for Finding Patterns in Strings |title=Handbook of Theoretical Computer Science |publisher=MIT Press |year=1990 |pages=255–300 }}</ref><ref>{{Cite web|url=https://www.computerworld.com/au/|archive-url=https://web.archive.org/web/20080529034813/http://www.computerworld.com.au/index.php/id%3B1726534212%3Bfp%3B4194304%3Bfpid%3B1|url-status=dead|title=IT news, careers, business technology, reviews|archive-date=May 29, 2008|website=Computerworld|access-date=May 18, 2023}}</ref>

Aho was elected into the [[National Academy of Engineering]] in 1999 for his contributions to the fields of algorithms and programming tools.

He and his long-time collaborator [[Jeffrey Ullman]] are the recipients of the 2020 [[Turing Award]], generally recognized as the highest distinction in [[computer science]].<ref name=":0" />

==Career==
Aho received a B.A.Sc. (1963) in Engineering Physics from the [[University of Toronto]], then an M.A. (1965) and Ph.D. (1967) in Electrical Engineering/Computer Science from [[Princeton University]].<ref>{{cite web |url=http://engineering.columbia.edu/files/engineering/final_86.pdf |title=Creating Reliable Programs from Unreliable Programmers |work=Excellentia}}</ref> He conducted research at [[Bell Labs]] from 1967 to 1991, and again from 1997 to 2002 as Vice President of the Computing Sciences Research Center.<ref>{{Cite web|last=Fitchard|first=Kevin|date=March 31, 2021|title=Bell Labs' Al Aho and Jeffrey Ullman honored with the prestigious Turing Award|url=https://www.bell-labs.com/institute/blog/bell-labs-al-aho-and-jeffrey-ullman-honored-with-turing-award/|url-status=live|access-date=April 3, 2021|website=Nokia Bell Labs|language=en|archive-url=https://web.archive.org/web/20210401055811/https://www.bell-labs.com/institute/blog/bell-labs-al-aho-and-jeffrey-ullman-honored-with-turing-award/ |archive-date=April 1, 2021 }}</ref>  Since 1995, he has held the Lawrence Gussman Professorship in [[Computer Science]] at [[Columbia University]]. He served as chair of the department from 1995 to 1997, and again in the spring of 2003.<ref>{{Cite web|title=Profile and Detailed Achievements of the Group B Recipients of the 2017 C&C Prize|url=https://www.nec.com/en/press/201710/images/1101-01-02.pdf|url-status=live|website=The [[NEC]] C&C Foundation|archive-url=https://web.archive.org/web/20220120120256/https://www.nec.com/en/press/201710/images/1101-01-02.pdf |archive-date=January 20, 2022 }}</ref>

In his PhD thesis Aho created [[indexed grammar]]s<ref>{{Cite journal|last1=Aho|first1=A. V.|year=1968|title=Indexed Grammars—An Extension of Context-Free Grammars|journal=Journal of the ACM|volume=15|issue=4|pages=647–671|doi=10.1145/321479.321488|s2cid=9539666|doi-access=free}}</ref> and the [[nested stack automaton|nested-stack automaton]]<ref>{{Cite journal|last1=Aho|first1=A. V.|year=1969|title=Nested Stack Automata|journal=Journal of the ACM|volume=16|issue=3|pages=383–406|doi=10.1145/321526.321529|s2cid=685569|doi-access=free}}</ref> as vehicles for extending the power of [[context-free languages]], but retaining many of their decidability and closure properties.  One application of indexed grammars is modelling parallel rewriting systems,<ref>{{Cite journal|last1=Rambow|first1=Owen|last2=Satta|first2=Giorgio|date=July 28, 1999|title=Independent parallelism in finite copying parallel rewriting systems|journal=Theoretical Computer Science|language=en|volume=223|issue=1–2|pages=87–120|doi=10.1016/S0304-3975(97)00190-4|issn=0304-3975|doi-access=}}</ref> particularly in biological applications.<ref>{{Cite book|last1=Culik|first1=Karel|last2=Maibaum|first2=T. S. E.|title=Automata, Languages and Programming |chapter=Parallel Rewriting Systems on Terms |date=1974|editor-last=Loeckx|editor-first=Jacques|chapter-url=https://link.springer.com/chapter/10.1007%2F978-3-662-21545-6_38|series=Lecture Notes in Computer Science|volume=14|language=en|location=Berlin, Heidelberg|publisher=Springer|pages=495–510|doi=10.1007/978-3-662-21545-6_38|isbn=978-3-662-21545-6}}</ref>

After graduating from Princeton, Aho joined the Computing Sciences Research Center at Bell Labs where he devised efficient [[regular expression]] and string-pattern matching algorithms that he implemented in the first versions of the [[Unix]] tools <code>[[egrep]]</code> and <code>[[fgrep]]</code>.  The <code>fgrep</code> 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.<ref>{{Cite journal|last1=Aho|first1=Alfred V.|last2=Corasick|first2=Margaret J.|date=June 1975|title=Efficient String Matching: An Aid to Bibliographic Search|url=|journal=[[Communications of the ACM]]|volume=18|issue=6|pages=333–340|doi=10.1145/360825.360855|s2cid=207735784|doi-access=free}}</ref>

At Bell Labs, Aho worked closely with [[Stephen C. Johnson|Steve Johnson]] and [[Jeffrey Ullman]] to develop efficient algorithms for analyzing and translating programming languages.<ref>{{Cite journal|last1=Aho|first1=A. V.|last2=Johnson|first2=S. C.|last3=Ullman|first3=J. D.|year=1977|title=Code Generation for Expressions with Common Subexpressions|journal=Journal of the ACM|volume=24|pages=146–160|doi=10.1145/321992.322001|s2cid=2614214|doi-access=free}}</ref> Steve Johnson used the bottom-up LALR parsing algorithms to create the syntax-analyzer generator [[yacc]],<ref name="red">{{cite news|last1=Morris|first1=Richard|date=October 1, 2009|title=Stephen Curtis Johnson: Geek of the Week|work=Red Gate Software|url=https://www.red-gate.com/simple-talk/opinion/geek-of-the-week/stephen-curtis-johnson-geek-of-the-week/|access-date=January 19, 2018}}</ref> and [[Michael E. Lesk]] and [[Eric Schmidt]] used Aho's regular-expression pattern-matching algorithms to create the lexical-analyzer generator [[lex (software)|lex]].<ref>{{cite web|last1=Lesk|first1=M.E.|last2=Schmidt|first2=E.|title=Lex – A Lexical Analyzer Generator|url=http://dinosaur.compilertools.net/lex/index.html|access-date=August 16, 2010}}</ref> The lex and yacc tools and their derivatives have been used to develop the front ends of many of today's programming language compilers.<ref>{{cite book|last1=Levine|first1=John R.|url=https://archive.org/details/lexyacc00levi|title=lex & yacc|last2=Mason|first2=Tony|last3=Brown|first3=Doug|publisher=[[O'Reilly Media|O'Reilly]]|year=1992|isbn=1-56592-000-7|edition=2|pages=[https://archive.org/details/lexyacc00levi/page/1 1]–2|author-link1=John R. Levine|url-access=registration}}</ref>

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]]'' 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]] to create a new edition, "the red dragon book" (which was briefly shown in the 1995 movie ''[[Hackers (film)|Hackers]]''), and in 2006 also by [[Monica Lam]] to create "the [[Compilers: Principles, Techniques, and Tools|purple dragon book]]". The dragon books are used for university courses as well as industry references.<ref>{{Cite web|title=DYOL: Design Your Own Language — corpus — Dragon Books — Purple Dragon|url=http://slebok.github.io/dyol/books/DB-PD.html|access-date=April 3, 2021|website=slebok.github.io}}</ref>

In 1974, Aho, [[John Hopcroft]], and Ullman wrote ''The Design and Analysis of Computer Algorithms'',<ref name="alg design & analysis">{{Cite book |first1=Alfred V. |last1=Aho |author-link1=Alfred Aho |first2=John E. |last2=Hopcroft |author-link2=John Hopcroft |first3=Jeffrey D. |last3=Ullman |author-link3=Jeffrey Ullman |year=1974 |title=The Design and Analysis of Computer Algorithms |publisher=Addison-Wesley |isbn=978-0-201-00029-0}}</ref> 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]]s as a central course in the computer science curriculum.<ref name=Ibaraki>{{cite web |url=https://www.forbes.com/sites/stephenibaraki/2021/03/31/jeffrey-ullman-and-alfred-aho-2020-acm-amturing-award-recipients/ |website=forbes.com |title= Jeffrey Ullman And Alfred Aho, 2020 ACM A.M.Turing Award Recipients |first=Stephen |last=Ibaraki |authorlink=Stephen Ibaraki |access-date=April 3, 2021}}</ref>

Aho is also widely known for his co-authorship of the [[AWK programming language]] with [[Peter J. Weinberger]] and [[Brian Kernighan]] (the "A" stands for "Aho").<ref>{{Cite journal|last1=Aho|first1=A. V.|last2=Kernighan|first2=B. W.|last3=Weinberger|first3=P. J.|year=1979|title=Awk — a pattern scanning and processing language|journal=Software: Practice and Experience|volume=9|issue=4|pages=267|citeseerx=10.1.1.80.4787|doi=10.1002/spe.4380090403|s2cid=29399630}}</ref> {{As of|2010}} Aho's research interests include programming languages, compilers, algorithms, and [[quantum computing]]. He is part of the Language and Compilers research-group at Columbia University.<ref>{{Cite web|url=http://landc.cs.columbia.edu/|title=Languages and Compilers|website=landc.cs.columbia.edu|accessdate=May 18, 2023}}</ref>

Overall, his works have been cited 81,040 times and he has an [[h-index]] of 66, as of May 8, 2019.<ref>{{Cite web|url = https://scholar.google.com/citations?user=gb2r2ssAAAAJ|title = Google Scholar Record for Alfred Aho}}</ref>

Aho has received many prestigious honors, including the [[Institute of Electrical and Electronics Engineers|IEEE]]'s [[IEEE John von Neumann Medal|John von Neumann Medal]] and membership in the [[National Academy of Engineering]] and the [[National Academy of Sciences]]. He was elected a Fellow of the [[American Academy of Arts and Sciences]] in 2003.<ref name=AAAS>{{cite web|title=Book of Members, 1780–2010: Chapter A|url=http://www.amacad.org/publications/BookofMembers/ChapterA.pdf|publisher=American Academy of Arts and Sciences|access-date=April 6, 2011| archive-url= https://web.archive.org/web/20110510021801/http://www.amacad.org/publications/BookofMembers/ChapterA.pdf| archive-date= May 10, 2011 | url-status= live}}</ref> He holds honorary doctorates from the [[University of Waterloo]],<ref name=":1">{{Cite web|date=February 16, 2017|title=DLS – Alfred Aho|url=https://uwaterloo.ca/computer-science/dls-alfred-aho|access-date=April 3, 2021|website=Cheriton School of Computer Science|language=en}}</ref> from the [[University of Helsinki]],<ref name=":1" /> and from the [[University of Toronto]].<ref name="Do">{{cite web |url=https://www.utoronto.ca/news/nobel-prize-computing-u-t-engineering-alumnus-alfred-aho-receives-am-turing-award |website=utoronto.ca |title='Nobel Prize of computing:' U of T Engineering alumnus Alfred Aho receives A.M. Turing Award | first=Liz |last=Do |access-date=April 3, 2021}}</ref> He is a Fellow of the [[American Association for the Advancement of Science]], [[Association for Computing Machinery|ACM]], [[Bell Labs]], and [[IEEE]].<ref name=Ibaraki/>

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]].<ref>{{cite news|url = https://www.nytimes.com/1987/02/17/science/brief-us-suppression-of-proof-stirs-anger.html|title = Brief U.S. Suppression of Proof Stirs Anger|date = February 17, 1987|access-date = November 10, 2015|via = Safari|newspaper = The New York Times}}</ref> Aho, Hopcroft, and Ullman were co-recipients of the 2017 [[C&C Prize]] awarded by [[NEC]] Corporation.<ref>{{Cite web|title=2017 C&C Prize Ceremony|url=https://www.candc.or.jp/en/2017/ceremony.html|url-status=live|access-date=April 3, 2021|website=[[NEC]] C&C Foundation|archive-url=https://web.archive.org/web/20180710002803/http://www.candc.or.jp:80/en/2017/ceremony.html |archive-date=July 10, 2018 }}</ref>  He and Ullman were named recipients of the 2020 [[Turing Award]] on March 31, 2021.<ref name=":0">[https://awards.acm.org/about/2020-turing ACM Turing Award Honors Innovators Who Shaped the Foundations of Programming Language Compilers and Algorithms].  Retrieved March 31, 2021.</ref>

==Personal life==
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.<ref>{{Cite web|date=July 18, 2013|title=Watch: Computer Scientist Alfred Aho|url=https://www.simonsfoundation.org/2013/07/19/alfred-aho/|access-date=April 3, 2021|website=Simons Foundation|language=en-US}}</ref><ref>{{Cite web |title=Master Recipient List |url=https://www.socgtoday.com/masterrecipientlist |access-date=2023-04-15 |website=Society of Columbia Graduates |language=en-US}}</ref>

==Books==
*A. V. Aho and [[Jeffrey Ullman|J. D. Ullman]], ''The Theory of Parsing, Translation, and Compiling, Vol. 1, Parsing.'' Prentice Hall, 1972. {{ISBN|0-13-914556-7}}
*A. V. Aho (ed.) ''Currents in the Theory of Computing.'' Prentice Hall, 1973. {{ISBN|0-13-195651-5}}<ref>{{cite book |url=https://www.worldcat.org/oclc/976868524 |via=worldcat.org |title=Currents in the theory of computing, edited by Alfred V. Aho. Contributing authors: Ronald V. Book [and others]. |oclc=976868524 |access-date=April 1, 2021}}</ref>
*A. V. Aho and [[Jeffrey Ullman|J. D. Ullman]], ''The Theory of Parsing, Translation, and Compiling, Vol. 2, Compiling.'' Prentice-Hall, 1973. {{ISBN|978-0-13-914564-3}}
*{{Cite book |first1=Alfred V. |last1=Aho |author-link1=Alfred Aho |first2=John E. |last2=Hopcroft |author-link2=John Hopcroft |first3=Jeffrey D. |last3=Ullman |author-link3=Jeffrey Ullman |year=1974 |title=The Design and Analysis of Computer Algorithms |publisher=Addison-Wesley |isbn=978-0-201-00029-0}}
*A. V. Aho and [[Jeffrey Ullman|J. D. Ullman]], ''Principles of Compiler Design.'' Addison-Wesley, 1977. {{ISBN|0-201-00022-9}}
*A. V. Aho, [[J. E. Hopcroft]], [[Jeffrey Ullman|J. D. Ullman]], ''Data Structures and Algorithms.'' Addison-Wesley, 1983. {{ISBN|0-201-00023-7}}
*A. V. Aho, [[Ravi Sethi|R. Sethi]], [[Jeffrey Ullman|J. D. Ullman]], ''[[Compilers: Principles, Techniques, and Tools]].'' Addison-Wesley, Reading MA 1986. {{ISBN|0-201-10088-6}}
*A. V. Aho, [[Brian W. Kernighan|B. W. Kernighan]], and [[Peter J. Weinberger|P. J. Weinberger]], ''The AWK Programming Language.'' Addison-Wesley, 1988. {{ISBN|978-0-201-07981-4}}
*A. V. Aho and [[Jeffrey Ullman|J. D. Ullman]], ''[http://infolab.stanford.edu/~ullman/focs.html Foundations of Computer Science].'' W. H. Freeman/Computer Science Press, 1992. {{ISBN|978-0-7167-8233-9}}<ref>{{cite book |url=https://www.worldcat.org/oclc/24669768 |via=worldcat.org |title=Foundations of computer science |oclc=24669768 |access-date=April 1, 2021}}</ref><ref>{{cite book |url=https://www.worldcat.org/oclc/797873166 |via=worldcat.org |title=Foundations of computer science |oclc=797873166 |access-date=April 1, 2021}}</ref>
**A. V. Aho and [[Jeffrey Ullman|J. D. Ullman]], ''Foundations of Computer Science, C Edition.'' W. H. Freeman, 1995. {{ISBN|978-0-7167-8284-1}}
*A. V. Aho, [[Monica S. Lam|M. S. Lam]], [[Ravi Sethi|R. Sethi]], and [[Jeffrey Ullman|J. D. Ullman]], ''[[Compilers: Principles, Techniques, and Tools]], Second Edition.'' Addison-Wesley, 2007. {{ISBN|978-0-321-48681-3}}

==References==
{{Reflist}}

==External links==
* {{zbMATH |name=Aho, Alfred Vaino}}
*[https://dl.acm.org/profile/81100024612 Alfred V Aho] at the [[Association for Computing Machinery|ACM]] Digital Library

{{Turing award}}
{{Authority control}}

{{DEFAULTSORT:Aho, Alfred}}
[[Category:1941 births]]
<!-- perhaps naturalized American -->
[[Category:Canadian people of Finnish descent]]
[[Category:Columbia University faculty]]
[[Category:Columbia School of Engineering and Applied Science faculty]]
[[Category:1996 fellows of the Association for Computing Machinery]]
[[Category:Fellows of the IEEE]]
[[Category:American people of Finnish descent]]
[[Category:Living people]]
[[Category:Princeton University School of Engineering and Applied Science alumni]]
[[Category:Programming language designers]]
[[Category:Scientists at Bell Labs]]
[[Category:Canadian theoretical computer scientists]]
[[Category:Turing Award laureates]]
[[Category:University of Toronto alumni]]
[[Category:People from Timmins]]
[[Category:Scientists from Ontario]]
[[Category:Fellows of the American Academy of Arts and Sciences]]
[[Category:Members of the United States National Academy of Engineering]]
[[Category:Members of the United States National Academy of Sciences]]
[[Category:Canadian textbook writers]]