Alfred Aho et Jeffrey Ullman remportent le prix Turing 2020

Alfred Aho et Jeffrey Ullman remportent le prix Turing 2020,
pour leurs travaux sur les compilateurs et les algorithmes

La plus importante société savante d’informatique, Association for Computing Machinery (ACM), a décerné, mercredi, sa prestigieuse récompense, le prix Turing, à deux pionniers de l’informatique, pour les algorithmes fondamentaux et la théorie qui sous-tendent la mise en œuvre des langages de programmation et pour avoir synthétisé ces résultats et ceux des autres dans leurs livres très impactants, qui ont formé des générations d'informaticiens. Le Canadien Alfred Aho et l’Américain Jeffrey Ullman se partagent le million de dollars du prix, qui représente le sommet de cette discipline depuis la fin des années 1960.

Créé par l’InterTrust Technologies Corporation’s Strategic Technologies and Architectural Research Laboratory (STAR Lab), le prix Turing est décerné par l’Association for Computing Machinery. Le prix Turing ou ACM Turing Award, en hommage à Alan Turing (1912-1954), est attribué tous les ans à une personne sélectionnée pour sa contribution de nature technique faite à la communauté informatique. Les contributions doivent être d’une importance technique majeure et durable dans le domaine informatique.

Alfred V. Aho est un informaticien canadien. Professeur émérite Lawrence Gussman d'informatique de l'université Columbia, il est surtout connu pour ses travaux sur les langages de programmation, les compilateurs et les algorithmes connexes, ainsi que pour ses manuels sur l'art et la science de la programmation informatique. Et Jeffrey D. Ullman est un informaticien américain. Également connu pour ses manuels sur les compilateurs, la théorie du calcul, les structures de données et les bases de données qui sont cités comme des références dans leur domaine.

Pièce jointe 594817
Jeffrey Ullman, à gauche, et Alfred Aho ont été des pionniers dans la création des compilateurs qui traduisent les langages de programmation en langage machine (un et zéro) pour les ordinateurs.

Aho et Ullman ont commencé leur collaboration aux Bell Labs, qu'ils ont tous deux rejoints après avoir obtenu leur doctorat à l'université de Princeton. Pendant leur séjour aux Bell Labs, ils ont mis au point des algorithmes efficaces pour l'analyse et la traduction des langages de programmation, et ils ont poursuivi leur étroite collaboration après que Ullman eut rejoint le monde universitaire en 1969. Leurs contributions, individuelles et conjointes, à la recherche sur plusieurs décennies, ont jeté les bases de la théorie et de la mise en œuvre des langages de programmation, ainsi que de la conception et de l'analyse des algorithmes.

Aho et Ullman ont contribué à la théorie des langages formels et ont inventé des algorithmes efficaces pour l'analyse lexicale, l'analyse syntaxique, la génération de code et l'optimisation du code. Comme exemple, dans un de leurs premiers articles, Aho et Ullman ont montré comment il était possible de faire fonctionner l'algorithme d'analyse syntaxique LR(k) de Knuth avec des grammaires simples qui, techniquement, ne répondaient pas aux exigences d'une grammaire LR(k) ; cette idée a donné naissance au générateur d'analyse syntaxique YACC, qui a été pendant de nombreuses années la méthode privilégiée pour construire rapidement des analyseurs syntaxiques.

Ils ont développé des algorithmes efficaces pour l'analyse du flux de données qui exploitent la structure des programmes sans goto, qui étaient à l'époque en train de devenir la norme. Alors que le domaine des bases de données relationnelles s'ouvrait, leur article (with Catriel Beeri) sur les « jointures sans perte » expliquait ce que les formes normales définies par Codd, Fagin et d'autres tentaient de faire en matière de conception de bases de données et donnait une méthodologie pour déterminer quand il était possible de décomposer une relation en composants plus petits sans perdre d'informations.

Leurs recherches, ainsi que celles d'autres personnes, ont constitué la base de leur série de deux volumes sur l'analyse syntaxique et la compilation, qui a abouti à leur ouvrage définitif sur la technologie des compilateurs, Principles of Compiler Design, publié en 1977. Ce "The gragon book" (surnommé ainsi en raison de sa couverture colorée) et ses éditions ultérieures avec Ravi Sethi, puis avec Sethi et Monica Lam, sont devenus les bibles de la conception de compilateurs. Ces livres exposent de manière lucide les phases de la traduction d'un langage de programmation de haut niveau en code machine, modularisant ainsi toute l'entreprise de la construction de compilateurs. Leurs algorithmes fondamentaux ont été incorporés dans des compilateurs commerciaux et des outils de construction de compilateurs populaires, tels que Lex et YACC, qui sont couramment utilisés par des millions de personnes dans le monde pour automatiser la construction des composants des compilateurs.

