Alfred Vaino Aho (né le 9 août 1941) est un informaticien canadien surtout connu pour ses travaux sur les langages de programmation, les compilateurs et les algorithmes associés, ainsi que pour ses manuels sur l'art et la science de la programmation informatique. Lui et son collaborateur de longue date Jeffrey Ullman sont les lauréats du prix Turing 2020, généralement reconnu comme la plus haute distinction en informatique. Aho a été élu à l'Académie nationale d'ingénierie en 1999 pour ses contributions aux domaines des algorithmes et des outils de programmation.
Les recherches et publications d'Aho ont eu un impact durable sur la manière dont les langages de programmation sont conçus, analysés et compilés. Ses manuels, en particulier les « livres du dragon » sur la conception de compilateurs, ont formé des générations d'informaticiens et d'ingénieurs. Son travail s'étend des fondements théoriques aux outils pratiques utilisés dans le système d'exploitation Unix.
Formation et début de carrière
Aho a obtenu un B.A.Sc. (1963) en physique de l'ingénierie de l'Université de Toronto, puis une maîtrise (1965) et un doctorat (1967) en génie électrique/informatique de l'Université Princeton. Dans sa thèse de doctorat, Aho a créé les grammaires indexées et l'automate à pile imbriquée comme véhicules pour étendre la puissance des langages hors-contexte tout en conservant plusieurs de leurs propriétés de décidabilité et de clôture. Une application des grammaires indexées est la modélisation des systèmes de réécriture parallèles, en particulier dans les applications biologiques.
Après avoir obtenu son diplôme de Princeton, Aho a rejoint le Centre de recherche en sciences informatiques de Bell Labs, où il a conçu des algorithmes efficaces de correspondance de motifs et d'expressions régulières qu'il a implémentés dans les premières versions des outils Unix egrep et fgrep. L'algorithme fgrep est devenu connu sous le nom d'algorithme d'Aho-Corasick ; il est utilisé par plusieurs systèmes de recherche bibliographique et d'autres applications de recherche de chaînes.
Contributions aux compilateurs et outils
Chez Bell Labs, Aho a travaillé en étroite collaboration avec Steve Johnson et Jeffrey Ullman pour développer des algorithmes efficaces pour analyser et traduire les langages de programmation. Steve Johnson a utilisé les algorithmes d'analyse LALR ascendante pour créer le générateur d'analyseur syntaxique yacc, et Michael E. Lesk et Eric Schmidt ont utilisé les algorithmes de correspondance de motifs d'expressions régulières d'Aho pour créer le générateur d'analyseur lexical lex. Les outils lex et yacc et leurs dérivés ont été utilisés pour développer les fronts d'analyse de nombreux compilateurs de langages de programmation actuels.
Aho est également largement connu pour sa co-auteur du langage de programmation AWK avec Peter J. Weinberger et Brian Kernighan (le « A » signifie « Aho »). Ce langage de traitement de texte est devenu un outil standard dans les environnements Unix et a influencé de nombreux langages de script ultérieurs.
Les livres du dragon et les algorithmes
Aho et Ullman ont écrit une série de manuels sur les techniques de compilation qui ont codifié la théorie pertinente pour la conception de compilateurs. Leur manuel de 1977, Principles of Compiler Design, avait un dragon vert sur la couverture et est devenu connu sous le nom de « livre du dragon vert ». En 1986, Aho et Ullman ont été rejoints par Ravi Sethi pour créer une nouvelle édition, « le livre du dragon rouge », et en 2006 également par Monica Lam pour créer « le livre du dragon violet ». Les livres du dragon sont utilisés pour les cours universitaires ainsi que comme références industrielles.
En 1974, Aho, John Hopcroft et Ullman ont écrit The Design and Analysis of Computer Algorithms, codifiant certaines de leurs premières recherches sur les algorithmes. Ce livre est devenu l'un des livres les plus cités en informatique pendant plusieurs décennies et a contribué à stimuler la création des algorithmes et des structures de données comme cours central dans le programme d'informatique.
Carrière académique et distinctions
Depuis 1995, Aho occupe la chaire Lawrence Gussman en informatique à l'Université Columbia. Il a été président du département de 1995 à 1997, puis à nouveau au printemps 2003. En 2010, ses intérêts de recherche incluent les langages de programmation, les compilateurs, les algorithmes et le calcul quantique. Il fait partie du groupe de recherche sur les langages et les compilateurs à l'Université Columbia.
Aho a reçu de nombreuses distinctions prestigieuses, notamment la médaille John von Neumann de l'IEEE et son adhésion à l'Académie nationale d'ingénierie et à l'Académie nationale des sciences. Il a été élu membre de l'Académie américaine des arts et des sciences en 2003. Il détient des doctorats honorifiques de l'Université de Waterloo, de l'Université d'Helsinki et de l'Université de Toronto. Il est membre de l'Association américaine pour l'avancement des sciences, de l'ACM, de Bell Labs et de l'IEEE. Aho, Hopcroft et Ullman ont été co-lauréats du prix C&C 2017 décerné par NEC Corporation. Lui et Ullman ont été nommés lauréats du prix Turing 2020 le 31 mars 2021.
Vie personnelle et enseignement
Aho enseigne à l'Université Columbia à New York depuis 1995. Il a remporté le prix du Grand Enseignant de la Société des diplômés de Columbia en 2003. Aho a été deux fois président du comité consultatif de la direction de l'informatique et des sciences de l'information de la Fondation nationale pour la science. Il est un ancien président du groupe d'intérêt spécial de l'ACM sur les algorithmes et la théorie de la calculabilité. Dans l'ensemble, ses travaux ont été cités 81 040 fois et il a un indice h de 66, au 8 mai 2019.