Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Pierre Weis Xavier Leroy LE LANGAGE CAML Deuxi` eme ´ edition Copyright 1992, 1

Pierre Weis Xavier Leroy LE LANGAGE CAML Deuxi` eme ´ edition Copyright 1992, 1993, 2009 Pierre Weis et Xavier Leroy. Ce texte est distribu´ e sous les termes de la licence Creative Commons BY-NC-SA. Le texte complet de la licence est disponible ` a l’adresse suivante : http://creativecommons.org/licenses/by-nc-sa/2.0/fr/legalcode Voici un r´ esum´ e des droits et conditions de cette licence. • Vous ˆ etes libres : – de reproduire, distribuer et communiquer cette cr´ eation au public – de modiﬁer cette cr´ eation • Selon les conditions suivantes : – Paternit´ e. Vous devez citer le nom de l’auteur original de la mani` ere indiqu´ ee par l’auteur de l’oeuvre ou le titulaire des droits qui vous conf` ere cette autorisation (mais pas d’une mani` ere qui sugg´ ererait qu’ils vous soutiennent ou approuvent votre utilisation de l’oeuvre). – Pas d’Utilisation Commerciale. Vous n’avez pas le droit d’utiliser cette cr´ eation ` a des ﬁns commerciales. – Partage des Conditions Initiales ` a l’Identique. Si vous modiﬁez, transformez ou adaptez cette cr´ eation, vous n’avez le droit de distribuer la cr´ eation qui en r´ esulte que sous un contrat identique ` a celui-ci. • A chaque r´ eutilisation ou distribution de cette cr´ eation, vous devez faire ap- paraˆ ıtre clairement au public les conditions contractuelles de sa mise ` a disposition. La meilleure mani` ere de les indiquer est un lien la page Web ci-dessus. • Chacune de ces conditions peut ˆ etre lev´ ee si vous obtenez l’autorisation du titu- laire des droits sur cette oeuvre. • Rien dans ce contrat ne diminue ou ne restreint le droit moral de l’auteur ou des auteurs. ` A mes parents, ` A Suzanne et Michel, ` A Lise, Marie, Jean-Baptiste et Ir` ene, ` A H´ el` ene. Pierre Weis Table des mati` eres Avant-propos xi I Programmer en Caml 1 Avertissement 3 1 Premiers pas 5 1.1 Id´ ees g´ en´ erales sur Caml 5 1.2 Dialoguer avec Caml 6 1.3 Les d´ eﬁnitions 6 1.4 Fonctions 8 1.5 Valeurs et programmes 13 1.6 Impression 13 1.7 Conventions syntaxiques 15 1.8 Diagrammes syntaxiques 17 2 R´ ecursivit´ e 19 2.1 Fonctions r´ ecursives simples 19 2.2 D´ eﬁnitions par cas : le ﬁltrage 27 2.3 Les tours de Hanoi 28 2.4 Notions de complexit´ e 31 3 Programmation imp´ erative 37 3.1 La programmation imp´ erative 37 3.2 Boucles 39 3.3 Manipulation de polynˆ omes 40 3.4 Impression des polynˆ omes 42 3.5 Caract` eres et chaˆ ınes de caract` eres 46 3.6 Les r´ ef´ erences 47 3.7 Un programme utilisant des r´ ef´ erences 49 3.8 R´ ecursivit´ e et boucles 50 3.9 R` egle d’extensionnalit´ e 52 3.10 Eﬀets et ´ evaluation 53 4 Fonctionnelles et polymorphisme 57 4.1 Notion de polymorphisme 57 4.2 Fonctions d’ordre sup´ erieur 59 4.3 Typage et polymorphisme 61 4.4 Curryﬁcation 64 viii Table des mati` eres 4.5 Une fonctionnelle de tri polymorphe 65 4.6 La pleine fonctionnalit´ e 67 4.7 Composition de fonctions 70 5 Listes 75 5.1 Pr´ esentation 75 5.2 Programmation assist´ ee par ﬁltrage 77 5.3 Tri par insertion 78 5.4 Fonctionnelles simples sur les listes 81 5.5 Les polynˆ omes creux 83 5.6 Filtrage explicite 84 5.7 Op´ erations sur les polynˆ omes creux 85 5.8 Animation des tours de Hanoi 88 5.9 Fonctionnelles complexes sur les listes 91 5.10 Eﬃcacit´ e des fonctions sur les listes : ´ etude de cas 98 5.11 Listes et r´ ecurrence 103 5.12 ` A la recherche de l’it´ erateur unique 105 6 Les structures de donn´ ees 109 6.1 Polynˆ omes pleins et polynˆ omes creux 109 6.2 Types sommes ´ elabor´ es 113 6.3 Les types somme 116 6.4 Les types produit 116 6.5 M´ elange de types somme et types produit 118 6.6 Structures de donn´ ees mutables 118 6.7 Structures de donn´ ees et ﬁltrage 120 6.8 Structures de donn´ ees et r´ ecurrence 122 7 Le docteur 125 7.1 Vue d’ensemble 125 7.2 Les exceptions 126 7.3 Fonctions de recherche dans les listes 130 7.4 Traitements de chaˆ ınes de caract` eres 133 7.5 Cam´ elia 135 7.6 Dialogue avec l’utilisateur 140 7.7 Exemple de session 143 7.8 Pour aller plus loin 144 8 Graphisme 147 8.1 Fractales 147 8.2 Le graphisme de Caml 148 8.3 Les nombres en repr´ esentation ﬂottante 149 8.4 Le crayon ´ electronique 149 8.5 Premiers dessins 152 8.6 Le ﬂocon de von Koch 154 9 Syntaxe abstraite, syntaxe concr` ete 155 9.1 Pr´ esentation 155 9.2 Le retard ` a l’´ evaluation 156 ix 9.3 L’´ evaluation des ordres du langage graphique 158 9.4 Syntaxe et s´ emantique 159 9.5 Notions d’analyses syntaxique et lexicale 160 9.6 Analyse lexicale et syntaxique 161 9.7 Ajout des proc´ edures 168 10 Programmes ind´ ependants et modules 179 10.1 Chargement de ﬁchiers 179 10.2 Programmes ind´ ependants 180 10.3 Entr´ ees-sorties de base 181 10.4 Programmes en plusieurs modules 183 10.5 Interfaces de modules 187 10.6 Compilations interactives 190 11 Interfaces graphiques 193 11.1 Structure d’une interface graphique 193 11.2 Relier des composants entre eux 194 11.3 Un convertisseur de devises 196 11.4 Le jeu du taquin 199 11.5 Pour aller plus loin 201 II Exemples complets 203 Avertissement 205 12 D´ emonstration de propositions 207 12.1 La logique math´ ematique 207 12.2 Calculs de tables de v´ erit´ e 210 12.3 Le principe des d´ emonstrations 212 12.4 Repr´ esentation et v´ eriﬁcation des propositions 213 12.5 Syntaxe concr` ete des propositions 217 12.6 Le v´ eriﬁcateur de tautologies 221 12.7 Exemples de th´ eor` emes 223 12.8 Pour aller plus loin : l’analyseur lexical universel 228 12.9 Pour aller encore plus loin : le hachage 232 13 Compression de ﬁchiers 237 13.1 La compression de donn´ ees 237 13.2 Plan du programme 238 13.3 L’algorithme de Huﬀman 240 13.4 Annexes 247 13.5 Mise en pratique 252 13.6 Pour aller plus loin 252 14 Simulation d’un processeur 255 14.1 Le pico-processeur 255 14.2 Le simulateur 260 14.3 L’assembleur 267 14.4 Pour aller plus loin 275 x Table des mati` eres 15 Compilation de mini-Pascal 277 15.1 Syntaxe abstraite, syntaxe concr` ete 277 15.2 Typage 283 15.3 Compilation 289 15.4 Pour aller plus loin 304 16 Recherche de motifs dans un texte 305 16.1 Les motifs 305 16.2 Syntaxe abstraite et syntaxe concr` ete des motifs 306 16.3 Les automates 309 16.4 Des expressions rationnelles aux automates 310 16.5 D´ eterminisation de l’automate 313 16.6 R´ ealisation de la commande grep 319 16.7 Annexe 320 16.8 Mise en pratique 321 16.9 Pour aller plus loin 321 III Introspection 323 17 Ex´ ecution d’un langage fonctionnel 325 17.1 Le langage mini-Caml 325 17.2 L’´ evaluateur 326 17.3 La boucle d’interaction 331 17.4 Mise en œuvre 333 17.5 Pour aller plus loin 334 17.6 Annexe 336 18 Un synth´ etiseur de types 339 18.1 Principes de la synth` ese de types 339 18.2 L’algorithme de synth` ese de types 344 18.3 Repr´ esentation des types 348 18.4 L’uniﬁcation 353 18.5 Inconnues, g´ en´ eralisation et sp´ ecialisation 356 18.6 Impression des types 357 18.7 La boucle d’interaction 358 18.8 Mise en œuvre 359 18.9 Pour aller plus loin 360 19 En guise de conclusion 365 19.1 Une m´ ethodologie de programmation 365 19.2 La compilation de Caml 367 Index 373 Avant-propos On prononce Caml avec le « ca » de caf´ e et le « mel » de melba. aml est un langage de programmation de conception r´ ecente qui r´ eussit ` a ˆ etre ` a la fois tr` es puissant et cependant simple ` a comprendre. Issu d’une longue r´ eﬂexion sur les langages de programmation, Caml s’organise autour d’un petit nombre de notions de base, chacune facile ` a comprendre, et dont la combinaison se r´ ev` ele extrˆ emement f´ econde. La simplicit´ e et la rigueur de Caml lui valent une popularit´ e grandissante dans l’enseignement de l’informatique, en particulier comme premier lan- gage dans des cours d’initiation ` a la programmation. Son expressivit´ e et sa puissance en font un langage de choix dans les laboratoires de recherche, o` u il a ´ et´ e utilis´ e pour traiter des probl` emes parmi les plus ardus de l’informatique : d´ emonstration assist´ ee par ordinateur, analyses automatique de programmes, syst` emes de r´ e´ ecriture, compila- tion et m´ etacompilation. En bref, Caml est un langage facile avec lequel on r´ esout des probl` emes diﬃciles. Longtemps r´ eserv´ e ` a de grosses machines coˆ uteuses, le langage Caml est main- tenant disponible gratuitement sur toute une gamme de machines, du micro-ordinateur personnel (PC, Macintosh, . . . ) aux stations de travail les plus puissantes, ce qui le rend accessible ` a un vaste public, de l’amateur curieux au professionnel chevronn´ e en passant par l’´ etudiant informaticien. ` A ce vaste public, Caml apporte une nouvelle approche de la programmation, des plus uploads/S4/ le-langage-caml.pdf