L'impact de leurs travaux depuis les années 1970 est si profond et si omniprésent qu'il est facilement considéré comme acquis. Quiconque a programmé en C ou l'un de ses dérivés, quiconque a utilisé des outils Unix tels qu'AWK, fgrep, Lex et YACC, quiconque a suivi un cours de compilation ou quiconque a construit un compilateur en lisant simplement le Dragon Book a été touché par le travail d'Aho et Ullman.

Leurs premiers travaux conjoints sur la conception d'algorithmes et les techniques d'analyse ont apporté des approches cruciales au noyau théorique de l'informatique qui a émergé à cette époque. Axé sur les méthodes de base pour le traitement des graphes, des chaînes de caractères et des séquences, ce travail algorithmique était également étroitement intégré à leurs recherches sur les langages de programmation.

Leur livre fondateur avec John Hopcroft, The Design and Analysis of Computer Algorithms, publié en 1974, a créé le cadre conceptuel non seulement pour l'enseignement des algorithmes dans le programme standard d'informatique pendant des décennies, mais aussi pour la présentation et l'analyse des nouveaux algorithmes développés par la communauté des chercheurs. En plus d'incorporer leurs propres résultats, le livre a codifié une série d'algorithmes disparates en un ensemble de méthodes de conception générales, dont le diviser pour régner, la récursion, la programmation dynamique et d'autres qui sont depuis longtemps entrées dans la boîte à outils standard des informaticiens.

Le prix A.M. Turing en hommage à Alan M. Turing, le mathématicien britannique qui a défini les fondements et les limites mathématiques de l'informatique et qui a joué un rôle clé dans la cryptanalyse du code Enigma par les Alliés pendant la Seconde Guerre mondiale. Depuis sa création en 1966, le prix Turing a honoré les informaticiens et les ingénieurs qui ont créé les systèmes et les fondements théoriques sous-jacents qui ont propulsé l'industrie des technologies de l'information.

« La pratique de la programmation informatique et le développement des logiciels de plus en plus sophistiqués sous-tendent presque toutes les transformations technologiques que nous avons connues dans la société au cours des cinq dernières décennies », explique Gabriele Kotsis, président de l'ACM. « Si d'innombrables chercheurs et praticiens ont contribué à ces technologies, les travaux d'Aho et Ullman ont été particulièrement influents. Ils nous ont aidés à comprendre les fondements théoriques des algorithmes et à tracer la voie de la recherche et de la pratique en matière de compilateurs et de conception de langages de programmation. Aho et Ullman sont des leaders d'opinion depuis le début des années 1970, et leurs travaux ont guidé des générations de programmeurs et de chercheurs jusqu'à aujourd'hui.

« Aho et Ullman ont établi des idées fondamentales sur les algorithmes, les langages formels, les compilateurs et les bases de données, qui ont joué un rôle déterminant dans le développement du paysage actuel de la programmation et des logiciels », a ajouté Jeff Dean, Senior Fellow de Google et SVP, Google AI. « Ils ont également illustré comment ces différentes disciplines sont étroitement interconnectées. Aho et Ullman ont introduit des concepts techniques clés, notamment des algorithmes spécifiques, qui ont été essentiels. En termes d'enseignement de l'informatique, leurs manuels ont été la référence pour la formation des étudiants, des chercheurs et des praticiens ».

Source : ACM

Et vous ?

:fleche: Avez-vous déjà lu un des manuels de ces deux lauréats ? Lequel ?

:fleche: Quel est votre avis sur le prix décerné à Alfred Aho et Jeffrey Ullman ?

Voir aussi :

:fleche: Les « parrains de l'intelligence artificielle » récompensés du prix Turing 2018, le prix Nobel de l'informatique

:fleche: Tim Berners-Lee lauréat du « Prix Nobel de l'informatique » 2016, remporte un million de dollars pour l'invention du WWW et du premier navigateu

:fleche: Le prix Turing pour un chercheur de légende, Google et Intel applaudissent ce « Nobel de l'informatique » remis à un employé de Microsoft

:fleche: Prix Turing 2013 décerné le 18 mars, Leslie Lamport remporte le prix pour cette année