Programmation_fonctionnelle cours.pdf

Support du cours Programmation fonctionnelle par Gilles Bernard version du 9 mars 2021 Licence d’Informatique L I Institut d’Enseignement à Distance Université Par...

Support du cours Programmation fonctionnelle par Gilles Bernard version du 9 mars 2021 Licence d’Informatique L I Institut d’Enseignement à Distance Université Paris 8 C E Copyleft : Creative Commons BY-NC-SA N C E Sommaire Introduction v I Introduction aux structures de données 1 II Dialogue, processus et structures de contrôle 35 III Introduction à Lisp 45 IV Créer des fonctions 79 V Maîtriser son environnement 121 VI Se perfectionner 173 Conclusion 201 Introduction 1. Avant-propos 1.1 Les métiers de l’informatique L’informatique et ses applications tendent aujourd’hui à prendre autant voire plus de place, dans le domaine des choses de l’esprit, que le microscope, la voiture et l’horloge en occupent dans le domaine de la physique. L’informatique, comme discipline, avec ses branches de pointe (intelligence artificielle, systèmes dyna- miques, modélisation et simulation, science des données), est en voie d’apporter aux sciences humaines et sociales des instruments d’expérimentation. Le métier d’informaticien est un métier dont la définition fluctue en fonction des besoins et des engouements des commanditaires. En réalité, il recouvre plusieurs types de tâches difficilement assumables par une seule personne ; par exemple : 1. la création et la maintenance d’applications, 2. la création et la maintenance de systèmes (ouverts), 3. l’utilisation critique d’applications. Une application est un programme qui sert à une tâche particulière, où les pos- sibilités que l’utilisateur a de redéfinir son environnement sont très limitées ; un système ouvert est en revanche un programme qui permet de définir des applica- tions de types divers, avec le moins de limitations possibles. La catégorie 3 mérite une attention particulière : elle ne possède pas les com- pétences qu’on associe traditionnellement à la programmation ; alors que dans la trinité concepteur (qui conçoit le programme) – programmeur (qui le réalise) – uti- lisateur, les deux premières fonctions sont souvent réunies (en un individu ou une équipe), et l’utilisateur isolé face au résultat de leur travail, ici, on a affaire à des concepteurs - utilisateurs, capables de maîtriser une application, de la programmer ou de diriger des programmeurs pour en réaliser des parties. Naturellement, ceci est vrai si les systèmes ouverts sont conçus de la manière la plus naturelle, ergonomique et conviviale possible. L’importance de la catégorie vi Introduction 3 n’a fait que croître ces dernières années, et les informaticiens de cette catégorie doivent élaborer leurs systèmes de concert avec les utilisateurs (développements en circuits courts, par exemple), en tenant compte de la structure de la pensée et de la communication humaine. D’où la nécessité, pour eux, d’une compétence en sciences humaines et sociales. Cette catégorie a même aujourd’hui donné naissance à un nouvel ensemble de métiers reconnus (pas forcément faciles à distinguer) : les spécialistes des données (data scientist, data ingénieur, data analyst, data ste- ward). La rapidité du développement de l’informatique rend nécessaire un renouvel- lement fréquent, non seulement de l’enseignement des techniques, mais aussi de l’évaluation du public potentiel, et, en conséquence, de la philosophie générale de l’enseignement. Il faut un enseignement intimement lié à la recherche, pour former des informaticiens par des études longues : que sera l’informatique dans trois ans, dans cinq ans ? Les plus connues des premières applications de l’informatique se rapportaient aux mathématiques et au calcul ; ce type d’application est marginal dans les appli- cations actuelles et en gestation, qui se rapportent à l’extraction de connaissances et à leur gestion, ainsi qu’à la simulation d’univers symboliques. Faut-il encore répéter, en 2020, qu’une connaissance préalable approfondie des mathématiques n’est nécessaire ni au concepteur, ni au programmeur, ni à l’utilisateur : au vu des formations le plus souvent proposées, il semble bien que oui. Ce qui ne veut pas dire que la connaissance des mathématiques est inutile, tout au contraire : mais son utilité apparaîtra beaucoup plus nettement à un informaticien déjà aguerri, qui aurait par exemple à traiter d’images ou d’apprentissage neuronal. Sa motivation pour apprendre ce qu’il faut de mathématiques pour résoudre son problème sera alors beaucoup plus grande. La rapidité et la diversification de la technologie a rendu nécessaire, pour ceux, en nombre toujours croissant, qui utilisent plus d’une machine ou plus d’un logiciel, que la connaissance de telle ou telle technologie passe après la maîtrise d’un en- semble de concepts généraux applicables partout. Chacun peut alors choisir logiciel et matériel en fonction de son problème spécifique. Mais les concepts généraux ne peuvent se comprendre sans une manipulation des outils qui les réalisent plus ou moins : nous nous sommes efforcé ici d’allier théorie et pratique, par une dialectique constante. Si la rigueur mathématique n’est pas nécessaire à votre apprentissage, en revanche la rigueur qu’apporte la pratique régulière des tests en machine est fondamentale. Gilles Bernard Université Paris 8 Vincennes 1. Avant-propos vii 1.2 Suivi du cours Deux choses seront donc cruciales pour suivre ce cours : ne pas considérer qu’on a compris une matière avant d’avoir appliqué sur la machine les connaissances apprises, d’une part, et d’autre part, être capable d’expliquer tout ce qui se passe sur sa machine lors de ses tests à l’aide du cours. La fonction des exercices dans ce cours a précisément pour but de tester ces connaissances. Vous ne devez pas passer à la suite du cours tant qu’un exercice n’a pas été réussi. C’est pourquoi je vous demande de m’envoyer les exercices par mail, et je vous réponds normalement dans les deux jours suivants ; dans les périodes très pleines (surtout de septembre à novembre), cela peut prendre jusqu’à une semaine. En dehors de cette période, si jamais vous n’avez pas reçu de réponse au bout de quatre jours, c’est qu’il y a un problème ; soit je n’ai pas reçu le mail, soit il s’est perdu dans les filtres de mon courrier (si vous n’avez pas obéi aux consignes d’envoi de chaque exercice), soit je vous ai répondu et la réponse s’est perdue. Dans tous les cas, n’hésitez pas à m’écrire. Les outils du cours sur Moodle servent à trouver ou à demander de l’aide. N’oubliez pas qu’un tuteur (ou plusieurs) est aussi là pour vous aider. Section Questions de compréhension du cours : pour demander ou trouver de l’aide sur le cours (un forum par chapitre) ; Section Aide pour réaliser les exercices : pour demander ou trouver de l’aide sur les exercices (un forum par chapitre contenant des exercices, une FAQ, un texte d’aide, et différents éléments) ; Section Questions générales : – Forum Coquilles et changements dans le cours : toutes les erreurs re- pérées dans le cours ou les exercices ; – Forum Questions sur Lisp en général : toutes vos questions générales sur Lisp ; – Forum Autres questions sur le cours : tout ce qui ne rentre pas dans une des catégories précédentes ; Quand vous postez un message dans un forum de ce cours, vous trouverez ci- dessous les consignes à respecter absolument. Programmation fonctionnelle 2021 viii Introduction Consignes globales pas de langage SMS ou d’abbréviation dans votre message ; mettez le message dans le bon forum de la bonne catégorie ; choisissez le sujet du message en fonction des règles ci-dessous. Consignes sur les sujets du message Si votre message porte sur une partie du cours, mettre en sujet le chemin de la partie et de la section du chapitre concernée ; par exemple, vous avez un problème avec Fonction compte : le problème se complique qui est la sous- section 3 de la section 2 Trace et récursivité du chapitre 4. Vous mettez le message dans le forum du chapitre 4 avec le sujet 2.3, en y ajoutant quelques mots pour caractériser votre problème de compréhension. Si votre message porte sur un exercice, mettre en sujet le sujet du mail de l’exercice ; par exemple Exo Lsp 5 Eval, éventuellement suivi du chemin de l’exercice concerné (ex. II.3) puis de quelques mots pour caractériser votre problème. Si votre message porte sur un sujet qui a déjà été traité mais dont les réponses ne vous satisfont pas (ou il n’y a pas encore de solution), utilisez le bouton répondre au sujet et non pas nouveau sujet. Si votre message porte sur une coquille que vous avez découverte, indiquez-la dans le forum sur les coquilles avec en sujet le chemin complet à partir du chapitre (ex. 4.2.3). En plus du mail et des forums, vous disposez du chat : on peut se donner rendez- vous par mail dans le salon de chat à l’occasion d’une difficulté que les outils précédents (mail et forums) ne permettraient pas de résoudre. Vous pouvez éga- lement vous rencontrer sur le chat entre étudiants (attention, pas de questions privées). Enfin, pour les questions qui ne sont pas directement liées au cours (problèmes d’installation ou de la formation), utilisez les forums et les wikis du pseudo-cours InfoScolL1Info (https://moodle.iedparis8.net/course/view.php?id=522). Gilles Bernard Université Paris 8 Vincennes 2. Les trois activités de la création informatique ix 2. Les trois activités de la création informatique 2.1 Conception, programmation et dialogue La création de systèmes informatiques fait intervenir trois sortes d’activités com- plémentaires : conception, programmation et implémentation ; ce dernier terme ne désigne en fait qu’un cas particulier de dialogue avec la machine, effectué pour mettre en oeuvre un problème déjà formalisé. Pour commencer, je parlerai donc des activités de conception, de programmation et de dialogue, liées à trois aspects de la création informatique : le problème, l’utilisateur, la machine. Les interactions définissent les tâches suivantes : conception → programmation : le concepteur explicite pour le programmeur, dans sa langue et à l’aide de schémas (modèles), la manière dont le problème est traité par un expert, à partir d’un examen et d’une classification des données de ce problème. conception → dialogue : le concepteur détermine le public auquel est destiné l’outil, et, à partir d’une analyse psycho-cognitive, choisit le type d’implé- mentation qui lui convient le mieux (convivialité, ergonomie). programmation → conception : le programmeur analyse le modèle fourni par le concepteur, le réduit en composantes susceptibles de recevoir une expression formelle (se ramener à des problèmes déjà résolus). programmation → dialogue : élaborer une correspondance entre les forma- lismes utilisés en programmation et les mécanismes propres aux différents environnements de dialogue homme-machine, aux différents systèmes d’ex- ploitation et aux différentes machines. dialogue → programmation : c’est l’implémentation proprement dite ; étant donné un problème formalisé, le traduire dans l’un des environnements de dialogue disponibles qui conviennent le mieux au formalisme - et éventuelle- ment corriger le formalisme proposé. dialogue → conception : répertorier les environnements de dialogues et les outils actuellement existants, et évaluer leur puissance (efficacité, rapidité, robustesse), pour permettre une meilleure exploitation des possibilités of- fertes ou l’élaboration d’outils manquants. Dans la création de systèmes ou d’applications, chaque tâche est conditionnée par les autres, et doit être effectuée de manière autonome mais en constante interac- tion. Ceci constitue évidemment un idéal qu’on s’efforcera datteindre mais que les Programmation fonctionnelle 2021 x Introduction disponibilités effectives restreignent plus ou moins. Si les tâches sont distribuées entre des individus différents (ou des équipes différentes) – ce qui est le cas le plus fréquent, chacun doit en savoir un minimum sur les autres tâches pour pouvoir échanger avec les autres. La réalisation d’un programme complexe par un individu seul est un cas rarissime, et encore plus dans le cadre de l’open-source. L’informatique, en particulier la programmation, est fondamentalement une activité de création, inséparable d’un certain sens de l’esthétique et d’un aspect ludique. Pendant la phase d’apprentissage, chacun doit pratiquer les différentes tâches possibles sans finalité, pour le plaisir, jusqu’à trouver quel est l’aspect de cette activité de création qui leur donne le plus de satisfaction. 2.2 Prérequis à acquérir 2.2.1 Dialogue Pour pouvoir dialoguer avec la machine, il faut en connaître la structure et les éléments fondamentaux : mémoire vive (pile du dialogue), mémoire morte ; uni- té centrale, interfaces, périphériques ; charger, lire, écrire, paramétrer ; syntaxe et lexique des environnements de dialogue. Il faut aussi connaître quelques environ- nements de dialogue : système d’exploitation, environnement de programmation, traitement de textes, environnement orienté objets. Et quelques environnements spécialisés dans une tâche : formater, tracer (les programmes et les données)... 2.2.2 Conception Pour concevoir, il faut naturellement avoir une bonne connaissance d’une part des problèmes du domaine de spécialisation (métier), et aussi connaître les concepts qui sont formalisables en termes de structures de données et de structures de processus (technique). Une bonne connaissance des éléments d’ergonomie, donc de psychologie des utilisateurs, est aussi nécessaire, ainsi que tout ce qui permet de mieux analyser les attentes de ces utilisateurs. 2.2.3 Programmation Programmer, c’est soit formaliser (ramener à des formes simples) les solutions qu’un concepteur propose pour un problème, soit généraliser les programmes déjà existants. Cela suppose une bonne connaissance des structures de données et de processus qui sont implémentables à l’heure actuelle sur les ordinateurs, et une bonne connaissance des techniques de programmation (descendante, ascendante, dirigée par les données, par les évènements, par l’environnement, structurée). Gilles Bernard Université Paris 8 Vincennes Chapitre I Introduction aux structures de données Sommaire 1. Introduction.......................... 2 2. Représentation interne : le point de vue de la machine 2 3. Les pointeurs.......................... 8 A. Exercices sur la représentation parenthésée....... 16 B. Exercices sur la représentation à points.......... 20 4. Représentation externe : le point de vue du problème. 22 C. Exercices sur les arbres................... 32 5. Conclusion........................... 34 2 CHAPITRE I. STRUCTURES DE DONNÉES 1. Introduction Une structure de données est un ensemble de liaisons entre données qui se rapportent à différents aspects d’un même problème, pour les regrouper en une donnée complexe. Les données peuvent être d’autres structures de données, ou des données élémentaires. Les données les plus élémentaires avec lesquels on travaille ordinai- rement sont les caractères (ou bytes : unités d’information), bien qu’elles-mêmes puissent être considérées comme composites, comme on va le voir plus loin. Il y a deux manières de concevoir les structures de données : soit du point de vue de la machine, en partant du plus élémentaire pour aller vers le plus com- plexe, soit du point de vue du problème, en partant de son expression la plus naturelle et réduisant sa complexité jusqu’à parvenir à une structure de données compréhensible par la machine. Le plus fondamental, pour la machine, c’est aujourd’hui la séquence de bits. Les recherches actuelles cherchent à introduire, au niveau le plus bas, des structures plus complexes, à partir de la structure du vivant (ce qui s’est révélé un échec) ou à partir du niveau quantique (ce qui semble plus prometteur) ; au lieu de partir des bits, qui sont des éléments à deux états, on pourrait partir d’éléments à n états. On est amené aujourd’hui à traiter sur machine des problèmes très complexes, dont l’exemple type est celui de la simulation d’environnements réalistes, c’est à dire reproduisant la réalité, avec son réseau de contraintes multiples et contradic- toires. Ce type de structures de données organisées en réseau ne s’exprime pas directement dans les structures de données élémentaires de la machine. L’exposé qui va suivre s’effectue en trois parties : tout d’abord, j’expliquerai comment sont construites les structures de données du point de vue de la machine, puis j’indiquerai comment on construit des briques élémentaires qui permettent de s’affranchir du point de vue de la machine, pour finir par exposer, dans la troisième partie, comment on décompose une structure de données complexe pour obtenir une traduction du problème en briques élémentaires. 2. Représentation interne : le point de vue de la machine 2.1 Structure de la mémoire La mémoire (ROM, RAM, disques, disquettes, bandes, etc.) est une séquence ca- librée en unités élémentaires. Chaque unité a une adresse, sa position dans la Gilles Bernard Université Paris 8 Vincennes 2. Représentation interne : le point de vue de la machine 3 mémoire ; pour y accéder, il faut connaître son adresse, déplacer la tête de lecture jusqu’à l’endroit voulu, puis interpréter ce qu’il y a. L’unité la plus élémentaire est le bit, qui signifie “bribe” et, par jeu de mots, bi[nary dig]it (nombre binaire), qui a deux états, conventionnellement associés aux valeurs 0 et 1 (ou vrai et faux). La mémoire est donc linéairement calibrée en bits : 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 0 0 1 1 1 0 1 0 1 0 1 0 0 0 0 1 0 1 1 1 0 0 1 1 0 0 1 1 1 0 Le bit ayant une capacité informative très faible (deux valeurs seulement), on fabrique des unités virtuelles plus grandes par regroupement de bits. Plus une unité contient de bits, plus elle a d’états différents ; rajouter un bit à une unité multiplie par deux son nombre d’états, c’est pourquoi toutes les unités mémorielles sont des puissances de deux. Une mémoire de 100 bits permet de stocker 12 caractères sur 8 bits, 14 ca- ractères sur 7 bits, 16 caractères sur 6 bits, ou un mélange de tout ça. Com- ment savoir s’il faut lire comme ou comme ou encore autrement ? Il y a deux solutions : soit on dé- cide que toutes les unités auront la même taille, et dans ce cas le processus qui lit ou écrit dans la mémoire doit connaître cette taille, soit les données ont des tailles différentes et dans ce cas on doit stocker la taille de chaque donnée quelque part, dans le programme de traitement ou avec la donnée. Les deux cas existent : tout d’abord la mémoire est calibrée en octets (groupes de 8 bits), tous identiques, et ces octets sont groupés en fonction du type de données stockées : par exemple en C, un char (caractère) utilise un octet, un int (entier) en utilisait quatre (aujourd’hui en général 8), un long int en utilise huit, etc. 2.2 Structures de données rigides, typées, dites statiques La mémoire, quelles que soient les unités dont elle est constituée, va bien sûr contenir plusieurs types de données. Supposons qu’une donnée figure à l’adresse 2011 ; pour savoir où elle s’arrête, il faut connaître sa taille ; chaque donnée ayant apriori une taille différente des autres, cette taille doit bien être écrite quelque part dans la mémoire ; on la fera ici arbitrairement figurer au début de la donnée, dans un en-tête (en réalité l’endroit où se trouve cette taille varie). Pour lire la donnée, nous devons donc d’abord lire la taille qu’elle occupe ; cette taille sera exprimée par une séquence de bits, à interpréter comme un nombre entier ; elle sera suivie par une séquence de bits à interpréter en fonction du type de la donnée : est-ce un nombre, un caractère, ou un ensemble plus complexe de données ? L’en-tête de la donnée va contenir ces informations. Programmation fonctionnelle 2021 4 CHAPITRE I. STRUCTURES DE DONNÉES Une structure de données rigide va donc contenir deux parties : l’en-tête (en jaune dans les tableaux ci-dessous), ensemble de données indiquant la manière dont il faut lire les données, et l’ensemble des données qui suivent. Pour savoir où s’arrête l’en-tête, on peut provisoirement supposer que tous les en-têtes ont la même taille, connue par le système (stockée quelque part ailleurs dans la mémoire), ou que l’en-tête a lui-même un en-tête, qui indique sa taille. en-tête données Une structure de données rigide occupera un morceau de la mémoire. Pour la stocker, il faut donc calculer sa taille (y compris celle de l’en-tête) et trouver, dans la mémoire, une place libre de cette taille, puis écrire l’en-tête et réserver l’espace nécessaire aux données : c’est ce qu’on appelle la déclaration. Une fois déclarée la structure de données, on peut ensuite écrire les données dans l’espace réservé, c’est ce qu’on appelle l’affectation. Dans les descriptions qui suivent, les représentations internes sont données à titre d’exemple (il y a plusieurs manières de représenter les structures de données) ; l’important est d’en comprendre le principe. Il y a trois types de structures de données rigides : le scalaire, le vecteur et l’agrégat. Le scalaire ne contient qu’une seule donnée. Son en-tête indiquera qu’il s’agit d’un scalaire, le type de la donnée (nombre par exemple), et sa taille (13 unités par exemple) ; représentation interne : S n 13 Le vecteur (qu’on appelle aussi table ou tableau) contient une séquence de don- nées toutes de même type et de même taille. Ces données, appelées les composantes du vecteur, sont caractérisées par leur position dans la séquence (leur adresse), ap- pelée l’indice de la composante. L’en-tête portera indication du fait qu’il s’agit d’un vecteur, de la taille et du type des composantes, et de leur nombre. Par exemple, les noms des jours de la semaine peuvent être enregistrés dans un vecteur (V ) de 7 composantes ; la taille des composantes se calcule à partir de la plus grande : 8 octets, comme dans dimanche, à interpréter comme des caractères (c) ; il est inutile d’indiquer la taille de l’ensemble, puisqu’elle peut être calculée (7*8, soit 56 octets) ; la représentation interne, à supposer que l’en-tête se trouve à l’adresse 11 de la mémoire (et comme par hypothèse nous avons déjà supposé que l’en-tête précède la donnée), ressemblerait à ceci (la troisième ligne contient les adresses internes au vecteur) : 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 V 7 c 8 L u n d i Ma r d i Me r c r e d i J e u d i 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 Gilles Bernard Université Paris 8 Vincennes 2. Représentation interne : le point de vue de la machine 5 Comment trouver la troisième composante ? Il suffit de sauter les composantes précédentes (deux de 8 octets) et d’aller à la case suivante : le nom du troisième jour de la semaine commence au 17ème octet (2*8+1) depuis le début des données (31ème octet de la mémoire). À partir de l’adresse 71 figurent d’autres informations, appartenant à d’autres données. La fin de la représentation interne du vecteur pourrait ressembler à ceci : 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 V e n d r e d i S a me d i D i ma n c h e &a b c d e 33 34 35 36 37 38 39 40 41 42 43 45 45 46 47 48 49 50 51 52 53 54 55 56 Si l’utilisateur demande par erreur le 8ème jour de la semaine, il ne faut pas que la machine lui réponde &abcde ; il faudra détecter, en consultant le nombre de composantes indiqué, que cette chaîne se trouve au-delà du vecteur. L’accès aux données d’un vecteur est dit accès direct (parce qu’on saute directement à la donnée) ou accès par indice. La position relative de la donnée recherchée est cal- culée à partir de son indice I, de la taille des composantes T, de leur nombre N. La formule générale, pour un vecteur comme celui que nous avons vu, appelé vecteur à une dimension, est : Si I < N , position-relative = ((I − 1) ∗ T ) + 1 Il existe des types de vecteurs (ou tableaux) plus complexes. C’est le cas du calen- drier des ventes ci-dessous, qui sera représenté par un vecteur à deux dimensions (ou une table à double entrée) ; pour accéder à une donnée, il faut deux indices (la ligne = l’objet, et la colonne = le mois) : Janvier Février Mars Avril Mai Cartes mères 5 7 9 15 18 Claviers 24 19 25 18 15 Écrans 32 28 27 12 52 Souris 57 62 58 65 35 Dans la représentation interne associée, on remplacera le nom des mois et le nom des objets par leur numéro d’ordre. Par une convention courante, on note calendrier[1,1] ou calendrier[0,0] (en C) la donnée en haut à gauche (nombre de cartes mères vendues en janvier) ; calendrier[2,3] représente le nombre de claviers vendus en mars ou (en C) le nombre d’écrans vendus en avril. La représentation interne d’un vecteur à deux dimensions est obtenue en li- néarisant le tableau, en notant dans l’en-tête le nombre de colonnes et de lignes et, comme pour les autres vecteurs, la taille (1 octet) et le type (nombre) des composantes : V 2 5 4 n 1 5 7 9 15 18 24 19 25 18 15 32 28 27 12 52 57 62 58 65 35 X a 12 a 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Programmation fonctionnelle 2021 6 CHAPITRE I. STRUCTURES DE DONNÉES Pour accéder à la donnée figurant en troisième ligne, deuxième colonne, on com- mence par sauter deux lignes ; chaque ligne fait 5 colonnes, de 1 octet chacune, donc on saute 10 octets ; on saute ensuite une colonne, donc un octet, et on se positionne sur la case suivante : 10+1+1, la donnée figure au 12ème octet. Soit L le nombre de lignes, C le nombre de colonnes, T la taille de la compo- sante, la formule générale pour calculer la donnée d’indices [l, c] (l ligne, c colonne) est : position − relative = ((l − 1) ∗ (C ∗ T )) + ((c − 1) ∗ T ) + 1 On peut généraliser cette procédure pour définir l’accès à des vecteurs à n dimen- sions, pour représenter des tables à n entrées. La déclaration d’un vecteur à n dimensions initialisera son en-tête de manière à pouvoir effectuer la réservation de sa place et à écrire les paramètres qui serviront pour l’accès aux données. Les vecteurs n’admettent qu’un seul type de données : bits, caractères, nombres entiers, nombres flottants, mots, ou même vecteurs. Pour réunir des types de don- nées distincts, on utilisera l’agrégat. L’agrégat étant la plus récente des structures de données rigides, il présente plusieurs noms : structure en C et en PL1, record (enregistrement) en Pascal ou dans les bases de données – où on utilise aussi le terme de ligne (row). Un bon exemple d’agrégat est celui de la feuille de soin ; elle contient des don- nées dans deux parties (le haut de la feuille ne contient pas de données, mais indique simplement de quoi il s’agit). Chacune de ces parties contient une éti- quette (mot-clé ou phrase-clé) qui indique de quoi elle traite, et qu’on appelle une rubrique ; la première contient la rubrique assuré (pour abréger) la seconde la ru- brique malade. Chacune de ces rubriques contient à son tour d’autres rubriques (nom, prénom, numéro, etc.). Pour trouver une information dans un agrégat, par exemple le nom de l’assuré, il faut indiquer le chemin à parcourir à travers les rubriques : d’abord la rubrique assuré, puis nom ; ce qu’on note par convention assuré.nom ; un agrégat est un arbre contenant l’ensemble des chemins possibles vers les données. Certaines données contenues dans cet agrégat sont des mots ou des suites de mots, d’autres sont des nombres, d’autres encore, comme la réponse à la rubrique accident ?, sont des données binaires (oui / non), etc. L’en-tête comporte l’indication qu’il s’agit d’un agrégat (A), le nombre de rubriques principales, la taille de chacune, et son nom (en réalité un nombre, pour occuper moins de place), le nombre et la taille des sous-rubriques ; pour chaque rubrique terminale, il faut indiquer la taille de la donnée et son type. Par exemple, pour un agrégat joignant un nom (N m) à 9 caractères à un numéro (N o, nombre de 4 octets, l’en-tête comporterait : Gilles Bernard Université Paris 8 Vincennes 2. Représentation interne : le point de vue de la machine 7 A 2 Nm 9 c No 4 n Z O R G L U B 0 4 3 5 1 2 3 4 5 6 7 8 9 10 11 12 13 Cherchons le numéro ; il y a deux rubriques, c’est la deuxième qu’on cherche, il faut donc sauter 9 caractères, plus 1 : la donnée sur 4 octets commence en position 10. 2.3 Les données Un mot sur les données contenues dans ces structures. On lit souvent qu’il y a trois types de données : chaîne (suite de caractères), nombre (suite de chiffres), booléen (valant 1 ou 0, vrai ou faux). Même si ce n’est pas faux, il n’y a en fait qu’un seul type de donnée réellement élémentaire, celui qui résulte du découpage du support de mémoire en unités de base : le bit - c’est à dire le booléen. Tous les autres types sont en fait des agencements de bits, ce sont des données structurées. Mais la mémoire ayant été recalibrée en séquences de 8 bits (parfois 16 bits), l’unité de base est devenue l’octet (pour l’instant !). Ce qui fait que pour accéder à un booléen, il faut maintenant d’abord accéder à un octet, puis à l’intérieur de celui-ci accéder à un bit. Un caractère est une séquence de bits (un octet, ou plusieurs dans les codages les plus récents) dont chacune est associée à une image (le caractère proprement dit) ; la chaîne est une séquence de caractères ; on la représentait souvent, dans des environnements anciens, par un vecteur de caractères, avec l’inconvénient majeur que la taille des chaînes qu’on pouvait écrire était arbitrairement limitée. Par exemple, avec MSDOS, les noms de fichier ne pouvaient dépasser 11 caractères, en Basic (1986), les chaînes ne pouvaient dépasser 256 caractères. Un nombre pourrait être conçu comme une séquence de chiffres (comme une chaîne est une séquence de caractères), mais ce n’est pas le cas, entre autres parce que sa représentation (et sa longueur) dépend de la base dans laquelle il a été écrit. Supposons qu’on représente le nombre comme un vecteur de chiffres décimaux (de 0 à 9), sur 16 bits ; il faut 4 bits pour chaque chiffre ; le nombre le plus grand serait donc 9999 ; en base deux (chiffres 0 et 1), sur 16 bits, le nombre le plus grand est 1111111111111111, c’est à dire 65.535. Et, bien entendu, c’est cette solution qu’on adopte. Si on veut exprimer le signe, on ajoutera un bit, et le nombre sera alors un agrégat signe + vecteur ; si on veut pouvoir exprimer des fractions (des nombres rationnels), on décomposera le nombre en signe + numérateur + dénominateur ; si on veut augmenter la quantité de nombres exprimables, on pourra exprimer 1456, 14,56 et 14.560 par le même nombre + une rubrique indiquant la puissance de 10 concernée. Etc. Toutes ces données sont à la base des séquences de bits. Ce qui les différen- Programmation fonctionnelle 2021  8 CHAPITRE I. STRUCTURES DE DONNÉES cie, c’est le traitement que le système en fera, et leur typage permet au système de savoir comment les interpréter : les nombres s’additionnent, les caractères se juxtaposent, les booléens sont reliés par des connecteurs logiques (et, ou, non). *** L’exposé qui précède n’est pas toujours à prendre au pied de la lettre : ainsi l’en-tête ne se trouve pas forcément juste avant les données qu’il caractérise, mais dans une autre portion de la mémoire, que le programme utilise pour traiter ces données, et on ne distingue pas le type et la taille des données, on utilise plutôt une combinaison des deux - comme l’int du C, mais le principe fondamental qu’il y a à comprendre, c’est qu’en fin de compte tout se ramène à trouver la partie de la mémoire qui nous intéresse et à la traiter en fonction de ce que nous savons (ou croyons savoir) d’elle. Même si la plus grande partie de l’activité des informaticiens consiste à s’affranchir de cette réalité pour la faire ressembler à la réalité du problème à traiter, il reste qu’en cas d’échec, la connaissance des mécanismes fondamentaux de la mémoire informatique est nécessaire. 3. Les pointeurs 3.1 L’accès aux structures de données Nous avons vu jusqu’à maintenant comment étaient construites les structures de données rigides, et comment accéder aux données qu’elles contenaient. L’environ- nement informatique d’un programme, considéré du point de vue des données, est l’ensemble des structures de données disponibles (mémorisées) à un instant donné et dans une zone donnée de la mémoire (la zone à laquelle le programme a accès). Comment accéder, non plus aux données dans les structures, mais aux struc- tures elles-mêmes ? Nous avons vu que chaque structure de données avait une adresse en mémoire. Pour accéder à une structure particulière, il faut soit fouiller toute la mémoire1 , soit conserver quelque part l’adresse de cette donnée dans un pointeur. Un pointeur est une donnée numérique qui représente l’adresse de la donnée ; la valeur sur laquelle pointe ce pointeur, c’est la donnée dont il contient l’adresse. La taille de la capacité maximale de la mémoire étant connue d’avance, il est facile de déterminer la taille du pointeur : par exemple, si on veut accéder 1. Évidemment, fouiller toute la mémoire pour retrouver une donnée est une méthode incommode, à laquelle on ne recourt que quand on y est obligé ; elle suppose qu’on connaisse au moins une partie de la donnée à retrouver. Gilles Bernard Université Paris 8 Vincennes  3. Les pointeurs 9 à chaque octet d’une mémoire de 256 octets, le pointeur devra pouvoir prendre toutes les valeurs entre 0 et 255 : un octet suffira (ce n’est pas le cas aujourd’hui, mais ça l’était pour certaines machines d’il y a trente ans). Comme n’importe quelle structure de données rigide, les pointeurs ont un en-tête et une adresse. Les pointeurs sur nos structures étant eux-mêmes stockés dans la mémoire, se pose le problème de comment les retrouver. Le principe est de donner un nom dif- férent, dit souvent identifiant, à chaque pointeur ; on parle d’accès par nom. Du coup notre problème devient celui de lier un nom donné (une chaîne de caractères) à un pointeur. La manière la plus simple de le faire est celle du carnet d’adresses : en face de chaque nom, on inscrit l’adresse de la donnée. Ces couples nom, pointeur sont des agrégats, et le carnet d’adresses est un vecteur d’agrégats qui contiendra l’ensemble des associations. Inode (Unix/Linux), Fat (MsDOS), Fat32 (MsWindows), NTFS (MsWindows), désignent les carnets d’adresses qui permettent de retrouver les adresses des fichiers à partir de leur nom. Mais cette solution n’est pas toujours adaptée et on recourt souvent à une autre méthode, appelée hash-coding, qui consiste à calculer l’adresse à partir du nom : c’est en quelque sorte le nom qui sert de pointeur sur la donnée. Le principe est simple : avec un alphabet de n lettres, on considère le nom comme un nombre écrit en base n, chaque lettre valant pour sa position dans l’alphabet ; BAI sera donc le nombre 2*n²+1*n+9, comme 219 est le nombre 2*10²+1*10+9.1 Les valeurs liées aux noms dépendent entièrement de l’environnement et des liaisons qui y ont été faites : Il n’y a pas qu’un âne qui s’appelle Martin. Par consé- quent, il est important de connaître chacun des environnements dans lesquels on peut se trouver (système d’exploitation, systèmes de gestion de fichiers, langages de programmation, systèmes de gestion de bases de données, éditeurs, etc.), et d’avoir accès à l’ensemble des liaisons valides à un moment donné. Si une struc- ture de données a été mémorisée, mais qu’on n’a pas conservé de pointeur sur elle (ou que le pointeur a été détruit), on peut toujours fouiller l’environnement à sa recherche2 ! Sinon, on la redécrit - et sa nouvelle description ne sera très proba- blement pas à la même adresse. On a donc trois possibilités pour accéder à une structure de données : par description (ou valeur), par adresse (ou pointeur), par nom. L’accès par nom est très populaire, en informatique comme dans la vie cou- rante : combien de gens donnent un nom non seulement à leurs dossiers, mais aussi à leur voiture, à leur chez-soi... Avec le nom d’une structure de données, on la re- 1. L’inconvénient de cette méthode étant qu’il y a trop d’adresses vides, les applications concrètes utilisent des techniques pour optimiser l’occupation de la table d’adressage ou hash-table 2. Il existe des outils spécialisés pour ce genre de recherche. Programmation fonctionnelle 2021 10 CHAPITRE I. STRUCTURES DE DONNÉES trouve même si elle a changé d’adresse, pourvu que l’environnement sache tenir à jour son répertoire : quel soulagement pour l’utilisateur, qui n’a même pas besoin de le savoir. Bien entendu, tous les objets ne nécessitent pas de nom : il y a des calculs qu’on ne fera qu’une seule fois, d’autres très peu de fois ; un nom est inutile dans le premier cas, dans le second, c’est affaire de pratique. Si on lie un nom à une nouvelle valeur, on perd son ancienne valeur. Si on lie à deux noms la même valeur décrite deux fois, ces valeurs ne seront pas à la même adresse, et la modification de l’une laissera l’autre inchangée. Si on lie à deux noms le même pointeur, il n’y a qu’une adresse : modifier la valeur liée à l’un des noms modifiera la valeur liée à l’autre. 3.2 Les indirections On peut avoir besoin d’introduire une donnée dont on ne connaît pas la taille à l’avance dans une structure de données. Par exemple, l’agrégat contenant le couple nom, pointeur limite la taille des noms possibles ; c’est effectivement le cas de certains environnements (d’où la limitation des noms de fichiers MsDOS à 11 caractères). Pour dépasser cet inconvénient, il suffit de remplacer dans l’agrégat le nom par un pointeur sur le nom. Remplacer une donnée par un pointeur sur cette donnée se dit effectuer une indirection. Autre exemple : les tables de caractères assignent à chaque position une image du caractère à afficher, suivant une norme qui peut varier (ASCII, ANSI, etc.). Chaque octet rencontré dans un fichier texte est un pointeur sur cette table : l’octet 65 (en décimal) est, en ASCII, le pointeur sur le caractère A, qui se trouve justement en 65ème position dans la table ASCII. Cette méthode a été élaborée à une époque où l’on ne se posait pas la question d’utiliser d’autres alphabets que l’alphabet anglais. Supposons maintenant qu’on utilise plusieurs alphabets (grec, cyrillique...) : une première solution consiste à augmenter la table des caractères ; un octet sera insuffisant, on en mettra deux, ce qui permettra d’accéder à 65.536 caractères de la table. Mais il sera assez compliqué, dans ce cas, de déterminer l’alphabet auquel appartient un caractère : il faut calculer (par exemple, l’alphabet grec serait compris entre 42.500 et 42.668), comme on le fait aujourd’hui pour convertir les majuscules en minuscules. De plus, chaque modification de la table entraîne la remise à jour des pointeurs dans tous les programmes qui l’utilisent (c’est-à-dire pratiquement tous). Une autre solution consiste à créer autant de tables différentes qu’il y a d’alpha- bets, puis d’utiliser une indirection : on prend deux octets, le premier est considéré Gilles Bernard Université Paris 8 Vincennes 3. Les pointeurs 11 comme un pointeur sur la table (ce qui permet d’avoir 256 alphabets), le second comme un pointeur sur le caractère dans cet alphabet (c’est le principe d’une des implémentations possibles de la norme unicode). L’ajout d’une nouvelle table ne modifie rien aux autres tables, les programmes peuvent continuer à fonctionner sans changements. C’est la solution qu’on a employée pour représenter les cou- leurs des caractères : plutôt que de distinguer un A rouge et un A vert, on utilise un pointeur sur la couleur à côté du pointeur sur le caractère. Nous venons de voir deux usages des pointeurs : pour retrouver une structure de données, ou pour effectuer une indirection ; nous allons en voir un troisième. 3.3 Structures de données souples, non typées, dites dyna- miques Les structures de données rigides présentent des inconvénients majeurs dès qu’il s’agit de représenter des données complexes ; on peut en repérer quatre : 1. Gaspillage d’espace : il y a de l’espace gaspillé quand la donnée est plus courte que l’espace qui lui est réservé ; par exemple, le vecteur des jours de la semaine réserve aux données un espace de 56 octets, alors qu’elles n’occupent que 45 caractères : 10 octets sont perdus. Quand on traite de grandes quantités de données, la place ainsi perdue peut être considérable. 2. Gaspillage de temps : si la mémoire ne contient pas d’espace libre assez grand pour écrire une structure de données, mais qu’il y a plein de petits espaces libres non contigus, il faudrait, avant de l’écrire, déplacer toutes les données de la mémoire pour libérer la place nécessaire. 3. Contraintes de type : si on ne peut pas savoir à l’avance le type ou la taille d’une donnée (par exemple si c’est à l’utilisateur de décider), on ne peut pas utiliser une structure de données rigide. 4. Contraintes de structure : si on a besoin de structurer les données de manière non linéaire (par exemple, si on veut représenter la semaine comme un cercle où dimanche est suivi par lundi), on ne peut pas utiliser une structure de données rigide. Pour éviter ces inconvénients, on utilise des structures de données souples, appelées listes. Une liste est une structure de données qui réunit un nombre quelconque de données, de type quelconque ; on peut y ajouter et y enlever des éléments à n’importe quel endroit, ou changer l’ordre des éléments ; aucun espace n’est gaspillé, une liste n’occupe que la place occupée par ses données. Programmation fonctionnelle 2021 12 CHAPITRE I. STRUCTURES DE DONNÉES Fig. 3.1 : Une liste faite de doublets Comme la taille d’une liste peut changer en cours de programme, on ne peut pas réserver sa place en mémoire. On ne peut pas écrire les données les unes à la suite des autres : il faudrait, à chaque insertion ou destruction, modifier toute la mémoire qui suit la donnée insérée ou ajoutée, ce qui impliquerait un énorme gaspillage de temps. Par conséquent, une liste est d’abord une manière de regrouper virtuellement des données physiquement dispersées dans la mémoire, à des adresses différentes. Ces regroupements virtuels s’effectuent à l’aide de pointeurs. Le problème est résolu à l’aide de ce qu’on appelle un doublet (en Lisp, aussi cons) ; c’est un vecteur de deux pointeurs, dont le premier pointe sur la donnée et le deuxième sur l’adresse du doublet suivant. Le parcours s’effectue comme un jeu de piste : il faut découvrir un objet (la donnée), et, à l’endroit où se trouve l’objet, figure l’adresse de l’objet suivant (sous forme d’une devinette dans le jeu, sous forme d’un pointeur ici) ; à la fin, au lieu de l’indication gagné !, on utilise un faux pointeur qu’on appelle conventionnellement nil (en Lisp) ou NULL (en C), qui ne pointe sur rien (nil signifie “rien” en latin), et indique que la liste est terminée. La figure 3.1 représente la liste composée des éléments a, b, c, x et d. Chaque rectangle composé de deux carrés représente un doublet ; les pointeurs sont repré- sentés par des flèches ; celui de gauche pointe sur un objet dont on indique le nom (a, b, etc.), celui de droite sur le doublet suivant. Le dernier carré est barré pour représenter le pointeur nil. La liste est donc un parcours qui introduit, entre des données qui ne se suivent pas physiquement, une séquencialité virtuelle. Le début de la liste est indiqué par un pointeur qui n’a pas été représenté dans la figure 3.1. Gilles Bernard Université Paris 8 Vincennes 3. Les pointeurs 13 Pour remplacer un élément par un autre, par exemple a à remplacer par toto, il suffit de remplacer le pointeur sur a par le pointeur sur toto. Pour insérer un élément n’importe où, par exemple insérer y dans la figure 3.1 entre c et x, il faut : créer un doublet, dont le pointeur de gauche pointe sur y, et dont celui de droite contient l’adresse du doublet qui contient le pointeur sur x, qu’on recopie à partir du doublet (c.x) ; dans le doublet qui contient le pointeur sur c, modifier le pointeur de droite pour le faire pointer sur le nouveau doublet créé. Pour ajouter l’élément y à la fin, c’est le même principe : il faut remplacer nil par un pointeur sur le nouveau doublet et mettre nil dans celui-ci. Pour supprimer un élément n’importe où, par exemple b, il faut copier le poin- teur de droite de l’élément à supprimer dans le doublet précédent (celui qui contient le pointeur sur a). Pour supprimer le dernier élément, il faut mettre nil dans l’avant- dernier doublet. Pour supprimer le premier élément, il faut remplacer le pointeur sur le début de la liste par le pointeur de droite du premier doublet. Avez-vous remarqué que quand vous supprimez une donnée d’une liste, la don- née reste en réalité intacte ? Supprimer une donnée, c’est simplement perdre sa trace, ne plus pouvoir la retrouver par son adresse. C’est pourquoi, même après avoir détruit un fichier, vous pouvez en retrouver le contenu en fouillant directe- ment la mémoire. Une donnée peut d’ailleurs appartenir à plusieurs listes, et ne pas être perdue pour tout le monde. Pour accéder à un élément d’une liste, il faut parcourir la liste : c’est l’accès séquentiel. Jeux de noms Nous avons jusqu’à maintenant manipulé une liste sans lui donner de nom. Avec un nom, donc la possibilité de manipuler aussi le pointeur d’entrée sur la liste, on peut fabriquer des structures de données extrêmement curieuses : par exemple, on peut remplacer le pointeur nil de la liste par le pointeur de début de liste, et on obtient une liste circulaire (il n’y a pas de dernier élément). Si une liste contient une autre liste, on peut de la même manière refermer la seconde liste sur la première : la première liste contient la deuxième, mais la deuxième contient aussi la première (et donc elle-même)... Exercez-vous, construisez des objets bizarres : la réalité étant complexe, un jour ou l’autre, vous trouverez un problème auquel l’une de vos structures conviendra (ex : une liste circulaire convient fort bien à représenter les jours de la semaine). Et n’oubliez pas : on n’est jamais limité que par sa propre imagination. Programmation fonctionnelle 2021 14 CHAPITRE I. STRUCTURES DE DONNÉES 3.4 Conventions de représentation La représentation que nous venons de voir, en doublets de pointeurs graphiques, est celle qui est la plus proche de la représentation en machine ; mais elle n’est pas très commode à utiliser, et on en utilise deux autres, qui ont elles l’avantage de pouvoir être écrites dans la ligne de commande d’un langage de programmation comme Lisp. 3.4.1 Représentation dite à point Dans la représentation à point, on représente les bords du doublet avec des paren- thèses et la barre du milieu par un point : (.) Certes, ça aurait été plus proche de la représentation graphique d’utiliser : [|] Mais ce n’est pas ce qui a été choisi (pour des raisons de commodité des anciens claviers). Dans ce doublet il devrait y avoir des pointeurs : (ptr. ptr) Le principe de la représentation dite à point va consister à remplacer les poin- teurs par ce sur quoi ils pointent. Prenons par exemple la représentation en dou- blets de pointeurs de la figure ci-dessus. On part du premier doublet : (ptr1. ptr2) Ptr1 pointe sur a, ça va donc être facile de le remplacer : (a. ptr2) Ptr2 pointe sur un autre doublet, dont le pointeur de gauche peut être remplacé par ce sur quoi il pointe, b : ptr2 = (b. ptr3) Ptr3 pointe sur un autre doublet, dont le pointeur de gauche peut êtreremplacé par c : ptr3 = (c. ptr4) Ptr4 pointe aussi sur un autre doublet : ptr4 = (x. ptr5) Et ptr5 pointe sur le dernier doublet, dont le pointeur de droite, appelé nil, ne pointe en fait sur rien : ptr5 = (d. nil) Remplaçons ptr5 par sa valeur dans ptr4 : Gilles Bernard Université Paris 8 Vincennes 3. Les pointeurs 15 ptr4 = (x. (d. nil)) Et ptr4 par sa valeur dans ptr3 : ptr3 = (c. (x. (d. nil))) Et ptr3 par sa valeur dans ptr2 : ptr2 = (b. (c. (x. (d. nil)))) Et enfin ptr2 par sa valeur dans le premier doublet : (a. (b. (c. (x. (d. nil))))) Et voilà pour les représentations à points ; bien qu’elles soient encore très proches de la représentation en machine, elles ne permettent pas de représenter les listes circulaires et autres créatures bizarres. 3.4.2 Représentation parenthésée La deuxième sorte de représentation est plus simple : il s’agit d’utiliser les pa- renthèses comme une sorte de sac qui groupe tous les éléments d’une liste, dans l’ordre où ils apparaissent dans la représentation en doublets de pointeurs. Par exemple, la liste de la figure 3.1 se représente sous la forme : (a b c x d) Bien plus simple à manipuler (pour un être humain) que la précédente, elle est aussi plus limitée. On verra plus tard qu’elle ne peut représenter certains doublets que la représentation à points représente sans problème. La maîtrise de ces trois types de représentations (à doublets de pointeurs gra- phiques, à points et à parenthèses simples) est nécessaire à la manipulation de listes, quelque soit le langage qu’on utilise, mais tout particulièrement en Lisp, qui sera notre langage de programmation. Les exercices suivants ont pour but de tester votre compréhension de ces représentations, et la réussite à ces exercices sera très importante pour la suite. Programmation fonctionnelle 2021 16 CHAPITRE I. STRUCTURES DE DONNÉES A. Exercices sur la représentation parenthésée Envoyez-moi par mail les réponses aux exercices ci-dessous, en suivant stricte- ment les consignes suivantes : Mettez l’énoncé de chaque question avant la réponse. Joignez les réponses dans un unique fichier PDF. Ecrivez dans le sujet du mail : Exo SD 1 Parenthèses. Pour vous simplifier la tâche de fabriquer votre document de réponses, copiez- collez chaque énoncé (schéma ou texte) avant d’écrire votre réponse. A.1 Convertir des schémas de doublets en listes parenthé- sées Convertir sous forme de liste parenthésée simple les schémas de doublets ci-dessous. Indications : chaque doublet contient un pointeur sur l’élément courant et un pointeur sur le doublet suivant ou nil si la liste est terminée. Pour construire une liste parenthésée, on place une parenthèse ouvrante en rencontrant le premier doublet de la liste puis on écrit l’un après l’autre les éléments de la liste. L’élément courant peut être un atome (caractère ici) ou une liste, auquel cas on place une parenthèse ouvrante au début puis on écrit l’un après l’autre les éléments de la liste. Etc. N’oubliez pas de mettre un espace entre deux atomes. Quand on rencontre un doublet dont le deuxième pointeur est nil, on écrit une parenthèse fermante. Enfin, la casse, ou différence majuscule / minuscule, est pertinente : abc, Abc, ABC, AbC, etc. sont tous différents et ne peuvent pas être mis l’un pour l’autre. Pour compléments, reportez-vous à l’explication donnée dans la partie 3.. A ces consignes pour la machine, s’ajoutent quelques conventions supplémen- taires pour le lecteur humain, dites de pretty-print, à respecter impérativement dans tous les exercices, si vous souhaitez avoir une correction : après une parenthèse ouvrante, on ne met pas d’espace ; après une parenthèse fermante, on met un espace s’il y a ensuite un atome ou une parenthèse ouvrante ; on n’en met pas s’il y a une parenthèse fermante ; après un atome, on met un espace s’il y a ensuite un atome ou une parenthèse ouvrante ; on n’en met pas s’il y a une parenthèse fermante. Gilles Bernard Université Paris 8 Vincennes A. Exercices sur la représentation parenthésée 17 1. 2. 3. Programmation fonctionnelle 2021 18 CHAPITRE I. STRUCTURES DE DONNÉES 4. 5. 6. Gilles Bernard Université Paris 8 Vincennes A. Exercices sur la représentation parenthésée 19 A.2 Convertir des listes parenthésées en schémas de dou- blets En vous aidant de l’éditeur de dessins Dia (suivez attentivement les consignes du Guide de l’étudiant > Questions sur l’installation de logiciels pour les cours > Installation de Dia) et des schémas de la feuille Lisp spécialement créée pour l’occasion (bandeau du milieu dans l’éditeur Dia pour choisir la feuille > Autres feuilles), ou encore du logiciel ConsMaster (disponible, comme la feuille Lisp, sur la page Moodle du cours), traduisez en représentation interne (doublets de pointeurs graphiques) les listes suivantes : 1. (a b x (c d)) 2. ((a) x (b c)) 3. (a (b x) c d) 4. (x (b) a (d)) 5. ((a b c d x)) 6. (((a)) b c x) Programmation fonctionnelle 2021 20 CHAPITRE I. STRUCTURES DE DONNÉES B. Exercices sur la représentation à points Envoyez-moi par mail les réponses aux exercices ci-dessous, en suivant stricte- ment les consignes suivantes : Mettez l’énoncé de chaque question avant la réponse. Joignez les réponses dans un unique fichier PDF. Ecrivez dans le sujet du mail : Exo SD 2 Points. Principe (rappel) La liste (a) peut être représentée par (a. nil), la liste (a b) par (a. (b. nil)), (a b c) par (a. (b. (c. nil))), etc. A quoi sert cette représentation, clairement plus com- plexe que notre représentation parenthésée, plus intuitive ? Et bien, si par exemple le dernier pointeur de la liste ne pointe pas sur nil, mais sur un autre objet, x par exemple, nous pourrons écrire : (a. (b. (c. x))) Et ce type de liste un peu curieux (mais qui a beaucoup d’usages) ne peut pas être représentée autrement que dans cette notation ou avec des schémas de doublets. Un exemple : un doublet dont la partie gauche pointe sur a et la partie droite sur b s’écrit (a. b) ; un doublet dont la partie gauche pointe sur le doublet précédent et dont la partie droite est nil, s’écrira ((a. b). nil) ; un troisième doublet dont la partie gauche pointe sur c et dont la partie droite pointe sur mon deuxième doublet, s’écrira (c. ((a. b). nil)) ; etc. À noter que certaines listes, en particulier les listes circulaires (où le dernier pointeur pointe sur le premier élément de la liste), ne peuvent être représentées qu’à l’aide des doublets de pointeurs graphiques : ni la représentation à point ni la représentation parenthésée ne peuvent le faire. Gilles Bernard Université Paris 8 Vincennes B. Exercices sur la représentation à points 21 B.1 Conversion de doublets en représentation à points Reprenez les schémas à doublets graphiques des exercices de A.1 sur la représenta- tion interne des listes et donnez leur représentation à points. Le point se comporte comme un atome, et doit donc être séparé des atomes : a. ou.a (le point fait partie du nom de l’atome) sont différents de a. (l’atome a est suivi d’un point). Respectez les consignes de pretty-print données lors de l’exercice précédent, que je reprend ici en les complétant pour le point qui sert pour les doublets : après une parenthèse ouvrante, on ne met pas d’espace ; après une parenthèse fermante, on met un espace s’il y a ensuite un atome, un point ou une parenthèse ouvrante ; on n’en met pas s’il y a une parenthèse fermante ; après un atome, on met un espace s’il y a ensuite un atome, un point ou une parenthèse ouvrante ; on n’en met pas s’il y a une parenthèse fermante ; après un point, on met toujours un espace (il est forcément suivi d’un atome ou d’une ouvrante). Installer Lisp (voir sur Moodle) vous permettra de tester si votre représentation à points est correcte : tapez-la en la faisant précéder d’une apostrophe obligatoire (explications plus tard...). Si c’est trop compliqué, remettez à plus tard, je ne répondrai pas aux questions sur Lisp (à part sur l’installation) à ce stade. B.2 Conversion de représentation à points en doublets Donnez (avec Dia) la représentation en doublets de pointeurs des exemples sui- vants : 1. (a. ((b. c). (x. nil))) 2. ((a. nil). ((b. (c. nil)). nil)) 3. ((a. (b. nil)). (d. (c. nil))) 4. (a. (b. (c. (d. nil)))) 5. (a. ((b. nil). (d. (c. nil)))) 6. (a. (c. (d. ((b. e). nil)))) Programmation fonctionnelle 2021 22 CHAPITRE I. STRUCTURES DE DONNÉES 4. Représentation externe : le point de vue du problème L’idée de cette section n’est pas de parcourir la totalité des problèmes possibles et de leurs solutions, mais plutôt de vous faire découvrir, en cheminant, com- ment, malgré la diversité et la complexité des problèmes à traiter, on aboutit à des structures de données implémentables en machine. On passera en revue, en même temps, des éléments de vocabulaire qui appartiennent au bagage de tout informaticien. 4.1 Problèmes utilisant des structures de données rigides Il y a un certain nombre de cas où une structure de données rigide suffira pour représenter les données d’un problème : par exemple, la check-list d’une hotline ou celle du pilote d’un avion, puisque les éléments à contrôler sont toujours les mêmes. D’une manière générale, les agrégats sont très en faveur dans l’administration ; par exemple, ils serviront pour la représentation interne d’un formulaire à remplir. Mais la plupart du temps, c’est pour représenter des problèmes de très bas niveau (proches de la machine) qu’on utilisera de telles structures de données. De fait, le principal cas d’emploi de ces structures est l’implémentation de structures de données souples, comme le doublet de pointeurs qu’on a vu dans la partie précédente. La liaison nom - pointeur sur une valeur, qu’on trouve dans les carnets d’adresses d’environnements (ceux du moins qui ne sont pas gérés par hash-code), appartient également à ce type. Si le nom a une taille maximale de 11 caractères (exemple, les noms de fichier d’anciens systèmes comme CPM ou MsDOS), cette liaison peut se représenter comme 11 octets + un pointeur. Si le nom peut avoir n’importe quelle taille (systèmes modernes) grâce à une indirection, cette liaison peut se représenter par un doublet de pointeurs (le premier pointant sur le nom). Si le nombre total de liaisons possibles est limité, et s’il est crucial de trouver vite une liaison quelconque, on utilisera un vecteur pour représenter le carnet d’adresses lui-même. La situation se complique un peu quand un même nom peut avoir plusieurs valeurs, ce qui est le cas normalement en Lisp. Si le nom a un nombre fini de valeurs, par exemple 4, on aura un vecteur de 5 pointeurs. Si le nom a un nombre indéfini de valeurs, grâce à une indirection, on aura un vecteur de deux pointeurs, le second pointant sur le début de la liste des valeurs. Gilles Bernard Université Paris 8 Vincennes 4. Représentation externe : le point de vue du problème 23 Fig. 4.2 : Structure d’un fichier Linux 4.2 Un exemple particulièrement complexe La structure de données servant à gérer les fichiers sous Linux, depuis le système de fichiers ext2 (celui que vous avez utilisé pour formater votre disque est proba- blement ext4), est un bon exemple de la complexité que peut atteindre une com- binaison d’indirections (de pointeurs) et de structures rigides. On a voulu éviter l’emploi d’une structure de données souple, parce que les disques sont des espaces mémoires limités et qu’on a voulu accélérer l’accès aux données dans les fichiers. En voici le principe. Les disques sont calibrés en un nombre fini de blocs (en anglais clusters ; il s’agit de séquences d’octets qui ont toutes la même taille, qui dépend de la taille totale du disque) ; chaque fichier est une suite de blocs, dont au plus un (le dernier) est partiellement « vide » (c’est à dire rempli d’octets dont tous les bits sont à zéro). Chaque fichier est représenté par un vecteur de pointeurs dont les n premiers pointent sur les premiers blocs du fichier, dont le suivant pointe sur un vecteur de pointeurs pointant sur les n blocs suivants du fichier (s’il y en a), dont le suivant pointe sur un vecteur de pointeurs... ça devient trop long à expliquer, je vous laisse regarder l’image 4.2 (version simplifiée, en réalité les vecteurs sont plus longs). Du fait de cette représentation, l’accès aux n premiers blocs du fichier est un accès direct, plus rapide que l’accès aux n suivants, lui-même plus rapide que l’accès aux n suivants, etc. Une autre conséquence est que les fichiers ont une taille maximale indépassable, qui conduira sans doute un jour à abandonner cette Programmation fonctionnelle 2021 24 CHAPITRE I. STRUCTURES DE DONNÉES représentation. Si on avait choisi de représenter le fichier sous forme de liste, avec accès séquentiel, l’accès au premier bloc serait plus rapide que l’accès au deuxième (une indirection à franchir)… : l’accès au nième bloc suppose le franchissement de n − 1 indirections, alors que là, le nombre d’indirections est limité à 3, d’où des performances nettement supérieures. Dans le compromis entre performance (rapidité) et souplesse (évolutivité) qui est l’une des caractéristiques fondamentales de l’implémentation, on a choisi ici de privilégier la performance. Dans d’autres cas, c’est la souplesse qui est le plus important : ainsi, s’il est crucial de pouvoir représenter des nombres avec une précision maximale (pour envoyer une fusée sur Jupiter par exemple), on devra avoir des nombres qui puissent occuper la mémoire de centaines d’ordinateurs interconnectés (on parle de big numbers ou d’arbitrary precision, grands nombres ou nombres à précision arbitraire), on utilisera des structures de données souples. Employer des structures rigides suppose deux conditions : les données du pro- blème à traiter sont toujours de même nature et dans les mêmes relations, et le programme une fois réalisé n’aura pas besoin d’être adapté à d’autres données. Si vous n’êtes pas dans ces conditions, les structures rigides vous obligeront à refaire tout le programme à chaque modification des données (vous avez vu trop petit ? Recommencez), à prévoir tous les cas possibles avant essai ; de plus, si vous avez vu trop grand, il y a gaspillage de place. 4.3 Problèmes complexes : réseaux et objets La structure de données la plus complexe (pour la machine), le réseau (appelé aussi plus scientifiquement graphe), est aussi une de celles qui nous est le plus familière (cf nos réseaux de relations). On peut parcourir un réseau, à partir de n’importe quel point (appelé noeud), en suivant des liens (appelés aussi arrêtes ; pour aller d’un point à un autre plusieurs parcours sont souvent possibles. Quelques exemples : Choisir le meilleur trajet d’un endroit à un autre dans une ville. L’ensemble des endroits possibles forme un réseau, et les liens entre les différents endroits sont affectés de différentes caractéristiques : chemin où ne peuvent passer que les piétons, les vélos, les voitures, sens interdit, existence de bouchons, présence de feux…Il faut tenir compte de tout cela quand on calcule un trajet. Implémenter un jeu où il y a une quête à accomplir, des objectifs à passer, une clé à trouver, des monstres à affronter : on aura encore affaire à un réseau, dont les points peuvent être les endroits et les personnages, avec des contraintes de toutes sortes : sans la clé on ne peut ouvrir telle porte, pour vaincre les monstres il faut avoir trouvé tel outil, etc. Gilles Bernard Université Paris 8 Vincennes 4. Représentation externe : le point de vue du problème 25 Fig. 4.3 : Réseau (graphe) d’objets Construire une liste d’invités pour une soirée ; il ne faut pas inviter x et y, car ils se haïssent, et inviter trop d’informaticiens ensemble fera que la soirée se passera à discuter informatique, il faut un équilibre entre hommes et femmes, il faut quelques amuseurs, etc. Il y a un réseau complexe de relations entre les personnages, dont il faut tenir compte. Construire un système de gestion pour une entreprise type Benetton, fonc- tionnant en flux tendu : chaque fois que le stock d’un produit dans un des magasins baisse trop, il faut soit transférer des produits d’un magasin à l’autre, soit lancer la fabrication dans une des usines. Il faut prendre en compte le type de produit, la courbe des ventes, les coûts de transport d’un magasin à l’autre ou à l’usine, le coût de fabrication, pour faire le choix le moins coûteux. La figure 4.3 est la représentation schématique d’un réseau liant les noeuds A B C D E et F (qui pourront représenter des points de la ville, des pièces d’un chateau, des invités, des magasins et des usines, suivant le problème) ; les liens sont différenciés (les demandes qui transitent entre magasins ne sont pas les mêmes qu’entre magasin et usine) et ne sont pas en général symétriques (x peut aimer y alors que y déteste x) ; de surcroît, le réseau évolue dans le temps en fonction des situations (ex. x rencontre y : un évènement peut se produire). Mais, pour simplifier le schéma, je n’en ai pas tenu compte. Sachant qu’il faut, à la fin, se ramener à des structures de données rigides très simples, comment pourrait-on représenter une structure de données aussi Programmation fonctionnelle 2021 26 CHAPITRE I. STRUCTURES DE DONNÉES Fig. 4.4 : Le réseau décomposé en trois objets complexe ? Tout d’abord, on décompose le réseau ; chaque noeud du réseau est une structure de données, contenant une description du noeud (ex. informaticien, homme, amusant), une description de ses relations avec les autres noeuds (hait x, s’entend bien avec y, appartient au clan z) - c’est ce qu’on appelle la description statique, et une description de son comportement quand il se trouve dans certaines situations (par exemple, si le stock d’un produit en magasin baisse en dessous du seuil minimal) - c’est ce qu’on appelle la description dynamique. La structure de données correspondant à un noeud du réseau s’appelle un ob- jet : un objet est donc une structure de données possédant une description propre, une description de ses relations statiques avec d’autres objets, une description de ses relations dynamiques dans les différentes situations possibles. Le schéma ci- dessus se décompose donc en six objets (les six noeuds du réseau), six schémas ; la figure 4.4 contient trois de ces schémas, ceux des objets A, C et E. On se ramène ainsi à des structures à un seul point d’entrée (en gras dans les schémas) qui ont des liens avec d’autres structures. Même si ce n’est pas visible sur nos figures, ces liens sont typés (différenciés) et pas forcément symétriques, certains de ces liens sont statiques, d’autres sont dynamiques ; il faut y ajouter la description propre de chaque objet (non représentée), mais qui peut aussi se ramener à des liens avec des valeurs ou des classes. Voici un exemple de comment se présente la description d’un objet sous forme de texte : Dupont taille 180 aime Duchmol déteste Trucmuche est-un informaticien est-un homme réaction-aux-blagues rigole Les liens statiques sont appelés attribut (slot en anglais) de l’objet et ce qui vient Gilles Bernard Université Paris 8 Vincennes 4. Représentation externe : le point de vue du problème 27 ensuite est la valeur de cet attribut (value en anglais). Le couple attribut-valeur s’appelle une propriété (de l’objet Dupont). Ainsi taille est un attribut dont la valeur est un nombre (description propre), aime est un attribut dont la valeur est un lien sur l’objet Duchmol (lui-même décrit de la même manière). Les liens dynamiques (comme le dernier, qui décrit le comportement de l’objet) sont appelés sélecteur (on dit aussi stimulus) et ce qui vient ensuite une méthode (rigole) qu’on exécute si le stimulus est actif. Un réseau n’est pas directement représenté dans la mémoire : ce sont les noeuds de ce réseau (objets) qui sont effectivement représentés (à noter qu’on peut consi- dérer les liens comme les objets et les noeuds comme des liens entre ces objets). Modifier un réseau se ramène donc à modifier certains de ses objets. Le pro- blème majeur, dans le traitement des réseaux, est celui de la cohérence : par exemple, supprimer un objet nécessite de contrôler que les objets qui y sont liés n’ont plus de liens dessus. 4.4 Arborescences et listes d’associations Les objets appartiennent à la classe des arborescences (on dit aussi souvent arbres, même si certains distinguent les deux concepts). Une arborescence est une structure de données avec une racine unique, constituée de branches et de noeuds (au début et à la fin de chaque branche), telle que chaque branche peut se diviser en plusieurs branches, mais où deux branches ne peuvent se réunir en une seule - ce qui n’empêche pas que deux noeuds différents puissent être par ailleurs liés l’un à l’autre. Les noeuds d’où ne sortent pas de branches sont appelés des feuilles. L’arborescence ressemble à un agrégat, mais la différence - fondamentale - est que l’arborescence est une structure de données souple, où l’on peut rajouter ou supprimer des branches à volonté. Un autre exemple d’arborescence est la structure en répertoires du système de fichier ext4. La racine y est notée « / », chaque branche conduit à un répertoire ou à un fichier (en réalité Linux traite les répertoires comme des fichiers spéciaux), caractérisé par un nom, etc. Certains fichiers sont en fait des liens vers d’autres fi- chiers situés ailleurs dans l’arborescence, mais l’arborescence n’en tient pas compte (ce sont deux fichiers différents). La figure 4.5 montre le schéma d’une arborescence dont A est la racine. Les arborescences peuvent être traduites en liste, par la convention suivante : chaque noeud est une liste qui commence par le nom du noeud et qui continue avec la liste des noeuds qui lui sont rattachés. Si on ne regarde que le premier niveau, l’arborescence de la figure 4.5 se repré- sente comme (A) ; si on regarde les deux premiers niveaux, elle se représente comme Programmation fonctionnelle 2021 28 CHAPITRE I. STRUCTURES DE DONNÉES Fig. 4.5 : Une arborescence (A (B) (C) (D)) ; si on veut représenter l’ensemble de la structure, on obtient : (A (B (E) (F)) (C (G)) (D (H) (I))) Comme on sait représenter une liste en machine (avec des doublets de pointeurs par exemple), on peut représenter une arborescence. Les objets sont des arborescences un peu particulières, caractérisées par deux propriétés : 1. ils n’ont que trois niveaux : la racine, qui est le nom de l’objet, les branches, qui sont les attributs ou les sélecteurs, et les feuilles, qui sont les valeurs ou les méthodes ; 2. les branches sont de deux types différents (voire plus), suivant qu’elles re- présentent des liens statiques ou dynamiques. On les ramènera donc à des arborescences particulières, appelées listes d’as- sociations ou listes de propriétés, en anglais aussi map (en Python on parle aussi de dictionnaire), qui auront une structure dans le genre de celle qui suit : Gilles Bernard Université Paris 8 Vincennes 4. Représentation externe : le point de vue du problème 29 (Dupont (taille 180) (aime Duchmol) (déteste Trucmuche) (est-un informaticien) (est-un homme) (réaction-aux-blagues rigole) ) On a ainsi converti assez naturellement notre description textuelle en liste d’as- sociations ; dans chaque association, le premier mot, appelé clé, caractérise la branche (le lien) qui conduit vers l’objet dont le nom vient en second (ce nom est un pointeur sur un autre objet de même structure. La différence entre lien dynamique et lien statique n’est pas pertinente du point de vue de la représenta- tion interne, elle ne le deviendra que quand l’objet sera inséré dans une situation particulière. On n’aurait pas pu transformer directement le réseau en liste, à cause de l’exis- tence dans le réseau de ce qu’on appelle des circuits, c’est à dire du fait qu’un parcours qui part d’un objet peut très bien revenir à cet objet au bout d’un certain nombre d’étapes : le parcours est infini. En revanche, la chaîne « Réseau → Objet → Arborescence → Liste d’associations » permet de convertir n’importe quel pro- blème, aussi complexe qu’il paraisse, en structures de données rigides et donc de l’implémenter. Les listes d’associations ont bien d’autres usages que d’implémenter des objets. En voici quelques exemples, qui pourront vous donner une idée des descriptions à quoi elles peuvent être utilisées : (pantalon (poche-gauche clés tickets chewing-gum) (poche-droite trombonne ficelle porte-monnaie) ) (french (tea thé) (coffee café) (cloud nuage) (turkey dinde) (swarm essaim) (eventually finalement) ) Programmation fonctionnelle 2021 30 CHAPITRE I. STRUCTURES DE DONNÉES (liaison124 (nom A) (valeur 254) (type integer) (base 10) (signe négatif) (durée-de-liaison 15mn) ) La clé est donc un point d’entrée qui permet de sélectionner un sous-ensemble de données (qui pourrait contenir plus d’un élément : c’est en quelque sorte un ac- cès par nom qu’on a inventé ici. Bien sûr, ces listes peuvent être plus complexes ; chacune des sous-listes peut être elle-même une liste d’association. C’est égale- ment grâce à une liste d’associations (ou de propriétés) qu’on peut s’arranger pour qu’un même nom, par exemple A, soit associé à différentes valeurs dans différents environnement : (A (environnement1 valeur1) (environnement2 valeur2) (environnement3 valeur3) ) Pour développer votre sens des structures de données, allez dans une bibliothèque et déterminez les structures de données qui permettent le rangement des livres, physiquement (dans les rayons), et virtuellement (dans les fichiers d’index). 4.5 Langages de programmation, modes et structures de données rigides Les applications numériques étant autrefois majoritaires – et assez simples par ailleurs –, les vecteurs, tableaux et scalaires (dont le nom est d’ailleurs d’origine mathématique) étaient les structures de données privilégiées. Avec le développe- ment des renseignements bancaires et administratifs, les agrégats ont ensuite trou- vé leur place dans les langages – même si les puristes ne les appréciaient guère. Aujourd’hui la plupart des applications demandant un vrai travail de program- mation traitent de problèmes dont le nombre de cas n’est pas connu ou est infini, comme ce que les humains font tout le temps : combien de visages pouvons-nous reconnaître ? Dans un premier temps on a traité ces applications avec des struc- tures de données rigides, mais depuis plus de vingt ans, les utilisateurs et les programmeurs se sont mis à trouver insupportables les torsions que cela imposait Gilles Bernard Université Paris 8 Vincennes 4. Représentation externe : le point de vue du problème 31 (voir l’exemple sur les fichiers ext2). Même des problèmes apparemment simples, comme la reconnaissance d’une date dans un flot de données, s’avèrent plus retors qu’il n’y paraît : 1/10/83, 83/1/10, dix janvier mille neuf cent quatre vingt trois, 10 janvier 1983… Pour autant, les structures de données souples ou le traitement de problèmes mal définis ne sont pas des nouveautés : Lisp n’a qu’un an de plus que Fortran et les premiers ordinateurs étaient destinés à la reconnaissance de formes, problème mal défini s’il en est. Les pointeurs et les structures de données souples étaient réservées aux programmeurs systèmes (la gestion interne de la mémoire reposant sur des pointeurs, impossible de faire autrement) et aux programmeurs de l’intelligence artificielle. Pour le reste, les pointeurs paraissaient effrayants ; un ancien directeur d’IBM-France écrivit d’ailleurs, au début des années 1980, que les pointeurs sont trop complexes pour être expliqués à des étudiants et que le langage Pascal est plus pédagogique que Lisp, puisqu’il est plus rigide. C’est aussi pourquoi beaucoup d’anciens manuels se basent sur les structures de données rigides, et réservent les pointeurs pour une formation plus avancée (ainsi que la programmation objet). Mais à l’ère où les utilisateurs naïfs manipulent sans arrêt des objets, des ré- seaux et des pointeurs (par exemple les interfaces graphiques des systèmes avec leurs boutons – pointeurs), il est clair que le pointeur est devenu la base de la pro- grammation. C’est pourquoi, dans cette formation et tout particulièrement dans ce cours, nous avons particulièrement insisté sur la compréhension des pointeurs. Parmi les langages de programmation, ceux qui ne permettent pas de manipuler les adresses des objets sont passés de mode. On distinguera plutôt des langages où le pointeur est « caché », comme Lisp, Python ou Forth, et des langages où on doit le manipuler directement, comme C. En Lisp, les vecteurs et les agrégats n’existent pas forcément (certains dialectes de Lisp en ont, d’autres pas) : la liste prévaut ; on peut tout de même construire des structures de données rigides. En C, seules les structures de données rigides sont prédéfinies, les listes doivent être fabriquées. Python prédéfinit les listes d’associations. Chaque langage a ses structures de données favorites, même si toutes les structures de données peuvent être définies dans tous les langages de programmation. D’où deux conséquences importantes, qui me serviront ici de conclusion. D’une part, le choix du langage de programmation dépend des contraintes posées par le problème (complexité) au moins autant que des contraintes posées par la machine (performance, quantité de mémoire). D’autre part, il est souvent conseillé de s’at- taquer à un problème dans un langage qui permet une expression simple de la complexité du problème, produisant ainsi une maquette, avant de transposer cette maquette dans un langage qui permet de prendre en compte les contraintes liées à la machine. Programmation fonctionnelle 2021 32 CHAPITRE I. STRUCTURES DE DONNÉES C. Exercices sur les arbres Envoyez par mail les réponses aux exercices ci-dessous en suivant strictement les consignes suivantes : Mettez l’énoncé de chaque question avant la réponse. Joignez les réponses dans un fichier PDF incluant les images. Ecrivez dans le sujet du mail : Exo SD 3 Arbres. C.1 Conversion d’arbres en listes Voici quelques schémas représentant des arbres (représentation externe) ; représentez- les sous forme de liste et envoyez-moi les résultats par mail. Respectez les consignes de pretty-print déjà données dans les exercices précédents. 1. 5. 3. 6. 2. 4. Gilles Bernard Université Paris 8 Vincennes C. Exercices sur les arbres 33 C.2 Conversion de listes en arbres Voici quelques représentations internes d’arbres sous forme de listes ; à l’aide de Dia, en utilisant la feuille Arbre, ou de Consmaster, tracez leur représentation externe (sous forme de schéma) et envoyez-moi les résultats par mail. 1. (a (b (c (d) (e) (f)) (g (h)) (i))) 2. (b (i (d) (e) (f (g (h)) (c))) (a)) 3. (a (i (c (b (e (h))) (g (d)) (f)))) 4. (a (d (e (b (c (f))) (g)) (i)) (h)) 5. (i (b (e (h)) (a)) (f) (c) (d (g))) 6. (h (f (g (b)) (i (d) (e)) (c (a)))) Programmation fonctionnelle 2021 34 CHAPITRE I. STRUCTURES DE DONNÉES 5. Conclusion Les exercices que vous venez de faire vous ont permis de voir concrètement com- ment passer d’un problème qui s’exprime naturellement sous forme d’arborescence (par exemple la classification des espèces) à une représentation interne sous forme de doublets de pointeurs. Remarquez également que la représentation interne des arbres s’exprime en représentation externe des listes : cette structuration par couche est une caracté- ristique de l’informatique qui cherche, depuis le début, à s’affranchir des contraintes matérielles. Pour récapituler ce que nous avons vu : En partant des doublets de pointeurs, on peut avoir : Représentation in- terne en doublets de pointeurs → représentation à points → représentation en liste parenthésée → représentation d’arbre → représentation d’objets → représentation de réseau ; Ou, en partant d’un problème complexe, on peut avoir : Représentation d’un réseau → représentation en objets → représentation en arbre → représenta- tion en liste parenthésée → représentation à points → représentation interne en doublets de pointeurs. Potentiellement, cette transformation vous permettra de traiter n’importe quel problème, aussi complexe soit-il, sous trois conditions : avoir bien représenté au départ ses structures de données propres (réseau, arbre, liste) ; bien connaître les structures disponibles en machine ; avoir la rigueur nécessaire au passage de l’un à l’autre. Cette troisième condition est sans doute la plus difficile, au moins au début ; il faut en effet comprendre qu’un ordinateur est stupide comme n’importe quelle mé- canique, malgré son apparente pertinence (parfois). Un informaticien est d’abord quelqu’un qui accepte de devenir aussi stupide que la machine, pour en retour pouvoir lui insuffler un peu de son intelligence. Cette torsion intellectuelle est, se- lon mon expérience, l’obstacle majeur, celui qui décide si l’informatique c’est fait pour vous ou pas. De ce point de vue l’informatique n’est pas très différente de la sculpture, par exemple, qui nécessite de comprendre intimement la pierre avant de pouvoir la travailler. Gilles Bernard Université Paris 8 Vincennes Chapitre II Dialogue, processus et structures de contrôle Sommaire 1. Introduction.......................... 36 2. Processus, procédures et fonctions............. 37 3. Structures de contrôle fondamentales........... 39 4. Piles, queues.......................... 40 5. Pile des appels......................... 41 6. Conclusion........................... 43 36 CHAPITRE II. DIALOGUE, PROCESSUS, CONTRÔLE Fig. 1.1 : Fonctionnement d’une cellule 1. Introduction Nous avons jusqu’à maintenant décrit la mémoire d’un point de vue statique. D’un point de vue dynamique une machine à mémoire se comporte comme une cellule vivante, et plus particulièrement comme une cellule nerveuse (schéma 1.1). Elle possède des points d’entrée, appelés périphériques d’entrée (clavier, ssuivan- touris, écrant tactile, tablette graphique...), qui reçoivent des signaux, et des points de sortie, appelés périphériques de sortie (écran, enceintes...), qui émettent des signaux. Elle possède également une zone frontière (correspondant à la membrane des cellules), appelée mémoire tampon (anglais buffer), destinée à contenir les informations d’entrée et le résultat des calculs, à durée de vie limitée, et elle com- munique avec une mémoire à plus long terme, où sont stockées les informations qui servent à interpréter les données d’entrée et à calculer les données de sortie. Cette présentation très générale se décline ensuite de plusieurs manières suivant les machines, mais mon propos n’est pas de rentrer très profond dans la structure physique de l’ordinateur, simplement d’en introduire le principe. Il n’y a pas for- cément de différence de nature (physique) entre la mémoire tampon et la mémoire à long terme : c’est l’usage qu’on en fait qui les différencie. Du point de vue de la mémoire tampon la mémoire à plus long terme est également une sorte d’exté- rieur, un périphérique comme un autre, un périphérique de stockage. Le schéma 1.2 illustre cette vision plus courante. Gilles Bernard Université Paris 8 Vincennes 2. Processus, procédures et fonctions 37 Fig. 1.2 : Schéma du dialogue 2. Processus, procédures et fonctions L’activité de la machine se passe essentiellement dans la mémoire tampon. C’est là que s’exécutent les processus (anglais process, pluriel processes) qui sont derrière les évènements (visibles ou invisibles) qui se déroulent dans la machine et derrière l’interaction de la machine avec son environnement (les utilisateurs, par exemple). Allumer l’ordinateur lance un ensemble de processus (tests de la mémoire, des disques, du clavier...) ; cliquer sur une icône déclenche également un processus (qui à son tour peut en déclencher d’autres). Les processus modifient l’état de la mémoire (de la mémoire tampon d’abord, mais également possiblement de la mémoire à long terme). L’ordinateur tout entier peut être considéré, du point de vue dynamique, comme un processus extrêmement complexe. Chaque processus est lui-même comme une petite machine : il possède ses entrées, ses dfnsorties, sa mémoire tampon (mémoire de travail) et accède éven- tuellement à de la mémoire à plus long terme. Il coexiste avec d’autres processus, ayant eux même les mêmes éléments, de même que la machine coexiste (en réseau) avec d’autres machines. L’ensemble de ces éléments (entrées, mémoire à long terme, sorties, processus coexistants) constitue le contexte d’activation du processus. Avant d’être déclenchés (ou activés), les processus existent sous forme « dor- mante » en fait sous forme de structures de données stockées dans la mémoire à long terme (avec une adresse et éventuellement un nom), qu’on appelle des pro- cédures. La même procédure peut donner naissance à plusieurs processus (par exemple si on clique plusieurs fois sur la même icône ou que plusieurs utilisateurs connectés à un même serveur déclenchent la même procédure), qui se ressemblent mais diffèrent par leur contexte d’activation. Une procédure qui porte un nom est appelée une fonction : une fonction est donc accessible par son nom et pas seulement par son adresse ou par sa description (valeur). De la même façon que les données sont regroupées au sein de structures de Programmation fonctionnelle 2021 38 CHAPITRE II. DIALOGUE, PROCESSUS, CONTRÔLE données, qui définissent les rapports et l’interprétation des données inclues dans ces structures, les processus sont également regroupés par des structures de pro- cessus, appelées structures de contrôle. Les structures de contrôle déterminent les relations que les processus vont avoir les uns avec les autres ; et ce sont des relations temporelles (alors que dans les structures de données les relations sont spatiales), interprétables en termes de succession ou de parallélisme (synchronique ou non) temporel. Elles servent à organiser l’écoulement du temps et ses effets sur la mémoire. Un processus, tout comme une donnée, peut être simple ou complexe, c’est à dire être décomposable en processus plus élémentaires. Les processus les plus élémentaires sont l’accès à une adresse (déplacer une tête de lecture réelle ou virtuelle jusqu’à cette adresse) et la copie d’une donnée d’une adresse dans une autre (rendre identiques deux zones de mémoire). Plus les données sont complexes, et plus l’accès et la copie sont complexes. Le processus qui lit une donnée (dans ses entrées ou dans la mémoire à long terme) commence par accéder à l’adresse de la donnée puis copie cette donnée dans sa mémoire tampon. Le processus qui écrit une donnée (dans ses sorties ou dans la mémoire à long terme) commence par accéder à l’adresse de la donnée puis copie depuis la mémoire tampon cette donnée. Pour qu’un processus puisse dialoguer avec son environnement, il faut : qu’il lise des signaux en provenance de l’entrée ; qu’il interprète ou évalue ces signaux à partir des informations stockées dans sa mémoire à (plus) long terme, qu’il doit également copier dans la mémoire tampon ; cette interprétation peut le conduire ou non à modifier la mémoire à long terme ; qu’il écrive un signal dans sa sortie. Un processus qui lit à partir d’un périphérique commandé par l’utilisateur (on parle dans ce cas plutôt de saisie que de lecture) et qui écrit dans un périphérique accessible à l’utilisateur (on parle dans ce cas plutôt d’affichage que d’écriture) est appelé un interprête. C’est le cas par exemple du Shell, de Lisp et de Python. Chaque structure de données est naturellement associée à plusieurs procédures : une procédure qui construit la structure ; des procédures pour lire chaque donnée de la structure ; des procédures pour écrire chaque donnée de la structure. Auxquelles s’ajoutent les procédures qui accèdent à la structure de données elle- même, par valeur, par adresse ou par nom (cf chapitre précédent), ainsi que celles qui permettent d’associer un nom à une structure. Gilles Bernard Université Paris 8 Vincennes 3. Structures de contrôle fondamentales 39 3. Structures de contrôle fondamentales Les différentes structures de contrôle permettent de préciser les relations tempo- relles entre processus. Pour pouvoir définir un processus complexe, il faut combiner plusieurs pro- cessus à l’intérieur de celui-ci. C’est une relation d’inclusion : le processus maître doit attendre que l’autre termine son calcul pour pouvoir continuer son travail. Un processus qui en inclut un autre est appelé processus appelant, le proces- sus invoqué est appelé processus appelé, et la structure d’ensemble est appelé l’appel. Le type de structure de contrôle le plus fondamental, c’est quand deux pro- cessus doivent être activés l’un après l’autre. Cela recouvre deux structures de contrôle : la séquence, quand les deux processus n’ont pas de relation particulière directe, et l’