Alfred Vaino Aho (* 9. August 1941) ist ein kanadischer Informatiker, der vor allem für seine Arbeiten an Programmiersprachen, Compilern und zugehörigen Algorithmen sowie für seine Lehrbücher über die Kunst und Wissenschaft der Computerprogrammierung bekannt ist. Er und sein langjähriger Mitarbeiter Jeffrey Ullman sind die Träger des Turing Awards 2020, der allgemein als die höchste Auszeichnung in der Informatik gilt. Aho wurde 1999 in die National Academy of Engineering gewählt, für seine Beiträge auf den Gebieten der Algorithmen und Programmierwerkzeuge.
Ahos Forschung und Veröffentlichungen haben einen bleibenden Einfluss darauf gehabt, wie Programmiersprachen entworfen, analysiert und kompiliert werden. Seine Lehrbücher, insbesondere die „Drachenbücher“ zum Compilerentwurf, haben Generationen von Informatikern und Ingenieuren ausgebildet. Seine Arbeit reicht von theoretischen Grundlagen bis zu praktischen Werkzeugen, die im Unix-Betriebssystem verwendet werden.
Ausbildung und frühe Karriere
Aho erhielt 1963 einen B.A.Sc. in Ingenieurphysik von der University of Toronto und anschließend 1965 einen M.A. sowie 1967 einen Ph.D. in Elektrotechnik/Informatik von der Princeton University. In seiner Doktorarbeit entwickelte Aho indizierte Grammatiken und den Nested-Stack-Automaten als Mittel, um die Ausdruckskraft kontextfreier Sprachen zu erweitern, während viele ihrer Entscheidbarkeits- und Abschlusseigenschaften erhalten blieben. Eine Anwendung indizierter Grammatiken ist die Modellierung paralleler Umschreibsysteme, insbesondere in biologischen Anwendungen.
Nach seinem Abschluss an Princeton trat Aho dem Computing Sciences Research Center bei Bell Labs bei, wo er effiziente Algorithmen für reguläre Ausdrücke und String-Musterabgleich entwickelte, die er in den ersten Versionen der Unix-Werkzeuge egrep und fgrep implementierte. Der fgrep-Algorithmus wurde als Aho-Corasick-Algorithmus bekannt; er wird von mehreren bibliografischen Suchsystemen und anderen String-Suchanwendungen verwendet.
Beiträge zu Compilern und Werkzeugen
Bei Bell Labs arbeitete Aho eng mit Steve Johnson und Jeffrey Ullman zusammen, um effiziente Algorithmen zur Analyse und Übersetzung von Programmiersprachen zu entwickeln. Steve Johnson nutzte die Bottom-up-LALR-Parsing-Algorithmen, um den Syntax-Analyse-Generator yacc zu erstellen, und Michael E. Lesk sowie Eric Schmidt verwendeten Ahos Algorithmen für reguläre Ausdrücke, um den Lexikalischen-Analyse-Generator lex zu erstellen. Die Werkzeuge lex und yacc sowie ihre Ableitungen wurden verwendet, um die Frontends vieler heutiger Compiler für Programmiersprachen zu entwickeln.
Aho ist auch weithin bekannt für seine Mitautorschaft an der Programmiersprache AWK mit Peter J. Weinberger und Brian Kernighan (das „A“ steht für „Aho“). Diese Textverarbeitungssprache wurde zu einem Standardwerkzeug in Unix-Umgebungen und beeinflusste viele spätere Skriptsprachen.
Die Drachenbücher und Algorithmen
Aho und Ullman schrieben eine Reihe von Lehrbüchern über Compilertechniken, die die für den Compilerentwurf relevante Theorie kodifizierten. Ihr Lehrbuch von 1977, Principles of Compiler Design, hatte einen grünen Drachen auf dem Cover und wurde als „das grüne Drachenbuch“ bekannt. 1986 kamen Ravi Sethi zu Aho und Ullman hinzu, um eine neue Ausgabe zu erstellen, „das rote Drachenbuch“, und 2006 auch Monica Lam, um „das lila Drachenbuch“ zu erstellen. Die Drachenbücher werden sowohl für Universitätskurse als auch als Industriestandardreferenz verwendet.
1974 schrieben Aho, John Hopcroft und Ullman The Design and Analysis of Computer Algorithms und kodifizierten damit einige ihrer frühen Forschungsarbeiten zu Algorithmen. Dieses Buch wurde mehrere Jahrzehnte lang zu einem der am häufigsten zitierten Bücher in der Informatik und trug dazu bei, Algorithmen und Datenstrukturen als zentralen Kurs im Informatik-Curriculum zu etablieren.
Akademische Karriere und Ehrungen
Seit 1995 hat Aho die Lawrence-Gussman-Professur für Informatik an der Columbia University inne. Er war von 1995 bis 1997 und erneut im Frühjahr 2003 Vorsitzender der Abteilung. Ab 2010 umfassen seine Forschungsinteressen Programmiersprachen, Compiler, Algorithmen und Quantencomputing. Er ist Teil der Forschungsgruppe für Sprachen und Compiler an der Columbia University.
Aho hat viele prestigeträchtige Ehrungen erhalten, darunter die John-von-Neumann-Medaille des IEEE und die Mitgliedschaft in der National Academy of Engineering und der National Academy of Sciences. Er wurde 2003 zum Fellow der American Academy of Arts and Sciences gewählt. Er besitzt Ehrendoktorwürden der University of Waterloo, der University of Helsinki und der University of Toronto. Er ist Fellow der American Association for the Advancement of Science, der ACM, von Bell Labs und des IEEE. Aho, Hopcroft und Ullman waren Mitempfänger des C&C-Preises 2017, verliehen von der NEC Corporation. Er und Ullman wurden am 31. März 2021 als Empfänger des Turing Awards 2020 benannt.
Persönliches Leben und Lehre
Aho lehrt seit 1995 an der Columbia University in New York City. Er gewann 2003 den Great Teacher Award der Society of Columbia Graduates. Aho war zweimal Vorsitzender des Advisory Committee für die Computer and Information Science and Engineering Directorate der National Science Foundation. Er ist ehemaliger Präsident der ACM Special Interest Group on Algorithms and Computability Theory. Insgesamt wurden seine Werke bis zum 8. Mai 2019 81.040-mal zitiert, und er hat einen h-Index von 66.