3 - Sequential algorithms as bistable maps

Summary

En guise de prologue

Gilles Kahn, pour moi, ce fut d'abord un article, en français s'il vous plait, texte qui fut le point de départ de ma recherche:

G. Kahn et G. Plotkin, Domaines concrets, TR IRIA-Laboria 336 (1978), paru en version anglaise en 1993 – signe de son influence dans le temps – dans le volume d'hommage à Corrado Böhm.

On ne pouvait imaginer un meilleur appât pour le jeune homme que j'étais, arrivé à l'informatique par le fruit d'une hésitation entre mathé matiques (intimidantes) et langues (les vraies). Un autre collègue trop tôt disparu, Maurice Gross, m'avait aidé à choisir une tierce voie et m'avait guidé vers le DEA d'Informatique Théorique de Paris 7. Les cours de Luc Boasson et de Dominique Perrin m'avaient déjà bien ferré, mais la rencontre des domaines concrets m'a définitivement “attrapé”, et parce qu'il s'agissait de structures ressemblant aux treillis – rencontrés assez tôt dans ma scolarité grâce aux Leçons d'Algèbre Moderne de Paul Dubreil et Marie-Louise Dubreil Jacotin que m'avait conseillées mon professeur de mathématiques –, et parce que Gérard Berry qui m'avait mis ce travail entre les mains avait une riche idée pour bâtir sur cette pierre.

L'idée directrice de cet article était de donner une définiton générale de structure de données, comprenant les listes, les arbres, les enregistrements, les enregistrements avec variantes, etc…, et, comme l'on fait dans toute bonne mathématique, une bonne notion de morphisme entre ces structures: Cette définition était donnée sous deux facettes équivalentes et reliées par un théorème de représentation: l'une concrète, en termes de cellules (nœeuds d'arbres, champs d'enrigistrements, …) et de valeurs, l'autre abstraite, en termes d'ordres partiels.