L'informatique de Claude Pair (2021) Créhange : Différence entre versions
(→Publications de Claude Pair) |
(→Références) |
||
Ligne 955 : | Ligne 955 : | ||
{{Corps article/Bibl | {{Corps article/Bibl | ||
|id=3 | |id=3 | ||
− | |texte= J.-W. Backus et coll | + | |texte= J.-W. Backus et coll <ref>Le comité de définition comprend un français, B. Vauquois, professeur à Grenoble.</ref>, Report on the algorithmic language Algol 60, Nümerische Mathematik 2, 1960.}} |
{{Corps article/Bibl | {{Corps article/Bibl | ||
|id=4 | |id=4 | ||
Ligne 971 : | Ligne 971 : | ||
|texte= N. Chomsky, On certain properties of grammars, Information and Control 2, 1959.}} | |texte= N. Chomsky, On certain properties of grammars, Information and Control 2, 1959.}} | ||
{{Corps article/Bibl | {{Corps article/Bibl | ||
− | |id=8|texte= M. Créhange, Structure du code de programmation, Thèse 3e cycle, Nancy, 1961 | + | |id=8|texte= M. Créhange, Structure du code de programmation, Thèse 3e cycle, Nancy, 1961 <ref> Dans l’article du journal du CNRS du 23.09.2016 par Martin Koppe, Pierre Mounier-Kuhn signale |
+ | qu’il s’agit « de la première thèse de France en informatique ».</ref>. Et Code de programmation, Cahier n° 1 du groupement des utilisateurs scientifiques des ordinateurs IBM 650, octobre 1960.}} | ||
{{Corps article/Bibl | {{Corps article/Bibl | ||
|id=9 | |id=9 |
Version du 25 mars 2022 à 10:18
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écialité « 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] (commeles piles ou les arbres syntaxiques d’une grammaire de Chomsky), langages de programmation ». 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).
- 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’impression 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 Mathemica dont elle envoie, à son tour, un tiré à part à Claude, article intitulé : « Die Pairschen freien Binoïden als Spezialfälle der angeordneten freien holomorphen 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 revue, à 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, reconnaissables 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 transformationnels [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 Algol 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éfinis 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 indiqué 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 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.
Indépendamment de l’équipe nancéienne, des développements très similaires 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 transversale, 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 orientations 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écification, 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 documentaire pour l’archéologie (CNRS, Jean-Claude Gardin à Marseille) qui la détermine à 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 applications 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épendant 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 premier départ vers la science des images, à laquelle il s’est ensuite consacré en 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 expliquer 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 construction 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érisation informelle du résultat :
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 :
avec introduction de deux intermédiaires à définir :
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 :
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
mbc : maximum de b et c a, b, c : données |
M = si a > mbc alors a sinon mbc
mbc = si b > c alors b sinon c 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
mbc : maximum de b et c a, b, c : données |
3
2 1 |
M = si a > mbc alors a sinon mbc
mbc = si b > c alors b sinon c 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ébutants 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], professeur à l’université libre de Bruxelles [17].
- Jacques André : « J’avais gardé quelques contacts ténus avec le Centre de calcul, et c’est ainsi que Claude Pair m’a invité à assister à une réunion de ce qui allait devenir le Groupe Algol 68, que j’ai suivi régulièrement par la suite, et « donc » le GROPLAN de l’AFCET, ce qui m’a laissé en contact avec Pair, et le monde universitaire... ».
Le premier institut de recherche sur l’enseignement des mathématiques est apparu en 1969 à Paris. C’est en 1971 que l’IREM de Nancy est créé sous l’impulsion de Claude. Il en assure la co-direction avec Jean-Louis Ovaert [24].
Dès les débuts de l’informatique universitaire, il faut aussi l’enseigner, performance inédite car, en l’absence de toute formation à une matière qui n’existe pas, les étudiants recrutés comme enseignants chercheurs, ont suivi le plus souvent des études de mathématiques. Ils ignorent donc tout de cette nouvelle discipline. En 1971, Claude crée, sous l’égide de l’AFCET, une université d’été francophone [25] (cf. figure 7), forme originale d’auto-formation du nouveau « milieu informatique ». Elle permet d’acquérir à la fois la matière à enseigner et la pédagogie pour la pré- senter.
1971 Alès |
1972 Neufchâtel |
1973 Grenade |
1974 Tarbes |
1975 Rabat |
1976 Lannion |
1977 Montréal |
1978 Namur |
1979 Monastir |
1980 Aix-en-Provence |
1981 Thès |
1982 Namur |
1983 Sfax | ||
Figure 7. École d'été d'informatique de 1971 à 1983. |
C’est aussi en 1971 que sont lancés des stages de « formation approfondie » à l’informatique pour quelques dizaines de professeurs du second degré. Ces cours ont lieu sur une année scolaire dans les universités de Grenoble, Nancy, Toulouse et à l’école normale supérieure de Saint-Cloud. Claude prend en charge avec une petite équipe (Noëlle Carbonell et Brigitte Jaray) la formation de Nancy ; celle-ci s’appuie à partir de 1973 sur la méthode déductive, avec programmation en LSE[26]. L’opération est stoppée par le ministère en 1976 et elle reprendra en 1982 à la suite d’un rapport sur l’introduction de l’informatique dans l’enseignement scolaire, confié en 1981 par le ministre Alain Savary à deux anciens présidents d’université, Yves Le Corre et... Claude Pair.
Conclusion
La pratique universitaire courante consiste à procéder à des évaluations au travers d’innombrables rapports établis par des comités d’experts. Ici, le lecteur l’aura compris, nous sommes dans une toute autre démarche puisque ce sont des élèves qui tentent d’évoquer les années de travail lointaines qu’ils ont vécues avec leur « maître », et grâce à lui. À l’époque, ils n’avaient pas bien conscience qu’ils vivaient une période aussi enrichissante pour eux que pour la science informatique. Mais ils avaient compris qu’ils bénéficiaient, auprès d’eux, d’une immense compétence, toujours disponible, parfois critique et avant tout visionnaire, comme ils ne l’ont réalisé que bien plus tard.
Critique, oui il pouvait être critique et parfois vivement mais toujours de manière argumentée et si habilement présentée qu’à la fin d’une réunion où nous avions tous largement divergé, nous entendions Claude conclure par sa synthèse si pertinente que nous le quittions avec le plan qu’il avait dessiné et pleinement convaincus que c’était notre plan [27] !
Disponible, devenu président de l’INPL (1976), Claude nous recevait encore longuement. Sur son bureau, symbole du personnage, rien d’autre qu’une feuille de papier, gratifiée de quelques lignes griffonnées [28] : son plan du jour.
Encourageant, toujours à l’écoute, faisant des observations pointues, bienveillantes et constructives, et promouvant nos idées, Claude nous a incités à raisonner de façon rigoureuse et sobre.
Fédérateur, Claude a tenu de manière constante à regrouper sans exclusion tous les enseignants chercheurs en informatique de Nancy sans tenir compte des clivages institutionnels.
Visionnaire, on peut constater que certaines publications de Claude sont encore citées plus de trente ans après leur parution [29].
Conclure, c’est aussi laisser une impression synthétique au lecteur. Alors, résumons : la motivation de Claude Pair chercheur, c’était de faire de l’informatique une science. Il y a réussi. Achevons par un graphe dont il est l’auteur (cf. figure 8).
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.
[P19] ↑ Concerning the syntax of Algol 68, Algol Bulletin 31, 16-27, 1970.
[P20] ↑ Rapport d’évaluation Algol 68, avec coauteurs, RIRO Informatique 5, n° 1, 15-106, 1971.
[P21] ↑ Application de la théorie des ramifications au problème de l’équivalence structurale de deux C- grammaires, RIRO Math. 5, n° 2, 130-136, 1971.
[P22] ↑ L’algorithme d’analyse syntaxique de P. Broize, RIRO Informatique, n° 2, 111-123, 1971.
[P23] ↑ Problèmes de cheminement dans les graphes, avec J.C. Derniame, Monographies d’informatique, Dunod, 1971.
[P24] ↑ Les structures de données et leur représentation en mémoire, cours à l’Ecole d’Eté de l’AFCET, 1971, puis, avec Marie-Claude Gaudel, IRIA Roquencourt, 270 p., 1977.
[P25] ↑ La formalisation des langages de programmation, Informatique et Sciences Humaines 9, n° 34, 71-86, 1971.
[P26] ↑ Définition du langage algorithmique Algol 68, avec le groupe Algol de l’AFCET, Act. Sc. et Ind. 1354, Hermann, 1972.
[P27] ↑ Compilation, cours à l’école d’été de l’AFCET, 1972.
[P28] ↑ Analyse syntaxique, cours à l’école d’été CEA-EDF-IRIA, 1973.
[P29] ↑ On description languages for algorithms and programs, rapport interne, 1973.
[P30] ↑ Formalization of the notions of data, information and information structure, in IFIP Working Conference Data Base Management Systems, Klimbie-Koffemann éd., North-Holland 149-168, https: //dblp.uni-trier.de/db/conf/ds/dbm74.html#Pair74, et 1974 [30]
[P31] ↑ Toute grammaire LL(k) est LR(k), RAIRO Informatique 8 n° 2, 59-62, 1974.
[P32] ↑ Aspects de la théorie de la programmation, avec coauteurs, cours à l’école d’été de l’AFCET, 1974.
[P33] ↑ Rapport de l’ATP Informatique 1972 : Informatique théorique, programmes et données, Équipe associée 364, Université de Nancy II. Éd, 1974.
[P34] ↑ Réflexions sur la programmation, journée SESORI sur la programmation, 13-18, 1974.
[P35] ↑ Calculs, ensembles de calculs, équivalence de programmes, Conv. Informatica Teorica 1973, Sym- posia Matematica 15, Academic Press, 35-54, 1975.
[P36] ↑ Introduction à une méthode de programmation déductive, avec J. Maroldt in L’enseignement de la programmation, IRIA, 1975.
[P37] ↑ Manuel du langage algorithmique Algol 68, P. Bacchus, J. André, C. Pair (éds), groupe Algol de l’AFCET, Act. Sc. et Ind. 1373, Hermann), 1975.
[P38] ↑ Algorithms for checking consistency of attribute grammars, in Proving and Improving programs, avec B. Lorho, IRIA Int. Coll., Arc et Senans, 29-54, 1975.
[P39] ↑ Some proposals for a very high level language on a variable universe, in New Directions in Algo- rithmic Languages (S. Schuman, ed.), W.G. 2.1. Conf., IRIA, 53- 70, 1975.
[P40] ↑ Du problème à sa solution, Colloque SESORI, Logique et Programmation, Le Bischenberg, 1975.
[P41] ↑ Initiation à la programmation, avec N. Carbonnel, CNTE, 1976.
[P42] ↑ Les arbres en théorie des langages, Colloque « Les arbres en algèbre et en programmation », Lille, 196-216, 1976.
[P43] ↑ Inference for regular bilanguages, in Formal Languages and programming (R. Aguilar, éd.), North- Holland, 15-30, 1976.
[P44] ↑ Objectifs, réalisations et expériences de l’introduction de l’informatique dans l’enseignement se- condaire en France, Colloque sur Informatique et Enseignement, Neuchatel, 1977.
[P45] ↑ La construction des programmes, Journées informatiques de Nice et Ecole d’été de Montréal, 1977.
[P46] ↑ Inference for regular bilanguages, avec J. Berger, Journ. Comp. System Sciences 16, 100-122, 1978.
[P47] ↑ MEDEE, a type of language for constructing programs, avec coauteurs, Workshop on reliable software, Bonn 1978.
[P48] ↑ La programmation : de l’énoncé au programme, conférence invitée au congrès de l’AFCET, 1978.
[P49] ↑ Correctnes proofs of syntax-directed processing description by attributes, avec M. Amirchahy et D. Néel Journ. Comp. System Sciences 18 , 1-17, 1979.
[P50] ↑ La construction des programmes, RAIRO Informatique 13, 113-137, 1979.
[P51] ↑ Construction de compilateurs basée sur une sémantique formelle, avec M.C. Gaudel, Journées francophones, Genève, 83-101, 1979.
[P52] ↑ The use of formal semantics to produce and prove compilers, avec M.C. Gaudel, Workshop on semantics of programming languages, Bad Hohnef, 1979.
[P53] ↑ Spécifications et langages de spécification, Panorama des langages d’aujourd’hui, séminaire GRO- PLAN, Congrès, 1979.
[P54] ↑ Computer Science, a new dimension of contemporary science, avec M. Borillo in Scientific Culture in the Contemporary World, Scientia, 343-363, 1979.
[P55] ↑ L’algorithmique, ou comment l’informatique amène à faire des mathématiques, Conférence invitée au 4e séminaire, coll. de la Comm. Int. Enst Math., Luxembourg, 117-134, 1979.
[P56] ↑ Some theorical aspects of program construction, in Program Construction, International Summer School, Springer Lecture Notes in Comp. Sc. 69, 617-651, 1979.
[P57] ↑ La production assistée du logiciel, introduction et perspectives, Journées Francophones, Genève, 1-13, 1980.
[P58] ↑ Types abstraits et sémantique algébrique des langages de programmation, CRIN 80-R-011, 1980.
[P59] ↑ Application of abstract data types to the définition of the semantics of programming languages, conférence invitée à « Formalization of Programming Concepts », Peniscola, 1981.
[P60] ↑ Claude Pair et Yves Le Corre, L’introduction de l’informatique dans l’éducation nationale, Rapport au Ministre, http://www.epi.asso.fr/revue/histo/h81_Pair-Le-Corre.htm, octobre 1981.
[P61] ↑ Abstract data types and algebraic semantics of programming languages, Theor. Comp. Sc.18, 1 – 31, 1982.
[P62] ↑ A systematic study of models of abstract data types, avec M. Broy et M. Wirsing Theor comp. Sc.33, 139-174, 1984.
[P63] ↑ Programmation, par Amédée Ducrin (ouvrage collectif : M. Créhange, J.-P. Finance, J. Guyard, N. Hertschuh, C. Pair, M. Quéré, J. Souquières), tomes 1 et 2, Dunod Informatique, 1984.
[P64] ↑ Informatique et enseignement : hier, aujourd’hui et demain, Bulletin de l’association Enseignement public et Informatique, septembre 1987.
[P65] ↑ Informatique et lutte contre l’échec scolaire, in J.-M. Hoc, P. Mendelsohn, Les langages informa- tiques dans l’enseignement, Psychologie française 32, 1987.
[P66] ↑ Construire les algorithmes, avec R. Mohr et R. Schott, Dunod Informatique, 1988.
[P67] ↑ Can computer help combat school failure ?, C. Pair et coll., Computers in education, Elsevier, 1988.
[P68] ↑ Programmation, langages et méthodes de programmation, Le Travail humain 51, no 4, 1988.
[P69] ↑ A tout CRIN : histoire d’un laboratoire, Colloque sur l’Histoire de l’Informatique en France, Gre- noble, 1988. in The History of a Laboratory, Annals of the History of Computing 12, 1990.
[P70] ↑ Programming, programming languages and programming methods, Psychology of Programming, Academic Press, 1990.
Thèses dirigées par Claude Pair
[T1] ↑ M. CUSEY. Construction d’un compilateur Algol pour IBM 1620, 3e cycle (1964).
[T2] ↑ R. ROMAC. Étude des méthodes de tri, 3e cycle (1964).
[T3] ↑ J. ANDRÉ. Contribution à la construction d’un compilateur Algol pour IBM 1620, 3e cycle (1965).
[T4] ↑ A. ÉMOND. Application de la notion de pile à des problèmes portant sur les chemins des graphes,3e cycle (1965).
[T5] ↑ A. FLOC’H. Achèvement d’un compilateur Algol, traitement des procédures, 3e cycle (1966).
[T6] ↑ J.C. DERNIAME. Étude d’algorithmes pour les problèmes de cheminement dans les graphes finis, 3e cycle (1966).
[T7] ↑ H. SCHIVI. Étude de Cogent, langage de traitement de structures arborescentes, 3e cycle (1968).
[T8] ↑ A. QUÉRÉ. Étude des ramifications et des bilangages, 3e cycle (1969).
[T9] ↑ J. VILLARD. Emploi de PL/1 pour les problèmes de linguistique, 3e cycle (1969).
[T10] ↑ J.M. DIRAND. Les langages ATF-LMU, application aux problèmes linguistiques, mise en œuvre sur CII 10070, 3e cycle (1969).
[T11] ↑ J.M. MARTIN. Un mode d’exploitation du dossier médical, 3e cycle (1969).
[T12] ↑ J. CHABRIER. Etude d’une télétransmission par terminal, 3e cycle (1970).
[T13] ↑ J.M. LECLAIRE. Définition de la syntaxe des langages de programmation, 3e cycle (1970).
[T14] ↑ R. KHALIL. Essai de formalisation de la description des compilateurs, docteur- ingénieur (1970).
[T15] ↑ C. LEMAIRE. Système général d’analyse syntaxique, 3e cycle (1971).
[T16] ↑ P. LESCANNE. Étude de quelques théories des langages et généralisation du théorème de Kleene, 3e cycle (1971).
[T17] ↑ F. BELLEGARDE. Face, langage d’écriture de compilateurs, définition et implémentation, 3e cycle (1972).
[T18] ↑ J. MAROLDT. Définition de Face, langage pour l’écriture des compilateurs, implémentation d’un sous-ensemble, docteur-ingénieur (1972).
[T19] ↑ P. GERMAIN. Système de gestion et d’exploitation documentaire d’un corpus de dossiers médi- caux, 3e cycle (1972).
[T20] ↑ R. MOHR. Modèle algébrique pour l’analyse syntaxique de figures, 3e cycle (1973).
[T21] ↑ N. CARBONELL. Rôle des fonctions récursives de ramifications dans la définition d’une langue naturelle, application à la syntaxe française, 3e cycle (1972).
[T22] ↑ J.B. JOUIN. Reconnaissance des fonctions primaires de la phrase anglaise, 3e cycle (1973).
[T23] ↑ J.C. DERNIAME. Le projet CIVA, un système de programmation modulaire, État (1974).
[T24] ↑ J.L. RÉMY. Structures d’information, formalisation des notions d’accès et de modification d’une donnée, 3e cycle (1974).
[T25] ↑ J.P. FINANCE. Contribution à la formalisation de la sémantique d’un langage de programmation, application à Algol 68, 3e cycle (1974).
[T26] ↑ P. MARCHAND. Étude et classification des bigrammaires, applications à l’étude des systèmes transfomationnels, 3e cycle (1974).
[T27] ↑ H. PISTRÉ. L’analyse syntaxique dans FACE, langage pour l’écriture des compilateurs, 3e cycle (1975).
[T28] ↑ J. JARAY. Le langage SNOBOL4, ses applications, son implémentation, 3e cycle (1975).
[T29] ↑ M. CRÉHANGE. Description formelle, représentation, interrogation des informations complexes : système Pivoines, État (1975).
[T30] ↑ A.M. RASSER. Outils d’aide à la mise au point d’un compilateur écrit dans le langage FACE, 3e cycle (1976).
[T31] ↑ M. MAZAUD. Système d’aide à la production de traducteurs, 3e cycle (1976).
[T32] ↑ J.J. GIRARDOT, F. MIREAUX. Réalisation d’un interprète complet du langage APL sur un mini- ordinateur, docteur-ingénieur (1978).
[T33] ↑ F. PRUSKER. Aspects théoriques et pratiques du tri par fusion sur disque, État (1977).
[T34] ↑ B. HUC. Mise en œuvre de la méthode de programmation déductive, docteur- ingénieur (1977).
[T35] ↑ J. BERGER. A study of inference for regular bilanguages, PH.D, University of Pensylvania (1977).
[T36] ↑ A. TISSERANT. Compilateur du langage Pascal sur mini-ordinateurs, réalisation sur Solar 16, docteur-ingénieur (1977).
[T37] ↑ A. COCHET-MUCHY. La production de programmes dans le projet SYGARE, docteur-ingénieur (1978).
[T38] ↑ P. NONN. Le système d’exploitation dans le projet SYGARE, docteur-ingénieur (1978).
[T39] ↑ P. LESCANNE. Étude algébrique et relationnelle des types abstraits et de leurs représentations, État (1979).
[T40] ↑ J.P. FINANCE. Étude de la construction des programmes : méthodes et langages de spécification et de réalisation de problèmes, État (1979).
[T41] ↑ J. MARIN-NAVARRO. Un método de programacion .- presentacion, implementacion, transporte, Universitad Complutense, Madrid (1979).
[T42] ↑ M. QUÉRÉ. Contribution à l’amélioration des processus d’enseignement, d’apprentissage et d’or- ganisation de l’éducation : l’ordinateur outil et objet d’enseignement, application au projet SATIRE, État (1980).
[T43] ↑ M.C. GAUDEL. Génération et preuve de compilateurs basées sur une sémantique formelle des langages de programmation, État (1980).
[T44] ↑ P. DESCHAMP. Production de compilateurs à partir d’une description sémantique des langages de programmation : le système PERLUETTE, docteur-ingénieur (1980).
[T45] ↑ P. MARCHAND. Langages d’arbres, langages dans les algèbres libres, État (1981).
[T46] ↑ E. CHOURAQUI. Contribution à l’étude théorique de la représentation des connaissances. Le sys- tème symbolique Arches, État (1981).
[T47] ↑ J.L. RÉMY. Etude des systèmes de réécriture conditionnels et applications aux types abstraits algébriques, État (1982).
[T48] ↑ Radhia COUSOT. Fondements des méthodes de preuve d’invariance et de fatalité de programmes parallèles, État (1985).
Références
[1] ↑ A. V. Aho and J. D. Ullman, The Theory of Parsing, Translation, and Compiling, Vol. 1, Parsing. Prentice Hall, 1972.
[2] ↑ R. M. Amadio, Luca Cardelli, Subtyping Recursive Types, ACM Trans. Program. Lang. Syst. 15(4),575-631, DOI :10.1145/155183.155231, 1993.
[3] ↑ J.-W. Backus et coll [31], Report on the algorithmic language Algol 60, Nümerische Mathematik 2, 1960.
[4] ↑ J. C. Boussard, Étude et réalisation d’un compilateur Algol 60 sur calculatrice du type IBM 7090/7094 et 7040/44, Thèse d’État Science appliquée, Grenoble, https://hal.archives-ouvertes.fr/tel-00009449/, 1964.
[5] ↑ J. C. Boussard, J. J. Duby (éds), Rapport d’évaluation Algol 68, Revue française d’informatique et de recherche opérationnelle R-1, 1971.
[6] ↑ J. Buffet, P. Arnal, A. Quéré Définition du langage algorithmique Algol 68, présent. et trad. française du Report on the algorithmic language Algol 68 éd. Hermann (Actualités scientifiques et industrielles), 1972.
[7] ↑ N. Chomsky, On certain properties of grammars, Information and Control 2, 1959.
[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
[11] ↑ J.C. Derniame, A propos du cheminement dans les graphes, revue de la SIF 1024, N° 16, 2020.
[12] ↑ E. W. Dijkstra, Go To Statement Considered Harmful, CACM, Communications of the ACM 11, 3. 147-148, 1968.
[13] ↑ J.-P. Finance, J.-L. Rémy, Structure d’information et sémantique d’un langage de programmation, école d’été de l’AFCET GRENADE 1973.
[14] ↑ J.-P. Finance, P. Lescanne, P. Marchand, R. Mohr, C. Pair, A. Quéré, J-L. Rémy, Aspect de la Théorie de la Programmation, Cours de l’école d’été d’informatique, Tarbes, (imprimé à l’IREM de Nancy), 1974.
[15] ↑ L. Fossier, M. Créhange, Un essai de traitement sur ordinateur des documents diplomatiques du Moyen Age, ANNALES Economies, Sociétés, Civilisations) 1, 1970.
[16] ↑ A. Gerbier, Mes premières Constructions de programmes, LNCS 55, Springer- Verlag, 1977.
[17] ↑ Anna Gram, Raisonner pour programmer, Dunod informatique, 1993.
[18] ↑ Y. Gurevich, Evolving algebras, Lipari guide. Specification and validation methods, 9-36, https: //dblp.uni-trier.de/db/conf/asm/eap1993.html#Gurevich93, 1993.
[19] ↑ Y. Gurevich : Sequential abstract-state machines capture sequential algorithms. ACM Trans. Comput. Log. 1(1) : 77-111,https://dblp.uni-trier.de/db/journals/tocl/tocl1.html#Gurevich00, 2000.
[20] ↑ S. C. Johnson, Yacc : Yet Another Compiler-Compiler, AT&T Bell Laboratories Tech- nical Reports. AT&T Bell Laboratories Murray Hill, New Jersey 07974 (32), http:// dinosaur.compilertools.net/yacc/, 1975, Retrieved 31 October 2014.
[21] ↑ D. E. Knuth. A proposal for input-output conventions in Algol 60. Commun. ACM 7, 5, 273-283, May 1964.
[22] ↑ D. E. Knuth, Literate Programming, Californie, Stanford University Center for the Study of Lan- guage and Information, (ISBN 978-0937073803), 1992.
[23] ↑ D. E. Knuth, The Art of Computer Programming, Addison-Wesley, https://www-cs- faculty.stanford.edu/%7Eknuth/taocp.html, à partir de 1968.
[24] ↑ E. Lazard, P. Mounier-Kuhn, Histoire illustrée de l’informatique, 2e édition, EDP Sciences, 2019.
[25] ↑ P. Lescanne, « La science informatique », dans Encyclopédie Illustrée de la Lorraine, Histoire des Sciences et des Techniques, vol. Sciences exactes, Éditions Serpenoises, p. 105-116, 1996.
[26] ↑ C. Livercy (nom collectif : J.-P. Finance, M. Grandbastien, P. Lescanne, P. Marchand, R. Mohr, A. Quéré, J.-L. Rémy), Théorie des programmes : schémas, preuves, sémantique, Dunod Informatique 1978 33.
[27] ↑ R. Mohr, Généralisation de la notion de langage à contexte libre. Application à l’analyse syntaxique de figures, RAIRO Informatique théorique, tome 9, no R2, p. 55-88, 1975.
[28] ↑ P. Naur.(éd.), Revised Report on the algorithmic language Algol 60, Comm. ACM, 1963.
[29] ↑ R. Péter, Recursive Functions. Traduit par István Földes. New York : Academic Press, 1967 34.
[30] ↑ R. Péter, Die Pair-schen freien Binoïden als Speziallfälle des angeordneten freien holomorphen Men- gen, Eötvös Lorand Universität Budapest, 1968, publié dans Acta Mathematica Academiae Scientiarum Hungaricae Tomus 21 (3—4), pp. 29--313, 1970.
[31] ↑ B. C. Pierce, Types and Programming Languages, The MIT Press Cambridge, Massachusetts, ISBN 0-262-16209-1, 2002.
[32] ↑ M. Quéré, Modèle mathématique d’un système d’enseignement, Computers in education, North Hol- land, 1975.
[33] ↑ D. Sangiorgi, On the origins of bisimulation and coinduction 35, ACM Trans. Pro- gram. Lang. Syst. 31(4), 15 :1-15 :41, https://dblp.uni-trier.de/db/journals/toplas/ toplas31.html#Sangiorgi09, 2009.
[34] ↑ J-D Warnier, B. M. Flanagan, Entraînement à la construction des programmes d’informatique : Prin- cipes et exercices pratiques, Les Éditions d’organisation, 1970.
[35] ↑ A. Van Wijngaarden, B. J. Mailloux, J. E. L. Peck, C. H. A. Koster (éds), Report on the Algorithmic Language Algol 68, Springer, 1969 et Traduction française par le groupe franco-belge Algol P. Arnal, J. Buffet, A. Quéré, éds.), Actualités scientifiques et industrielles, Hermann, 1972.
[36] ↑ N. Wirth, Helmut Weber, EULER : a generalization of Algol and its formal definition, Part 1. Com- mun. ACM 9(1), 13-25 (1966) et Part II. Commun. ACM 9(2), 89-99, 1966.
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.
- ↑ Le mot « ordinateur » a été inventé en 1955 par le philologue Jacques Perret, en réponse à une demande d’IBM, qui voulait un nom plus parlant que « calculateur » pour son IBM 650.
- ↑ L’Est Républicain du 6 novembre 1958 annonce la création d’un institut de calcul automatique dont la direction sera confiée à Jean Legras : « Doté d’un matériel ultra moderne, cet institut est destiné à être commun à toutes les facultés de la région de l’Est ; les cours seront notamment suivis par les élèves de 3ème cycle de mathématiques appliquées. On pense qu’il pourrait ouvrir ses portes dans un délai de deux mois : au 1er janvier très probablement ».
- ↑ Que Claude, adepte de la francophonie, rebaptisera « langages à contextes libres » dans son cours.
- ↑ http://jacques-andre.fr/.
- ↑ Jacques André, Michel Cusey, Alain Floc’h, Jean-Marie Laporte.
- ↑ A tout CRIN : de la naissance à la maturité (1963-1976), Archives Poincaré, Nancy, janvier 2019.
- ↑ Une équation à point fixe est une équation de la forme . 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).
- ↑ Qu’il appelle « mode » à la mode de l’époque !
- ↑ La société savante d’informatique à l’époque.
- ↑ 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. »
- ↑ 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.
- ↑ 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).
- ↑ Mais la méthode était encore étudiée avec un oeil mathématique en 2010, bulletin No48 de l’APMEP, juillet-aôut 2010.
- ↑ Dénomination proposée par Pierre Lescanne et déclinée en Amédée Ducrin, nom d’auteur du livrede programmation associé à la méthode [P63].
- ↑ 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.
- ↑ Jean-Louis Ovaert était un ami de Claude depuis leur scolarité au lycée Louis le Grand. Mathématicien hors pair et excellent pédagogue il a enseigné à la faculté des sciences de Nancy et plusieurs de ses étudiants ont rejoint l’équipe de Claude à la fin des années soixante.
- ↑ Directeurs : Claude Pair de 1971 à 1974, Jean-Claude Derniame en 1975, Georges Stamon de 1976 à 1983.
- ↑ Langage symbolique d’enseignement implémenté sur des ordinateurs Mitra 15 installés dans 58 lycées.
- ↑ Socrate parlait de maïeutique.
- ↑ On ne peut pas dire que Claude a une belle écriture
- ↑ Par exemple, selon Google Scholar, pour l’article sur les bilangages paru en 1968 [P11], on trouve encore 37 citations postérieures à l’an 2000. Le lecteur pourra aussi lire l’introduction prémonitoire du livre de Livercy [26].
- ↑ On peut aussi consulter la page dédiée à Claude Pair sur le site du Digital Bibliography & Library Project, https://dblp.uni-trier.de/pid/63/4413.html..
- ↑ Le comité de définition comprend un français, B. Vauquois, professeur à Grenoble.
- ↑ Dans l’article du journal du CNRS du 23.09.2016 par Martin Koppe, Pierre Mounier-Kuhn signale qu’il s’agit « de la première thèse de France en informatique ».