L'informatique de Claude Pair (2021) Créhange : Différence entre versions
(→Didactique de la programmation : la méthode déductive) |
|||
Ligne 431 : | Ligne 431 : | ||
à chaque étape une définition puisée dans une liste prédéfinie de primitives usuelles | à chaque étape une définition puisée dans une liste prédéfinie de primitives usuelles | ||
de l’algorithmique : formules, conditionnelles, itérations — considérées ici comme | de l’algorithmique : formules, conditionnelles, itérations — considérées ici comme | ||
− | + | la définition de suites —, fonctions, dont la définition apparaît comme un nouveau | |
+ | problème à résoudre. Chaque étape de la construction est une déduction, d’où le nom | ||
+ | de « méthode déductive ». | ||
+ | Pour illustrer la démarche contentons-nous d’un exemple simplissime, à savoir la | ||
+ | recherche du maximum de 3 nombres. Commençons donc par écrire la caractérisa- | ||
+ | tion informelle du résultat : | ||
+ | M : est le maximum de a, b, c | ||
+ | Il s’agit alors de choisir, parmi les définitions algorithmiques référencées dans la | ||
+ | méthode, l’une d’entre elles qui nous fera progresser vers la solution en introduisant | ||
+ | au besoin de nouvelles entités. Ce sera, ici, une définition conditionnelle : | ||
+ | M = si a > mbc alors a sinon mbc | ||
+ | avec introduction de deux intermédiaires à définir : | ||
+ | a = donnée, | ||
+ | mbc = maximum de b et c | ||
+ | et l’introduction de deux intermédiaires à définir, b et c qui sont des données. Une | ||
+ | nouvelle conditionnelle porte sur des données qui sont connues : | ||
+ | mbc = si b > c alors b sinon c | ||
+ | Ce qui résout le problème. La méthode organise ce travail dans une table à deux | ||
+ | colonnes, les définitions informelles et définitions formelles. Ici : | ||
+ | Définitions informelles | ||
+ | Définitions formelles (algorithmiques) | ||
+ | M : Maximum de a, b, c | ||
+ | M = si a > mbc alors a sinon mbc | ||
+ | mbc : maximum de b et c | ||
+ | mbc = si b > c alors b sinon c | ||
+ | a, b, c : données | ||
+ | a, b, c = lire | ||
+ | Pour faire de ces définitions un algorithme séquentiel, il reste à les organiser, | ||
+ | c’est à dire à les ordonner pour la relation « dépend de » (tri topologique) facile à | ||
+ | déterminer depuis la colonne de droite. Une troisième colonne peut servir à établir | ||
+ | ce tri, tâche qui peut être automatisée qu’on peut rapprocher de la méthode [P47] que | ||
+ | Claude introduit à partir de 1973. | ||
+ | Définitions informelles | ||
+ | Ordre | ||
+ | Définitions formelles (algorithmiques) | ||
+ | M : Maximum de a, b, c | ||
+ | 3 | ||
+ | M = si a > mbc alors a sinon mbc | ||
+ | mbc : maximum de b et c | ||
+ | 2 | ||
+ | mbc = si b > c alors b sinon c | ||
+ | a, b, c : données | ||
+ | 1 | ||
+ | a, b, c = lire | ||
+ | Cette méthode a été largement employée à Nancy (université, IUT, écoles, IREM | ||
+ | et formation des professeurs du second degré), notamment pour l’initiation avec un | ||
+ | avantage pédagogique notoire : montrer aux étudiants que la programmation, loin | ||
+ | de se ramener à quelques recettes, peut s’appuyer sur le raisonnement et que ce | ||
+ | raisonnement s’enseigne. | ||
+ | Cependant, sa pratique ne s’est pas répandue et elle est donc restée une méthode | ||
+ | purement nancéienne 21. Son implantation informatique (Bernard Huc, [T34]), était | ||
+ | complète, mais la faiblesse des techniques ergonomiques de l’époque l’ont desservie. | ||
+ | Encore une innovation arrivée trop tôt, sans doute ! | ||
+ | Jacques Jaray évoque cette période : « à l’IUT, avec des élèves débu- | ||
+ | tants en informatique, nous avions constaté qu’en mal d’inspiration pour | ||
+ | construire l’algorithme solution d’un problème, ils commençaient par écrire | ||
+ | lire(données) et s’ensuivait une période de grande perplexité. | ||
+ | Je situe la naissance de la Méthode déductive, abrégée en MÉDÉE 22, | ||
+ | un peu après 1973. Claude était professeur au département informatique de | ||
+ | l’IUT, il enseignait la programmation aux élèves de première année. Il avait, | ||
+ | entre autres comme assistants : Françoise Bellegarde, Hubert Pistré, Bernard | ||
+ | Huc et moi-même... La méthode déductive s’est éteinte au milieu des années | ||
+ | 80, lorsque les langages objets ont été enseignés et parce qu’elle était peu | ||
+ | naturellement adaptée pour concevoir des systèmes réactifs ». | ||
+ | Autres aventures : école d’été, IFIP, Algol 68, IREM... | ||
+ | Nous ne pouvons pas décrire toutes les facettes de l’activité de Claude. Il nous | ||
+ | a plus d’une fois étonnés par sa manière d’accumuler les responsabilités... et de | ||
+ | les assumer tranquillement. Nulle boulimie, mais simplement quelques facilités, une | ||
+ | grande capacité de travail, de l’imagination, l’envie de servir et le soutien indéfec- | ||
+ | tible de son épouse Monique. Évoquons ici quelques autres aspects de ses actions en | ||
+ | lien avec la recherche. | ||
+ | Tout de suite après sa thèse, Claude entre en 1966 au groupe de travail WG 2.2 | ||
+ | de l’IFIP Formalisation of programming concepts qui vient d’être créé. Nous avons | ||
+ | indiqué son rôle d’animateur du groupe franco-belge sur Algol 68 (Manuel Algol 68, | ||
+ | [P37]), groupe qui subsistera sous plusieurs formes jusqu’en 1993 avec des partici- | ||
+ | pants de Grenoble, Rennes, Nancy, Paris, Montpellier [16]. Du côté belge, le groupe | ||
+ | bénéficiera notamment de la contribution déterminante de Michel Sintzoff 23, profes- | ||
+ | seur à l’université libre de Bruxelles [17]. | ||
+ | 21. Mais la méthode était encore étudiée avec un oeil mathématique en 2010, bulletin No48 de l’AP- | ||
+ | MEP, juillet-aôut 2010. | ||
+ | 22. Dénomination proposée par Pierre Lescanne et déclinée en Amédée Ducrin, nom d’auteur du livre | ||
+ | de programmation associé à la méthode [P63]. | ||
+ | 23. C’est par Algol68 que Claude et ses élèves ont connu Michel Sintzoff lorsqu’il était chercheur au | ||
+ | MBLE (laboratoire de Philips). Michel est resté en contact avec le CRIN. Lors d’une année sabbatique | ||
+ | passée à Nancy, il y a donné un séminaire remarquable sur les fondements de la programmation. | ||
Ligne 441 : | Ligne 525 : | ||
[[File:Informatique Claude Pair 2021 Créhange-18 1.jpg|500px|center]] | [[File:Informatique Claude Pair 2021 Créhange-18 1.jpg|500px|center]] | ||
− | |||
===Publications de Claude Pair=== | ===Publications de Claude Pair=== |
Version du 23 mars 2022 à 17:54
L'informatique de Claude Pair
L'apport de Claude Pair à la création de la science informatique (années 1963 - 1981)
|
Sommaire
Avant-propos
Cet article a été mis en ligne dans le cadre des travaux menés au sein d'un groupe de travail mémoire de l'association des émérites de Lorraine.
L'article
Introduction
Sur une suggestion amicale de Claude Pair, nous avons accepté, 50 ans après, de présenter son activité scientifique en tant que l’un des fondateurs de l’informatique universitaire en France. Cet article couvre la période 1963–1981 : en effet après avoir été professeur en classe préparatoire, Claude rejoint l’enseignement supérieur en 1963. Dix-huit ans plus tard, en 1981, il s’oriente vers la haute administration en devenant directeur des lycées au ministère de l’Éducation nationale.
Avant d’aborder la rédaction, nous avons proposé à Claude l’organisation d’un colloque. Cette formule a permis de multiplier les témoignages et de mieux faire collectivement le bilan de ses recherches. Ce colloque a eu lieu au LORIA, à Nancy, le 14 juin 2019 [2]. Il a réuni 150 participants avec 17 intervenants dont Antoine Petit, PDG du CNRS. Près de deux ans plus tard, nous avons assemblé nos notes, puisé dans les documents à notre disposition et activé notre mémoire.
Précisons d’entrée que le lecteur ne trouvera pas ici des démonstrations rigoureuses ni des formalisations complètes. Il lui faudra pour cela consulter les nombreuses publications de Claude ou les 48 thèses qu’il a dirigées [3]. Nous avons choisi d’ajouter à des propos scientifiques des parties plus anecdotiques signalées en italique. Nous espérons ainsi aérer la lecture et évoquer l’ambiance du travail d’équipe que Claude a instauré, équipe qui au départ se comptait sur les doigts d’une main. Équipe interuniversitaire qui, en grandissant, sera associée au CNRS en 1973 grâce à Claude, puis constituera le Centre de recherche en informatique de Nancy (CRIN) en 1975. La croissance s’est poursuivie : 70 personnes en 1977, une centaine en 1984 avec la venue de l’INRIA [4].
Il faut se souvenir qu’au début des années 60, la science informatique est dans la petite enfance. La plupart des domaines que nous connaissons aujourd’hui sont alors à créer, le plus souvent dans l’indifférence — ou même contre l’avis — des mathématiciens qui ne voient alors aucune raison de s’intéresser aux ordinateurs. Il faut aussi rappeler que les moyens de communication actuels n’existent pas. Il n’y a pas encore de terminologie propre à la recherche informatique [5] et beaucoup de chercheurs français publient dans leur langue maternelle, ce qui contribue à les isoler dans le monde. C’est dans ce cadre que Claude Pair imagine des concepts qui ont été redécouverts par la suite. Comme nous le montrerons, Claude est un bel exemple d’application de la loi de Stigler[6] qui affirme qu’une découverte scientifique ne porte jamais le nom de son premier auteur. Nous souhaitons donc que le lecteur retienne de ce texte le caractère extrêmement novateur de ses recherches. Le recul du temps permet en effet d’affirmer qu’il a été un authentique visionnaire.
Les débuts : la compilation
Comme sa formation initiale l’y conduit[7], Claude devient professeur de « taupe » à Metz avant son service militaire qui lui offre l’opportunité de faire ses premiers pas en « calcul automatique » au CEA en 1958-59. Il y programme en langage machine sur Bull Gamma « à extension tambour », concurrent de l’IBM 650. Il est ensuite nommé à Nancy, au lycée Henri Poincaré.
- À Nancy, l’informatique universitaire a été introduite par Jean Legras [8] dès 1957 avec une machine à programme câblé, l’IBM 604, puis un ordinateur 9 IBM 650 dès 1958 10. En 1962, Claude prend contact avec Jean Legras qui lui donne accès au « Centre de calcul » qu’il a créé, et l’invite à suivre à la rentrée le cours de programmation sur 650 destiné à des adultes (cf. figure 1). Marion Créhange, chargée de la seconde partie, ne se doutait pas que cet élève, qui lui paraissait doué, allait devenir le père de la recherche en informatique à Nancy et serait son patron de thèse d’état !
Claude prend vite conscience que, derrière des machines différentes, se cache une réalité commune qu’il préfère explorer, plutôt que de s’orienter vers l’analyse numérique, spécialité de Jean Legras. Au Centre de calcul, il consulte la collection des Communications de l’ACM et d’autres revues. C’est ainsi qu’il découvre un nouveau langage de programmation, Algol [3], défini par un groupe international indépendant de tout constructeur, donc attirant pour des universitaires, et beaucoup plus novateur que le Fortran d’IBM : la récursivité de la définition des programmes et des fonctions fait rêver. Un programme n’est plus une suite d’instructions apparaissant au même niveau, mais commence à ressembler à un texte en langue naturelle ; sa syntaxe est d’ailleurs décrite par des règles proches des grammaires formelles dites context-free 11, introduites quelques années plus tôt par le linguiste Noam Chomsky. Compiler ce langage demeure un problème sérieux. Claude, devenu pour un an attaché de recherche au CNRS, constitue une équipe dans ce but et, dès 1963, il signe une première publication aux Comptes-rendus de l’Académie des sciences [P1], puis, en 1964, il publie l’article intitulé « Arbres, piles et compilation » dans la revue française de traitement de l’information [P2].
Cours de DEA, création de l’équipe
- En 1963, Jean Legras assiste, à Grenoble, à un séminaire dont l’objet est la présentation de la version française de la définition d’Algol 60. Claude se souvient de son retour enthousiaste : « un langage avec des SI et des DO ! ». Jacques André 12[T3] raconte : « toute affaire cessante, ils ont organisé dans le cadre du DEA un cours sur Algol 60 : ça a été pour moi une révélation car c’était quand même plus passionnant que le PASO de la 650 ! Quand Claude a parlé au début de l’année scolaire suivante de prendre des étudiants en 3e cycle pour faire un compilo d’Algol 60, j’ai sauté sur l’occasion ».
À cette époque, Claude met en place des réunions régulières, premier « séminaire informatique nancéien », associant théorie et applications. Il signe plusieurs publications internes au Centre de calcul.
- Jacques André raconte : « Claude Pair nous donnait des conférences sur les langages et nous devions chacun rédiger un chapitre. Je me souviens qu’il m’avait rendu ma prose couverte de rouge. Voyant cela, je m’étais dit que ce n’était pas la peine que je continue... Mais en réalité il était content de ma rédaction et visait seulement à en améliorer le fond ».
Compilateur Algol 60 (1963-1965) et thèses à Nancy
Puisqu’il n’existe pas encore de cursus informatique, la plupart des étudiants qui rejoignent cette équipe jusqu’en 1968 viennent des « mathématiques pures ». C’est le cas de Michel Cusey [T1], premier thésard de Claude et pilote de la petite équipe.
Jacques André se souvient : « On a commencé le compilo sur IBM 650, j’y ai travaillé la lecture des nombres, et assez vite, bonne nouvelle, on allait avoir accès à un 1620 chez IBM (cf. figure 2). Mais cette machine était à Metz et n’était disponible qu’après la fermeture des bureaux. Tous les quatre 13, on y allait avec la voiture de Michel, départ vers 17 heures et retour... quand nos essais étaient finis, le plus souvent à deux heures du matin. La bécane était en vitrine et on avait l’impression d’être des ours en cage quand les passants nous regardaient avec curiosité. On « sandwichait » autour de la machine jusqu’au jour où le directeur du centre IBM nous a convoqués pour nous signifier assez rudement que les bières sur le pupitre, ce n’était pas vraiment dans l’esprit de l’entreprise. Du coup, on est allé souvent prendre une choucroute à la fin du travail à la brasserie de la gare de Metz, et je n’en ai jamais mangé d’aussi bonnes depuis... ».
Avant d’envisager la programmation du compilateur, Michel Cusey travaille sur son ossature générale : l’analyse syntaxique, les déclarations de variables, la gestion des piles et de l’ensemble de la mémoire, la construction du programme objet. Il le fait en respectant scrupuleusement les idées de Claude qui souhaitait vérifier sur un cas concret la pertinence de son approche mathé- matique. Claude est ravi que sa théorie « marche » et il lui en est reconnaissant. Jacques André est en charge des entrées-sorties et des procédures de service. La définition du langage Algol 60 ne définissant rien sur les entrées-sorties, il adopte les propositions de Donald Knuth [21]. Jean-Marie Laporte s’occupe des tableaux. Plus tard, Marion Créhange traite des procédures, en particulier de la récursivité, avec la collaboration d’Alain Floc’h qui sera ensuite chargé de la mise au point finale du compilateur.
Citons Claude 14 : « En 1965, le compilateur est presque achevé. Le groupe européen des utilisateurs de 1620 me propose de le présenter à sa réunion de Mannheim [P5]. À partir de là, l’université de Saint-Andrews (Écosse) me demande de le lui envoyer sur cartes perforées, l’outil de l’époque pour entrer des informations dans un ordinateur. Mais, patatras, pour remplacer le 650 vieillissant, Legras choisit, dans le cadre du Plan calcul naissant, plutôt que le 1620, une machine française CAE 510 qui possède déjà un compilateur Algol.
Notre motivation disparaît et IBM arrête son prêt, avant que le compilateur soit réellement utilisable par d’autres que nous ».
Dans les mois qui suivent, l’équipe commence à se disperser. Mais l’expérience ne sera pas perdue. Des notions ont été dégagées, comme celles d’analyse syntaxique et de pile, des étudiants ont été formés, en particulier à la théorie des langages, et cinq thèses de troisième cycle ont été soutenues, dont trois à propos du compilateur [T1, T2, T3, T4, T5].
Fin 1965, Claude soutient sa thèse d’État, « Étude de la notion de pile, application à l’analyse syntaxique ». Elle récapitule les méthodes d’analyse syntaxique des lan- gages de Chomsky, mettant en évidence trois familles d’algorithmes de construction d’arbres syntaxiques, une ascendante et deux descendantes « en profondeur d’abord » et « en largeur d’abord », dira-t-on plus tard. D’un style formel, rangée dans la spécia- lité « mathématiques », elle suscitera quelque incompréhension des mathématiciens « purs ». Par la suite, Claude pensera d’ailleurs que sa présentation était trop mathé- matique : « Il faudra un peu de temps pour inventer un style d’écriture rigoureux mais moins uniquement mathématique, adapté à cette nouvelle science et tenant compte de ses composantes fondamentales : algorithmes [P66], types de données [P24] (comme les piles ou les arbres syntaxiques d’une grammaire de Chomsky), langages de pro- grammation ». Quoi qu’il en soit, il s’agit de la seconde thèse d’État en informatique, après celle que Jean-Claude Boussard avait soutenue l’année précédente à Grenoble, décrivant un compilateur Algol qu’il avait écrit pour un IBM 704 que son université avait la chance de posséder. Cette thèse, elle, était qualifiée « de science appliquée » car l’informatique n’était pas encore reconnue comme une discipline à part entière à l’époque dans les universités françaises.
Le chercheur et sa prescience
L’analyse syntaxique de précédence
L’analyse syntaxique est la première étape de la compilation : elle consiste à cal- culer, d’après la chaîne de caractères du programme à traduire, sa structure gramma- ticale sous la forme d’un arbre. Cette opération doit être faite de façon déterministe si on veut éviter tout retour en arrière. Claude montre que c’est possible pour le lan- gage Algol, en mettant au point un algorithme (cf. figure 3) qui le permet, fondé sur une analyse ascendante, qui sera celui du compilateur nancéien et qu’il décrit dans un article publié en 1964.
Cet algorithme, redécouvert en 1966 par Niklaus Wirth et Helmuth Weber [36], est nommé méthode de « précédence » (ordre de priorité sur les carac- tères au cours de l’analyse). Dans leur livre sur l’analyse syntaxique [1], Aho et Ullman parlent du concept de précédence de Wirth-Weber (p.404), mais, surtout, de façon étonnante, ils leur attribuent aussi l’algorithme, en écrivant « les grammaires simples de précédence ont été définies par Wirth et Weber (1966) et indépendamment par Pair (1964) » (p. 428). Une belle application de la loi de Stigler !
Les problèmes de cheminement dans les graphes
Après avoir soutenu sa thèse et constaté l’arrivée d’étudiants visant une thèse de troisième cycle, Claude ouvre de nouveaux domaines de recherche, à partir des notions rencontrées pour la compilation. Il s’agit en particulier des graphes dont les arbres sont un cas particulier, et de leur exploration à l’aide d’une pile pour ré- soudre les problèmes de cheminement, par exemple l’existence d’un chemin d’un point à un autre ou la recherche de plus courts chemins. Constatant le foisonnement de différents articles indépendants sur le sujet et la similitude des algorithmes pour des problèmes divers, il remarque qu’en adoptant un point de vue algébrique, il est possible de retrouver ces algorithmes, ainsi que d’autres, par simple définition d’ho- momorphismes adaptés. Cette idée élégante sera présentée plus tard dans différentes publications [T6, P16]. Elle est malheureusement restée méconnue (ou plagiée ?). Le lecteur intéressé est invité à consulter Jean-Claude Derniame [11] qui raconte cette « histoire chaotique ».
Langages et bilangages
Claude est donc féru d’algèbre, et c’est pourquoi la théorie des langages le comble. Un langage est un ensemble de phrases, éléments unidimensionnels ; mais l’analyse syntaxique construit des arbres, à deux dimensions, et Claude nomme « bilangage » un ensemble d’arbres (cf. figure 4). De même qu’un langage a une structure algébrique de monoïde (une seule opération), les bilangages conduisent à deux opérations, pour engendrer les arbres, et à la structure de « binoïde ». L’histoire commence en mai 1968, par la publication de l’article de Claude Pair et Alain Quéré [T8] « Définition et Étude des Bilangages Ré- guliers » dans la revue Information and Control [P11]. Le mot « régulier », utilisé pour les langages reconnus par un automate fini, est étendu ici aux bilangages : l’ensemble des arbres syntaxiques d’un langage context-free est un bilangage régulier.
Après cette publication, Claude reçoit de nombreuses demandes de tirés à part. L’une vient de Rózsa Péter une chercheuse hongroise, pionnière de la calculabilité et qui a écrit le tout premier livre sur les fonctions récursives [29] et publié sur elles des contributions remarquables.
En particulier, en utilisant la récurrence structurelle, Rózsa Péter a eu l’idée d’étendre la récursivité qui, à l’origine, se limitait aux entiers naturels, à ce que nous appellerions aujourd’hui des structures de données bien fondées. Elle les nomme angeordneten freien holomorphen Mengen (ensembles libres holomorphes structurés).
FIGURE 5. Rózsa Péter accuse réception du tiré à part et annonce sa réponse sur le fond. On peut comprendre son excitation quand elle a vu qu’à partir de besoins de formalisation en informatique, Claude proposait une telle structure pour les arbres syntaxiques. Claude envoie donc aussitôt l’article qu’elle demande et le remerciement arrive par une jolie carte postale du Pont Élisabeth à Budapest (cf. figure 5). Elle se plonge donc avec passion dans les écrits de Claude, y passant des nuits, lisant et réfléchissant jusqu’à 4–5 heures du matin, comme elle l’écrit avec enthousiasme et fraîcheur, dans sa lettre du 28 octobre 1968. On a l’im- pression qu’à travers le rideau de fer qui divise alors l’Europe, elle parle à un ami qu’elle connaît depuis toujours, bien qu’elle ne l’ait jamais rencontré. Elle annonce dans cette lettre l’article qu’elle va publier dans Acta Mathe- mica dont elle envoie, à son tour, un tiré à part à Claude, article intitulé : « Die Pairschen freien Binoïden als Spezialfälle der angeordneten freien ho- lomorphen Mengen ». On notera la création, en allemand, du nouvel adjectif « Pairschen » !
En réponse, Claude et son élève Alain Quéré publient dans la même re- vue, à l’invitation de leur collègue hongroise, un complément intitulé « Sur les fonctions récursives primitives de ramifications » qui montre que l’égalité est primitive récursive dans le binoïde libre qu’on peut comparer aux ensembles holomorphes libres de Rózsa Péter.
Dans la ligne de recherche ainsi créée, en 1971, Pierre Lescanne [T16] a emprunté à la théorie des catégories ses concepts pour généraliser les langages réguliers, re- connaissables par automates et solutions d’équations spécifiques. Il montre ainsi que, même généralisées, ces trois familles de langages coïncident.
En 1974, Pierre Marchand étudie les « bigrammaires » et les systèmes transfor- mationnels [T26]. Plus tard, en utilisant des algèbres libres (objets mathématiques à plusieurs opérations, dont les chaînes de caractères ne sont qu’un cas très particu- lier), il généralise, lui aussi, les notions de langages reconnaissables et de langages algébriques, mais dans un cadre plus général où des relations existent entre les opéra- teurs. Il montre la construction algorithmique des algèbres minimales de reconnais- sance pour les parties reconnaissables, et, par ailleurs il explique, par l’adjonction d’une loi à une algèbre, la hiérarchie de Chomsky, qui devient alors infinie [T45].
L’équivalence des types infinis
Le groupe Algol francophone, que les collègues grenoblois de Claude lui ont proposé d’animer, se fixe pour objectif de faire connaître le nouveau langage Al- gol 68, notamment à travers plusieurs publications comme la traduction du rapport de définition et un copieux manuel d’utilisation. Algol 68 fait avancer la science informatique : le principal progrès est que les types de données n’y sont plus prédéfi- nis comme en Algol 60 (nombres entiers, réels, valeurs booléennes, tableaux), mais peuvent être introduits en fonction des besoins de chaque programme. Il permet donc de définir des types de données, et de le faire éventuellement de manière récursive. La question se pose alors de savoir si deux définitions distinctes sont équivalentes, c’est-à-dire conduisent au même type. En 1970, Claude publie un algorithme de décision dans la revue Algol Bulletin, alors destinée aux spécialistes d’Algol 68, sous le titre un peu imprécis Concerning the Syntax of Algol 68 [P19]. Cette décidabilité est redécouverte en 1993 dans un cadre plus général par Roberto Amadio et Luca Cardelli [2]. La démonstration repose sur un concept mis en évidence autour de 1980 : la coinduction. Cardelli [2] a indi- qué que, cherchant une antériorité, il avait pensé à Simula, mais n’avait pas regardé du côté d’Algol 68. L’aurait-il fait, qu’il n’aurait sans doute pas trouvé l’article de Claude, bien caché dans la littérature scientifique ! Aujourd’hui, nous dirions que la démonstration de la décidabilité d’un problème se fait soit par réduction à un autre problème décidable, soit par la description d’un algorithme de décision, et c’est ce que propose Claude dans la section 4 de l’article cité [P19]. Il propose une méthode de raisonnement sur des objets infinis qui, comme plus tard la coinduction, fait appel à la résolution d’une équation à point fixe 15. Une équation à point fixe peut avoir plusieurs solutions. Alors que l’induction s’appuie sur un raisonnement fondé sur le plus petit point fixe, la coinduction s’appuie sur le plus grand point fixe. Claude ne peut pas connaître ces différences, qui ne seront mises en évidence qu’une décennie plus tard, mais il doit en avoir l’intuition, car 15. Une équation à point fixe est une équation de la forme X = F(X ). Si l’ensemble dans lequel on cherche les solutions est ordonné, par exemple par inclusion d’ensembles, il y a une plus grande et une plus petite solution (on dit aussi un plus grand et un plus petit point fixe).
sa démonstration fonctionne en deux temps. Premier temps, il démontre l’unicité du
point fixe, le plus petit point fixe est aussi le plus grand. Deuxième temps, il démontre
que sur cet unique point fixe, on peut mettre en œuvre un processus de décision.
Et Benjamin Pierce peut donc écrire dans son livre de référence [31]
qu’il s’agit bien de la première démonstration de la décidabilité de l’égalité
de deux types (équi)-récursifs alors qu’il lui faut 648 pages pour présenter aux
étudiants en master la notion que Claude avait introduite, à savoir les types 16
dans les langages de programmation.
Les structures de données
En juillet 1971 à Alès, lors de la première école d’été de l’AFCET 17, Claude donne l’un des trois cours, « les structures de données et leur représentation en mé- moire ». Ce cours, destiné à la programmation, sera revu par Marie-Claude Gaudel et publié par l’IRIA en 1977 [P24]. Une donnée est un objet informatique (liste, pile, arbre, table...) susceptible d’être transformé par des opérations. Une structure de données [P33] indique ces opérations et leurs propriétés, de la même façon qu’en mathématiques une structure algébrique (groupe, anneau, corps...) comprend une ou plusieurs opérations et leurs propriétés sous la forme d’axiomes.
En 1972, Claude obtient du CNRS un contrat d’Action thématique programmée (ATP) sous le titre « Informatique théorique, programmes et données ». Il le confie à Jean-Luc Rémy qui précise en particulier que les axiomes sur les opérations seront des égalités (axiomes équationnels). Le contrat dure deux ans et fait l’objet en 1974 d’un rapport de Claude au nom de l’équipe de recherche associée 364 au CNRS et de l’université de Nancy II.
Dans les années qui suivent, Claude commence à s’effacer devant ses chercheurs qui prennent leur envol, échangent entre eux et publient ensemble. Jean-Pierre Fi- nance et Jean-Luc Rémy font une communication à l’école d’été de Grenade (1973, [13]), à la suite de quoi Jean-Pierre Finance reprend avec Claude la rédaction d’un document de travail qui donnera lieu à un article dans une des premières conférences IFIP [P30]. Deux thèses en sont issues, soutenues toutes les deux le 25 juin 1974 : celle de Jean-Luc Rémy [T24] étudie les aspects les plus formels, par une utilisation de la logique mathématique ; la thèse de Jean-Pierre Finance [T25] utilise les struc- tures de données pour décrire la sémantique d’un langage de programmation. Plus tard, celle de Marie-Claude Gaudel [T43] emploiera la sémantique pour engendrer des compilateurs et prouver leur correction. En 1979, dans sa thèse [T39], Pierre Les- canne revisite les structures d’information dans une approche d’algèbres, préfigurant les contributions de Yuri Gurevich et de ses collaborateurs. 16. Qu’il appelle « mode » à la mode de l’époque ! 17. La société savante d’informatique à l’époque. Indépendamment de l’équipe nancéienne, des développements très simi- laires ont émergé à partir de 1993, notamment grâce à Yuri Gurevich, sous le nom d’Evolving Algebras [18], puis de Sequential abstract-state machines, nom plus attractif [19], quand l’industriel Microsoft s’y est intéressé. Ces recherches sur les données ont stimulé une activité de nature didactique sur la théorie des programmes et l’informatique théorique en général, qui sera le support d’un cours à l’école d’été d’informatique de Tarbes en 1974 puis conduira à l’écriture d’un livre publié en 1978 chez Dunod [26]. Entre eux, les sept auteurs Jean-Pierre Finance, Monique Grandbastien, Pierre Lescanne, Pierre Marchand, Roger Mohr, Alain Quéré et Jean-Luc Rémy, s’appelaient, dans un premier temps, Blanche Neige, nom inapproprié, puisqu’ils n’étaient que sept nains, sous le charme d’une princesse. Le nom de Livercy (pour Liverdun et Commercy, deux villes lorraines où eurent lieu les séances d’édition) fut finalement retenu. Ce livre, l’un des premiers à traiter d’informatique théorique, toutes langues confondues, fut utilisé, par exemple, par Jean-Louis Lassez comme base de ses cours à l’Université de Melbourne en Australie ou par Olivier Danvy, professeur à l’Université d’Aarhus au Danemark, pour s’initier à la théorie des continuations.
Autres approches et nouvelles pousses
Claude aime aussi étendre son domaine de compétence et il ne se limite pas à un seul axe en matière de recherche. Nous évoquons ici la diversité de ses intérêts. Cependant, nous sommes loin d’un inventaire à la Prévert, car, chez Claude, ses inté- rêts sont tous ancrés sur une exigence de rigueur scientifique. Parcourons brièvement ces autres approches qui sont devenues aussi de nouvelles directions de recherche au CRIN. En informatique, dans la lignée des premières recherches, au début de la décennie 1970, les compilateurs de compilateurs se multiplient, le plus connu étant le couple lex et yacc. Le nom de yacc, « encore un compilateur de compilateur » montre com- bien le sujet est chaud à cette époque. Sa version finale est publiée en 1975 [20]. À Nancy, Claude aiguille Françoise Bellegarde [T17] et Jean Maroldt [T18] sur ce sujet, ils soutiennent une thèse en 1972. Notez l’antériorité du yacc nancéien, uti- lisé aussi comme outil d’enseignement. Il s’appellera Fabrication automatique de compilateurs efficaces (Face) et mis à profit pour la mise au point de compilateurs (Anne-Marie Rasser [T30]). Dès les débuts, Claude avait conscience que l’informatique, science transver- sale, pouvait servir en dehors de son champ propre et donner lieu à des recherches mixtes, au-delà de simples utilisations. La liste des thèses dirigées par Claude et explorant des nouvelles branches donne un aperçu de cet esprit d’ouverture. Indi- quons quelques exemples qui montrent l’étendue des domaines abordés : linguis- tique [T9, T21, T22], médecine [T11, T19], enseignement [T42], représentation des connaissances [T46]. Le plus souvent ce sont les thésards eux-mêmes qui ont choisi des orien- tations correspondant à leur compétence. Ils auraient pu être découragés par un patron trop directif. Au contraire, Claude les a encouragés dans le sens de leurs goûts. Donnons quelques exemples. Jean-Claude Derniame s’est intéressé à la prise en compte dans un même environnement des différentes étapes de construction du logiciel : spécifica- tion, analyse, programmation, exécution, maintenance. En référence au dieu hindou auquel la tradition attribue cinq bras, il nomme CIVA son projet qui traite de définition modulaire et de classes d’objets, préfigurant les langages à objets si populaires aujourd’hui [T23]. Pour Marion Créhange, c’est un stage au laboratoire d’Analyse documen- taire pour l’archéologie (CNRS, Jean-Claude Gardin à Marseille) qui la déter- mine à s’orienter vers les questions de recherche d’informations. Ensuite, elle collabore avec la médiéviste Lucie Fossier qui l’avait sollicitée pour traiter des documents diplomatiques du Moyen Âge au Centre de recherche et applica- tions linguistiques (CRAL) [15] ; ce qui lui permet d’acquérir une expérience en recherche documentaire. Plus tard, ce sera la conception de PIVOINES, langage d’interrogation de bases de données, très « déclaratif » et indépen- dant des choix de représentation [T29] dans la ligne des études théoriques sur les structures de données. Voilà un exemple représentatif des allers-retours entre théorie et application qui se fécondent l’une l’autre, une démarche qui intéressait particulièrement Claude 18. Autre exemple : Maryse Quéré [T42] avait débuté sa recherche en mathé- matiques pures, puis s’était consacrée à la formation d’adultes au CUCES 19. Elle avait ensuite participé à celle de professeurs de lycées à l’informatique, puis créé le Centre lorrain d’enseignement par ordinateur (CLEO), d’où son attrait pour l’usage innovant de l’informatique dans l’enseignement. Pour Roger Mohr 20, la proposition de Claude d’imaginer les figures comme des objets à deux dimensions engendrés par une grammaire [T20] a été un pre- mier départ vers la science des images, à laquelle il s’est ensuite consacré en 18. Marion écrit « j’ai pu apprécier la qualité extrême de Claude comme directeur de thèse, ferme et incitatif, mais gentil et promouvant, préoccupé par la réussite de ses élèves. » 19. Autre institution nancéienne, le Centre universitaire de coopération économique et sociale et l’un des tous premiers organismes de formation des adultes, créé par le recteur Capelle et André Grandpierre de la société Pont-à-Mousson, puis dirigé par Bertrand Schwartz. 20. Cf. In memorian Roger Mohr, revue 1024 n° 11, septembre 2017. créant au CRIN, avec Jean-Paul Haton, l’équipe Reconnaissance des formes et intelligence artificielle (RFIA).
Recherche et enseignement
Didactique de la programmation : la méthode déductive
Pour Claude, l’informatique naissante n’est pas seulement un objet de recherche, c’est aussi une discipline à enseigner. Dans les années 60, on sait laborieusement ex- pliquer un programme, mais la démarche qui consiste à trouver un algorithme pour résoudre un problème reste difficile, voir impossible, à expliciter. Le plus souvent l’enseignant, tel un magicien, dessine un organigramme qu’il transpose ensuite dans un langage de programmation. Si la seconde partie du travail est facile, l’invention de l’algorithme est certes immédiatement saisie par les étudiants les plus brillants, mais reste incompréhensible pour la plupart. La conséquence de cette situation est l’erreur de programmation, le plus souvent découverte lors d’une exécution sur ma- chine et rectifiée par des essais successifs sans s’appuyer sur des preuves sérieuses. Depuis 1968, la programmation structurée [12], [10] a mis en évidence une construc- tion raisonnée des algorithmes et il existe quelques méthodes, le plus souvent sous forme de recettes standard pour résoudre certaines familles de problèmes (Méthode Warnier [34]).
D. E. Knuth propose « la programmation littéraire » [22] qu’on peut rapprocher de la méthode que Claude introduit à partir de 1973. Cette méthode sépare par étapes les activités de définition du problème, d’écriture de l’algorithme et enfin du pro- gramme. L’idée de départ est aussi simple que nouvelle : résoudre un problème, c’est partir du but à atteindre, « le résultat », et remonter le chemin jusqu’aux en- tités connues, appelées « données ». Autrement dit, construire un programme, c’est raisonner à partir de la définition du résultat pour revenir aux données en utilisant à chaque étape une définition puisée dans une liste prédéfinie de primitives usuelles de l’algorithmique : formules, conditionnelles, itérations — considérées ici comme la définition de suites —, fonctions, dont la définition apparaît comme un nouveau problème à résoudre. Chaque étape de la construction est une déduction, d’où le nom de « méthode déductive ». Pour illustrer la démarche contentons-nous d’un exemple simplissime, à savoir la recherche du maximum de 3 nombres. Commençons donc par écrire la caractérisa- tion informelle du résultat : M : est le maximum de a, b, c Il s’agit alors de choisir, parmi les définitions algorithmiques référencées dans la méthode, l’une d’entre elles qui nous fera progresser vers la solution en introduisant au besoin de nouvelles entités. Ce sera, ici, une définition conditionnelle : M = si a > mbc alors a sinon mbc avec introduction de deux intermédiaires à définir : a = donnée, mbc = maximum de b et c et l’introduction de deux intermédiaires à définir, b et c qui sont des données. Une nouvelle conditionnelle porte sur des données qui sont connues : mbc = si b > c alors b sinon c Ce qui résout le problème. La méthode organise ce travail dans une table à deux colonnes, les définitions informelles et définitions formelles. Ici : Définitions informelles Définitions formelles (algorithmiques) M : Maximum de a, b, c M = si a > mbc alors a sinon mbc mbc : maximum de b et c mbc = si b > c alors b sinon c a, b, c : données a, b, c = lire Pour faire de ces définitions un algorithme séquentiel, il reste à les organiser, c’est à dire à les ordonner pour la relation « dépend de » (tri topologique) facile à déterminer depuis la colonne de droite. Une troisième colonne peut servir à établir ce tri, tâche qui peut être automatisée qu’on peut rapprocher de la méthode [P47] que Claude introduit à partir de 1973. Définitions informelles Ordre Définitions formelles (algorithmiques) M : Maximum de a, b, c 3 M = si a > mbc alors a sinon mbc mbc : maximum de b et c 2 mbc = si b > c alors b sinon c a, b, c : données 1 a, b, c = lire Cette méthode a été largement employée à Nancy (université, IUT, écoles, IREM et formation des professeurs du second degré), notamment pour l’initiation avec un avantage pédagogique notoire : montrer aux étudiants que la programmation, loin de se ramener à quelques recettes, peut s’appuyer sur le raisonnement et que ce raisonnement s’enseigne. Cependant, sa pratique ne s’est pas répandue et elle est donc restée une méthode purement nancéienne 21. Son implantation informatique (Bernard Huc, [T34]), était complète, mais la faiblesse des techniques ergonomiques de l’époque l’ont desservie. Encore une innovation arrivée trop tôt, sans doute ! Jacques Jaray évoque cette période : « à l’IUT, avec des élèves débu- tants en informatique, nous avions constaté qu’en mal d’inspiration pour construire l’algorithme solution d’un problème, ils commençaient par écrire lire(données) et s’ensuivait une période de grande perplexité. Je situe la naissance de la Méthode déductive, abrégée en MÉDÉE 22, un peu après 1973. Claude était professeur au département informatique de l’IUT, il enseignait la programmation aux élèves de première année. Il avait, entre autres comme assistants : Françoise Bellegarde, Hubert Pistré, Bernard Huc et moi-même... La méthode déductive s’est éteinte au milieu des années 80, lorsque les langages objets ont été enseignés et parce qu’elle était peu naturellement adaptée pour concevoir des systèmes réactifs ». Autres aventures : école d’été, IFIP, Algol 68, IREM... Nous ne pouvons pas décrire toutes les facettes de l’activité de Claude. Il nous a plus d’une fois étonnés par sa manière d’accumuler les responsabilités... et de les assumer tranquillement. Nulle boulimie, mais simplement quelques facilités, une grande capacité de travail, de l’imagination, l’envie de servir et le soutien indéfec- tible de son épouse Monique. Évoquons ici quelques autres aspects de ses actions en lien avec la recherche. Tout de suite après sa thèse, Claude entre en 1966 au groupe de travail WG 2.2 de l’IFIP Formalisation of programming concepts qui vient d’être créé. Nous avons indiqué son rôle d’animateur du groupe franco-belge sur Algol 68 (Manuel Algol 68, [P37]), groupe qui subsistera sous plusieurs formes jusqu’en 1993 avec des partici- pants de Grenoble, Rennes, Nancy, Paris, Montpellier [16]. Du côté belge, le groupe bénéficiera notamment de la contribution déterminante de Michel Sintzoff 23, profes- seur à l’université libre de Bruxelles [17]. 21. Mais la méthode était encore étudiée avec un oeil mathématique en 2010, bulletin No48 de l’AP- MEP, juillet-aôut 2010. 22. Dénomination proposée par Pierre Lescanne et déclinée en Amédée Ducrin, nom d’auteur du livre de programmation associé à la méthode [P63]. 23. C’est par Algol68 que Claude et ses élèves ont connu Michel Sintzoff lorsqu’il était chercheur au MBLE (laboratoire de Philips). Michel est resté en contact avec le CRIN. Lors d’une année sabbatique passée à Nancy, il y a donné un séminaire remarquable sur les fondements de la programmation.
Publications de Claude Pair
[P1] ↑ Justification théorique de l’utilisation des piles en compilation, CR AS 257, 3278- 3281, 1963.
[P2] ↑ Arbres, piles et compilation, Revue française de traitement de l’information - Chiffres 7, n°3, 199- 216, 1964.
[P3] ↑ Sur la détermination de la correspondance paramètre formel - paramètre effectif des procédures Algol, congrès AFIRO, 157-162, 1964.
[P4] Essai de description de la sémantique des langages de programmation, séminaire AFIRO et rapport interne, 1964. [P5] Description d’un compilateur Algol, European Région 1620 Users Group, Mannheim, 1965. [P6] Étude d’un algorithme d’analyse syntaxique, manuscrit consultable aux Archives Henri-Poincaré, https://poincare.univ-lorraine.fr/, Nancy, 1965. [P7] Étude de la notion de pile, application à l’analyse syntaxique, thèse d’État, Nancy, 1965. [P8] Analyse syntaxique des langages de Chomsky, exposé à un séminaire à Grenoble, 1966. [P9] Sur des algorithmes pour les problèmes de cheminement dans les graphes, Théorie des graphes, Journées internationales d’étude, Rome, Dunod - Gordon and Breach, 271-300, 1966. [P10] La formalisation des grammaires, Centre de Recherches et d’Applications Linguistiques, Faculté des lettres et sciences humaines, Nancy, 1967. [P11] Définition et étude des bilangages réguliers, avec A. Quéré, Inf. and Control 13, 565-593, mai 1968. [P12] Introduction à Algol 68, RIRO Informatique 3, n°3, 17-52, 1969. [P13] Algol 60, Techniques de l’Ingénieur H 2160, 1970. [P14] Sur des notions algébriques liées à l’analyse syntaxique, RIRO Math.4 n° 3, 3-29, 1970. [P15] Sur les fonctions primitives récursives de ramifications, avec A. Quéré, Acta Math. Acad. Sc. Hung. 21, 437- 444, 1970. [P16] Mille et un algorithmes pour les problèmes de cheminement dans les graphes, RIRO Informatique 4 n° 3, 125-143, 1970. [P17] Survol de la théorie des langages, journées AFCET, Grenoble, 1970. [P18] FACE, langage pour l’écriture des compilateurs, avec F. Bellegarde et J. Maroldt, congrès AFCET, broch. 2, 5-21, 1970. 29. Par exemple, selon G
Références
...
[8| M. Créhange, Structure du code de programmation, Thèse 3e cycle, Nancy, 1961 32. Et Code de programmation, Cahier n° 1 du groupement des utilisateurs scientifiques des ordinateurs IBM 650, octobre 1960.
[9] ↑ M. Créhange et M.-C. Haton,, L’informatique universitaire à Nancy : un demi-siècle de développement, revue de la SIF 1024 no 3, pp. 59-74. 2014.
[10] O. J. Dahl, E.W. Dijkstra, C. A. H. Hoare, Structured Programming, Acad. Press, 1972
...
Notes de l'article
- ↑ marion.crehange@sfr.fr, pierre.lescanne@ens-lyon.fr, apmf.quere@laposte.net. Ar- ticle également disponible sur HAL, https://hal.archives-ouvertes.fr/hal-03193950v2.
- ↑ http://claudepair.fr/
- ↑ Pour être précis, 47 thèses sur la période considérée ici puis, quelques années plus tard, celle de Radhia COUSOT (1985).
- ↑ En 1997, l’ensemble est devenu le LORIA, unité mixte associant CNRS, INRIA et les universités. En 2017, il comptait 300 permanents de 48 nationalités (rapport HCERES). Sur l’histoire de l’informatique à Nancy, voir aussi [9] [9, 25].
- ↑ Un seul exemple : pour traduire l’inélégant garbage collector, Claude a introduit le terme « ramasse miettes », voir Wikipedia.
- ↑ Il se dit que cette loi s’applique aussi à son auteur, voir « loi de Stigler » sur Wikipédia
- ↑ Né à Blâmont (Meurthe-et-Moselle) en 1934, Claude devient un élève brillant au collège à Lunéville. Il est admis en 1951 au lycée Louis le Grand à Paris, puis en 1953 à l’École normale supérieure. Il est agrégé en 1956, et nommé professeur de mathématiques spéciales à Metz (1956-1957).
- ↑ http://www.professeurs-medecine-nancy.fr/livre_jean_legras.htm.