Source: https://b-ok.cc/book/2352579/6bce57
Timestamp: 2020-05-26 20:30:19+00:00

Document:
Cours d'informatique : langages et programmation | Pierre-Claude Scholl, Marie-Christine Fauvet, Fabienne Lagnier, Florence Maraninchi | download
Main Cours d'informatique : langages et programmation
Cours d'informatique : langages et programmation
Pierre-Claude Scholl, Marie-Christine Fauvet, Fabienne Lagnier, Florence Maraninchi
2225842892
9782225842894
Download (djvu, 3.79 MB)
les2131
une2001
est1834
par1514
dans1424
d'un760
d'une745
fonction719
qui599
sur592
peut573
exemple562
sont514
nous506
valeur451
sous413
alors391
une séquence389
nom376
par exemple357
la fonction338
arbre315
vide314
un entier313
nombre313
langage306
fonctions294
forme290
texte285
dans le275
selon271
une fonction267
soit255
dans la255
cette253
ensemble242
l'on211
sinon210
premier208
comme206
tableau202
l'expression197
la valeur194
domaine182
valeurs178
gauche174
noms166
ainsi166
entre164
entiers160
est une159
chaque159
un arbre155
nombre de152
l'ensemble151
remarque149
Fred Espen Benth, Jurate Saltyte Benth, Steen Koekebakker
(enseignement) \ in i I n ci t ro citi R-C.SCHOLL M.-C.FAUVET F.LAGNIER F. MARANINCHI Préface de M. SINTZOFF MASSON N V
Pour la liste complète, voir catalogue MÉTHODES DE PROGRAMMATION ET ALGORITHMIQUE ANALYSE INFORMATIQUE. P.-A. Goupille. CONCEPTION OBJET DES STRUCTURES DE DONNÉES. B. Quément. ÉLÉMENTS D'ALGORITHMIQUE. D. Beauquier, J. Berstel et Ph. Chrétienne. CONCEPTION ET PROGRAMMATION PAR OBJETS. Techniques, outils, et applications. J.-P. Aubert et P. Dixneuf. • ALGORITHMIQUE. Conception et analyse. G. Brassard et P. Bratley. PROGRAMMATION IMPÉRATIVE ET PROGRAMMATION DÉCLARATIVE. Ph. Collard. • INTRODUCTION À LA PROGRAMMATION 1. Algorithmique et langages. J. Biondi et G. Clavel. 2. Structures de données G. Clavel et J. Biondi. 3. Exercices corrigés G. Clavel et F.B. Jorgensen. • SCHÉMAS ALGORITHMIQUES FONDAMENTAUX P.C. Scholl et J.P. Peyrin. ASSEMBLAGE, MODÉLISATION, PROGRAMMATION (80x86). M. Margenstem. LA COMPRESSION DES DONNÉES. Méthodes et applications. G. Held. • ALGORITHMIQUE ET PRÉSENTATION DES DONNEES 1. Files, automates d'états finis. M. Lucas, J.-P. Peyrin et P.-C. Scholl. 2. Évaluations, arbres, graphes, analyse de texte. M. Lucas. 3. Récursivité et arbres. P.-C. Scholl. PROCESSUS CONCURRENTS. Introduction à la programmation parallèle. M. Ben Ari. PROCESSUS SÉQUENTIELS COMMUNICANTS. C.A.R. Hoare. CONSTRUCTION ET VÉRIFICATION DE PROGRAMMES. R. Backhouse. LES LANGAGES ET LEUR TRAITEMENT LE LANGAGE C. B.W. Kernighan et D.M. Ritchie. LE LANGAGE C. Solutions. CL. Tondo et S.E. Gimpel. CONSTRUCTION LOGIQUE DE PROGRAMMES COBOL. Mise à jour COBOL 85. M. Koutchouk. • LANGAGE C norme ANSI. Vers une approche orientée objet. Ph. Drix. TURBO INITIATION À LA PROGRAMMATION EN PASCAL, pour Turbo-Pascal 4.0, 5.0, 5.5, 6.0. J. Thiel, C. Léger et G. Jacquet. • MÉTHODOLOGIE DE LA PROGRAMMATION EN LANGAGE C. Principes et applications. J.-P. Braquelaire. • (COMMON) LISP. Une introduction à la programmation. H. Wertz. COBOL. Perfectionnement et pratique. M. Koutchouk. PROGRAMMER EN C++. S.C. Dewhurst et K.T. Sta; rk. LE GÉNÉRATEUR AUTOMATIQUE DE PROGRAMME RPG. M. Rémy. LANGAGE C : MANUEL DE RÉFÉRENCE. S.H. Harbison et G.L. Steele. LANGAGE C. PROBLÈMES ET EXERCICES. A.R. Feuer. • LANGAGE C, norme ANSI. Variations sur des thèmes Pascal. Ph. Drix. • LES LANGAGES DE PROGRAMMATION. Concepts essentiels, évolution et classification. J. Lonchamp. INTRODUCTION AU LANGAGE ADA. D. Price. • TRAITEMENT DES LANGAGES ÉVOLUÉS. Compilation. Interprétation. Support d'exécution. Y. Noyelle. • APPRENDRE PASCAL ET LA RÉCURSIVITÉ. Avec exemples en TURBO PASCAL. R. Romanetti. LE LANGAGE PASCAL. J.-M. Crozet et D. Serain. MANUEL ADA. LANGAGE NORMALISÉ COMPLET. M. Thorin. INFORMATIQUE THÉORIQUE -—-- — ^--—-—— ™- ThÉORIE DES LANGAGES ET DES AUTOMATES. J.-M. Autebert. CALCULABILITÉ ET DÉCIDABILITÉ. J.-M. Autebert. • Cours rédigé et enseigné par un professeur francophone. (Suite page 3 de couverture)
cour/d informatique: langage/ et programmation
CHEZ LE MÊME ÉDITEUR Des mêmes auteurs Schémas algorithmiques fondamentaux. Séquences et itération, par P.-C. Scholl, J.-P. Peyrin. MIM-Algorithmiquet Programmation, série Enseignement. 1989, 288 pages. Algorithmique et représentation des données, par M. Lucas. Tome 1. — Files, automates d'états finis, en collaboration avec J.-P. Peyrin et P.-C. Scholl. MIM - Algorithmique, Programmation. 1985, 2e tirage, 200 pages. Tome 2. — Évaluations, arbres, graphes, analyse de textes. MIM - Algorithmique, Programmation. 1986, 2e édition revue et complétée, 200 pages. Tome 3. — Récursivité et arbres, par P.-C. Scholl. MIM - Algorithmique, Programmation. 1989,2e tirage, 224 pages. Dans la même collection Introduction a la programmation, par G. Clavel et J. Biondi. Tome 1. — Algorithmique et langages. Préface de O. Lecarme. 1987, 3e édition révisée et complétée, 280 pages. Également publié en espagnol (1985) et en italien (1985). Tome 2. — Structures des données. 1989, 2e tirage, 272 pages. Également publié en espagnol (1985) et en italien (1985). Tome 3. — Exercices corrigés, par G. Clavel et F.B. Jorgensen. 1985, 176 pages. Également publié en espagnol (1985). Découvrir la programmation orientée objets avec smalltalk V, par G. Clavel et L. Veillon. 1991,242 pages. Éléments d'algorithmique, par D. Beauquier, J. Berstel et Ph. Chrétienne. 1992,480 pages. Technologie des ordinateurs, pour les IUT et BTS d'informatique, avec exercices, par P.-A. Goupille. 1990,368 pages. Apprendre pascal et la récursivité, avec exemples en Turbo Pascal, par R. Romanetti. 1989,168 pages. Dans la collection Logique, Mathématiques, Informatique Mathématiques pour l'informatique, par D.B. Arnold et I. Guessarian. 1992, 360 pages. Algorithmes et complexité, par H.S. Wilf. Traduit de l'anglais par P. Roux. 1989, 208 pages.
manueis inpoRmflTioues mnsson cour/ d'informatique: langage/ et programmation P.-C. SCHOLL Professeur M.-C. FAUVET F. LAGNIER F. MARANINCHI Maîtres de conférences Université Joseph Fourier Préface de M. Sintzoff MASSON Paris Milan Barcelone 1993
Tous droits de traduction, d'adaptation et de reproduction par tous procédés, réservés pour tous pays. Toute reproduction ou représentation intégrale ou partielle, par quelque procédé que ce soit, des pages publiées dans le présent ouvrage, faite sans l'autorisation de l'éditeur, est illicite et constitue une contrefaçon. Seules sont autorisées, d'une part, les reproductions strictement réservées à l'usage privé du copiste et non destinées à une utilisation collective, et d'autre part, les courtes citations justifiées par le caractère scientifique ou d'information de l'œuvre dans laquelle elles sont incorporées (loi du 11 mars 1957 art. 40 et 41 et Code pénal art. 425). Des photocopies payantes peuvent être réalisées avec l'accord de l'éditeur. S'adresser au : Centre français d'exploitation du droit de copie, 3 rue Hautefeuille, 75006 Paris, tél. : 43 26 95 35. © Masson, Paris, 1993 ISBN : 2-225-84289-2 ISSN : 0249-6992 Masson S.A. 120, bd Saint-Germain, 75280 Paris Cedex 06 Masson S.p.A. Via Statuto 2/4, 20121 Milano Masson S.A. Avenida Principe de Asturias 20, 08012 Barcelona
Préface Cette préface présente quelques idées et points de vue que la lecture du livre a suscités ou rafraîchis ; ce devrait être la preuve de l'intérêt qu'il peut éveiller. Le choix des thèmes traités est aussi original que captivant, puisqu'ils concernent la programmation par fonctions, par relations et par actions. L'auteur de cette préface a redécouvert avec amusement les traces de sa propre évolution scientifique depuis bientôt trente ans. Il a en effet d'abord étudié les langages formels, traités à la fin du livre, ensuite la programmation par actions dans le contexte des systèmes parallèles, et puis la programmation de fonctions pour formaliser les preuves ; il a aussi exploré la programmation par relations dans le cadre d'un enseignement sur les systèmes d'information. De même, chaque nouvel ou futur informaticien trouvera dans le livre une présentation méthodique et claire des grands axes de la programmation. En effet, la conception de systèmes informatiques s'exprime souvent dans le cadre de la programmation par actions, l'emploi de bases de données relationnelles correspond à la programmation par relations, et la programmation par fonctions caractérise le développement d'applications en intelligence artificielle à l'aide de langages du genre Lisp. La grande ouverture intellectuelle dont témoigne le livre reste maîtrisée par un recours systématique aux idées mathématiques pertinentes. La programmation par fonctions fait ainsi appel aux concepts de composition et d'induction, et prend une forme syntaxique de plus en plus algébrique. L'idée d'homomorphisme éclaire le rapport essentiel entre les inductions sur les données et celles sur les fonctions, et sous-tend d'élégants énoncés de divers schémas de calcul. La programmation par relations se base sur une algèbre élémentaire des relations, et permet déjà de modéliser l'utilisation courante de bases de données relationnelles. La programmation par actions est présentée comme aussi mathématique que la programmation fonctionnelle ou relationnelle. Ceci dément à juste titre une vue scientifique étroite. En effet, si les fonctions et relations font en quelque sorte appel à l'algèbre, les actions expriment elles le point de vue dynamique comme étudié en analyse. Il est remarquable que la programmation par actions se base sur les concepts de prédicat invariant et de fonction d'états décroissante : l'on retrouve ainsi les deux piliers essentiels de l'étude des systèmes dynamiques, en particulier sous l'impulsion de Poincaré, à savoir l'invariance et la stabilité, celle-ci étant assurée par des fonctions décroissantes. Les concepts d'ensembles d'états et de transitions entre états s'avèrent aussi fondamentaux qu'universels, comme en témoigne l'importance permanente de la théorie des
VI Préface automates. De plus, les principes de composition et d'induction s'appliquent autant aux actions qu'aux fonctions. Une autre qualité de l'ouvrage est le désir d'ouvrir l'esprit aussitôt que possible dans la formation. En particulier, l'utile et limpide algèbre relationnelle introduite ici n'est que trop souvent reléguée dans des formations spécialisées ou tardives. Un enseignement de base dans la ligne équilibrée du livre ne peut que favoriser l'éducation d'informaticiens ayant une tête bien faite plutôt que bien pleine. Il faut de plus louer la volonté constante des auteurs de garder les pieds sur terre : ils présentent de nombreux exemples et applications modèles, qui concernent des problèmes souvent suggestifs et pertinents. Il faut aussi les remercier pour leur liberté d'esprit : leur sélection de langages se caractérise par un goût sûr autant que par une analyse scientifique correcte. Il faut enfin les inciter à ne pas s'arrêter en si bon chemin. L'entreprise n'est au fond qu'à ses débuts : les pistes abordées dans ce premier livre sont fort prometteuses, comme en témoignent de bouillonnantes activités de recherche. La programmation par fonctions et par relations tend à se cristalliser dans une algèbre algorithmique, basée sur des concepts mathématiques tels qu'homomorphisme et point fixe et sur des notations d'emploi facile comme en algèbre élémentaire. Il est possible qu'un tel calcul algorithmique intègre, même si c'est dans un futur lointain, les divers calculs spéciaux des mathématiques actuelles, tels que les calculs booléen, matriciel, différentiel et intégral. C'est ainsi que le livre éclaircit le lien existant entre la notation de sommation et la notation de liaison de variable. La programmation par actions sous-tend la conception de systèmes parallèles et de réseaux neuromimétiques, puisque ceux-ci se mod- élisent par des systèmes de transitions et plus généralement par des systèmes dynamiques. L'étude de grammaires formelles, concept symétrique de celui d'automates, constitue un premier pas vers celle de la programmation par grammaires, dont l'analyse mathématique reste encore peu développée alors que son importance pratique est connue depuis deux décennies. Dans cette perspective de travail futur, l'éventail des études de cas ne peut que croître, depuis les applications multi-media jusqu'au traitement de la langue en passant par la bioinformatique. L'on peut évidemment discuter chacun des choix des auteurs quant aux sujets traités et aux approches suivies. Mais il ne faut pas tirer sur les pianistes. L'intégration et la simplification intellectuelles que promeut le livre méritent éloge et reconnaissance. Pouvons-nous espérer un nouveau volume d'ici cinq ans ? Michel Sintzoff Professeur d'informatique Université catholique de Louvain
Table des matières Préface V Avant-propos XI I Expression fonctionnelle 1 1 Valeurs, expressions, fonctions 3 1.1 Analyse descendante 4 1.2 Langage des expressions 8 1.3 Analyse par cas 11 1.4 Fonctions dont le codomaine 16 1.5 Exercices 18 1.6 Pour expérimenter : découvrir Scheme 19 2 Types construits 25 2.1 Spécification d'un type 25 2.2 Réalisation d'un type 28 2.3 Exercices 34 2.4 Problème dirigé : calendrier grégorien 36 2.5 Pour expérimenter 42 3 Définitions récursives 45 3.1 Introduction à la récursivité 46 3.2 Preuve par récurrence 48 3.3 Définition récurrente d'un ensemble, 51 3.4 Analyse récurrente d'une fonction 55 3.5 Exercices 64 3.6 Problème dirigé : à propos de monnaie 67
VIII Table des matières 3.7 Pour expérimenter 69 4 Séquences : schémas d'analyse 73 4.1 Le constructeur séquence 73 4.2 Découpages élémentaires d'une séquence 77 4.3 Découpage selon une propriété 80 4.4 Exercices 85 4.5 Problèmes dirigés / . 88 4.6 Pour expérimenter 91 5 Le type arbre, une introduction 93 5.1 Définitions, terminologie 93 5.2 Traitement d'arbres binaires 99 5.3 Traitement d'arbres n-aires et de forêts 105 5.4 Exercices 108 5.5 Problèmes dirigés 110 5.6 Pour expérimenter 117 6 Ordre supérieur 123 6.1 Fonctions d'ordre supérieur, 124 6.2 Liaison des noms 128 6.3 Schémas fonctionnels 132 6.4 Formes récursives terminales 135 6.5 Schéma de réduction d'une séquence 138 6.6 Exercices 144 6.7 Pour expérimenter 148 II Expression relationnelle 153 7 Ensembles et relations 155 7.1 Ensembles 155 7.2 Relations 162 7.3 Modélisation à l'aide de relations 165 7.4 Opérations sur les relations 172 7.5 Exercices 176 8 Notation relationnelle 179 8.1 Spécification d'une relation 179 8.2 Opérations sur les relations 181 8.3 Récapitulatif des opérateurs 185
Table des matières IX 8.4 Limites de la notation 187 8.5 Exemple commenté 188 8.6 Exercices 193 8.7 Problèmes dirigés 194 9 Expérimenter en SQL 199 9.1 Consultation des données en SQL 199 9.2 Valeurs inconnues 209 9.3 Les vues ou relations dérivées 212 9.4 Exemple commenté 214 9.5 Problèmes dirigés 217 III Expression actionnelle 223 10 Langage des actions 225 10.1 Informations, actions, états, assertions 225 10.2 Compositions d'actions 229 10.3 Paramétrisation 235 10.4 Exercices 239 10.5 Pour expérimenter : machine-tracés 241 11 Actions récursives 247 11.1 Observation d'actions récursives 247 11.2 Transformation récursif-itératif 251 11.3 Etude d'un algorithme de tri récursif 256 11.4 Exercices 259 11.5 Pour expérimenter : dessins récursifs 261 12 Séquences et tableaux 263 12.1 Représentation contiguë d'une séquence à l'aide de tableaux 263 12.2 Cas des séquences triées 272 12.3 Exercices 274 12.4 Problème dirigé 278 12.5 Pour expérimenter 281 13 Analyse itérative 283 13.1 Séquences et itérations 283 13.2 Choix des variables d'une itération 292 13.3 Automates 302 13.4 Exercices 310
X Table des matières 13.5 Pour expérimenter 314 IV A propos de langages 321 14 Les langages, objets d'étude 323 14.1 Repères 323 14.2 Un exemple de méta-langage . 327 14.3 Exercices 336 15 Langages et grammaires 339 15.1 Notion de grammaire 339 15.2 Utilisation des grammaires 344 15.3 Analyse descendante 355 15.4 Exercices 363 15.5 Pour expérimenter 365 16 Etude de cas 367 16.1 Découverte du langage 367 16.2 Spécification de la syntaxe 372 16.3 Ecriture d'un analyseur 375 16.4 Pour expérimenter 377 Annexes 381 A Programmes Scheme 383 A.l Calendrier Grégorien 383 A.2 Schémas d'ordre supérieur 387 B Programmes Pascal 391 B.l Patchwork 391 B.2 Machine tracé 400 Liste d'exemples et d'exercices 407 Index 411 Bibliographie 416
Avant-propos Présentation Le cours d'Informatique que nous présentons ici est issu de quatre années d'expériences menées en deuxième année de DEUG Scientifique a l'Université Joseph Fourier de Grenoble. Il est conçu pour apporter des bases scientifiques et techniques, nécessaires aujourd'hui à toute formation scientifique. Il peut être utilisé, en tout ou en partie, dans les cursus nécessitant des fondements en informatique, et plus particulièrement : - DEUG Scientifique ou Technologique, IUT, IUP ; - licence d'Informatique, première année de MIAG ou de MST en Informatique ; - diplômes universitaires en Mathématiques ou en Sciences de la Matière ; formations d'ingénieurs, formations de formateurs, ... Le livre s'adresse à un lecteur ayant déjà acquis un premier niveau en informatique. Par exemple, dans notre université, ce premier niveau (une cinquantaine d'heures d'enseignement) est fondé sur ([BeB92]) : - La découverte des constituants d'un environnement informatique (matériel, système d'exploitation, compilateur, éditeur, ... ) ; - Une première approche des concepts liés à. la pratique d'un langage de programmation (information, langage, type, variable, structures de contrôle et de données) ; - Une première vision de la problématique de l'informatique (formulation de problèmes-types, méthodes d'analyse, situations où intervient l'informatique, ... ) ; - Une réflexion sur les modes d'expression utilisés en informatique (problèmes, algorithmes, programmes, résultats, ... ). Au-delà de nombreux aspects techniques, les principaux sujets étudiés dans le livre sont les suivants : - La résolution progressive et raisonnée des problèmes en s'appuyant sur l'identification de niveaux d'abstraction successifs et l'utilisation de langages adaptés. - L'explicitation de démarches d'analyse et de modes de raisonnement, que l'on retrouve partout en informatique : spécification, décomposition, analyse par cas, récurrence, organisation modulaire, ...
XII Avant-propos - L'étude des propriétés des textes que l'on produit, en complément à la seule intuition ou observation du comportement d'une machine à laquelle en est confiée l'exécution. - L'étude de structures informatiques et leur description à divers niveaux de langage, concernant aussi bien la structuration des logiciels (types, fonctions, actions), l'organisation des données (ensembles, relations, séquences, arbres) que le contrôle de l'exécution (itération, récursion, automates). - L'observation des langages dans leurs aspects syntaxiques, sémantiques et pragmatiques. Ces éléments fondamentaux de l'Informatique sont traités au travers d'aspects théoriques, de méthodes de résolution de problèmes et d'expérimentations concrètes. La compréhension et la maîtrise des facteurs de complexité s'appuie sur l'étude et la confrontation de trois niveaux de langages informatiques : fonctionnel, relationnel et actionnel. L'algorithmique est vue comme l'art de s'imposer une attitude méthodique dans la construction de programmes, en se plaçant au bon niveau d'abstraction, en choisissant les moyens d'expression adéquats et en ré-utilisant des algorithmes fondamentaux. Le livre regroupe ainsi des sujets traditionnellement séparés dans des ouvrages informatiques spécialisés traitant de l'algorithmique, de la programmation, des bases de données ou des langages. Le livre en présente les bases, de manière unifiée, en prenant pour fil directeur la relation entre Langages et Programmation. Le texte, illustré par de nombreuses figures, comporte une grande variété d'exemples commentés, d'exercices et de problèmes, et fournit des scénarios d'expérimentation pratique en SCHEME, SQL et PASCAL. Objectifs Le livre vise à transmettre une démarche scientifique vis-à-vis des programmes, des algorithmes, des descriptions d'analyse et de problèmes, Le débutant doit comprendre le besoin d'une discipline, en accepter les contraintes, et équilibrer ses goûts et ses énergies entre les problèmes de spécification, la ré-utilisation adéquate de techniques répertoriées et l'expérimentation. La structuration de cet apprentissage repose sur une claire perception des divers niveaux de complexité qui caractérisent l'informatique : complexité factuelle, inhérente aux problèmes et/ou aux limites des machines, complexité technique, liée à la variété des outils et à leur sophistication, et complexité conceptuelle, imposée par la distance entre l'énoncé d'un problème et une solution informatique. La résolution d'un problème informatique procède d'une démarche progressive mettant en évidence des niveaux d'abstraction successifs : de manière générale, on réduit la complexité du développement d'un logiciel en le décomposant en étapes auxquelles sont associés des produits intermédiaires. Le passage d'une étape à une autre est soumis à une vérification de ces intermédiaires, qui tient compte des propriétés attendues du logiciel. Il est ainsi nécessaire de disposer d'une variété de stratégies d'analyse et de moyens d'expression, adaptés aux divers points de vue pris en compte dans cette démarche. Les multiples savoir- faire informatiques s'appuient par conséquent sur la maîtrise de ces moyens d'expression et sur des attitudes rigoureuses et précises, même si elles ne sont pas formelles ([Gra86]).
Avant-propos XIII C'est pourquoi nous mettons un accent important, dans une formation de base, sur la notion même de langage, en exposant le lecteur à divers moyens d'expression et en montrant leurs aspects pragmatiques, au plan conceptuel pour l'expression de la pensée, et au plan technique pour la mise en œuvre d'une solution. Contenu Tout en présentant les éléments techniques indispensables, le cours est conçu autour des aspects méthodologiques liés aux questions d'analyse, d'expression et de validation de solutions. Il comporte une pratique expérimentale et propose des ouvertures sur divers domaines (algèbre, logique, langages, modélisation des informations, ... ). Il est organisé en quatre thèmes, ce qui permet d'aborder les sujets d'étude, séparément et selon divers points de vue, tout en les reliant progressivement. Le thème /, centré sur l'expression fonctionnelle, installe la problématique évoquée ci-dessus : explicitât ion des modes de raisonnement, exposé et pratique d'une notation fonctionnelle, utilisation de la récursivité et de l'ordre supérieur, étude des structures de séquences et d'arbres, expérimentations au travers d'un langage de programmation à dominante fonctionnelle (SCHEME, qui fait partie des dialectes de LlSP). Les chapitres 1 et omettent en place le cadre d'expression, les modes de raisonnement et les notions de base : - notions d'information, de type, de valeur et modes de description à l'aide de règles de composition (produit de types, tableaux). - notion de fonction et modes de description en termes d'expressions, conditionnelles le cas échéant. - paradigmes d'analyse : désignation, typage, analyse par cas, paramétri- sation, introduction d'objets intermédiaires (types ou fonctions). - modèles d'évaluation précisant la sémantique des notations employées. Le chapitre 3 étend la puissance d'expression de la notation par la possibilité de définitions récursives des types ou des fonctions. Les principes de récurrence sont à la fois un guide pour l'analyse des problèmes et un moyen de vérifier la validité des textes fournis. Une démarche systématique d'analyse est exposée dans le cas, particulier mais fréquent, où les informations mises en jeu relèvent de types récursifs (entiers, séquences, arbres, ensembles). Les chapitres ^ et 5 renforcent la maîtrise de l'analyse récurrente tout en présentant les structures de séquence et d'arbre. L'expression fonctionnelle permet de les comprendre et de les manipuler à un niveau d'abstraction élevé, en évitant de devoir présenter simultanément les techniques, de plus bas niveau, de représentation de ces structures. Le chapitre 6 complète le langage en introduisant l'ordre supérieur. On peut alors formaliser une démarche de programmation fondée sur l'utilisation de schémas fonctionnels décrivant des classes générales de problèmes. Par ailleurs, l'ordre supérieur offre un cadre pour une compréhension plus précise des mécanismes d'évaluation des langages. Le thème II est centré sur Vexpression relationnelle. Fondé sur l'algèbre relationnelle, il est concrétisé par une expérimentation dans le langage SQL. Outre l'ouverture qu'il offre sur le domaine des bases de données, ce thème illustre,
XIV Avant-propos dans un autre cadre linguistique, la relation entre la nature des problèmes traités, le niveau d'abstraction auquel on se place et le moyen d'expression employé. La notation relationnelle offre des opérations de haut niveau permettant de concentrer l'effort d'analyse sur la complexité des informations. Les raisonnements s'appuient sur des connaissances de base sur les ensembles, les relations et la logique. Les chapitres 7 et 8 montrent comment modéliser un ensemble d'informations en termes d'un ensemble structuré de relations. On utilise l'expression fonctionnelle et l'ordre supérieur pour spécifier les opérations de base sur les ensembles et les relations. On présente l'algèbre relationnelle. Les concepts sont illustrés par des problèmes typiques de consultation d'informations complexes. Le chapitre 9 est le support de l'expérimentation dans le langage SQL. C'est l'occasion pour le lecteur d'être confronté à un nouveau langage de programmation et d'exercer son esprit critique sur ses caractéristiques syntaxiques, sémantiques et pragmatiques. Le thème III complète les acquis des étudiants en matière d'expression actionnelle. Il est concrétisé par une expérimentation en PASCAL. Le niveau d'abstraction auquel on se place permet d'aborder des techniques liées à l'expression du contrôle séquentiel de l'exécution (itérations et actions récursives) ou de la représentation des informations (à l'aide de tableaux). L'exposé assure le lien avec les thèmes précédents, en montrant comment l'analyse d'un problème, même si l'on vise une expression actionnelle, peut s'appuyer sur une spécification fonctionnelle ou relationnelle préalable. De plus, il comporte une ouverture sur la notion d'automate, vue comme un moyen d'expression adéquat pour l'analyse de certains problèmes itératifs. Les chapitres 10 et 11 présentent une notation actionnelle et situent la complémentarité des démarches d'un mode d'expression à l'autre. L'étude d'actions récursives renforce les principes de récurrence dans un contexte où l'on raisonne sur des états, et permet d'expliciter le lien entre processus récursifs et itératifs. Le chapitre 12 propose des techniques systématiques liées à la manipulation des tableaux. Il illustre, sur le cas de la structure de séquence, le passage d'une vue fonctionnelle abstraite à une forme concrète de représentation. Le chapitre 13expose une approche méthodique de la construction d'itérations. L'application systématique de schémas itératifs (parcours et recherche) permet de limiter les problèmes de terminaison. La question de la découverte des variables pertinentes pour une itération est abordée en partant d'une expression fonctionnelle du problème, que l'on raffine progressivement en tenant compte des propriétés des itérations. On montre alors dans quels cas et comment représenter un algorithme itératif à l'aide d'un automate d'états fini. Le thème IV est centré sur les langages en tant qu'objets d'étude. Il s'appuie sur la pratique des divers moyens d'expression rencontrés pendant le cours et renforce l'ensemble des concepts et techniques introduits. L'expérimentation, en PASCAL, porte sur l'étude et la traduction d'un langage jouet. Le chapitre 14 situe la notion de langage selon divers points de vue : constituants (syntaxe, sémantique et pragmatique), définition, traduction. Ceci est concrétisé en abordant les techniques liées à la description de la syntaxe et à l'analyse syntaxique, dans le cas de langages réguliers.
Avant-propos XV Le chapitre 15 aborde le cadre formel des grammaires pour étudier les propriétés syntaxiques des langages et leur influence sur la structure des programmes de traitement d'un langage. Diverses formes d'expression de la syntaxe sont comparées : notations BNF et EBNF, diagrammes syntaxiques. Les techniques descendantes de reconnaissance syntaxique sont illustrées, sous forme fonctionnelle et sous forme actionnelle. Le chapitre 16 est un scénario d'expérimentation autour de l'étude d'un langage de description de dessins et la réalisation d'un logiciel de visualisation de dessins décrits à l'aide de ce langage. Remerciements L'Université Joseph Fourier de Grenoble a, depuis le début des années 80, favorisé une politique d'installation de l'Informatique comme discipline fondamentale en DEUG Scientifique. Elle a ainsi constamment soutenu les efforts en ce sens de l'UFR d'Informatique et de Mathématiques Appliquées notamment en présidant à la définition de cursus intégrant l'enseignement de l'informatique de manière significative, et en aidant à l'obtention des moyens matériels et humains adéquats. Jean-Paul Bertrandias, Professeur d'Informatique à l'Université Joseph Fourier, est le pionnier, l'artisan et l'animateur constant et infatigable de la réflexion politique, scientifique et pédagogique, de la mise en œuvre matérielle (des locaux, aux machines en passant par les finances,...), de la constitution d'équipes pédagogiques, qui ont permis de créer le contexte actuel d'enseignement de l'Informatique en DEUG Scientifique dans notre université. Il a largement contribué, au cours de nombreuses séances de travail, à la mise en place de l'enseignement dont nous rendons compte ici et à la rédaction de cet ouvrage. La Société des Personnels Enseignants Chercheurs en Informatique (SPECIF) a organisé plusieurs confrontations nationales, sous la houlette de Michel Lucas, Professeur d'Informatique à l'Université de Nantes, sur la question de l'enseignement de l'informatique en premier cycle. Ceci a donné une dimension nationale à la question posée et conforté les uns et les autres dans les efforts entrepris. Au cours des quatre années pendant lesquelles nous avons expérimenté le matériel pédagogique présenté dans ce livre, nous avons travaillé avec de nombreux collègues, et notamment : P. Amblard, 0. Baudoin, M.F. Bruandet, S. Bensalem, X. Girod, C. Loiseaux, J. Mailfert, C. Oriat, S. Pinchinat. Grenoble, Mai 1993, Pierre-Claude Scholl, Marie-Christine Fauvet, Fabienne Lagnier, Florence Maraninchi
Thème I Expression fonctionnelle Nous abordons le cours dans une ambiance fonctionnelle : on raisonne et on s'exprime en termes de fonctions — au sens mathématique du terme — et des ensembles qu'elles mettent en jeu, que l'on appelle des types en informatique. On se place ainsi à un niveau d'abstraction élevé par rapport au fonctionnement de l'ordinateur, fondé, quant à lui, sur la notion d'état et sur l'évolution des états dans le temps. C'est dans ce cadre que nous élaborons, dans ce thème, la problématique du cours autour des axes suivants : - Les moyens d'expression : la présentation d'une notation fonctionnelle (proche de celle proposée dans [FiH88]) et d'un langage de programmation est le support d'une réflexion sur la notion même de langage préalable à la discussion proposée dans le thème IV. - Le concept de type et les notions associées : leur présentation fait apparaître progressivement leur rôle central en informatique, pour modéliser les informations du monde réel, pour structurer puis valider les solutions, pour organiser les connaissances techniques, pour concevoir les langages, ... - Les démarches d'analyse des types et des fonctions : décomposition, analyse par cas et récurrence sont explicitées. Les conditions de leur application sont exposées en relation avec les outils linguistiques associés : composition fonctionnelle et conditionnelle, construction de types et définitions récursives. Un accent particulier est porté sur la définition la plus précise et la plus rigoureuse possible des propriétés des entités que l'on fait intervenir. Spécifier (une partie d') un problème avant de le résoudre est une activité inhabituelle et difficile pour qui raisonne en priorité en termes du fonctionnement de la machine. Le niveau d'abstraction et la puissance d'expression du style fonctionnel favorisent la compréhension puis l'assimilation de cette activité. - Les types inductifs : la présentation des structures de séquence et d'arbre au niveau fonctionnel facilite leur assimilation et renforce la notion de type, la récursivité et les démarches d'analyse. - L'expérimentation en machine : les activités proposées, ici autour de la pratique d'un langage à dominante fonctionnelle, concrétisent les concepts du cours, développent une attitude pragmatique face aux aspects techniques et ouvrent sur des sujets tels que l'analyse de l'exécution d'un programme, le test d'un programme, la documentation, ...
1 Valeurs, expressions, fonctions La modélisation informatique d'un problème s'appuie en premier lieu sur la collecte des informations pertinentes dans la réalité de ce problème, sur le regroupement en ensembles des valeurs que ces informations font intervenir, et sur l'identification des opérations dont on doit munir ces ensembles pour refléter la réalité. En informatique, un tel ensemble de valeurs est appelé un type. Les valeurs que regroupe un type sont les constantes de ce type. Elles sont notées de manière précise : on parle des dénotations de constantes. Les langages informatiques offrent des types de base prédéfinis, mais permettent aussi de définir de nouveaux types (chapitre 2). Dans un style fonctionnel, la résolution d'un problème consiste en l'identification d'une ou plusieurs fonctions dont l'application à des valeurs données fournira les résultats escomptés : une fonction est une association entre deux types, qui à chaque élément du type de départ, appelé domaine de la fonction, fait correspondre un élément du type d'arrivée, appelé codomaine de la fonction. Le domaine et le codomaine d'une fonction peuvent être des types de base ou composés de plusieurs types (§1.4 et chapitre 2). Une fonction est définie à partir de fonctions attachées aux types qu'elle met en jeu. Pour décrire les fonctions qui nous intéressent en informatique, nous utilisons un langage d'expressions (§1.2). Il existe trois formes de composition d'expressions : fonctionnelle (§1.1), conditionnelle (§1.3) et récursive (chapitre 3). Du point de vue de la résolution des problèmes, le style fonctionnel permet de traduire le principe général d'analyse descendante, ce qui conduit à distinguer la spécification d'une fonction, sa réalisation et son utilisation (§1.1). L'étude de l'expression fonctionnelle est ainsi l'occasion d'expliciter quelques paradigmes d'analyse fondamentaux : désignation, typage, paramétrisation, analyse par cas, analyse récurrente, ... Nous les préciserons progressivement en montrant les notations associées dans le style fonctionnel.
4 1 : Valeurs, expressions, fonctions A propos de la lecture des données et de l'affichage des résultats De manière classique, un programme comporte des instructions de lecture des données et d'écriture des résultats. Par exemple, dans un contexte actionnel (Cf. chapitre 10), un programme de calcul de la somme de deux entiers pourrait être : lexique a, b : des entiers algorithme lire (a, b) ; écrire (a-f b) Lors de l'exécution d'un tel programme, l'interprétation de l'instruction de lecture conduit à une attente des données de la part de l'utilisateur. De même, le résultat est affiché du fait de l'interprétation de l'instruction d'écriture apparaissant explicitement dans le programme. Dans un langage purement fonctionnel, c'est-à-dire qui ne permet de manipuler que des expressions et des fonctions, il n'existe pas a priori d'action de lecture ou d'écriture, qui par essence modifient des états. En principe, c'est donc au niveau de l'environnement de programmation plus qu'à celui du langage proprement dit, que l'interaction avec l'extérieur ou avec les supports de mémorisation externes est explicitée (dans la pratique, les langages fonctionnels n'ont pas la pureté mentionnée ci-dessus et incluent des actions d'entrée-sortie). Dans ce qui suit, nous nous concentrons sur les bases de l'expression fonctionnelle et nous ne voulons pas nous préoccuper de la question des entrées et des sorties. A cet effet, nous nous plaçons dans un environnement de programmation interactif dans lequel l'utilisateur fournit une expression du langage et l'environnement réagit en évaluant cette expression et en affichant la valeur obtenue. Par exemple, l'utilisateur fournit l'expression 3+4 et le système affiche 7 (ce qui correspond implicitement à la lecture de 3 et de 4 et à l'écriture de leur somme comme dans le programme ci-dessus). Ainsi pour tous les problèmes d'écriture de programmes que nous proposerons en exemple ou en exercice, la solution consistera en l'écriture d'une ou plusieurs fonctions. La mise en œuvre sur l'ordinateur consistera alors à utiliser ces fonctions dans des expressions : les données seront fournies en paramètre des fonctions et les résultats seront affichés à la suite de l'évaluation de ces expressions. 1.1 Analyse descendante Le principe d'analyse descendante est le suivant : après une phase de spécification du problème, on le décompose en problèmes intermédiaires indépendants qui à leur tour sont spécifiés. On exprime alors la solution du problème de départ en supposant les problèmes intermédiaires résolus, puis on résout les sous-problèmes en procédant de la même manière. Les fonctions permettent de rendre compte d'une telle analyse : elles ont ainsi un rôle de structuration des textes décrivant la solution d'un problème. Une fonction fixe un certain niveau d'abstraction. Lorsqu'on introduit une fonction, on enrichit le répertoire de fonctions disponibles que l'on pourra ré-utiliser. Dans le processus de construction d'un programme, nous distinguons la spécification d'une fonction, sa réalisation et son utilisation : - Spécifier une fonction, c'est la nommer, définir son domaine et son codomaine et en fixer la signification : par exemple, on introduira une fonc-
1.1 : Analyse descendante 5 tion de nom Cube, on indiquera que son domaine et son codomaine sont le type entier, et, supposant la notion de cube connue, on dira simplement qu'elle associe à un entier son cube. - Réaliser une fonction, c'est associer à un nom de fonction spécifiée au préalable une expression paramétrée de manière adéquate. Par exemple, on associera au nom de fonction Cube l'expression a*a*a ou encore l'expression a3, où a est un nom formel. On parle des paramètres formels d'une fonction, c'est-à-dire des noms choisis pour décrire la fonction en faisant abstraction de la valeur particulière dont on veut connaître le cube. - Utiliser une fonction, c'est décrire son application aux arguments désirés au sein d'une expression, comme par exemple Cube (2) + Cube (3). Les arguments sont appelés les paramètres effectifs (de cette application particulière de la fonction). La spécification d'une fonction peut être vue comme un contrat, intermédiaire entre la réalisation de la fonction et son utilisation : - Au niveau de l'utilisation, on fait abstraction de la réalisation : si l'on fournit le bon nombre de paramètres dans le bon ordre, si ces paramètres ont les types indiqués et vérifient les autres contraintes explicitées dans la spécification, il est garanti que l'expression aura la valeur spécifiée. - Au niveau de la réalisation, on fait abstraction du contexte d'utilisation, et on garantit que l'expression fournie comme solution a la valeur spécifiée quel que soit le contexte d'utilisation. Dans ce qui suit, nous illustrons ces diverses notions au travers d'un exemple simple. Exemple El.l : Moyenne olympique Décrire une fonction qui étant donnés quatre entiers positifs, leur associe la moyenne des deux nombres parmi les quatre qui ne sont ni le plus grand, ni le plus petit. Par exemple, la moyenne olympique des quatre nombres 10, 8, 12, 14 est 11, celle des nombres 12, 12, 12, 12 est 12. a) Spécification et utilisation d'une fonction Dans un premier temps, nous spécifions la fonction : nous la nommons mo, nous définissons son domaine, quatre entiers positifs, et son codomaine, un réel, et nous rappelons sa signification : mo : un entier > 0, un entier > 0, un entier > 0, un entier > 0 —► un réel { mo (u, v, w, x) désigne la moyenne olympique des nombres u, v, w et x } Remarque : On peut abréger la description du domaine de la fonction de la manière suivante : mo : quatre entiers > 0 —► un réel. Un exemple simple de contexte d'utilisation de cette fonction est l'expression mo (10, 8, 12, 14) dont l'évaluation donne la valeur 11. On peut aussi combiner l'utilisation d'une fonction dans une expression plus large telle que : (mo (10, 8, 12, 14) + mo (18, 13, 17, 18))/2 (qui peut représenter une moyenne sur deux épreuves). La spécification d'une fonction comporte sa désignation, son typage et la définition de sa signification.
6 1 : Valeurs, expressions, fonctions A propos de désignation, citons [Gra86] (pp 23, 24) : "... le paradigme de désignation a pour rôle d'expliciter une entité en la nommant et en lui associant une définition plus ou moins intuitive. Les noms introduits servent en premier lieu à la formulation des énoncés. Par ailleurs, ils interviennent constamment dans les justifications des choix de Vanalyse... Le choix d'un nom mérite une certaine attention : en début d'analyse, on a sans doute intérêt à utiliser des mots ou des groupes de mots, les plus significatifs possibles. La fréquence d'utilisation de ces mots dans le reste de l'analyse peut conduire à rechercher une diminution de leur taille ou une prononciation plus facile. Par ailleurs, les contraintes imposées par certains langages de programmation peuvent conduire à modifier ces mots au moment de la traduction dans ces langages". Le typage de la fonction consiste à définir son profil : nature du domaine, ici un quadruplet d'entiers, et nature du codomaine, ici un réel. Pour cela, on utilise des noms de types qui font partie de la notation fonctionnelle en les restreignant éventuellement par une propriété. Dans notre exemple, on a utilisé une restriction du type entier (entier > 0) et le type réel. Remarque : On parle de prédicat pour qualifier une fonction dont le codomaine est le type booléen. Pour expliciter la signification, on exprime, sous forme d'un commentaire (que nous délimitons par des accolades), la relation entre un élément du domaine et l'élément correspondant du codomaine, en termes du contexte d'application. Ici on fait simplement référence à la notion de moyenne olympique donnée dans l'énoncé. Notre exemple illustre aussi comment utiliser la fonction : V appel de la fonction comporte son nom suivi, entre parenthèses et séparés par des virgules, des paramètres effectifs : ce sont les expressions à la valeur desquelles doit être appliquée la fonction. Le nombre de paramètres effectifs fournis doit correspondre à celui apparaissant dans la spécification. Ils doivent être énumérés dans l'ordre indiqué et respecter les types spécifiés. Remarque : On emploie ainsi une syntaxe préfixée pour décrire un appel de fonction. Ceci se distingue de la syntaxe infixée employée habituellement pour les opérations arithmétiques par exemple (Cf. chapitre 15). b) Réalisation d'une fonction Réaliser une fonction consiste à associer à son nom une expression qui décrit l'association caractérisant la fonction. L'expression peut être composée en termes des opérations primitives du langage ou nécessiter l'introduction de fonctions intermédiaires. On spécifie alors ces fonctions, puis on réalise la fonction initiale en leurs termes et on répète le processus en réalisant les fonctions intermédiaires introduites. Dans notre exemple, on peut proposer plusieurs idées de résolution de la fonction mo : - Classer les quatre nombres, puis enlever le premier et le dernier, puis faire la moyenne des deux nombres restants. - Enlever le plus grand des quatre nombres, puis enlever le plus petit des trois nombres restants, puis faire la moyenne des deux nombres restants. - Additionner les 4 nombres, soustraire le plus grand et le plus petit, diviser par 2.
1.1 : Analyse descendante 7 C'est cette troisième idée que nous décrivons ici. Son énoncé suggère l'introduction de deux fonctions intermédiaires, nommées maxquatre et minquatre : maxquatre : quatre entiers > 0 —► un entier { maxquatre (i, j, k, l) désigne le maximum des quatre nombres } minquatre : quatre entiers > 0 —► un entier { minquatre (i, j, k, l) désigne le minimum des quatre nombres } Remarque : Les deux fonctions ayant le même profil, on peut abréger l'écriture en écrivant : maxquatre, minquatre : quatre entiers > 0 —► un entier { respectivement le maximum et le minimum des quatre nombres donnés } On peut alors réaliser mo par une expression faisant intervenir ces deux fonctions. On fait abstraction des objets auxquels la fonction pourra être appliquée, à l'aide de noms : on parle des paramètres formels de la fonction (ici, u, v, w et x). mo (u, v, w, x) : (u-f v-f w-f x - minquatre (u, v, w, x) - maxquatre (u, v, w, x)) /2 c) Réalisation des fonctions intermédiaires De même que l'expression u-fv-fw-fx décrit la somme de 4 nombres par composition d'additions de 2 nombres, on décrit minquatre et maxquatre en termes de deux fonctions plus élémentaires : maxdeux, mindeux : deux entiers > 0 —► un entier { maximum et minimum de deux nombres } On peut alors décrire minquatre et maxquatre, par exemple : maxquatre (i, j, k, I) : maxdeux (maxdeux (maxdeux (i, j), k), I) minquatre (i, j, k, I) : mindeux (mindeux (mindeux (i, j), k), I) Pour réaliser mindeux et maxdeux, nous utilisons ici l'opération abs, valeur absolue d'un nombre (supposée primitive) : maxdeux (a, b) : (a+b + abs (a-b)) / 2 mindeux (a, b) : (a-f b - abs (a-b)) / 2 d) Présentation récapitulative de l'analyse du problème Dans ce qui précède nous avons mis en évidence que l'analyse d'une fonction consiste en plusieurs étapes dans lesquelles on spécifie des fonctions, on montre leur utilisation, puis on les réalise. Pour rendre compte de l'analyse, on regroupe l'ensemble des spécifications et des réalisations, par exemple de la manière suivante : Moyenne olympique, une solution Principe de résolution : additionner les 4 nombres, soustraire le plus grand et le plus petit puis diviser par 2.
8 1 : Valeurs, expressions, fonctions { spécification descendante des fonctions } mo : quatre entiers > 0 —► un réel { moyenne olympique de quatre nombres } maxquatre, minquatre : quatre entiers > 0 —► un entier { maximum et minimum de quatre nombres } maxdeux, mindeux : deux entiers > 0 —► un entier { maximum et minimum de deux nombres } { réalisation ascendante des fonctions } maxdeux (a, b) : (a+b + abs (a-b)) / 2 mindeux (a, b) : (a-f b - abs (a-b)) / 2 maxquatre (i, j, k, I) : maxdeux (maxdeux (maxdeux (i, j), k), I) minquatre (i, j, k, I) : mindeux (mindeux (mindeux (i, j), k), I) mo (u, v, w, x) : (u-f v-f w-f x - minquatre (u, v, w, x) - maxquatre (u, v, w, x)) /2 1.2 Langage des expressions Pour décrire les fonctions qui nous intéressent en informatique, nous utilisons un langage d'expressions. Au niveau syntaxique, une expression est formée de noms, de dénotations de constantes, de symboles (ou de noms) d'opérateurs ou de fonctions, de parenthèses, de virgules ... Sa forme est régie par des règles qui fixent l'ordre entre opérandes et opérateurs, entre nom d'une fonction et arguments, et qui précisent l'emploi de parenthèses et de séparateurs tels que les virgules, ... Une expression arithmétique décrit une valeur, simple ou complexe, par composition de fonctions appliquées à des valeurs. Cette valeur est définie par les modèles d'évaluation attachés aux formes de composition. Par exemple, la phrase (2+4)*5 décrit la valeur 30 par une composition des opérations d'addition et de multiplication. De même, si le symbole x désigne le produit cartésien de deux ensembles, l'expression {"a", "b"} x {1, 2, 3} décrit la valeur {<"a", 1>, <"a", 2>, <"a", 3>, <"b", 1>, <"b", 2>, <"b", 3>}. Une expression algébrique généralise une expression arithmétique par l'introduction de noms permettant de faire abstraction des valeurs particulières auxquelles on s'intéresse. Par exemple, l'expression a3 est la généralisation en un texte unique de toutes les expressions telles que 23, 753, .. .et représente le cube d'un nombre. L'évaluation de l'expression n'est alors possible que dans un contexte qui définit les valeurs particulières que l'on veut associer aux noms qui apparaissent dans l'expression (nous approfondirons les mécanismes de noms au chapitre 6). Les types des opérandes auxquels on applique un opérateur (ou des arguments auxquels on applique une fonction) doivent être compatibles avec les types spécifiés pour l'opérateur (ou la fonction). a) Evaluation d'une fonction L'évaluation d'une fonction comporte deux étapes : dans la première, dite étape de réduction, on évalue les arguments auxquels est appliquée la fonction en tenant compte du contexte ; dans la seconde, dite étape d'expansion, on ré-écrit l'appel de la fonction en substituant les valeurs des arguments aux paramètres formels. En aucun cas, l'évaluation d'un appel de fonction ne peut
1.2 : Langage des expressions 9 modifier la valeur des paramètres. On dit qu'il n'y a pas & effet de bord. Ceci tient à ce que dans l'étape de réduction, l'évaluation d'un paramètre ne doit pas avoir d effet sur l'évaluation des autres paramètres. Il est donc inutile de préciser un ordre dans l'évaluation des arguments lorsqu'il y en a plusieurs. Illustrons ce principe sur un exemple. Exemple El.2 : Longueur d'un segment Soit à calculer la longueur d'un segment défini par les coordonnées de ses extrémités. Considérons la solution suivante : Is : quatre réels —► un réel { Is (xl, yl, x2, y2) désigne la longueur du segment défini par ses extrémités de coordonnées xl, yl et x2, y2 } cd : deux réels —► un réel { carré de la différence de deux réels } c : un réel —► un réel { carré d'un réel } \s (xl, yl, x2, y2) : >/cd (y2, yl) + cd (x2, xl) (1) cd (x, y) : c (x - y) (2) c (x) : x*x (3) Un processus d'évaluation de Is (1, 3, 5, 6) comporte alors les étapes suivantes : (le symbole —► marque une ré-écriture) : ls (1, 3, 5, 6) —► \/cd (6, 3) -f cd (5, 1) {expansion, d'après 1} {on choisit d'évaluer d'abord cd (6, 3)} —► y/ c (6 -3) -f cd (5, 1) {expansion, d'après 2} —y y/ c (3) -f cd (5, 1) {réduction après évaluation de - } —► \J (3*3) -f cd (5, 1) {expansion, d'après 3} —y \J 9 -f cd (5, 1) {réduction après évaluation de *} —► y/ 9 + c (5-1) {expansion, d'après 2} —► V7 9 + c (4) {réduction après évaluation de -} —► y/ 9 -f (4*4) {expansion, d'après 3} —y y/ 9 -f 16 {réduction après évaluation de *} —► y/ 25 {réduction après évaluation de +} —y 5 {réduction après évaluation de ^r} Remarque : Il s'agit ici du modèle d'évaluation dit en ordre applicatif. Il existe d'autres modèles d'évaluation. Par exemple, on peut d'abord regrouper toutes les expansions, puis opérer les réductions (Cf. [FÎH88], p 63). Une expression peut aussi n'être évaluée que partiellement : certains arguments ne sont évalués que sous certaines conditions. b) Désignation d'expressions intermédiaires On peut vouloir structurer la forme d'une expression, à l'aide d'un nom intermédiaire auquel est associée une expression. Par exemple, nommons la somme de quatre nombres avant de l'utiliser dans l'expression décrivant la moyenne olympique (El.l). On écrit alors la réalisation de la fonction mo comme suit :
10 1 : Valeurs, expressions, fonctions mo (u, v, w, x) : soit s=u-fv-fw-fx dans (s — minquatre (u, v, w, x) — maxquatre (u, v, w, x)) /2 On introduit ainsi la notation soit... dans... qui a la forme suivante : soit x=E dans F, où x est un nom et E et F sont des expressions. La phrase soit x=E dans F est une expression : son évaluation dans le contexte où elle apparaît consiste à évaluer l'expression E puis à remplacer dans l'expression F toute occurrence de x par la valeur de E et enfin à évaluer F. Ainsi l'expression E n'est évaluée qu'une fois avant l'évaluation de F. Le nom x ainsi introduit est local à l'expression F, c'est-à-dire que l'association de E à x n'a de sens que dans l'expression F (nous reviendrons sur cette notion au chapitre 6). Remarques : • Une utilisation fréquente de la construction soit est liée au souci de n'évaluer qu'une fois une sous-expression. Par exemple, l'évaluation de l'expression (1-f a*b) * (1—2*a*b) conduit à évaluer deux fois la sous-expression a*b. Pour éviter cette redondance de calcul, on écrit : soit p = a*b dans (1-f p) * (l-2*p). • On ne donne pas explicitement le type d'un nom local à une expression. Toutefois on peut le déduire des opérandes et des opérateurs intervenant dans l'expression associée. Plus généralement, on peut décrire simultanément plusieurs associations : soit xl = El, x2 = E2, ... xk = Ek dans F { on peut aussi écrire "soient" dans ce cas } Ces associations sont indépendantes les unes des autres : si dans une expression Ei on fait référence à un nom xj (i 7^ j), le nom xj tire sa signification du contexte englobant la construction soit et non de l'expression Ej. Si l'on veut effectivement exprimer une dépendance, on doit emboîter deux ou plusieurs constructions soit. Par exemple, l'évaluation de l'expression soit x= 3-f 4*5 dans soit y = x-f 5 dans x + y est celle de x + y, sachant que l'évaluation de l'expression associée à x donne la valeur 23 et que celle de l'expression associée à y donne la valeur 28. Dans l'analyse d'un problème, on peut introduire un nom local à une expression, ou introduire une fonction. Par exemple, dans la résolution de la moyenne olympique, au lieu d'introduire les fonctions maxquatre et minquatre, on aurait pu introduire deux noms intermédiaires M et m et écrire : mo (u, v, w, x) : soient s = u-fv-fw-fx { somme } M = maxdeux (maxdeux (maxdeux (u, v), w), x) { maximum } m = mindeux (mindeux (mindeux (u, v), w), x) { minimum } dans (s - m - M) /2
1.3 : Analyse par cas 11 Remarque : Le choix entre l'introduction d'une fonction ou d'un nom dépend du degré de généralité que l'on veut donner à la solution, une fonction pouvant être ré-utilisée dans un autre contexte. 1.3 Analyse par cas L'analyse par cas est une forme particulière de décomposition d'un problème en plusieurs problèmes considérés comme plus simples que l'on peut résoudre indépendamment les uns des autres. L'objectif d'une analyse par cas est de définir une partition sur le domaine de la fonction considérée, énumérant ainsi un ensemble de cas : un cas est la restriction du problème à un sous-domaine. Les cas doivent recouvrir la fonction et s'exclure mutuellement. A ces deux contraintes correspondent deux types d'erreurs : cas manquant, incohérence lorsque l'intersection de deux sous-domaines n'est pas vide. L'analyse par cas est un paradigme très général que nous introduisons ici en relation avec la composition conditionnelle. Un cas particulier d'application est la définition d'une fonction en extension. Les cas correspondent alors simplement aux différentes valeurs du domaine de la fonction. Il existe d'autres manières d'exprimer une fonction en extension, notamment à l'aide de tableaux (Cf. §2.2.d), d'automates (Cf. 13.3), ... a) Déterminer les cas Au travers d'un exemple simple, nous montrons diverses approches permettant de conduire une analyse par cas pour réaliser une fonction : par un examen du codomaine de la fonction, par un examen du domaine de la fonction ou par une réduction préalable du domaine de la fonction. Exemple El.3 : Maximum de trois entiers Décrire une fonction qui détermine le maximum de trois entiers, que l'on suppose distincts deux à deux. Nous spécifions la fonction de la manière suivante : Maxtrois : trois entiers —► un entier { maximum de trois nombres distincts deux à deux } a.l identification des cas par examen du codomaine de la fonction On identifie les expressions possibles du résultat et, pour chacune d'elles, on pose la question : "dans quelle condition le résultat peut-il être formulé de cette manière ?\ On exprime alors ces conditions à l'aide d'expressions à valeur booléenne. Dans notre exemple, le maximum de trois entiers a, b et c est soit a, soit b, soit c. On identifie ainsi trois cas. Par exemple, la valeur de la fonction est b si et seulement si b est plus grand que a et c. L'expression booléenne correspondante est b > a et b > c. On obtient ainsi une première solution : Maxtrois (a, b, c) : selon a, b, c a>b et a>c : a b>a et b>c : b c>a et c>b : c
12 1 : Valeurs, expressions, fonctions a.2 identification des cas par examen du domaine de la fonction Les données sont des triplets d'entiers. On répartit l'ensemble des triplets selon les positions respectives des nombres. Par exemple, si b est compris entre a et c , le résultat est c. On obtient ainsi une deuxième solution : Maxtrois (a, b, c) : selon a, b, c a>b et b>c : a b>a et a>c : b a>c et c>b : a b>c et c>a : b a. 3 réduction du domaine de la fonction On ne considère d'abord que deux des trois données, puis la plus grande des deux et la troisième. Ce principe est formulé par un emboîtement d'expressions conditionnelles : Maxtrois (a, b, c) : selon a, b a > b : selon a, c a < b : selon b, c a>c:a b>c:b a<c:c b<c:c Variantes La même idée peut être mise en œuvre en introduisant un nom intermédiaire auquel on associe le maximum de deux des données. Maxtrois (a, b, c) : soit m = selon a, b a > b : a a < b : b dans selon m, c m > c : m m < c : c On peut aussi introduire une fonction Maxdeux comme précédemment (§l.l.b) et écrire : Maxtrois (a, b, c) : Maxdeux (Maxdeux (a, b), c) Remarque : Que va-t-il se passer si l'on augmente le nombre de données considérées ? Parmi les solutions précédentes, lesquelles sont facilement réutilisables ? La solution 3 est à la base d'une définition récurrente (Cf. E3.2, §3.1) : le maximum de n nombres est le maximum de deux nombres, l'un des nombres et le maximum des n — 1 autres. b) La notation selon La forme syntaxique selon explicite tous les cas et met donc en évidence l'analyse par cas sous-jacente : on énumère l'ensemble des couples < condition, sous-expression >. Chaque condition est décrite par une expression booléenne. Par exemple, pour trois cas, on écrit : Oa et a>b : c c>b et b>a : c
1.3 : Analyse par cas 13 selon { description du domaine } Cl : El C2: E2 C3: E3 Le commentaire suivant le mot-clé selon a pour objet de décrire le domaine afin de permettre de vérifier que l'analyse par cas est correcte. Remarque : Le cas échéant, si cela n'introduit pas d'ambiguïté, on peut disposer les cas sur plusieurs colonnes : selon { description du domaine } Cl : El C2 : E2 C3 : E3 Evaluation : une telle phrase est une expression, nous parlons d'expression conditionnelle. Son évaluation comporte d'une part l'évaluation des sous- expressions booléennes Ci pour déterminer celle qui a la valeur vrai et d'autre part l'évaluation de la sous-expression Ei correspondant au cas ainsi identifié. La valeur alors obtenue est la valeur de l'expression conditionnelle. Du fait que l'on n'évalue pas toutes les expressions Ei, l'évaluation d'une expression conditionnelle est partielle. Soulignons que chaque cas doit pouvoir être compris indépendamment des autres. De ce fait, Vordre dans lequel les cas sont énumérés n'est pas pertinent vis-à-vis de l'évaluation. Propriété : on doit alors avoir (Cl ou C2 ou C3) et { recouvrement } non (Cl et C2) et non (Cl et C3) et non (C2 et C3) { exclusion mutuelle } c) Autres notations Pour exprimer une analyse en deux cas, on peut utiliser la forme si... alors... sinon Les deux expressions suivantes ont le même sens : si C alors El sinon E2 selon { description du domaine } C: El non C : E2 On n'explicite donc qu'un seul cas, le deuxième s'en déduisant implicitement. L'évaluation de l'expression consiste à évaluer la condition C puis à évaluer soit l'expression El, soit l'expression E2, selon que C a la valeur vrai ou faux. Lorsqu'il y a plus de deux cas on peut aussi utiliser le mot-clé sinon pour exprimer que la condition correspond à utous les autres cas" que ceux énumérés explicitement. Par exemple les expressions selon { description du domaine } selon { description du domaine } Cl : El Cl : El C2 : E2 C2 : E2 C3 : E3 C3 : E3 sinon : E4 non Cl et non C2 et non C3 : E4 ont le même sens.
14 1 : Valeurs, expressions, fonctions Remarques : • De nombreux langages de programmation n'offrent que la forme si... alors... sinon. On est alors obligé de traduire des analyses comportant plus de deux cas par des expressions conditionnelles emboîtées. La lecture, et donc la correction le cas échéant, de telles constructions est ainsi rendue difficile par une structuration artificielle, d'autant plus que les cas ne sont pas entièrement explicités. • Lors d'une analyse par cas, un recours trop rapide à la clause sinon peut conduire à oublier des cas, erreur difficile à trouver par la suite, dans la mesure où justement le cas correspondant n'est pas explicité dans l'expression. • Dans une expression conditionnelle, il est nécessaire d'exprimer la valeur de l'expression dans tous les cas : par conséquent, une notation de la forme si... alors..., qui existe dans l'expression actionnelle (Cf. §10.2), n'a pas de sens dans l'expression fonctionnelle. • Dans certaines conditions, on peut accepter que les cas ne s'excluent pas mutuellement. Un exemple simple est celui du maximum de deux valeurs : Maxdeux : deux entiers —► un entier { maximum de deux nombres } Maxdeux (a, b) : selon a, b a > b : a a < b : b En cas d'égalité de a et de b, les deux expressions booléennes ont la valeur vrai. Il n'y a donc pas exclusion mutuelle. Mais on peut accepter cette formulation dans la mesure où les deux sous-expressions a et b ont alors la même valeur. d) Tabulation d'une fonction et analyse par cas Exemple El.4 : Quantième d'une date des années 1900 On considère des dates de la période [1900... 1999] données sous forme de triplets d'entiers correspondant au jour, au mois et a l'année. Par exemple le triplet < 3,4,93 > correspond au troisième jour du quatrième mois de l'année 1993. On désire connaître le quantième d'une date dans son année, c'est-à-dire le nombre de jours entre le début de l'année et la date (incluse). Par exemple, pour le triplet 1, 1, 82, le résultat est 1, pour le triplet 31, 12, 72, le résultat est 366, pour le triplet 3, 4, 93> Ie résultat est 93. On doit tenir compte des années bissextiles. On spécifie la fonction : LeQuantièmel900 : un entier sur [1.. .31], un entier sur [1.. .12], un entier sur [0.. .99] —► un entier sur [1.. .366] { quantième d'une date donnée sous forme d'un triplet <jour, mois, année>. Le triplet doit correspondre à une date effective des années 1900 } Remarque : On a ainsi précisé les types intervenant dans le profil de la fonction en fournissant les intervalles d'entiers considérés comme valides. Ceci
1.3 : Analyse par cas 15 n'est pas encore suffisamment précis, le nombre de jours par mois variant d'un mois à l'autre. Cette imprécision est levée dans le commentaire. Le quantième d'une date se déduit simplement du quantième du premier jour du mois de cette date. On raisonne tout d'abord sur une année non bissextile. Si l'année est bissextile, on ajoute éventuellement un jour selon le mois. On introduit ainsi deux fonctions intermédiaires : EstBisl900 : un entier sur [0.. .99] —► un booléen { vrai <=> l'entier correspond à une année bissextile des années 1900 } qpm : un entier sur [1... 12] —> un entier sur [1.. .365] { quantième du premier jour du mois correspondant à l'entier donné dans une année non bissextile } On réalise maintenant la fonction LeQuantièmel900 : LeQuantièmel900 (j, m, a) : qpm (m) + j - 1 + (si m > 2 et EstBisl900 (a) alors 1 sinon 0) Remarque : On a ici un exemple d'utilisation d'une sous-expression conditionnelle dans une expression. La réalisation de la fonction EstBisl900 tient compte de la période particulière (1900 n'est pas bissextile) : EstBisl900 (a) : a ^ 0 et a reste 4 = 0 Il n'est pas vraiment naturel de chercher à exprimer la fonction qpm à l'aide d'une formule. On est ici dans le cas où l'on veut définir une fonction en extension. On utilise une expression conditionnelle : qpm (m) : selon m m=l : 1 m=2 : 32 m=3 : 60 m=4 : 91 m=5 : 121 m=6 : 152 m=7 : 182 m=8 : 213 m=9 : 244 m=10 : 274 m=ll : 305 m=12 : 335 e) Les opérateurs booléens conditionnels "et puis" et "ou alors" Reprenons l'expression de la fonction LeQuantième. Nous avons écrit : LeQuantième (j, m, a) : qpm (m) + j - 1 + (si m > 2 et EstBisl900 (a) alors 1 sinon 0) Si l'on veut être un peu plus précis, il n'y a lieu de s'intéresser à l'année qu'au-delà du mois de février. On écrira donc plutôt : qpm (m) + j - 1 + (si m > 2 alors si EstBisl900 (a) alors 1 sinon 0 sinon 0) H s'agit d'une situation générale, dans laquelle on veut exprimer une évaluation partielle d'une expression à valeur booléenne. Dans notre exemple, il s'agit de l'expression m>2 et EstBisl900 (a). On peut utiliser à cet effet les deux opérateurs binaires à valeur booléenne et puis et ou alors. Nous les définissons par une équivalence avec une expression conditionnelle :
16 1 : Valeurs, expressions, fonctions A et B étant deux expressions booléennes : - Les expressions A et puis B et si A alors B sinon faux ont le même sens : B n'est évalué que si A a la valeur vrai. - Les expressions A ou alors B et si A alors vrai sinon B ont le même sens : B n'est évalué que si A a la valeur faux. Remarque : Ainsi le modèle d'évaluation de ces opérateurs ne relève pas du modèle donné au paragraphe 1.2 : il s'agit d'une évaluation partielle. Dans notre exemple, nous pouvons maintenant écrire : LeQuantième (j, m, a) : qpm (m) -f j - 1 -f (si m > 2 et puis EstBisl900 (a) alors 1 sinon 0) On retrouve une structure de phrase analogue à la première solution, la précision étant exprimée par le remplacement de l'opérateur et par l'opérateur et puis. f) Expression conditionnelle à valeur booléenne Une expression conditionnelle à valeur booléenne peut toujours être ré-écrite sous forme d'une expression booléenne à l'aide de l'opérateur et puis. Par exemple, l'expression selon Cl : Bl C2 : B2 C3 : B3 peut s'écrire (Cl et puis Bl) ou (C2 et puis B2) ou (C3 et puis B3) Remarque : Si de plus on veut exprimer un ordre dans l'évaluation des termes de l'expression, on remplacera l'opérateur ou par l'opérateur ou alors. Une telle expression peut être alors sensiblement simplifiée dès que l'un des Bi dénote une constante. Par exemple, l'expression conditionnelle selon Cl : vrai C2 : faux C3 : B3 se réduit à l'expression Cl ou (C3 et puis B3). 1.4 Fonctions dont le codomaine est un type composé Comme nous l'avons vu, une fonction peut avoir une ou plusieurs données. De la même manière la valeur associée à une fonction peut être un n-uplet. Nous illustrons ceci à l'aide d'un exemple simple et nous voyons les conséquences du point de vue de l'expression. Exemple El.5 : Représentation d'une durée Décrire une fonction qui à une durée exprimée sous forme d'un nombre de
/ i : Fonctions dont le codomaine... 17 secondes inférieur à un million, associe l'équivalent en nombre de jours, d'heures, de minutes et de secondes. Exemple : donnée 309639, résultat <3, Il 0, 39>. a) Spécification d'une fonction à valeur n-uplet Une lecture attentive de l'énoncé, notamment à l'aide d'exemples pertinents, met en évidence ses implicites : le résultat est toujours un quadruplet sous une forme canonique. Par exemple, à la donnée 123 correspond le résultat 0, 0 2, 3 et non 0, 0, 1, 63. On introduit une fonction, nommée La Durée. Pour la typer, on décrit la donnée, les résultats et la relation qui les lie, notamment pour préciser la forme canonique attendue : LaDurée : un entier sur [0.. .999999] —► < un entier > 0, un entier sur [0.. .23], deux entiers sur [0.. .59] > { Posons <a, b, c, d> = LaDurée (X). Alors a, b, c, d, sont respectivement le nombre de jours, d'heures, de minutes et de secondes correspondant à X, et on a : X=86400*a -h 3600*b -h 60*c -h d } Remarque : Le résultat est un quadruplet, valeur composée de quatre éléments. On parle de fonction à valeur n-uplet , et par abus de langage de fonction à plusieurs résultats. Pour décrire un n-uplet de valeurs, on les énumère en les séparant par des virgules. Lorsque ces valeurs peuvent être de types différents, on entoure le n-uplet des chevrons "<" et ">". Pour particulariser la situation où les valeurs sont nécessairement de même type, on peut utiliser les crochets "[" et "]" en place des chevrons. De même pour décrire le type d'un n-uplet, on énumère les types de ses composants entre virgules à l'intérieur de chevrons. Toutefois, on peut éventuellement omettre les chevrons apparaissant dans la spécification du codomaine dans la mesure où il n'y pas ambiguïté. b) Réalisation d'une fonction à valeur n-uplet Pour exploiter la relation définissant le résultat, on introduit une fonction à deux résultats, nommée QR : QR : un entier > 0, un entier > 0 —► deux entiers > 0 { soit <q, r> = QR (N, D), q est le quotient et r le reste de la division de N par D : N=q*D -h r et 0 < r et r<D } QR (N, D) : <N quotient D, N reste D> { où quotient et reste sont des fonctions primitives correspondant à la division entière } LaDurée (X) : soit <j, rj> = QR (X, 86400) dans soit <h, rh> = QR (rj, 3600) dans soit <m, s> = QR (rh, 60) dans <j, h, m, s> Remarque : On voit que la réalisation d'une fonction à valeur n-uplet est décrite sous forme d'un n-uplet d'expressions. Il faut que l'ordre des
18 1 : Valeurs, expressions, fonctions valeurs dans ce n-uplet soit cohérent par rapport à l'ordre apparaissant dans la spécification du codomaine de la fonction. Par ailleurs, l'exemple de l'utilisation de la fonction QR nous montre qu'il est nécessaire de nommer les composants du résultat d'une fonction à valeur n-uplet, pour pouvoir exploiter leur valeur. 1.5 Exercices El.6 (Cf. [AbS89] p 51) En utilisant des fonctions intermédiaires ou des noms locaux décrire autrement l'expression suivante : x(\ -\- xy)2 -\- y(\ — y) + (l + *y)(l-y) El.7 : Représentation d'un entier On s'intéresse à la valeur d'un nombre entier caractérisé par les quatre chiffres binaires de sa représentation en base deux. Par exemple, l'entier nommé treize en français est représenté par la chaîne "1101" en base deux et par la chaîne "13" en base 10. a) les quatre chiffres binaires étant donnés dans l'ordre par quatre entiers de valeur 0 ou 1 et nommés respectivement a, b, c et d, donner l'expression de la valeur de l'entier correspondant. Par exemple, si l'on associe à a, b, c et d respectivement les valeurs 1, 1, 0 et 1, le résultat est la valeur 13. b) reprendre la question en supposant que les quatre chiffres binaires sont donnes par l'intermédiaire d'un entier qui s'écrit "abcd" en base dix. Par exemple, au lieu de donner comme en a) les entiers 1, 1, 0 et 1, on donne l'entier 1101. El.8 : Signe du produit Etant donnés deux nombres, on veut fournir l'un des deux messages suivants : "/e produit des deux nombres est positif ou nuP ou "/e produit des deux nombres est négatif. Décrire la fonction correspondante (le produit ne doit pas être calculé). El.9 : Une date est-elle correcte ? On considère une date représentée par un couple d'entiers : un numéro de jour dans le mois et un numéro de mois dans l'année. Décrire un prédicat indiquant si un couple d'entiers correspond à une date. C'est par exemple le cas pour <28, 1>. Par contre <31, 4> ne correspond pas à une date. On suppose que l'année considérée n'est pas bissextile. El. 10 : Représentation d'une durée On reprend l'exemple El.5 p. 17. a) donner une autre forme de la réalisation de la fonction La Durée, sans utiliser la fonction QR et sans noms intermédiaires. b) donner une nouvelle réalisation de la fonction, en utilisant la relation suivante entre la donnée X et le n-uplet résultat <j, h, m, s> : X = ((24*j+h)*60+m)*60+s El. 11 : Heure à la seconde suivante Décrire une fonction qui étant donnée une heure sous forme d'un triplet <heure, minute, seconde> lui associe l'heure à la seconde suivante. El.12 : Somme de deux durées On considère des durées sous forme de triplets <nombre d'heures, nombre de minutes, nombre de secondes>. Etudier une fonction exprimant la somme de
/ 6 '• P°ur expérimenter : découvrir Scheme 19 deux durées. Développer une solution indirecte passant par un calcul sur des nombres de secondes, puis une solution directe s'appuyant sur la somme des composants et un mécanisme de retenue. 1.6 Pour expérimenter : découvrir Scheme Nous proposons d'expérimenter la programmation en style fonctionnel avec le langage Scheme. Nous utilisons ici une version pour matériel Atari due à Aubrey Jaffer, du laboratoire d'Intelligence Artificielle du Massachusetts Insti- tute oi Technology, et compatible avec la description donnée dans [Scheme91]. Scheme est un dialecte du langage Lisp défini par G.L. Steele et G.J. Suss- mann ; on peut se référer au rapport cité ci-dessus et à [AbS89]. Remarque : Le langage Lisp a été développé en 1960 par Mac Carthy (peu de temps après Fortran) et a beaucoup évolué, pour répondre aux besoins de ses utilisateurs et à des considérations de mise en œuvre. Lisp et Scheme sont des langages dits fonctionnels (ou applicatifs) ; il en existe beaucoup d'autres : ML, MIRANDA, Haskell, etc (Cf. par exemple [FiH88], chapitre 4). Dans ce paragraphe, nous guidons le lecteur dans la découverte du langage et de l'environnement de programmation. Les activités proposées consistent en : - L'étude des constructions de base du langage : on fournit des phrases du langage et on observe la réaction du système. On complète ainsi la compréhension des constructions du langage, et on en assimile la syntaxe. - La traduction en Scheme de fonctions préalablement décrites dans la notation fonctionnelle. Nous distinguons ainsi l'analyse du problème, rédigée dans la notation fonctionnelle, de la mise en œuvre de la solution dans un environnement de programmation particulier. Le lecteur pourra ainsi expérimenter d'autres langages fonctionnels sur la base d'activités analogues. Remarque : Les activités proposées sont numérotées EPn (pour Expérimentation Pratique). Lorsque nous nous référons à des exemples ou à des exercices proposés par ailleurs dans le texte nous accompagnons le numéro de l'exercice de référence du suffixe "suite". Interaction avec l'interprète Scheme L'interprète du langage attend des commandes en affichant le symbole d'invite (en anglais prompt) >. L'usager lui fournit une commande terminée par un retour a la ligne. Deux réactions sont alors possibles : - Tout se passe bien : l'interprète répond en affichant une valeur puis attend de nouveau une commande en affichant le symbole d'invite ; - L'interprète ne peut pas fournir de valeur ; il répond par un message d'erreur, suivi du symbole d'invite.
20 1 : Valeurs, expressions, fonctions A titre d'exemple, observer les réponses du système aux demandes suivantes : - La valeur de l'entier 24 : >24 - La valeur associée au nom x : >x a) Familiarisation avec la syntaxe du langage Voici la traduction en Scheme de la réalisation de la fonction maxdeux (jjl.l.c) : (define (maxdeux a b) (/ (+ a b (abs (- a b))) 2) ) Un contexte d'utilisation de cette fonction pour les entiers 5 et 7, s'écrit : (maxdeux 5 7). Cet exemple nous permet d'observer les éléments suivants du langage Scheme : - Les expressions sont préfixées, c'est-à-dire que l'on fait apparaître les opérateurs (ou noms de fonctions) avant les opérandes. Par exemple, a-b est écrit (- a b), abs (a-b) est écrit (abs (- a b)). - Certains opérateurs ont un nombre variable d'arguments : ceci est illustré par l'écriture de a + b + abs (a-b) dans la définition de la fonction maxdeux ci-dessus. - Un appel de fonction est noté (nomdefonction pei pe2 ...) où pet- désigne un paramètre effectif. - Une définition de fonction est notée (define (nomdefonction pfi pf2 ...) expression) où pft- désigne un paramètre formel. - Lors de la définition des fonctions, on ne précise pas les types des objets manipulés. Toutefois le langage possède la notion de type (des types sont associés aux valeurs et non aux noms). Essayer par exemple d'ajouter un entier et un caractère. D'une façon générale, toute expression Scheme est une séquence d'éléments séparés par des espaces : (nom_de_fonctionjou_d_operateur sequencejcLarguments) où un argument peut être lui-même une séquence parenthésée. Pour la définition de fonction, on retrouve le même type de syntaxe : (define (nom_de_fonction séquencejie_parametres_formels) expression) On peut aussi définir un nom : (def ine nom expression). Lors de l'utilisation d'un tel nom, on ne le met pas entre parenthèses. Remarque : La syntaxe est ainsi extrêmement simple ; par ailleurs, la lisibilité est grandement améliorée si l'on indente proprement les sous-expressions (Cf. les exemples donnés ci-dessous). EP1.1 - Observer les réponses du système aux demandes suivantes : (-5 2), (- 2 5), (* (- 4 1) 5), (abs 3), (abs -3), (/ 6 2), (/ 5 2). - Saisir la définition ci-dessus de la fonction maxdeux, puis essayer un appel de la fonction (attention à fournir le bon nombre de parenthèses). - Traduire la définition de la fonction mindeux (jjl.l.c).
y. 6 : Pour expérimenter : découvrir Scheme 21 EPI.2 Traduire en Scheme les fonctions suivantes : - El.7.a suite : construction d'un entier dont la forme binaire est donnée par quatre entiers 0 ou 1 (§1.5) - El.l suite : construction de la moyenne olympique de quatre notes (§1.1). b) Expressions booléennes, expressions conditionnelles Voici deux autres écritures de la fonction maxdeux : (define (maxdeux a b) (cond ((>= a b) a) ((< a b) b) ) ) (define (maxdeux a b) (if (>= a b) a b) ) Les opérateurs cond et if permettent de traduire respectivement les formes selon et si ... alors ... sinon de la notation fonctionnelle. La syntaxe est la suivante : (cond (expression.boleenne expression) (expression.boleenne expression) (expression.boleenne expression) (expression.boleenne expression) ) (if expression.boleenne expression expression) Remarques : • Contrairement à la forme selon, l'ordre dans lequel les cas sont exprimés est pertinent ; ils sont examinés séquentiellement (ordre de lecture du texte) • Comme dans la forme selon, on peut exprimer l'un des cas comme étant le complément de tous les autres par l'utilisation du mot clé else : (cond (exprèssion.boleenne expression) (expression.boleenne expression) (expression.boleenne expression) (else expression) ) EP1.3 - Quelle est la valeur des expressions suivantes ? (< 4 2), (< 2 4), (< 2 2), (>= 4 2), (>= 4 4), (cond ((>= 5 2) 5) ((< 5 2) 2)). En déduire la notation en Scheme des constantes de type booléen. - Pour décrire des expressions booléennes, on dispose des opérateurs and, or et not. Les opérateurs and et or ont respectivement la sémantique du et puis et du ou alors (Cf. §1.3.e).
22 1 : Valeurs, expressions, fonctions Quelle est la valeur des expressions suivantes ? - (not #t) - (not #f) - (and (< 3 2) (=3 2)) - (and #t #f) - (or #t #f) - (if (> 5 7 ) 2 3) EPI.4 Traduire en Scheme les fonctions suivantes : - El.3 suite : les trois premières solutions de la fonction maxtrois (§1.3.a) qui détermine le maximum de trois valeurs entières données. Comparer 1 utilisation des opérateurs cond et if. - El.8 suite : une fonction qui détermine le signe du produit de deux nombres, sans le calculer. Remarque : En Scheme, les chaînes sont notées entre guillemets. Par exemple, demander la valeur de "ceci est une chaine de caractères". - El.9 suite : une fonction qui vérifie que deux valeurs données correspondent effectivement à une date ; les valeurs fournies doivent être des entiers et ces entiers doivent correspondre à une date correcte. Remarque : Pour vérifier si un objet est un entier, on dispose du prédicat integer? : essayer (integer? 3),(integer? "test"). EPI.5 Donner en Scheme la traduction de la fonction LeQuantième définie dans l'exemple El.4 (§1.3.d). c) Désignation d'expressions intermédiaires L'expression let permet de traduire l'expression soit. ..dans (§1.2.b) comme dans la traduction suivante d'une des formes de la fonction maxtrois (§1.3.a.3) : (define (maxtrois abc) (let ( (m (if (> a b) a b)) ) (if (> m c ) m c ) ) ) EPI.6 : Désignation simple - Demander la valeur des expressions suivantes : - (let ( (x 2) ) (+ x 5) ) - (let ( (x 2) ) (let ( (y 3) ) (+ x y))) - (let ( (y 3) ) (+ x y)) - (let ( (m (if (> 5 3) 5 3)) ) (+ m 1) ) - El.6 suite : écrire une fonction de x et de y qui donne la valeur de l'expression suivante : x(l + xy)2 + y(l — y) + (1 + xy)(l — y) de manière à éviter les redondances de calculs qu'elle comporte.
1.6 : Pour expérimenter : découvrir Scheme 23 - E1.7.b suite : construction de l'entier dont la représentation binaire est donnée par un entier dont la représentation décimale comporte quatre chiffres 0 ou 1. Par exemple, si la donnée est l'entier 1101, le résultat est l'entier 13. Remarque : On utilisera les fonctions prédéfinies quotient et remainder fournissant respectivement le quotient et le reste de la division entière. Essayer par exemple : (quotient 7 2), (remainder 7 2). EPI.7 : Désignations multiples La construction let peut être utilisée pour nommer plusieurs valeurs décrites par des expressions : (let ( (noml expressionl) (nom2 expression2) ) expression utilisant noml et nom2 ) L'ordre entre les associations nom-valeur n'est pas pertinent. On peut donc aussi écrire : (let ( (nom2 expression2) (noml expressionl) ) expression utilisant noml et nom2 ) Dans la même situation que ci-dessus, si une valeur dépend de l'autre, par exemple, si l'on utilise noml dans expression2, on utilise deux expressions let emboîtées : (let ( (noml expressionl) ) (let ( (nom2 expression2) ) expression - Essayer (let ( (x 3) ) (let ( (y (+ x 5)) ) (+ x y) )). - Essayer (let ( (x 3) (y (+ x 5)) ) (+ x y) ). - Essayer (define a 5) puis (let ( (a 3) (b (+ a 5)) ) (+ a b) ). - On peut aussi utiliser une forme particulière notée let* : (let* ( (noml expressionl) (nom2 expression2) ) expression La construction let* est fournie pour simplifier l'écriture ; elle a exactement le même sens que lorsque l'on utilise des let emboîtés. Noter que dans le cas d'utilisation du let*, l'ordre dans lequel sont écrits les couples (nom valeur) est significatif. L'expression ci-dessus s'écrit aussi : (let* ( (x 3) (y (+ x 5)) ) (+ x y) ) d) Représentation de n-uplets Les n-uplets sont représentés en Scheme par des listes. La liste est une structure plus générale qui sera étudiée aux chapitres 3 et 4. Une liste peut être construite avec la fonction list. Essayer par exemple, (list 1 2 3). Pour accéder à un élément particulier d'une liste, le système fournit la fonction list-ref. Essayer, par exemple, (list-ref (list 3 4 5) 0) et (list-ref (list 3 4 5 6) 2).
24 1 : Valeurs, expressions, fonctions Une fonction à valeur n-uplet (§1.4) peut être écrite en Scheme comme une fonction qui délivre une liste. Par exemple, la traduction en Scheme de la fonction QR (§1.4.b) est la suivante : (define (qR n d) (list (quotient n d) (remainder n d)) Un appel de la fonction : (qR 7 5) délivre une liste à deux éléments auxquels on peut accéder en utilisant la fonction prédéfinie list-réf. EPI.8 Donner la définition de la fonction qR, puis essayer (qR 7 5), (list-ref (qR 7 5) 0), (list-ref (qR 7 5) 1). EPI.9 Traduire en Scheme les fonctions suivantes : - El. 11 suite : heure à la seconde suivante - El. 12 suite : somme de deux durées (deux solutions) - El. 10 suite : fonction LaDuree EPI. 10 : Permutation ordonnée de trois nombres Décrire une fonction nommée POtrois, qui étant donnés 3 nombres, détermine une liste ordonnée de ces trois nombres, sans redondance. Exemples : données résultats 3,1,6 1,3,6 5,1,1 1,5 2, 2, 2 2 a) résoudre le problème, en supposant que l'on dispose d'une fonction POtroisdif qui fournit la solution pour trois entiers distincts deux à deux et d'une fonction POdeuxdif qui à deux nombres différents associe leur permutation ordonnée. On examinera plus particulièrement la manière de spécifier le résultat de la fonction POtrois. b) réaliser les fonctions POdeuxdif et POtroisdif.
2 Types construits L'analyse d'un problème procède par un examen simultané des informations et des traitements qui leur sont appliqués. Dans le chapitre 1, nous avons vu comment exprimer des traitements sous forme de fonctions définies en termes de types de base de la notation. De manière plus générale, l'analyse d'un problème peut nécessiter de décrire d'autres types. Nous parlons alors de types construits. Ils permettent de décrire les informations au niveau d'abstraction souhaité, de manière descendante par l'introduction de nouveaux types, ou de manière ascendante en réutilisant des types déjà définis. On retrouve l'idée de spécification, intermédiaire entre utilisation et réalisation. Nous montrons comment utiliser l'expression fonctionnelle pour spécifier un type construit (§2.1). Par ailleurs, la notation fournit des constructeurs de types permettant de décrire des types construits : nous présentons ici le produit de type et les tableaux (§2.2). Chacun des chapitres 4 à 7 introduit de nouveaux constructeurs (séquences, arbres, fonctions, ensembles). 2.1 Spécification d'un type a) Type simple et type construit De manière générale, un type est un ensemble de valeurs et une famille d'opérations définies sur cet ensemble. La donnée d'un type fixe le niveau d'abstraction auquel on se place : il fournit les opérations que l'on pourra appliquer aux valeurs de ce type, tout en faisant abstraction de sa représentation en termes d'autres types ou de sa matérialisation en machine. Par exemple, on peut considérer des entiers, des mots ou des dates ... et les opérations associées en faisant abstraction du fait qu'un entier est matérialisé sous forme d'une suite de bits, ou qu'un mot est décrit par une suite de caractères, chaque caractère étant codé sur huit bits, ou qu'une date est par exemple décrite par un entier correspondant au nombre de jours écoulés depuis une date de référence ...
26 2 : Types construits Un type peut être simple c'est-à-dire atomique au niveau de représentation fixé par la notation employée, par exemple, un entier, un caractère, ... ou construit, c'est-à-dire défini en termes des types de base, directement ou à partir de types construits plus élémentaires. Par exemple, une durée est décrite par un nombre entier de secondes ; un relevé de notes est décrit en termes de notes, chaque note étant un réel d'un intervalle précis ; un dictionnaire est décrit en termes de mots, chaque mot étant décrit en termes de caractères, ... Remarque : Cette distinction est relative au niveau de description auquel on se place. Par exemple, une valeur de type booléen est atomique au niveau de la notation fonctionnelle. Dans le contexte d'un langage ne fournissant pas le type booléen, on peut imaginer qu'il soit représenté à l'aide d'entiers en convenant que 1 et 0 représentent respectivement les constantes vrai et faux. A et B étant deux valeurs booléennes, l'opération A et B peut alors être réalisée par l'expression A*B (Cf. E2.4, §2.3). b) Variété des représentations En général, une valeur peut être décrite de diverses manières : ceci est vrai dans le monde de l'utilisateur qui fournit les données et exploite les résultats d'un logiciel, nous parlons de description externe, aussi bien que dans le contexte d'exécution du logiciel, nous parlons de représentation interne. Le choix des descriptions externes, en entrée ou en sortie, dépend des conventions que veut pratiquer l'utilisateur. Celui des représentations internes est lié aux traitements appliqués aux informations et aux qualités attendues de la solution, par exemple, la lisibilité, la modifiabilité, les performances, ... Observons par exemple le concept de date. Dans la vie courante une date est souvent décrite par un triplet, dans un ordre qui dépend de la langue, comme par exemple 21/3/89 (en français) ou 3/21/89 (en anglais). Mais il existe d'autres formes de description, liées à des contextes particuliers : par exemple un ticket de péage mentionne l'année et le nombre de jours écoulés depuis le début de l'année et il est courant dans les entreprises de préciser une date dans l'année par un numéro de semaine et le jour dans la semaine ... La représentation interne d'une date doit permettre de décrire toutes les opérations souhaitées, par exemple la comparaison dans l'ordre chronologique, le nombre de jours écoulés entre deux dates, le nombre de jours écoulés depuis le premier de l'an, ... On peut par exemple utiliser un triplet de valeurs de type entier, ou au contraire uniquement une valeur de type entier correspondant au quantième par rapport à une date de référence ... Le choix dépendra de la fréquence d'utilisation de telle ou telle primitive, ou d'un argument de simplicité, ... Cette variété des représentations pose le problème du caractère modifiable des logiciels que l'on écrit : dans quelle mesure, une évolution souhaitée d'un logiciel (amélioration d'une performance, extension des fonctions attendues, changement des descriptions externes ... ) se traduit-elle par une profonde modification du logiciel ? Comment localiser la partie du logiciel qu'il faut modifier en cas d évolution ? On parle de "modifiabilité" et d'"extensibilité" du logiciel. c) Démarche d'analyse La démarche d'analyse que nous introduisons ici vise à faciliter la réduction progressive de la complexité du problème. Elle consiste à structurer le
2.1 : Spécification d'un type 27 répertoire de fonctions disponibles autour des types pertinents, et à rendre indépendantes l'utilisation et la représentation des types et des fonctions. On distingue trois niveaux d'analyse d'un type : l'étude du contexte de son utilisation, sa spécification et sa réalisation. Au niveau du contexte d'utilisation, on identifie les types et les fonctions associées nécessaires à la résolution du problème. Pour spécifier un type, on identifie des fonctions élémentaires appelées constructeurs de valeurs de ce type : on choisit un mode de construction des valeurs du type à partir des valeurs de types plus élémentaires ; les constructeurs sont les fonctions correspondantes. Symétriquement, la spécification du type comporte des fonctions élémentaires appelées sélecteurs d'une valeur élémentaire ayant participé à la construction d une valeur de type. Enfin, au niveau de la réalisation, on choisit une représentation des types et on exprime en conséquence les constructeurs et les sélecteurs du niveau précédent. Ce sont les types simples et les constructeurs de types de la notation employée qui fixent le niveau terminal auquel on se place. Exemple E2.1 : Spécification d'un type date Pour caractériser la notion de date, on identifie les fonctions qui les manipulent, par exemple, la construction d'une date à partir d'un triplet correspondant au jour, au mois et à l'année, la sélection d'informations élémentaires associées à une date comme par exemple le jour dans le mois, le quantième dans l'année, ou des opérations telles que la comparaison de dates, la différence entre deux dates, ... Nous nous limitons ici à la spécification de quelques fonctions pour illustrer la démarche et l'abstraction qu'elle met en jeu. Nous poursuivons l'étude dans le problème dirigé proposé au paragraphe 2.4. On introduit le type date et les types NJour, Nmois et année caractérisant la forme externe habituelle des dates. NJour : le type entier [1.. .31] { numérotation des jours dans le mois } Nmois : le type entier [1.. .12] { numérotation des mois dans Vannée } année : le type entier > 0 { numérotation des années dans le calendrier } date : un type { notion abstraite de date } { constructeur de valeurs de type date à partir d'un triplet } LaDateJMA : un NJour, un Nmois, une année —► une date { LaDateJMA (j, m, a) est la date correspondant au jème jour du même mois de l'année a } { selon le contexte, on peut introduire d'autres constructeurs de date, par exemple à partir d'un couple de valeurs correspondant à l'année et au quantième dans l'année } { sélecteurs de valeurs composant une date } LeJour : une date —► un NJour { LeJour (LaDateJMA (j, m, a) = j } LeMois : une date —► un Nmois { LeMois (LaDateJMA (j, m, a) = m } Lannée : une date —► une année { Lannée (LaDateJMA (j, m, a) = a} { on peut compléter par d'autres sélecteurs tels que le quantième dans l'année, • ••}
28 2 : Types construits { autres fonctions } EstAvant : deux dates —► un booléen { EstAvant (Dl, D2) est vrai <=>- Dl est strictement avant D2 } NbJ1900 : une date —► un entier { nombre de jours écoulés depuis le 1/1/1900 } { on peut compléter par d'autres fonctions telles que l'édition d'une date dans une forme ou une autre, la différence entre deux dates, ... } Remarquons que la spécification des constructeurs et sélecteurs associés à une forme de description de date permet de réaliser les autres fonctions. Par exemple, on peut proposer la réalisation suivante de la fonction EstAvant : EstAvant (Dl, D2) : soit jl = LeJour (Dl), ml = LeMois (Dl), al = Lannée (Dl), j2 = LeJour (D2), m2 = LeMois (D2), a2 = Lannée (D2) dans si al ^ a2 alors (al < a2) sinon si ml ^ m2 alors (ml < m2) sinon (jl < j2) Mais on peut aussi la réaliser en exploitant la fonction NbJ1900 : EstAvant (Dl, D2) : NbJ1900 (Dl) < NbJ1900 (D2) Le choix entre diverses possibilités de réalisation d'une fonction dépendra de critères variés tels que la simplicité, la performance, ... Mais ceci restera caché au niveau d'utilisation du type considéré. 2.2 Réalisation d'un type Réaliser un type construit consiste à décrire sa représentation en termes de types définis par ailleurs et à en déduire la réalisation des fonctions associées. Les langages de programmation fournissent pour cela des types simples et des constructeurs de types . Le plus souvent ce sont le produit de types (on parle parfois d'agrégation), les tableaux, les fichiers ... A chaque constructeur sont associées des conventions de notation permettant d'exprimer l'accès à une valeur élémentaire composant la valeur structurée considérée, ou la construction d'une valeur structurée à partir de valeurs plus élémentaires. Remarque : Les types simples et les constructeurs de types varient d'un langage de programmation à Pautre. Par exemple, dans certaines versions de Lisp, on ne dispose que du constructeur de séquences ; en Basic on ne dispose pas du type booléen, et on ne dispose que du constructeur de tableaux ; en Pascal, on ne dispose pas du constructeur de séquences ou du constructeur d'arbres ... a) Types simples Un type simple est spécifié dans une notation par : - Son nom, qui sera utilisé pour spécifier des fonctions ou pour décrire d'autres types.
2.2 : Réalisation d'un type 29 - Son domaine de valeurs. Il peut exister une différence entre un domaine théorique et sa restriction dans le contexte d'un environnement particulier de matérialisation. C'est par exemple, le cas du type entier. - Les conventions de dénotation des constantes de ce type, que l'on peut assimiler aux noms propres de chaque valeur du domaine. C est ainsi que les valeurs booléennes sont notées par les mots vrai et faux. Les valeurs numériques, de type entier ou réel, sont notées à l'aide de suites de chiffres selon les conventions habituelles : représentation décimale, par exemple 314 ou 3.14, ou flottante, par exemple 0.314E1. Les caractères sont distingués des noms ou des nombres en les marquant par des symboles spéciaux, par exemple des guillemets. - Les noms, profils et significations des opérations qui permettent de manipuler les valeurs de ce type. Ces opérations sont spécifiées indépendamment d'une représentation interne du type. Remarques : • Le plus souvent, on dispose des quatre types de base entier, réel, caractère et booléen. Le lecteur peut les examiner et notamment observer la différence entre une valeur, concept abstrait, et les conventions qui permettent de la noter selon le type. Par exemple, la phrase 101 dénote une valeur de type entier alors que la phrase "101" dénote une chaîne de caractères formée de chiffres "0" et "1" que l'on peut interpréter par exemple, comme la représentation binaire de l'entier noté 5 ou comme la représentation décimale de l'entier noté 101 (Cf. exercices El.7, §1.5 et E2.4, §2.3). • Certaines opérations sont définies en faisant abstraction du type des arguments auxquels elles sont appliquées : on parle d'opérations génériques . C'est par exemple le cas des relations d'ordre et d'équivalence qui sont naturellement définies sur les types, par exemple, les opérations booléennes d'égalité et de différence, notées par les symboles = et ^, ou les opérations booléennes de comparaison notées par les symboles <, <, >, >. b) Spécialisation d'un type La manière la plus simple de réaliser un type est de le décrire directement en termes d'un autre type. Par exemple, si l'on veut définir la notion de durée, en faisant abstraction d'une représentation particulière, on écrira : durée : un type { notion abstraite de durée } ce qui permettra de spécifier des opérations attachées à cette notion, par exemple une opération d'addition : PlusD : deux durées —► une durée { somme de deux durées } Pour réaliser le type, on peut décider de représenter une durée par un entier correspondant à un nombre de secondes. On écrira alors : durée : le type entier { nombre de secondes } Ceci permettra d'hériter des conventions propres au type entier pour noter des valeurs de type durée et d'utiliser les opérations sur les entiers pour réaliser les opérations définies sur les durées.
30 2 : Types construits par exemple : PlusD (Dl, D2) : Dl + D2 On peut aussi définir un type comme étant la restriction d'un autre type, par exemple un intervalle d'entiers, un sous-ensemble de caractères. On hérite alors des conventions de notation des constantes, et des opérateurs du type de référence. On écrira par exemple : naturel : le type entier > 0 ; Nmois : le type entier sur [1.. .12], Température : le type entier sur [-40.. .60] chifFrebinaire : le type caractère sur ["0", "1"] ; bit : le type entier sur [0,1] c) Produit de typesx Le produit de types permet de représenter un type comme un agrégat de types plus simples : on parle des composants, attributs ou champs du type. Le type des composants et leur nombre est fixé dans la description du type produit. Les composants peuvent être de types différents. Pour définir un produit de types, on décrit un n-uplet de types entouré de chevrons (< et >), les types étant séparés par des virgules. Le domaine de valeurs d'un produit de types est le produit cartésien des domaines de valeurs des types composants. Par exemple, une date est un triplet d'entiers, un segment est un couple de points, un point est un couple de coordonnées. Pour dénoter une constante d'un produit de types, on décrit entre chevrons un n-uplet de constantes séparées par des virgules, et on utilise les notations de constantes des types composants. L'ordre de cette énumération correspond à l'ordre dans lequel les composants sont décrits dans la définition du type. Par exemple, si l'on représente des dates par des triplets, la phrase <3,10,1991> décrit une constante de type date. De même, si l'on représente un segment par ses deux points extrêmes et un point par ses deux coordonnées, la phrase < <3.5, 0.1>, <2, 1> > décrit une constante de type Segment. Dans cette expression, <3.5, 0.1> et <2, 1> sont des constantes de type Point. De même, la construction d'une valeur d'un produit de type est décrite par l'énumération entre chevrons des expressions décrivant les valeurs des composants. La sélection d'un composant d'un produit de types est aussi appelée projection selon ce composant. Nous précisons les notations dans les exemples ci-dessous. E2.1 suite : Réalisation du type date par un produit de type On réalise le type date à l'aide d'un produit de types : date : le type <qj : un NJour, qm : un Nmois, a : une année > Les noms qj, qm et a introduits dans cette phrase ont pour objet d'exprimer la sélection des valeurs composant une valeur de type date : D désignant une date, qj de D, qm de D et a de D désignent respectivement le quantième du jour dans le mois, le quantième du mois dans l'année et l'année de la date D. Par exemple, qj de <3,10,1991> = 3, qm de <3,10,1991> = 10, a de <3,10,1991> = 1991. On peut maintenant réaliser les constructeurs et sélecteurs du type date :
2,2 •' Réalisation d'un type 31 LaDateJMA (j, m, a) : <j, m, a> LeJour (D) : qj de D LeMois (D) : qm de D Lannée (D) : a de D Remarque : On peut penser à réaliser directement la fonction EstAvant en tenant compte de cette représentation : EstAvant (Dl, D2) : si a de Dl ^ a de D2 alors (a de Dl < a de D2) sinon si qm de Dl ^ qm de D2 alors (qm de Dl < qm de D2) sinon (qj de Dl < qj de D2) Mais, si on procède ainsi, un changement de représentation du type nécessite de changer la réalisation de la fonction. variante à*écriture Dans la description du type date, on peut omettre les noms associés aux types composants. On écrit alors : date : le type <un NJour, un NMois, une année > Pour sélectionner les composants d'une date, on doit alors utiliser des noms locaux. On étend à cet effet la notation soit (§1.2.b) : D étant une date, l'expression soit <j, m, a> = D dans ... associe aux noms j, m et a chacun des composants de D. Par exemple : LeMois (D) : soit <j, m, a>=D dans m EstAvant (Dl, D2) : soit <jl, ml, al> = Dl, <j2, m2, a2> = D2 dans si al / a2 alors (al < a2) sinon si ml ^ m2 alors (ml < m2) sinon (jl < j2) Exemple E2.2 : Etude d'un type segment { spécification descendante de types } Segment : un type LeSegment : deux Points —► un Segment { constructeur } LesExtrémités : un Segment —► deux Points { sélecteur } Point, Coordonnée : des types LePoint : deux Coordonnées —► un Point { constructeur } LAbscisse : un Point —► une Coordonnée { sélecteur } LOrdonnée : un Point —► une Coordonnée { sélecteur } { exemple de fonction } Milieu : un Segment —► un Point { point milieu du segment donné } Milieu (S) : soit <Ei, E2> = LesExtrémités (S) dans soit al = LAbscisse (Ei), ol = LOrdonnée (Ei) a2 = LAbscisse (E2), o2 = LOrdonnée (E2) dans LePoint ((al + a2)/2, (ol + o2)/2)
32 2 : Types construits { réalisation ascendante des types } M : un réel { lié à à la dimension physique de Vécran } Coordonnée : le type réel sur [-M... + M] Point : le type < abs, ord : des Coordonnées > { abscisse et ordonnée du point } LePoint (x, y) : <x, y> LAbscisse (P) : abs de P LOrdonnée (P) : ord de P Segment : le type <pl, p2 : des points> { points extrémités du segment

References: art. 40
 art. 425
 §2
 §3
 §10
 §1
 §2
 §1
 §2