Programmation Avance(INF441)

Franois Pottier

8 mars 2016

2

Table des matires

Introduction 5

1 Donnes et comportement 71.1 Donnes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.1.1 Blocs, tiquettes et champs en Java . . . . . . . . . . . . . . . . . . . . . . 81.1.2 Blocs, tiquettes et champs en OCaml . . . . . . . . . . . . . . . . . . . . 91.1.3 Sommes, produits et rcursivit . . . . . . . . . . . . . . . . . . . . . . . 10

1.2 Comportement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141.2.1 Procdures et fonctions traditionnelles . . . . . . . . . . . . . . . . . . . . 161.2.2 Fonction = clture = objet = service . . . . . . . . . . . . . . . . . . . . . 171.2.3 Cltures en Java 8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201.2.4 Suspensions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

1.3 Modle de cot . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

2 Abstraction 272.1 Abstraction fonde sur un type abstrait . . . . . . . . . . . . . . . . . . . . . . . 302.2 Abstraction fonde sur une clture . . . . . . . . . . . . . . . . . . . . . . . . . . 34

3 Paramtrisation 373.1 Paramtrer vis--vis dun type . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

3.1.1 Polymorphisme en OCaml . . . . . . . . . . . . . . . . . . . . . . . . . . 383.1.2 Polymorphisme en Java . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

3.2 Paramtrer vis--vis dune fonction . . . . . . . . . . . . . . . . . . . . . . . . . . 423.3 Paramtrer vis--vis dun type muni doprations . . . . . . . . . . . . . . . . . 44

3.3.1 Structures, signatures, et foncteurs en OCaml . . . . . . . . . . . . . . . . 453.3.2 Signatures paramtres et polymorphisme contraint en Java . . . . . . . 49

4 Itration 554.1 Rducteurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

4.1.1 Sans accumulateur explicite . . . . . . . . . . . . . . . . . . . . . . . . . . 574.1.2 Avec accumulateur explicite . . . . . . . . . . . . . . . . . . . . . . . . . . 59

4.2 Itrateurs modifiables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 624.3 Flots . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

Solutions des exercices 71

Bibliographie 143

Index 144

3

4 TABLE DES MATIRES

Introduction

Ce cours sadresse aux lves de deuxime anne de lcole Polytechnique, cest--dire destudiants ayant acquis une certaine familiarit dune part avec la programmation (en particulieren Java) et dautre part avec quelques algorithmes et structures de donnes lmentaires.

Lobjectif de ce cours est dapprofondir la matrise de la programmation. Son propos nestdonc pas de prsenter de nouveaux algorithmes ou structures de donnes. Il ne sagit pasnon plus de passer en revue les dtails de tel ou tel langage de programmation, ni de donnerun catalogue de trucs et astuces connus des vieux programmeurs. Lobjectif est de mettrelaccent sur un petit nombre de concepts fondamentaux, communs la plupart des langagesde programmation. Parmi ces concepts, labstraction joue un rle central, car elle seule permetde construire des logiciels complexes partir de composants simples et rutilisables. Nousmettons en lumire les deux principales significations de ce mot, qui rappellent respectivementles quantifications existentielle et universelle familires aux mathmaticiens. Nous tudionsgalement les diffrentes formes concrtes que peut prendre labstraction dans un langage deprogrammation.

Afin de mieux souligner la faon dont un mme concept existe sous des formes lgrementdiffrentes dans plusieurs langages de programmation, nous utilisons Java et OCaml. Noustablissons, chaque fois que cela est possible, des liens entre ces deux langages. Nous nousefforons de nemployer quun fragment relativement rduit, essentiel, de ces langages. Noussupposons connues les variables (modifiables en Java, immuables en OCaml), les structures decontrle lmentaires (if, switch, while en Java ; if, match, while en OCaml), et les mthodesou fonctions rcursives. Le Chapitre 1 propose des remarques et exercices qui servent de rappelou dintroduction ces notions, surtout en ce qui concerne OCaml.

Sagit-il dun cours de programmation avance , comme le suggre immodestement sontitre ? Le lecteur ou llve en sera juge. Ce cours est constitu de huit sances seulement, ce quien limite bien sr la porte. Disons simplement quil ne sagit plus dapprendre crire du codepour rsoudre un problme fix, mais dapprendre organiser son code pour le rendre volutif,rutilisable dans de nombreuses situations, applicable donc de nombreux problmes.

Aperu

Le Chapitre 1 rappelle comment les donnes et les comportements sont reprsents, enJava et en OCaml, laide de concepts tels que les structures de donnes algbriques, les objets,et les fonctions. Il souligne le fait que lorganisation de la mmoire (la pile, le tas) est la mmepour ces deux langages. Il rappelle quel est le cot asymptotique (en temps et en espace) desoprations lmentaires, comme la cration dun objet ou lappel dune mthode. La sance 1correspond ce chapitre.

Le Chapitre 2 met en avant la notion dabstraction, comprise comme une forme disolationvolontaire entre composants logiciels. Labstraction favorise la construction de logiciels degrande envergure partir de composants rutilisables et qui peuvent voluer indpendammentles uns des autres. Les sances 2 et 3 correspondent ce chapitre.

Le Chapitre 3 met laccent sur le fait que abstraire peut aussi signifier paramtrer.Un composant peut tre paramtr par une valeur, par un type, voire par une collection de

5

6 Introduction

types et de valeurs, cest--dire par un autre composant. En ce sens, labstraction multiplieles possibilits dassemblage entre composants, et facilite donc nouveau la construction delogiciels modulaires. Les sances 4 et 5 correspondent ce chapitre.

Le Chapitre 4 aborde le problme de litration. Comment crire du code rutilisablepour produire ou pour consommer une suite dlments ? Cette question trs concrte eten apparence trs simple soulve en ralit la question fondamentale de la rpartition ducontrle entre producteur et consommateur. Elle admet plusieurs familles de solutions, parmilesquelles nous tudions les rducteurs, galement connus sous le nom de fold , frquentsen OCaml ; les itrateurs modifiables, galement appels iterators , frquents en Java ; et lesitrateurs immuables, galement connus sous le nom de flots ou streams . Les sances 6, 7et 8 correspondent ce chapitre.

Principales rfrences bibliographiques

Ce polycopi a vocation rester relativement court et proche du contenu des huit sances.Pour aller plus loin, je recommande chaudement la lecture de tout ou partie des deux ouvragessuivants :

1. Program development in Java : abstraction, specification, and object-oriented design .Barbara Liskov et John Guttag (2001).Ce livre est consacr la construction modulaire de programmes. La notion dabstractiony joue, comme ici, un rle central. Les exemples sont crits en Java, mais les conceptsprsents sont indpendants de ce langage. Ce livre est beaucoup plus complet que nousne pouvons ltre ici.

2. Apprendre programmer avec OCaml : algorithmes et structures de donnes .Sylvain Conchon et Jean-Christophe Fillitre (2014).Une premire partie est consacre lapprentissage dOCaml laide dexemples varis.Les deux parties qui suivent prsentent diffrentes structures de donnes et algorithmes.Le code y est toujours crit dans un style abstrait, modulaire et concis, ce qui en fait uneexcellente cole de labstraction.

propos de ce document

Afin de clarifier le contenu de ce polycopi, des remarques isoles expliquent certainesides quil nest pas essentiel de connatre, mais qui peuvent nanmoins tre intressantes. Defaon symtrique, des dtails isols dcrivent certains aspects pratiques qui ne sont pastoujours dignes dintrt dun point de vue fondamental, mais qui peuvent nanmoins treutiles !

Ce polycopi contient des exercices corrigs relativement nombreux. Les exercices fontpartie du cours. Cest souvent grce un exercice que lon saperoit que lon navait pasvraiment compris... et que lon progresse vers une meilleure comprhension du cours. Laplupart sont des exercices de programmation. Aussi, il faut les traiter non pas sur papier, maisavec laide de la machine. Vrifiez que votre code est accept par un compilateur Java ouOCaml, et testez-le.

Ce cours a eu lieu pour la premire fois en 20142015. Vous avez donc entre les mains laseconde itration de ce polycopi. Elle contient certainement encore de nombreuses imperfec-tions. Je vous remercie par avance de bien vouloir me signaler les erreurs que vous remarquerezet me faire part de vos remarques et suggestions damlioration.

Franois Pottier

Chapitre 1

Donnes et comportement

Un langage de programmation est dit gnraliste ou general-purpose sil a vocation tre utilis dans de nombreux domaines dapplication, et non pas seulement dans un domaineprcis, pour lequel il serait spcialis, et auquel il serait limit.

Les langages gnralistes sont Turing-complets : dune faon ou dune autre, ils permettentdexprimer tous les algorithmes concevables. De plus, ces langages sefforcent doffrir des faci-lits pour que ces algorithmes scrivent sous une forme concise, claire, et gnrale. Parmi lesfacilits communes presque tous ces langages, on trouve ( quelques dtails prs) une mmeorganisation des donnes en mmoire, et une mme faon de dcrire des comportements, viades mthodes ou des fonctions.

Lobjet de ce premier chapitre est de souligner cette uniformit conceptuelle. Bien quedes langages comme Java, OCaml, Scala, C#, Scheme, Python, ou JavaScript puissent semblerassez diffrents en apparence, ils sappuient en ralit sur les mmes concepts fondamentaux.Il est important de comprendre cela avant de pousser plus loin notre tude.

Dans ce chapitre, nous rappelons dabord comment les donnes sont structures dans letas (1.1). Ensuite, nous prsentons un certain nombre dentits (fonctions, objets, suspensions)qui marient donnes et comportement et offrent lutilisateur un service abstrait (1.2). Enfin,nous dcrivons brivement le modle de cot commun Java et OCaml, cest--dire le cot entemps et en espace de chaque opration lmentaire (1.3).

Parmi les langages de programmation, on distingue ceux qui sont typs statiquement,comme Java, OCaml, Scala, C#, o le compilateur impose le respect dune certaine discipline,et garantit ainsi labsence de certaines erreurs ; et ceux qui sont typs dynamiquement, commeScheme, Python, JavaScript, o cette discipline nest pas impose pendant la compilation, maisseulement pendant lexcution du programme. (Dautres encore, comme C, ne sont pas typs ausens o jemploie ce mot. Mme si C impose une certaine discipline de types, il existe des erreursque C ne dtecte ni la compilation, ni lexcution.) Dans les langages typs statiquement,les types offrent un vocabulaire pour dcrire les donnes et les comportements. Aussi, dansce premier chapitre, nous utilisons les types de Java et dOCaml pour dcrire les objets quenous construisons. Dans les langages typs dynamiquement, ce vocabulaire descriptif nexistepas officiellement. Nanmoins, donnes, fonctions, objets sont organiss de la mme manire.Les concepts fondamentaux que nous prsentons dans ce chapitre valent donc pour tous leslangages typs cits plus haut, quils soient typs statiquement ou dynamiquement.

1.1 Donnes

Les langages de programmation qui nous intressent proposent un mcanisme dallocationdynamique de mmoire. Cela signifie quil existe une zone de la mmoire, nomme tas ou heap , dans laquelle il est possible tout moment (dans la limite de lespace disponible) de

7

8 CHAPITRE 1. DONNES ET COMPORTEMENT

crer de nouveaux blocs de mmoire, ou simplement blocs . Un bloc de mmoire est parfoisgalement appel objet , mais nous viterons cette terminologie, car le mot objet a unsens plus riche dans le cadre de la programmation oriente objets (1.2).

La structure dun bloc est simple : un bloc est en gnral compos dune tiquette et duncertain nombre de champs. Ltiquette indique quelle est la nature de ce bloc, et dterminele nombre et la nature des champs. Chaque champ contient une valeur, cest--dire soit unevaleur primitive (un nombre entier, un nombre virgule flottante, un caractre, etc.), soit unpointeur vers un autre bloc.

1.1.1 Blocs, tiquettes et champs en Java

titre dexemple, voici un fragment de code Java extrait du polycopi INF411 (Fillitre,2014). Pour les besoins de lalgorithme de Huffman, on souhaite construire un arbre binaire.Plus prcisment, on souhaite allouer (dans le tas) des blocs, et relier ces blocs les uns auxautres par des pointeurs, de faon former un arbre binaire. La forme de ces blocs peut tredcrite ainsi en Java :

abstract class HuffmanTree {int freq;// constructeur et m thodes omis

}class Leaf extends HuffmanTree {

final char c;// idem

}class Node extends HuffmanTree {

HuffmanTree left , right;// idem

}

Cette manire de reprsenter les arbres en Java est parfois appele composite pattern.Pour Java, ltiquette dun bloc allou dans le tas est simplement sa classe. On peut donc

crer des blocs tiquets Leaf, laide de lexpression new Leaf (...), ou bien des blocstiquets Node, laide de lexpression new Node (...). La classe HuffmanTree est abstraite :il est interdit dcrire new HuffmanTree (...). Un bloc x de type HuffmanTree a donc pourtiquette soit Leaf, soit Node.

Notons que, lorsquon crit le bloc x , on veut dire en ralit le bloc situ dans le tas ladresse x , voire, de faon encore plus explicite, le bloc situ dans le tas ladresse qui estcontenue dans la variable x .

Un bloc tiquet Leaf a deux champs, nomms respectivement freq et c. Tous deuxcontiennent des valeurs primitives, savoir respectivement un entier et un caractre. Unbloc tiquet Node a trois champs, nomms respectivement freq, left et right. Le premiercontient un entier, tandis que les deux suivants contiennent des pointeurs vers dautres blocs,censs reprsenter les sous-arbres gauche et droit. On voit que le nombre et la nature deschamps dun bloc dpendent de son tiquette.

Lorsquon dispose dun bloc x de type HuffmanTree, on ne sait pas a priori si cest une feuilleou un nud, donc sil a un champ c ou bien des champs left et right. (On sait toutefois, dansles deux cas, quil a un champ freq.) Il faut donc analyser ltiquette avant de pouvoir accderaux champs. En Java, cette analyse se fait typiquement via un appel de mthode. Supposonsquune mthode, par exemple traverse, est dclare dans la classe abstraite HuffmanTree etdfinie dans les deux sous-classes Leaf et Node. Alors, un appel de la forme x.traverse(...)consulte ltiquette du bloc x et choisit, parmi les deux dfinitions de la mthode traverse,celle qui est approprie. (Ce mcanisme est connu sous le nom de dynamic dispatch .) Ladfinition de la mthode traverse situe dans la classe Leaf a accs au champ c, tandis que

1.1. DONNES 9

celle situe dans la classe Node a accs aux champs left et right. Ainsi, rptons-le, lanalysede ltiquette permet laccs aux champs.

Remarque 1.1 (Cast et instanceof) Lanalyse de ltiquette dun objet x peut se faire nonseulement via un appel de mthode, comme nous lavons illustr ci-dessus, mais aussi via untest de la forme x instanceof Node ou bien via un cast de la forme (Node) x.

Lexpression x instanceof Node teste si ltiquette du bloc x est Node. Si oui, elle renvoietrue. Si non, elle renvoie false.

Lexpression (Node) x teste elle aussi si ltiquette du bloc x est Node. Si oui, elle renvoie x.Si non, elle lance une exception ClassCastException. Du point de vue du compilateur, si x a letype HuffmanTree, alors (Node) x a le type Node. Ce cast explicite, qui peut chouer, permetdonc de convertir le type de x de HuffmanTree vers Node. On lappelle parfois downcast ou conversion vers le bas , parce que Node est sous-classe de HuffmanTree. Rappelons, titrede comparaison, que lupcast ou conversion vers le haut , par exemple de Node versHuffmanTree, est toujours permise : tout objet de type Node peut tre considr comme unobjet de type HuffmanTree. Cette conversion est implicite et nchoue jamais.

1.1.2 Blocs, tiquettes et champs en OCaml

Si lon transcrit cet exemple en OCaml, alors il scrit de faon diffrente en apparence, maisla structure des blocs allous dans le tas est exactement la mme. Voici la dfinition du typedes arbres :

type tree =| Leaf of int * char| Node of int * tree * tree

Cette dfinition indique quun bloc de type tree porte soit ltiquette Leaf, soit ltiquetteNode. Ces tiquettes sont appeles constructeurs de donnes, en anglais data constructors ,ou bien constructeurs tout court. Cette dfinition indique de plus que si ltiquette est Leaf,alors le bloc a deux champs, dont les types sont respectivement int et char ; tandis que siltiquette est Node, alors le bloc a trois champs, dont les types sont respectivement int, treeet tree. La structure des blocs est donc bien la mme que dans le cas de Java.

Pour crer un nouveau bloc, en Java, on crit par exemple new Leaf (f, c). En OCaml,lexpression correspondante est Leaf (f, c). Cela explique pourquoi Leaf est appel unconstructeur : on lutilise pour construire (cest--dire allouer et initialiser) un nouveau bloc.

Comme en Java, en OCaml, il faut analyser ltiquette avant de pouvoir accder aux champs.En OCaml, cette analyse se fait obligatoirement via une expression match ... with .... Onpeut la considrer comme une forme gnralise de linstruction switch que lon trouve en Cet Java. Si lon dispose dun bloc x de type tree, elle permet dexaminer ltiquette de x etdadopter un comportement diffrent suivant que cette tiquette est Leaf ou Node. Par exemple,une fonction traverse peut tre dfinie ainsi :

let rec traverse (path : string ) (x : tree) : unit =match x with| Leaf (_, c) ->

Hashtbl .add dictionary c path| Node (_, x0 , x1) ->

traverse (path ^ "0") x0;traverse (path ^ "1") x1

Cette expression match x with ... comporte deux branches, qui correspondent aux deuxvaleurs possibles de ltiquette porte par le bloc x. Dans la premire branche apparat unenouvelle variable locale c, dans laquelle on va trouver la valeur du second champ du bloc x.De mme, les variables x0 et x1 sont locales la seconde branche, et on y trouve les valeursdes second et troisime champs du bloc x. Le premier champ du bloc x nest pas utilis ici ;

https://docs.oracle.com/javase/7/docs/api/java/lang/ClassCastException.html

10 CHAPITRE 1. DONNES ET COMPORTEMENT

cest pourquoi on a prfr crire _ plutt que dintroduire une variable locale freq que lonnutilisera pas. On retrouve, en OCaml, le fait que lanalyse de ltiquette permet laccs auxchamps : en dehors de linstruction match, il nexiste aucun moyen daccder aux champs dunbloc x de type tree.

1.1.3 Sommes, produits et rcursivit

Dans les deux langages, Java et OCaml, les blocs qui constituent un arbre sont dcritspar un type que lon peut qualifier de somme de produits. En effet, ltiquette dun bloc estsoit Leaf, soit Node. Or, on parle traditionnellement de somme lorsque lon a un choix entreplusieurs alternatives. Ensuite, dans la branche Leaf, on a un champ freq et un champ c ;dans la branche Node, on a un champ freq et un champ left et un champ right. Or, on parletraditionnellement de produit lorsque lon a simultanment plusieurs composantes.

Dans les deux langages, Java et OCaml, ces blocs sont dcrits par un type rcursif. Cephnomne est clairement visible en OCaml, o la dfinition du type tree fait rfrence autype tree lui-mme : les deuxime et troisime composantes dun arbre tiquet Node sontelles-mmes des arbres. Il est moins visible en Java, parce quon ncrit pas explicitement le faitque un bloc de type HuffmanTree est soit un bloc de classe Leaf, soit un bloc de classe Node .Si on lcrivait, on verrait que la dfinition de HuffmanTree fait rfrence Leaf et Node, tandisque les dfinitions de Leaf et Node font rfrence HuffmanTree.

Les trois concepts que nous venons de mettre en vidence type somme, type produit, typercursif sont fondamentaux. Ils permettent de dfinir tous les types de donnes usuels. Unmathmaticien ou un informaticien thoricien, qui aime employer des notations plus concisesque Java ou OCaml, dfinirait ainsi notre type des arbres :

T = (Int Char) + (Int T T)

Il sagit bien dune dfinition rcursive, dont le membre droit est une somme de produits.On parle de type algbrique pour dsigner un type construit ainsi laide de sommes, deproduits, et de rcursivit.

Remarque 1.2 (GC) En Java et en OCaml, il nexiste aucun moyen pour le programmeur dedemander la dsallocation dun bloc. Chaque bloc est libr automatiquement, ds quil devientinaccessible, par un systme appel glaneur de cellules ou garbage collector. (Un objet estaccessible si on peut y parvenir, partir dune variable, en suivant une srie de pointeurs.)Cela offre confort et sret : on ne peut pas dtruire, par erreur, un bloc dont on aura encorebesoin. Toutefois, il peut tre difficile de prdire quel moment un bloc sera dsallou. LesExercices 4.26 et 4.27 illustrent certaines des subtilits de ce mcanisme.

Remarque 1.3 (Unit) En OCaml, le type unit est un type algbrique une seule branche,dfini par type unit = (). Il existe donc une (et une seule) valeur de ce type, savoir ().Le nom unit provient du fait que ce type est un produit de zro champs, donc lunit duproduit. En langage mathmatique, on le note parfois 1.

Ce type qui premire vue pourrait sembler dnu dintrt pratique joue en ralit unrle trs important. En effet, en OCaml, on considre que chaque fonction a exactement unargument et un rsultat. Une fonction sans argument doit donc tre simule laide dunefonction un argument de type unit. De mme, une fonction sans rsultat est simule laidedune fonction un rsultat de type unit.

En Java, de faon analogue, on peut poser public class Unit {} et construire une valeurde ce type en crivant new Unit (). Le mot-clef void de Java, qui permet dindiquer quunemthode renvoie zro rsultats, correspond en ralit au mme concept.

Remarque 1.4 (Pointeur nul et options) Java a un pointeur nul. Si une variable x a le typeHuffmanTree, elle contient soit la valeur null, soit ladresse dans le tas dun bloc tiquet Leafou Node. Bien que parfois utile pour des raisons defficacit, la prsence du pointeur null

1.1. DONNES 11

est source derreurs, puisquelle ajoute silencieusement une alternative que le programmeurrisque doublier, ce qui conduit au lancement dune exception NullPointerException. Nousviterons autant que possible lemploi du pointeur nul.

OCaml na pas de pointeur nul. Lorsquon souhaite dcrire soit rien du tout, soit unevaleur de type A , on emploie un type somme deux branches, de faon reprsenterces deux alternatives. En langage mathmatique, ce type somme scrirait 1 + A, o 1 estle type unit (Remarque 1.3). En OCaml, on emploie le type a option, dfini ainsi dansla bibliothque : type a option = None | Some of a. Ainsi, un bloc de type int optionporte soit ltiquette None, soit ltiquette Some, et dans le second cas, il a un champ de typeint. Par exemple, None et Some 42 sont des blocs de type int option. LExercice 3.8 donne unexemple dutilisation du type int option.

Remarque 1.5 (Champs modifiables et champs immuables) Une fois que lon a allou unbloc dans le tas, est-il permis de modifier le contenu de ses champs ? On peut, au choix,interdire ou autoriser cela. On dit quun champ est modifiable ou mutable sil est permis demodifier son contenu. Il est immuable ou immutable dans le cas contraire. En Java, chaquechamp est par dfaut modifiable, mais on peut rendre un champ immuable en prcdant sadclaration du mot-clef final. En OCaml, la convention est inverse : chaque champ est pardfaut immuable, mais (dans le cas dun type enregistrement, voir le Dtail 1.11) on peutrendre un champ modifiable en prcdant sa dclaration du mot-clef mutable. LExercice 1.2en donne un exemple.

Remarque 1.6 (Variables locales) Une variable locale est soit un paramtre dune fonction,soit une variable introduite dans le corps dune fonction.

En Java, on crit par exemple int x pour dclarer une variable x de type int. En OCaml,une variable locale est introduite par les constructions fun x -> ... ou let x = ... in ...ou encore match ... with Leaf (x, _) -> ... | Node (x, _, _) -> ....

En Java, une variable locale est par dfaut modifiable. On peut la rendre immuable enprcdant sa dclaration du mot-clef final.

En OCaml, une variable locale est toujours immuable. Pour simuler une variable localemodifiable, on peut introduire une variable immuable x dans laquelle on trouve ladressedune rfrence (Exercice 1.2), cest--dire un bloc de mmoire dot dun champ modifiable.On crit let x = ref (...) in ... pour allouer une rfrence et introduire une variableimmuable x qui reprsente ladresse de cette rfrence. On crit ensuite !x pour lire luniquechamp de cette rfrence et x := ... pour le modifier.

Remarque 1.7 (Abrviations de types) En OCaml, un nouveau type peut tre dfini commeune abrviation pour un type existant. Si on pose type alphabet = (char, int) Hashtbl.t,par exemple, alors le type alphabet dsigne le type dune table de hachage dont les clefs sontdes caractres et les valeurs des entiers. En Java, ce mcanisme nexiste pas : pour dfinir unnouveau type, il faut dfinir une nouvelle classe ou interface. On ne peut pas introduire uneabrviation pour HashMap.

Dtail 1.8 (Tableaux) Le type des tableaux, qui scrit E[] en Java et a array en OCaml, estprimitif : il nest pas dfini par lutilisateur, mais pr-existant. Nous avons affirm plus hautque, en gnral, la longueur dun bloc de mmoire (cest--dire le nombre de ses champs)est dtermine par son tiquette. On peut dire que les tableaux obissent cette rgle silon considre que la longueur dun tableau fait partie de son tiquette . Java et OCamlfournissent des oprations primitives pour obtenir la longueur dun tableau et pour accder(en lecture ou en criture) ses champs. Contrairement aux blocs dfinis par lutilisateur,les tableaux permettent laccs alatoire, ou random access : lindice du champ auquel onsouhaite accder peut tre le rsultat dun calcul.

Dtail 1.9 (Champ partag) Dans une dfinition de type en Java, un champ peut tre commun toutes les branches. Il est alors possible dy accder sans examiner ltiquette du bloc. Cest

12 CHAPITRE 1. DONNES ET COMPORTEMENT

le cas du champ freq de lexemple prcdent. Il est dclar dans la classe mre, HuffmanTree,donc prsent dans tous les blocs de ce type, indpendamment de leur tiquette, Leaf ouNode. Si on dispose dun bloc x de type HuffmanTree, lexpression x.freq est valide : on peutaccder ce champ sans examiner ltiquette. En langage mathmatique, on pourrait crireT = Int (Char + T T). En OCaml, de mme, on pourrait poser type tree = int * restet type rest = Leaf of char | Node of tree * tree. Ici, nous avons prfr rpter ladfinition du premier champ, de type int, dans les deux branches. Nous pouvons toutefoisnous doter dune fonction auxiliaire pour accder ce champ sans nous soucier de ltiquette :let freq t = match t with Leaf(f, _) | Node (f, _, _) -> f.

Dtail 1.10 (Champs anonymes) En Java, chaque champ est nomm. En OCaml, comme onla vu ci-dessus, les champs dun type somme ne sont pas nomms. Dans la dfinition du typetree, on lit que le constructeur Leaf a deux champs et que le constructeur Node a trois champs,mais on ne leur donne pas de nom. Ils sont identifis par leur position : on parle par exempledu premier champ ou du second champ du constructeur Leaf.

Lorsquon crit une expression match, on est libre de choisir les noms des variables localesqui apparaissent dans chaque branche. Par exemple, pour accder au champ frquence du bloc x, on peut crire match x with Leaf (f, c) -> f | Node (f, t0, t1) -> f ouencore match x with Leaf (freq, c) -> freq | Node (qerf, foo, bar) -> qerf.

On peut toutefois nommer les champs dun type enregistrement ; voir le Dtail 1.11.

Dtail 1.11 (Enregistrements) Dans le cas o une dfinition de type est constitue dune seulebranche, et dans ce cas seulement, OCaml nous autorise nommer les champs. On crit parexemple :

type point = { x: int; y: int }

On dit alors que le type point est un type enregistrement, ou record type . On crit parexemple { x = 0; y = 1 } pour allouer un bloc de type point. On crit p.x et p.y pouraccder aux champs du bloc p. Dun point de vue mathmatique, le type point est un typeproduit ; on pourrait crire P = Int Int.

En OCaml, on peut aussi crire :

type point = Point of int * int

Le type point est alors un type somme une seule branche. On doit crire Point (0, 1) pourallouer un bloc de type point, et on doit utiliser match p with Point (x, y) -> ... ou bienlet Point (x, y) = p in ... pour accder aux champs du bloc p. La syntaxe nest pas lamme, mais la faon dont le bloc est reprsent en mmoire est la mme : un point a toujoursune tiquette (sans intrt, puisque cest toujours la mme) et deux champs.

Dtail 1.12 (Paires) Il est frquent que lon souhaite grouper deux valeurs v1 et v2 pourconstruire une paire, cest--dire un bloc deux champs, qui contiennent respectivementles valeurs v1 et v2. Cest utile, par exemple, lorsquune fonction doit renvoyer deux rsultats.

Java noffre aucune facilit particulire pour cela. Nanmoins, il est bien sr possible dedfinir par soi-mme une classe (paramtre) Pair. Voir par exemple la Figure 4.31, quifait partie de la solution de lExercice 4.19.

De mme, en OCaml, on pourrait dfinir par soi-mme un type (paramtr) des paires enposant type (a, b) pair = Pair of a * b. On crirait Pair (0, 1) pour allouer unepaire dont le type scrirait (int, int) pair. On crirait match p with Pair (x, y) -> ...ou bien let Pair (x, y) = p in ... pour accder aux composantes de la paire p.

Afin doffrir une syntaxe plus concise, OCaml possde un type primitif des paires. Onpeut crire simplement (0, 1) pour construire une paire, dont le type est not int * int.On crit match p with (x, y) -> ... ou bien let (x, y) = p in ... pour accder auxcomposantes de la paire p. Encore une fois, ce sont l des dtails syntaxiques, mais la faondont une paire est reprsente en mmoire est toujours la mme : cest un bloc dot dunetiquette (sans intrt) et de deux champs.

1.1. DONNES 13

Plus gnralement, pour chaque entier n, OCaml possde un type primitif des n-uplets, ou tuples . Par exemple, lexpression ("Paris", 75, "France") alloue un bloc trois champs,dont le type est string * int * string. Dautres langages de programmation suivent cetexemple : en Scala, par exemple, ("Paris", 75, "France") est une faon concise dcrirenew Tuple3 ("Paris", 75, "France"), dont le type est Tuple3[String, Int, String].

Dtail 1.13 (Types numrs) En OCaml, lors de la dclaration dun type algbrique, si unconstructeur a zro champs, alors on omet le mot-clef of. Ainsi, on crit type color = Red |Green | Blue et non pas type color = Red of | Green of | Blue of. La dfinition dutype option (Remarque 1.4) en donne un autre exemple.

Le type color est un exemple de type numr, cest--dire un type somme dont chaqueconstructeur a zro champs. En OCaml, ce concept nest quun cas particulier du concept plusgnral de type algbrique. En Java, il existe un mot-clef enum pour dclarer un type numr.

Dtail 1.14 (Syntaxe des constructeurs) En OCaml, lorsquon construit un bloc, les argumentsdu constructeur (cest--dire les valeurs initiales des champs) sont entours de parenthses :on crit Leaf (f, c) ou Node (f, x0, x1) ou Some (42). Il y a deux exceptions cette rgle.Si le constructeur a zro arguments, alors on doit omettre les parenthses : on crit None et nonpas None (). Si le constructeur a un argument, alors on peut omettre les parenthses : on peutcrire Some (42) ou bien Some 42.

Exercice 1.1 (Recommand) Solution page 71.En Java puis en OCaml, dfinissez un type de donnes pourreprsenter les entiers tendus , cest--dire les entiers relatifs auxquels on ajout les deuxlments et +. (Vous utiliserez les entiers de la machine.) Dfinissez des moyens pourlutilisateur de construire toutes les valeurs de type entier relatif . Dfinissez une oprationpour convertir un entier relatif en une chane de caractres. Dfinissez une opration leqpermettant de comparer (au sens large) deux entiers relatifs. Enfin, dfinissez une oprationmax sur les entiers relatifs.

Exercice 1.2 (Recommand) Solution page 71.En OCaml, dfinissez un type box reprsentant un bloc dot dunseul champ, modifiable, contenant un entier. (Le Dtail 1.11 pourra tre utile.) crivez troisfonctions create, get, set pour crer une bote, cest--dire un bloc de type box ; pour lire soncontenu ; pour modifier son contenu. Gnralisez ensuite votre code pour que le contenu dela bote ne soit pas ncessairement une valeur entire, mais une valeur de type arbitraire a.Les botes ainsi obtenues sont habituellement appeles rfrences, et le type a box est dfinisous le nom a ref dans la bibliothque.

Exercice 1.3 Solution page 73.Comme dans lExercice 1.2, mais cette fois en Java, on souhaite dfinir des botes , cest--dire des blocs dots dun champ contenant une valeur de type X. De plus, onsouhaite imposer sur chaque bote le protocole suivant. Une nouvelle bote est cre vide ,cest--dire non initialise : son champ ne contient pas de valeur de type X. Une mthode setpermet dinitialiser ce champ ; elle est cense tre appele au plus une fois. Une mthode getpermet de consulter le contenu de la bote ; elle peut tre appele un nombre arbitraire de fois,mais aprs seulement que set a t appele. Dfinissez une classe Box reprsentant unebote dont le contenu est de type X. Dotez-la dun constructeur, dune mthode set et dunemthode get. Faites en sorte quune erreur ait lieu pendant lexcution si le protocole dcritci-dessus nest pas respect.

Exercice 1.4 (Recommand) Solution page 74.Une liste est soit vide, soit constitue dun lment (le premierlment de la liste) et dune sous-liste (la liste des lments suivants). En langage mathmatique,si X est le type des lments, alors le type L des listes est dfini par lquation L = 1 + X L. EnJava puis en OCaml, transcrivez cette dfinition, dans le cas o les lments sont des entiers.Dfinissez une opration pour convertir une liste en une chane de caractres. Dfinissez uneopration pour dterminer si une liste contient ou non un lment pair.

14 CHAPITRE 1. DONNES ET COMPORTEMENT

Exercice 1.5 (Recommand)Solution page 76. On se donne en OCaml un type algbrique reprsentant desarbres binaires. Le constructeur Leaf reprsente une feuille ; il ne porte aucune information.Le constructeur Node reprsente un nud interne ; il porte un lment de type int ainsi quedeux sous-arbres.

type tree =| Leaf| Node of tree * int * tree

crivez une fonction rcursive elements, de type tree -> int list, telle que elements t estla liste des lments contenus dans larbre t, lue dans lordre infixe, de gauche droite. Parexemple, si t est larbre Node (Node (Leaf, 1, Leaf), 2, Node (Leaf, 3, Leaf)) alors laliste elements t doit tre [1; 2; 3]. Vous pourrez utiliser la fonction List.append, galementnote @, qui construit la concatnation de deux listes.

Quelle est la complexit asymptotique en temps de la fonction elements ?Pour obtenir une meilleure complexit, crivez une fonction elements_append, de type

tree -> int list -> int list, telle que la liste elements_append t tail soit gale laliste (elements t) @ tail. Quelle est la complexit asymptotique de elements_append ?

laide de elements_append, dfinissez en une ligne une nouvelle version, plus efficace,de la fonction elements.

Exercice 1.6Solution page 77. On souhaite programmer une calculatrice capable de manipuler des expressionssymboliques une variable, par exemple 20 , 20 + x , 20 + 3 x + x x , etc. Uneexpression sera soit la variable x , soit une constante, soit la somme de deux expressions,soit le produit de deux expressions. Cela se rsume ainsi : e ::= x | c | e + e | e e, o la lettre cdnote une constante entire. Dfinissez en OCaml un type de donnes pour reprsenter cesexpressions. Dfinissez une opration qui, tant donne une expression e et tant donne unevaleur numrique pour la variable x, calcule la valeur numrique de lexpression e. Enfin,dfinissez une opration qui, tant donne une expression e, calcule sa drive e vis--vis dela variable x. (Notons que lExercice 4.8, en Java, concerne un sujet proche.)

1.2 Comportement

Dans ce qui prcde (1.1), nous avons utilis le vocabulaire des types algbriques sommes, produits, rcursivit pour dcrire des structures de donnes. Ce vocabulaire per-met de dcrire des listes, des arbres, et plus gnralement toutes les structures de donnesconstruites partir de blocs de mmoire et de pointeurs entre ces blocs.

Le vocabulaire des types algbriques, seul, ne permet de dcrire que la forme des donnes,cest--dire leur organisation en mmoire. Il ne permet pas de leur attribuer un comportement.Il permet, par exemple, de dcrire la forme des arbres binaires de recherche ; mais, pourdfinir les oprations dinsertion ou de recherche dans un tel arbre, il faut crire du code : desmthodes, en Java, ou bien des fonctions, en OCaml.

Dans le monde de la programmation traditionnelle ou programmation procdurale,donnes et comportement sont spars. Si par exemple nous avons dfini dune part un typedes listes et dautre part une fonction qui convertit une liste en une chane de caractres(Exercice 1.4), alors nous avons affaire deux entits bien distinctes. Dune part, une listeest reprsente, dans la mmoire de la machine, par une srie de blocs allous dans le tas.Dautre part, notre fonction de conversion est reprsente dans la mmoire de la machine sousforme dune suite dinstructions, stocke en dehors du tas, dans une zone (non modifiable) dela mmoire, rserve au code. Pour appeler cette fonction, il suffit de connatre son adresse,cest--dire ladresse de sa premire instruction. On parle parfois de pointeur de code pourdsigner cette adresse.

La programmation oriente objets, dont Java est lun des reprsentants, de mme quela programmation fonctionnelle, dont OCaml est lun des reprsentants, assouplissent cette

1.2. COMPORTEMENT 15

sparation totale entre donnes et comportement. Toutes deux permettent de marier donneset comportement de faon plus subtile.

Dans le monde de la programmation oriente objets, on appelle objet une entit dote duntat et dun comportement.

Le mot tat dsigne ici les donnes qui constituent cet objet, cest--dire, au minimum,le bloc de mmoire sous-jacent cet objet. Ltat dun objet peut ventuellement engloberdautres objets : par exemple, lorsque lon parle abstraitement de ltat dune table dehachage de type HashMap, on dsigne tous les blocs qui participent la reprsentation de cette table en mmoire, et non pas seulement le bloc de classe HashMapqui en constitue la racine. Cet tat peut tre modifiable ou non.

Le mot comportement dsigne les mthodes de cet objet. On adopte souvent un point devue anthropomorphe et lon dit que lobjet sait effectuer certaines oprations : par exemple,un objet dot dune mthode toString sait produire une description de lui-mme sousforme dune chane de caractres. Le code de la mthode toString nest pas le mme suivantla classe laquelle appartient lobjet : ainsi, des objets appartenant diffrentes classes ontdiffrents comportements. Une mthode est parfois appele message : on dit alors que lobjet sait rpondre au message toString.

Un objet, vu comme un bloc de mmoire, contient une tiquette et des champs. Cettetiquette indique quelle classe appartient lobjet, donc permet (indirectement, via quelquescalculs) dobtenir le pointeur de code de chacune des mthodes de cette classe. On constatedonc que, dans ce bloc, sont stocks non seulement des donnes mais aussi un comportement(plus prcisment, une tiquette, qui donne accs des pointeurs de code).

Un objet marie donc tat et comportement. Au-del de la mtaphore anthropomorphe, enquoi cela est-ce utile ou souhaitable ? Cela permet une forme dencapsulation, ou dabstraction.On entend par l le fait quon peut interdire tout accs direct depuis lextrieur ltat dunobjet. En Java, il suffit pour cela de dclarer que les champs de cet objet sont privs, ou private.Seules les mthodes de la classe laquelle appartient lobjet ont alors accs ces champs. Pouraccder depuis lextrieur ltat dun objet, il est donc obligatoire de passer par lintermdiairedun appel de mthode. Ceci permet au concepteur de la classe de contrler ou de limiter lafaon dont ltat de lobjet peut tre consult ou modifi. Lutilisateur sait alors quel est leservice offert par cet objet, mais ne sait pas de quelle manire ce service est implment, doncne peut ni en perturber le bon fonctionnement, ni le distinguer dune autre implmentation dece mme service. Selon certains, cest l lessence de la programmation oriente objets (Aldrich,2013).

Dans le monde de la programmation fonctionnelle, aussi, on trouve des entits qui associenttat et comportement. On les appelle fonctions ou cltures. Afin de mettre en vidence cettecombinaison entre donnes et comportement sans toutefois entrer trop avant dans les dtailspour le moment, supposons que lon calcule ainsi la somme des lments dune liste dentiers :

let sum (xs : int list) : int =let s = ref 0 inList.iter (fun x -> s := !s + x) xs;!s

On alloue dans le tas une rfrence s, dont la valeur initiale est 0, puis on itre sur la liste xs. Pourcela, on appelle List.iter, en lui passant une fonction anonyme qui a accs la rfrence s.Pour chaque lment x de la liste, List.iter appelle cette fonction anonyme, qui met alors jour la somme partielle stocke dans s. Une fois litration termine, s contient la somme detous les lments. (La fonction List.iter est tudie plus en dtail en 4.1.1.)

Quelle est la nature exacte de lobjet construit par lexpression fun x -> s := !s + x ?Cest, premire vue, une fonction . Comment est-il reprsent en mmoire ? Il doit contenirun pointeur de code, cest--dire ladresse o est situe la suite dinstructions correspondant la fonction anonyme fun x -> s := !s + x. Cependant, ce pointeur de code ne suffit pas.Il faut que la fonction anonyme puisse accder la rfrence s, qui est alloue dans le tas. Or,ladresse de s ne peut pas apparatre dans le code. Celui-ci est immuable et existe dj, stock

16 CHAPITRE 1. DONNES ET COMPORTEMENT

sur un disque, avant mme que le programme soit excut ; la rfrence s, au contraire, nexistepas au moment o le programme commence son excution. Le bloc de mmoire qui reprsentela fonction anonyme doit donc contenir non seulement un pointeur de code, mais aussi unedonne, savoir ladresse de s. Ce bloc, appel clture, marie donc donnes et comportement.

Ceci suggre que les fonctions dOCaml sont trs proches des objets de Java. En effet,elles aussi associent donnes et comportement, et, pour cette raison, elles aussi permettent uneforme dencapsulation ou dabstraction.

Dans la suite, nous rappelons dabord ce que lon appelle traditionnellement une procdureou une fonction (1.2.1). Puis, nous tudions de plus prs les fonctions-cltures dOCaml, quenous expliquons en approfondissant lanalogie avec les objets de Java (1.2.2). Nous prsentonsgalement les cltures de Java 8 (1.2.3). Enfin, nous introduisons la notion de suspension(1.2.4), qui combine une clture et un mcanisme de mmoisation. Nous ne parlerons pas desclasses et des objets dOCaml, car la notion de fonction-clture nous suffira amplement pourdfinir des abstractions utiles et intressantes.

1.2.1 Procdures et fonctions traditionnelles

Les notions de mthode, au sens de Java, ou de fonction, au sens dOCaml, descendenttoutes deux de ce que lon appelait aux dbuts de linformatique les procdures ou sous-routines . On lira avec amusement et intrt les deux pages de larticle de Wheeler (1952), quidcrivent fort bien lattrait de cette notion. Une fois que lon a crit une fonction pour raliserune certaine tche par exemple, tant donn un nombre x, calculer le nombre sin x tout sepasse comme si on avait ajout une nouvelle instruction lmentaire ici, linstruction sin une machine qui en tait dpourvue. La dcomposition dun programme en fonctions permetden matriser la complexit : lauteur de la fonction sin peut se concentrer sur lcriture dela suite dinstructions (probablement complexe) qui constitue cette fonction, sans sinquiterdu reste du programme, et peut tester isolment cette fonction on parle en anglais de unittesting . Symtriquement, lutilisateur de la fonction sin na pas sinquiter de la maniredont le sinus est calcul. Il lui suffit de savoir ce que fait la fonction, pas comment elle le fait.Cest ce que Liskov et Guttag (2001) appellent abstraction procdurale.

Quels sont les points communs aux procdures, mthodes, ou fonctions que lon trouvedans presque tous les langages de programmation, par exemple C, Java, OCaml ?

Un premier point commun est le mcanisme dappel et de retour lui-mme. Lexcutionde lappelant (la fonction qui effectue lappel) est suspendue, pour donner la main lappel(la fonction qui est appele). Symtriquement, une fois que lappel a termin son excution,lexcution de lappelant reprend au point qui suit lappel.

Un second point commun est le mcanisme de communication entre appelant et appel.Lappelant transmet lappel une valeur, appele argument ; symtriquement, une fois sonexcution termine, lappel transmet lappelant une valeur, appele rsultat.

Un troisime point commun est la notion de variable locale. Chaque fonction peut crerautant de variables locales quelle le souhaite. Ces variables lui sont propres ; il ny a pasdinterfrence entre les variables locales de lappelant et celles de lappel.

Ces trois points supposent un mcanisme dallocation de mmoire. En effet, pour reprendrelexcution de lappelant au point qui suit lappel, il est ncessaire de mmoriser ladressede retour, cest--dire le point du programme o lexcution de lappelant doit reprendre.Cela demande dallouer un nouvel emplacement en mmoire. De mme, pour stocker lesvariables locales de lappel, de nouveaux emplacements en mmoire sont ncessaires. Enfin,largument transmis de lappelant lappel est plac dans une variable locale de lappel,qui demande elle aussi un emplacement en mmoire. Ces emplacements ne sont utiliss quependant lexcution de lappel : une fois celle-ci termine, ils sont librs. Cest pourquoi ilest naturel dallouer ces emplacements non pas dans le tas, qui est utilis pour des blocs dontla dure de vie est a priori inconnue, mais dans la pile, une zone de mmoire utilise pourallouer des emplacements dont la dure de vie concide avec lexcution dune fonction. La

1.2. COMPORTEMENT 17

pile est invisible pour le programmeur, puisquelle est entirement gre par le compilateur ;mais il faut garder lesprit le fait quun appel de fonction alloue une certaine quantit demmoire sur la pile, qui est libre lorsque la fonction termine. Lexcution du programmepeut dailleurs tre brutalement interrompue si la taille de la pile dpasse la limite fixe parle systme dexploitation. On observe alors une exception nomme StackOverflowError enJava et Stack_overflow en OCaml.

Un quatrime et dernier point commun est la rcursivit. La rcursivit joue un rleessentiel lorsque lon souhaite diviser un problme en plusieurs sous-problmes (diviser pourrgner) et/ou lorsque lon manipule des structures de donnes arborescentes. Du point devue de la machine et du compilateur, autoriser une fonction sappeler elle-mme (ou, plusgnralement, autoriser un groupe de fonctions sappeler les unes les autres) ne pose aucunedifficult. Du point de vue du programmeur, pour garder les ides claires, il faut (commetoujours) considrer lappel comme une bote noire il suffit de savoir ce que fait lappel,pas comment il le fait et ignorer le fait quappelant et appel sont la mme fonction, carcest en ralit un dtail sans importance. En bref, labstraction procdurale facilite la pensercursive.

Remarque 1.15 (Reconnatre une fonction traditionnelle) Quelles notions correspondent, enJava et en OCaml, une procdure ou fonction au sens traditionnel de ces mots ?

En Java, une mthode statique joue ce rle. Elle na pas dargument this implicite. Lesseules donnes auxquelles elle a accs sont ses arguments et les variables globales (appels champs statiques en Java). Elle est traduite par le compilateur en une srie dinstructions.Pour lappeler, il suffit de connatre ladresse du dbut de ces instructions, cest--dire unpointeur de code. On peut dire quelle est reprsente en mmoire par un pointeur de code.

En OCaml, une fonction close joue ce rle. Une fonction est dite close si elle ne mentionneaucune variable dfinie lextrieur : par exemple, la fonction (fun x -> x + 1) est close,tandis que la fonction (fun x -> x + y) ne lest pas, car elle mentionne y, qui a t dfiniepralablement. Les seules donnes auxquelles elle a accs sont ses arguments et les variablesglobales. Elle est reprsente en mmoire par un simple pointeur de code.

Les mthodes statiques de Java et les fonctions closes dOCaml sont donc analogues auxprocdures et fonctions que lon trouve dans les langages procduraux , dont le plus connuet le plus utilis est probablement le langage C.

1.2.2 Fonction = clture = objet = service

Les blocs allous dans le tas, dont nous avons dcrit prcdemment lorganisation (1.1),constituent les donnes . La notion traditionnelle de fonction, dont nous venons de rappelerles principes (1.2.1), permet de dfinir des comportements . Comme nous lavons suggrplus haut, il faut marier donnes et comportement pour dfinir une abstraction, cest--direoffrir un service, sans rvler de quelle manire ce service est implment. Les objets de Javaet les fonctions dOCaml permettent cela.

partir dici, le mot fonction dsigne une fonction dOCaml dans toute sa gnralit, etnon pas seulement une fonction traditionnelle ou fonction close (Remarque 1.15). Nousconsidrons ce mot comme synonyme de clture.

titre dexemple, tudions une abstraction simple : un compteur que lon peut incrmenterde step en step. On souhaite disposer de trois oprations :

1. La cration dun nouveau compteur, dont la valeur initiale est zro. Cette oprationattend un argument, savoir un entier step, qui reste fix par la suite.

2. Lincrmentation dun compteur. La valeur actuelle du compteur augmente de step.Cette opration na ni argument ni rsultat.

3. La consultation du compteur. Cette opration na pas dargument. Son rsultat est lavaleur actuelle du compteur.

18 CHAPITRE 1. DONNES ET COMPORTEMENT

Il est facile dimplmenter cette abstraction en Java, sous forme dune classe Counter, quipermettra ensuite de crer autant dobjets compteur quon le dsire. Commenons donc parcela, comme le propose lexercice suivant.

Exercice 1.7 (Recommand)Solution page 78. Implmentez en Java une classe Counter qui offre le servicedcrit ci-dessus. Expliquez quel est ltat dun objet de classe Counter, cest--dire quelle estsa reprsentation en mmoire.

Dans cet exemple exprim en Java, un appel au constructeur provoque lallocation dunnouvel objet dans le tas. Un appel aux mthodes increment ou get permet ensuite de modifierou de consulter ltat de cet objet.

Transcrivons prsent cet exemple en OCaml. Un appel au constructeur, par exemplenew Counter (2), est transcrit en un appel new_counter 2, o new_counter est une fonctionqui cre un nouveau compteur. Mais, quest-ce quun compteur ? En Java, un compteur taitun objet dot de deux mthodes increment et get. En OCaml, parce que les fonctions sontdes valeurs comme les autres, on peut poser quun compteur est une paire de fonctions,qui permettent respectivement dincrmenter et de consulter la valeur actuelle du compteur.Introduisons un type enregistrement (voir le Dtail 1.11) qui dcrit cette paire :

type counter ={ increment : unit -> unit; get: unit -> int }

Il faut maintenant crire la fonction new_counter, dont le type doit tre int -> counter,puisquelle attend la valeur de lentier step, et produit un nouveau compteur. Ceci est propossous forme dexercice. Essayez de le rsoudre, mais si vous ny parvenez pas, considrez quesa solution fait partie du cours.

Exercice 1.8 (Recommand)Solution page 78. Implmentez la fonction new_counter.

Considrer un compteur comme une paire de fonctions peut sembler une ide mystrieuse.Quelle est alors la reprsentation en mmoire dun compteur ? Cest une paire, donc un bloccompos de deux champs, qui contiennent chacun un pointeur vers une fonction. Nous parlonsici dune fonction au sens le plus gnral, cest--dire une clture. Notre compteur est une paire(alloue dans le tas) de pointeurs vers des cltures (elles-mmes alloues dans le tas).

Contrairement une fonction close, qui nest que comportement (Remarque 1.15), uneclture marie donnes et comportement. Par exemple, la composante get dun compteur, quiest une clture de type unit -> int, a accs certaines donnes, savoir dune part lentierstep, dautre part ladresse de la rfrence modifiable o est stocke la valeur actuelle ducompteur. Elle a galement un comportement, savoir, lorsquelle est appele, lire et renvoyerla valeur actuelle du compteur.

Pour mieux comprendre ce quest une fonction ou une clture en OCaml, voyons comment,dans le cas gnral, on peut simuler ce concept en Java. Puisquune fonction allie donnes etcomportement, il est naturel de la simuler en Java laide dun objet. Un objet de Java censreprsenter une fonction pourra avoir diffrents champs, suivant les besoins ; ces champscontiennent les donnes dont la fonction a besoin. Cet objet aura toujours une mthode et uneseule, que nous appellerons par exemple call. Cette mthode reprsente le comportement dela clture. Dfinissons une interface, au sens de Java, pour dcrire un objet dot dune mthodeapply :

public interface Function {R apply (T argument );

}

Si f est un objet de type Function, alors lappel de mthode f.apply(x) en Java simulelappel de fonction f(x) en OCaml.

Comme nous ne souhaitons pas fixer le type T de largument ni le type R du rsultat,nous en avons fait des paramtres de linterface Function. Ainsi, un objet de Java de type

1.2. COMPORTEMENT 19

Function correspond une fonction OCaml de type T -> R. Linterface Function faiten ralit partie de la bibliothque de Java 8.

En conclusion, une bonne faon de comprendre ce quest une clture en OCaml est dela considrer essentiellement comme un objet, au sens de Java, qui implmente linterfaceFunction. Donc, comme un objet de Java, une clture est alloue dans le tas, et marie donnes(stockes dans ses champs) et comportement (dtermin par son tiquette).

Un objet de Java de type Function ou une clture dOCaml de type T -> R estabstrait, cest--dire opaque : on ne sait pas a priori combien de champs possde un tel objet,ni quel est son contenu. On sait seulement que cet objet rend un certain service : tant donnune valeur de type T, il produit une valeur de type R.

Dtail 1.16 (Fonctions plusieurs arguments en OCaml) En OCaml, une fonction a toujoursexactement un argument et un rsultat. Son type scrit t -> u, o t est le type de largumentet u le type du rsultat. Une fonction sans argument ou sans rsultat est simule laide dunefonction un argument ou un rsultat de type unit (Remarque 1.3). Une fonction plusieursarguments ou plusieurs rsultats est simule laide dune fonction un argument ou unrsultat de type tuple (Dtail 1.12). Par exemple, une fonction qui attend deux entiers etcalcule leur somme peut scrire fun (x, y) -> x + y. Son type est (int * int) -> int,que lon peut crire aussi int * int -> int. Si lon souhaite nommer cette fonction add, onpeut crire :

let add = fun (x, y) -> x + y

ou bien employer la forme suivante, plus concise mais quivalente :

let add (x, y) = x + y

Pour appeler cette fonction, il faut bien sr lui fournir un argument, lequel doit tre une paire.On crit donc, par exemple, add (3, 4).

En mathmatiques, au lieu de considrer laddition comme une fonction qui une pairedentiers (x, y) associe lentier x + y, on peut aussi la considrer comme une fonction qui unentier x associe la fonction qui un entier y associe la somme x + y. En OCaml, puisquunefonction est une valeur comme une autre, on peut faire de mme. On crit alors :

let add = fun x -> fun y -> x + y

ou bien, sous forme plus concise mais quivalente :

let add = fun x y -> x + y

ou encore :

let add x y = x + y

Dans ce cas, add est une fonction qui renvoie une fonction ; son type est naturellementint -> (int -> int), que lon peut crire aussi int -> int -> int. Si lon crit add 3, onobtient une fonction de type int -> int, qui ajoute 3 son argument. Si lon applique encorecette fonction, en crivant par exemple (add 3) 4 ou plus simplement add 3 4, on obtient unentier. Cette faon dcrire la fonction add est dite dans le style de Curry , o curryfie .

La syntaxe de lappel de fonction est toujours f x, que lon peut crire si on le souhaiteavec des parenthses : f(x). Bien sr, encore faut-il que largument x ait bien le type attendupar la fonction f.

Tout ceci est remarquablement rgulier et naturel. Nanmoins, il est malheureux quil existedeux faons de simuler une fonction deux arguments. En pratique, il faut retenir que si unefonction f est de type t * u -> v, alors pour lappeler il faut crire f(x, y), mais si son typeest t -> u -> v, alors pour lappeler il faut crire f x y. On peut dire aussi que si la dfinitionde f est de la forme let f (x, y) = ... alors pour lappeler il faut crire f(x, y), mais si sadfinition est de la forme let f x y = ... alors pour lappeler il faut crire f x y.

https://docs.oracle.com/javase/8/docs/api/java/util/function/Function.html

20 CHAPITRE 1. DONNES ET COMPORTEMENT

Exercice 1.9 (Recommand)Solution page 79. On dfinit en OCaml une notion de cellule mmoire , quistocke une valeur entire. Une cellule est prsente lutilisateur sous forme dune fonction detype int -> int. Cette fonction a pour double effet de stocker dans la cellule la valeur reueen argument et de renvoyer la valeur prcdemment stocke dans la cellule. Le code scritainsi :

type cell =int -> int

let new_cell () : cell =let value : int ref = ref 0 inlet exchange ( new_value : int) =

let old_value : int = !value invalue := new_value ;old_value

inexchange

Traduisez ce code en Java de la faon suivante. Dans une classe CellFactory, crivez unemthode statique newCell, sans argument, qui renvoie une nouvelle cellule, reprsente parun objet de type Function. Expliquez quelle est la reprsentation enmmoire de cet objet.

Exercice 1.10Solution page 80. En guise de variation sur lexemple du compteur (Exercice 1.8), on crit enOCaml un compteur reprsent par une seule fonction de type unit -> int. Cette fonctiona pour double effet dincrmenter le compteur et de renvoyer son ancienne valeur. Le codescrit ainsi :

type counter =unit -> int

let new_counter (step : int) : counter =let value = ref 0 inlet get_and_increment () =

let c : int = !value invalue := c + step;c

inget_and_increment

Traduisez ce code en Java de la faon suivante. crivez une classe Counter. Dotez-la dunconstructeur qui attend un argument step de type entier. Faites en sorte que cette classeimplmente linterface Function. ( propos des types unit et Unit, voir laRemarque 1.3.)

1.2.3 Cltures en Java 8

Nous avons prsent un peu plus haut linterface Function, qui est dfinie dans la biblio-thque de Java 8, et quon peut dfinir soi-mme si on utilise une version antrieure de Java.Nous avons expliqu quune clture nest autre quun objet qui satisfait cette interface. Donc,en un sens, les cltures existent en Java.

Nanmoins, dans les versions de Java antrieures 8, il manque une syntaxe lgre pourconstruire une clture. Supposons, par exemple, que lon dispose dun entier x, et que lonsouhaite construire la fonction qui y associe x + y. En OCaml, on crirait simplementfun y -> x + y (Dtail 1.16). En Java 7, il faut dfinir une classe anonyme qui implmentelinterface Function. On doit donc crire :

new Function () {public Integer apply ( Integer y) {

return x + y;

https://docs.oracle.com/javase/8/docs/api/java/util/function/Function.htmlhttps://docs.oracle.com/javase/8/docs/api/java/util/function/Function.htmlhttps://docs.oracle.com/javase/8/docs/api/java/util/function/Function.htmlhttps://docs.oracle.com/javase/8/docs/api/java/util/function/Function.html

1.2. COMPORTEMENT 21

}}

Cest bien lourd. Pour allger cela, Java 8 introduit une syntaxe naturelle et concise pour dfinirune clture. Il suffit alors dcrire :

y -> x + y

Le compilateur remplace automatiquement cette expression concise par la version beaucoupplus lourde que nous avons donne prcdemment. Il nest mme pas ncessaire dindiquerquelle interface nous cherchons satisfaire : le compilateur dtermine, daprs le contexte, quilsagit de linterface Function. Il nest pas non plus ncessaire de dclarerle type de y : le compilateur le dtermine automatiquement.

Ce mcanisme permet aussi de construire une clture qui satisfait une interface autre queFunction. La seule restriction est que cette interface doit tre fonctionnelle : elle ne doit exiger laprsence que dune seule mthode. Considrons par exemple linterface Comparator. Cetteinterface est fonctionnelle : elle exige uniquement une mthode int compare (T o1, T o2).Si on souhaite construire un objet de type Comparator qui reprsente la relationdordre habituelle sur les entiers, on peut crire en Java 7 :

new Comparator () {public int compare ( Integer x, Integer y) {

return x < y ? -1 : x == y ? 0 : 1;}

}

mais on prfrera probablement crire en Java 8 :

(x, y) ->x < y ? -1 : x == y ? 0 : 1

Une interface fonctionnelle est indique dans la documentation de Java par lannotation@FunctionalInterface. La bibliothque de Java 8 en dfinit un grand nombre, parmi lesquelleson trouve Function, BiFunction, Consumer, Predicate, Supplier,Callable, etc.

Cette traduction dune fonction anonyme en un objet existe dans dautres langages deprogrammation. En Scala, par exemple, lexpression (x: Int) => x + 1 est traduite ainsi parle compilateur :

new Function1 [Int , Int] {def apply(x: Int ): Int = x + 1

}

Dtail 1.17 (Syntaxe des cltures de Java) Une fonction anonyme deux arguments scrit(x, y) -> .... Le corps de la fonction doit tre soit une expression, soit une instruction entreaccolades. La fonction y -> x + y peut donc scrire aussi y -> { return x + y; }. Unefonction peut ne pas renvoyer de rsultat ; par exemple, x -> { System.out.println(x); }.Cette dernire fonction peut scrire aussi, sous forme plus concise, System.out::println.Elle satisfait (entre autres) linterface Consumer. Cette dernire notation est appeleune rfrence une mthode.

1.2.4 Suspensions

Une fonction dOCaml de type unit -> a reprsente un calcul en attente, cest--dire uncalcul pas encore effectu. Le jour o on appelle cette fonction, le calcul a lieu, et on obtient unrsultat de type a. De mme, en Java, un objet de type Callable reprsente un calcul enattente. Le jour o on appelle sa mthode call, le calcul est effectu, et on obtient un rsultatde type T.

https://docs.oracle.com/javase/8/docs/api/java/util/function/Function.htmlhttps://docs.oracle.com/javase/8/docs/api/java/util/function/Function.htmlhttps://docs.oracle.com/javase/7/docs/api/java/util/Comparator.htmlhttps://docs.oracle.com/javase/8/docs/api/java/util/function/Function.htmlhttps://docs.oracle.com/javase/8/docs/api/java/util/function/BiFunction.htmlhttps://docs.oracle.com/javase/8/docs/api/java/util/function/Consumer.htmlhttps://docs.oracle.com/javase/8/docs/api/java/util/function/Predicate.htmlhttps://docs.oracle.com/javase/8/docs/api/java/util/function/Supplier.htmlhttps://docs.oracle.com/javase/8/docs/api/java/util/concurrent/Callable.htmlhttps://docs.oracle.com/javase/8/docs/api/java/util/function/Consumer.htmlhttp://docs.oracle.com/javase/tutorial/java/javaOO/methodreferences.htmlhttps://docs.oracle.com/javase/7/docs/api/java/util/concurrent/Callable.html

22 CHAPITRE 1. DONNES ET COMPORTEMENT

Dtail 1.18 (Quelle interface ?) On pourrait prfrer employer Function plutt queCallable. Ce choix est essentiellement arbitraire. Une diffrence mineure entre ces deuxinterfaces est que la mthode call de linterface Callable est autorise lancer une exceptionquelconque.

Le fait de pouvoir construire en mmoire une reprsentation dun calcul en attente estfondamental. On peut ainsi construire (par exemple) en temps et en espace O(1) une descriptiondune structure de donnes dont la taille peut tre arbitrairement grande, voire infinie, et dontle contenu peut tre arbitrairement coteux calculer. Les itrateurs (4.2) et les flots (4.3)en donnent un exemple, dans le cas o cette structure de donnes reprsente une squencedlments. Seuls les lments dont lutilisateur a besoin seront effectivement calculs. En bref,lide fondamentale est de ne calculer que si ncessaire.

cette premire ide, il est parfois utile dadjoindre une seconde ide fondamentale : nejamais effectuer deux fois un mme calcul. On aimerait que, si lutilisateur demande deuxfois le rsultat dun calcul en attente, alors ce calcul ne soit effectu que la premire fois, etque le rsultat soit ensuite mmois. On choisit ainsi dutiliser plus despace, dans lespoir degagner du temps.

En OCaml ou en Java, cette mmoisation nest pas automatique ; si on appelle deux foisfact(5), le calcul de la factorielle de 5 est bien effectu deux fois. Cependant, il ne nous estpas difficile de construire par nous-mmes un mcanisme de mmoisation. partir dunefonction dOCaml de type unit -> a ou dun objet de Java de type Callable, nous allonsobtenir une suspension, ou thunk , cest--dire un objet qui non seulement reprsente uncalcul en attente, mais de plus fournit la garantit que ce calcul sera effectu au plus une fois.La construction de cette notion fait lobjet des exercices suivants.

Exercice 1.11 (Recommand)Solution page 80. En OCaml, on peut dfinir une suspension comme une fonctionparticulire, qui la premire fois quelle est appele effectue un calcul (potentiellement coteux)et en mmorise le rsultat, de faon pouvoir renvoyer ce rsultat en temps O(1) si jamais elleest appele nouveau. On pose donc :

type a thunk = unit -> a

crivez une fonction thunk de type (unit -> a) -> a thunk qui prend un calcul en attenteet renvoie une suspension de ce mme calcul.

Exercice 1.12 (Recommand)Solution page 82. Cet exercice est lanalogue en Java de lexercice prcdent. Onchoisit de reprsenter un calcul en attente par un objet de type Callable. Pour reprsenterune suspension, dfinissez une classe Thunk, dote dun constructeur dont la signature estThunk (Callable f), et qui elle-mme implmente linterface Callable.

LExercice 1.11 ci-dessus montre que lon peut dfinir soi-mme, si on le souhaite, la notionde suspension. Nanmoins, pour des raisons de simplicit et defficacit, le langage OCamlpropose une notion primitive de suspension.

On construit une suspension en crivant lazy (e), o e est une expression. Cette expressionnest pas value immdiatement ; elle est suspendue. Si lexpression e a le type t, alorslexpression lazy (e) a le type t Lazy.t. Par exemple, posons :

let s = lazy ( print_endline "Hello!"; 0)

Cette dfinition ne provoque pas laffichage du message Hello!, puisque lexpression quicontient lappel print_endline nest pas value immdiatement. La suspension s admet letype int Lazy.t.

On value une suspension laide de la fonction primitive Lazy.force, dont le type esta Lazy.t -> a. Par exemple, posons :

let x = Lazy.force s

https://docs.oracle.com/javase/8/docs/api/java/util/function/Function.htmlhttps://docs.oracle.com/javase/7/docs/api/java/util/concurrent/Callable.htmlhttps://docs.oracle.com/javase/7/docs/api/java/util/concurrent/Callable.htmlhttps://docs.oracle.com/javase/7/docs/api/java/util/concurrent/Callable.htmlhttps://docs.oracle.com/javase/7/docs/api/java/util/concurrent/Callable.html

1.3. MODLE DE COT 23

Cette dfinition provoque laffichage du message Hello!. La variable x a pour type int et pourvaleur 0. Si, une seconde fois, on demande lvaluation de la suspension s :

let y = Lazy.force s

alors cette fois aucun message nest affich, puisque lexpression print_endline "Hello!"; 0a dj t value, et sa valeur mmoise. La variable y a pour type int et reoit la valeur 0.

Une suspension peut en un certain sens tre considre comme un objet immuable, puisque,une fois sa valeur calcule, celle-ci reste fixe jamais. Nanmoins, son implmentation exploitela mmoisation, donc la modification dun champ en mmoire. Il sagit dun subtil hybrideentre un objet immuable et un objet modifiable.

Nous utilisons les suspensions, plus loin, pour dfinir les flots (4.3).

1.3 Modle de cot

Pour analyser les performances des programmes que nous crivons, nous devons connatrele modle de cot propos par le langage de programmation que nous utilisons. En dautrestermes, nous devons connatre le cot, en temps et en espace, de chacune des oprationslmentaires offertes par ce langage.

Soulignons que nous ne parlons pas ici de cot rel, mesur en secondes pour le temps ouen octets pour lespace. Le cot rel dpend du compilateur, du systme dexploitation, de lamachine, et des conditions dutilisation de la machine (prsence ou non dautres processus,temprature !, etc.). Il est en gnral trs difficile analyser. Nous parlons donc seulement decot asymptotique une constante prs.

Comme nous lavons montr dans ce chapitre, Java et OCaml ont dimportants pointscommuns. Lutilisation de la pile pour stocker les variables locales dune mthode ou fonctionest identique. Lorganisation des donnes dans le tas, sous forme de blocs dots dune tiquetteet de champs, est la mme. Les objets de Java et les cltures dOCaml, allous dans le tas, sonttrs proches. Si lon a compris cela, on voit que les modles de cot de Java et dOCaml sontessentiellement les mmes.

Considrons dabord Java.Les oprations lmentaires dont il faut connatre le cot sont peu nombreuses.La cration dun objet, qui scrit new A (...), demande lallocation et linitialisation dun

nouveau bloc de mmoire dans le tas. (Elle demande galement un appel au constructeur, quelon peut considrer sparment comme un appel de mthode.) Le nombre de champs de cebloc est fix : il ne dpend que du texte du programme. Donc, cette opration cote O(1) entemps et O(1) en espace dans le tas. La cration dun tableau, qui scrit new A [n], cote O(n)en temps et O(n) en espace dans le tas. La cration dune clture, qui scrit x -> ..., signifieen ralit la cration dun objet (1.2.3), donc cote O(1) en temps et O(1) en espace dans letas. Dans ces trois situations, un bloc est allou dans le tas. Il sera dsallou par le GC lorsquildeviendra inaccessible ; nous discutons cela plus loin.

Laccs un champ en lecture, qui scrit o.f, et laccs un champ en criture, qui scrito.f = v, demandent un accs au tas. Ils ont un cot O(1) en temps.

Lappel dune mthode, qui scrit o.f(...), exige dabord de lire et analyser ltiquettede lobjet o pour en dduire quelle mthode doit tre appele. Il exige ensuite de rserver sur lapile un espace suffisant pour stocker les variables locales de cette mthode. Lespace ncessairepour cela est fix : il ne dpend que du texte du programme. Donc, cette opration cote O(1)en temps et O(1) en espace sur la pile. Cet espace est libr ds que la mthode termine sonexcution. Soulignons que nous mesurons ici uniquement le cot du mcanisme dappel demthode. Naturellement, la mthode qui est appele peut elle-mme avoir un cot arbitraire.

Laccs une variable locale en lecture, qui scrit x, et laccs une variable locale encriture, qui scrit x = v, ont un cot O(1) en temps. En effet, deux situations peuvent seprsenter. Si la mthode accde une de ses propres variables locales, alors il faut accder la

24 CHAPITRE 1. DONNES ET COMPORTEMENT

pile. Si la mthode accde une variable locale en provenance de lextrieur, comme cest lecas lors de laccs la variable y dans la fonction x -> x + y, alors il faut en ralit accder un champ de la clture. Dans les deux cas, un accs la mmoire suffit.

Considrons prsent OCaml.La cration dune valeur appartenant un type algbrique, qui scrit par exemple

Node (f, t1, t2), demande lallocation et linitialisation dun nouveau bloc de mmoire dansle tas. Donc, cette opration cote O(1) en temps et O(1) en espace dans le tas. La constructiondun tuple, par exemple (t1, t2), ou dun enregistrement, par exemple { x = 0; y = 0 },sont des notations diffrentes pour cette mme opration. La cration dun tableau, qui scritArray.make n x, cote O(n) en temps et O(n) en espace dans le tas. La cration dune clture,qui scrit fun x -> ..., exige comme en Java la cration dun bloc de mmoire dans le tas,donc cote O(1) en temps et O(1) en espace dans le tas.

Laccs un champ en lecture prend la forme o.f pour les enregistrements, mais aussilet (x1, x2) = o in ... pour les paires et match o with Node (f, x1, x2) -> ... pourles types algbriques. Laccs un champ en criture scrit o.f

1 + length xs

En effet, aprs lappel de length xs, il reste encore effectuer une addition 1 + .... Toutefois,en tirant parti de lassociativit de laddition, on peut reformuler cette dfinition ainsi :

let rec length_aux accu xs =match xs with| [] ->

accu| x :: xs ->

length_aux (accu + 1) xs

let length xs =length_aux 0 xs

1.3. MODLE DE COT 25

On voit que la fonction length_aux accu xs calcule la somme accu + length xs, et que, parconsquent, la nouvelle dfinition de length xs comme length_aux 0 xs est correcte. Danscette nouvelle dfinition, lappel rcursif de length_aux elle-mme est terminal. On peutnoter galement (mme si cela est moins important) que lappel de length length_aux estgalement terminal.

Comme nous lavons not plus haut, on peut considrer quun appel terminal ne consommepas despace sur la pile. En effet, le compilateur OCaml traite un tel appel de faon particulire :les variables locales de lappelant sont dsalloues avant la cration des variables locales delappel. Il en rsulte que lappel rcursif de length_aux elle-mme (par exemple) ne modifiepas la hauteur de la pile. La fonction length_aux travaille donc en espace O(1). En fait, le codemachine produit par le compilateur OCaml pour length_aux est une boucle.

Les solutions des Exercices 3.12 et 4.16, entre autres, offrent des exemples dappels rcursifsterminaux.

Scheme a t lun des premiers langages garantir que les appels terminaux sont compilsde faon efficace. Aujourdhui, OCaml, Haskell, C#, Scala, entre autres, offrent cette garantie.Malheureusement, C et Java traitent les appels terminaux comme des appels ordinaires.

Il nous reste discuter le cot du garbage collector (Remarque 1.2). Celui-ci est appellorsquon souhaite allouer un bloc dans le tas et lorsque lespace libre restant est insuffisantpour crer ce bloc. Le GC examine alors tout ou partie du contenu du tas. Sil dtermine quecertains blocs de mmoire sont inaccessibles, alors il peut dtruire ces blocs, cest--dire librerlespace quils occupent.

Le temps ncessaire lexcution du GC est en gnral difficile valuer, car il dpenddune part de lalgorithme utilis par le GC pour dterminer quels objets sont inaccessibles,dautre part de la taille du tas. On imagine bien, intuitivement, que si le tas est trs grand, alorsle GC sera appel moins frquemment et cotera donc moins cher. la limite, lorsque la tailledu tas tend vers linfini, le cot du GC tend vers zro. Inversement, si le tas est trs petit, alorsle GC sera appel plus frquemment et cotera donc plus cher. la limite, si la taille du tastend vers sa valeur minimum acceptable ( savoir, un instant donn, la somme des taillesdes blocs accessibles), chaque tentative dallouer un bloc risque de demander lexamen parle GC de tous les blocs existants. On peut ainsi construire un programme dont la complexiten temps passe de O(n) lorsquon lui attribue suffisamment de mmoire (n2) lorsquon luiattribue trop peu de mmoire.

Bien que le GC puisse en pratique avoir un cot important, on nglige habituellement soninfluence lors de ltude thorique de la complexit dun algorithme ou dun programme. Pourcertains algorithmes de GC, on peut dmontrer que si la taille du tas est tout instant au moins2 fois sa valeur minimum acceptable, alors le cot amorti du GC est nul. En dautres termes,sous cette hypothse, on peut considrer que lallocation cote O(1) et que la dsallocation necote rien : cela conduit une analyse valide du temps de calcul total.

Pour tudier le cot en espace dun programme, on tudie sparment lespace maximalrequis sur la pile (cest--dire, une constante prs, le nombre maximal dappels de fonctionsimbriqus) et lespace maximal requis dans le tas (cest--dire la valeur maximale au coursdu temps de la somme des tailles des blocs accessibles). Cette dernire tude peut tre assezsubtile, comme lillustrent par exemple les Exercices 4.26 et 4.27.

26 CHAPITRE 1. DONNES ET COMPORTEMENT

Chapitre 2

Abstraction

Au cours du Chapitre 1, nous avons mis en vidence dimportants points communs entredeux langages de programmation que lon aurait pu croire au premier abord trs diffrents, savoir Java et OCaml. Dune part, nous avons compar lorganisation des donnes en mmoireet constat que, pour ces deux langages, elle peut tre comprise et dcrite en termes de sommes,de produits, et de rcursivit. Dautre part, nous avons prsent la faon dont un comportementest reprsent par un objet de Java ou par un groupe de fonctions dOCaml.

Vis--vis de ces deux aspects, les types jouent un rle fondamental. Dabord, ils constituentun langage de description des donnes. laide dun petit nombre de concepts universels, savoir types primitifs, types produits, types sommes, et types rcursifs, on peut dcrirelorganisation en mmoire de nimporte quelle structure de donnes : liste, arbre, etc. Ensuite,ils offrent un langage de description de composants logiciels. En effet, laide des types dobjetde Java (cest--dire les classes et interfaces) ou bien laide des types de fonction dOCaml,on dcrit la faon dont un composant logiciel est prt communiquer avec lextrieur : uncompteur fournit une mthode ou fonction get qui nattend aucun argument et renvoie unrsultat entier ; une mthode ou fonction increment qui, etc. . Bref, les types dcrivent leservice rendu par ce composant.

Cependant, le rle des types nest pas seulement descriptif. Leur principale force, en ralit,est de nous permettre de construire et faire respecter des abstractions. Selon Reynolds (1983), type structure is a syntactic discipline for enforcing levels of abstraction .

Que signifie ceci ? Souvent, dcrire la structure concrte, dtaille, des donnes dans lammoire nest pas souhaitable. Une date, par exemple, est intuitivement un objet auquel onpeut appliquer certaines oprations, comme ajouter une semaine ou comparer uneautre date . Certes, une date doit tre reprsente en mmoire dune certaine manire, parexemple par un triplet dentiers (anne, mois, jour), par un unique entier (la norme POSIXreprsente une date comme le nombre de secondes coules depuis le 1er janvier 1970), ouencore par un nombre rel virgule flottante. Mais, en dehors du composant logiciel quidfinit la notion de date et les oprations associes, la faon dont les dates sont reprsentesen mmoire est un dtail qui na pas et ne doit pas avoir dimportance. En dautres termes,vue de lextrieur, la notion de date est une abstraction. On souhaite que les utilisateursmanipulent des valeurs de type date comme sil sagissait dun type primitif, au mme titreque les types entier et boolen . On souhaite de plus quil soit impossible de confondreune date et un entier, mme sil est vrai aujourdhui quune date est reprsente en mmoiresous forme dun entier. Une telle confusion soit serait une erreur dinadvertance de la partde lutilisateur, soit rsulterait du fait que lutilisateur sait (ou croit savoir) quune date estreprsente en mmoire par un entier, et souhaite en tirer parti, par exemple en crivantlet tomorrow (d : date) : date = d + 86400. Mme dans ce dernier cas, lutilisateur atort, car si date est une abstraction, alors son auteur conserve la libert de modifier lamanire dont une date est reprsente en mmoire.

27

28 CHAPITRE 2. ABSTRACTION

La notion dabstraction nest pas propre linformatique. Elle existe galement, entre autresdomaines, en mathmatiques. La fable prsente par Reynolds (1983) souligne le fait quunnombre complexe ne doit pas tre considr comme une paire de rels sous forme cartsiennea + ib, ni comme une paire de rels sous forme polaire rei. Mieux vaut considrer un nombrecomplexe comme un lment dun certain corpsC, dont on sait quil est une clture algbriquede R. En dehors de la leon o on construit effectivement le corps des nombres complexes laide dune dfinition concrte, le corps C peut et doit tre trait comme une abstraction.

En informatique, comment construire et faire respecter une abstraction ? Plus prcisment,quels outils un langage de programmation fournit-il pour cela ? On peut apporter cettequestion (au moins) deux rponses fondes sur deux outils distincts.

La premire rponse suppose que la discipline des types est impose statiquement, cest--dire impose par le compilateur. Cest le cas pour Java et pour OCaml. Alors, le concepteurde labstraction date peut indiquer au compilateur que le type date doit tre considrcomme un type abstrait, cest--dire un type dont la dfinition est connue du concepteur, maisinconnue des utilisateurs. Ainsi, lintrieur du composant qui dfinit labstraction date ,on sait, par exemple, que le type date est synonyme du type entier , ou bien que le type date possde un champ de type entier . lextrieur de ce composant, toutefois, cetteinformation ne peut pas tre exploite : le compilateur linterdit. lextrieur, donc, on saitque date est un type, mais rien de plus. Si un programme crit par un utilisateur fournitun entier l o une date est attendue, alors ce programme est considr comme erron, et estrejet par le compilateur.

La seconde rponse sappuie sur la notion de fonction, au sens de clture (1.2.2). Ellesuppose quune clture est opaque, cest--dire que la seule manire possible dutiliser unefonction est dappeler cette fonction. Cest le cas des langages typs statiquement, comme Java 8et OCaml, mais aussi de certains langages typs dynamiquement, comme Scheme et JavaScript. laide de cette abstraction primitive, cest--dire fournie par le langage de programmation,on peut alors construire de nouvelles abstractions. Un compteur , par exemple, peut tredfini comme un objet qui rend deux services, savoir increment et get (1.2.2). On peutproposer, en Java, une dfinition du type compteur sous forme dune interface :

public interface ICounter {void increment ();int get ();

}

En OCaml, on peut poser quun compteur est une paire de cltures :

type counter ={ increment : unit -> unit; get: unit -> int }

Dans un langage typ dynamiquement, comme JavaScript, on ncrit pas de dfinitions detypes. Nanmoins, on pourrait poser (sous forme dun commentaire) quun compteur estun objet dot de deux mthodes increment et get. Dans tous les cas, la notion de compteur est bien une abstraction, au sens o lutilisateur na accs quaux deux oprations prvues par leconcepteur, et ne sait pas comment un compteur est reprsent en mmoire. Si un programmecrit par lutilisateur demande lire le champ value dun compteur, alors ce programme estrejet (ds la compilation si le langage est typ statiquement ; pendant lexcution si le langageest typ dynamiquement), et ce indpendamment du fait que lobjet compteur ait ou non,en ralit, un champ nomm value.

Les deux outils prsents ci-dessus, savoir les types abstraits et les cltures, sont desmcanismes de protection : ils interdisent lutilisateur certaines oprations. Dans les deux cas,cest grce une certaine discipline de types (impose soit statiquement, soit dynamiquement)que lon peut distinguer oprations permises et oprations interdites.

En rsum, dans un langage de programmation de haut niveau, les types constituent unmcanisme de protection, donc permettent de construire des abstractions inviolables.

29

Parmi les deux mcanismes de protection que nous venons de prsenter, savoir les typesabstraits et les cltures, lun est-il prfrable lautre, ou plus puissant que lautre ? Tenter derpondre formellement cette question nous conduirait un peu loin. Nous laborderons lorsde certains exercices, dont les Exercices 3.21 et 4.13.

Entre les langages typs statiquement et ceux typs dynamiquement, lesquels sont prf-rables, ou plus puissants ? Les premiers offrent quelques avantages importants :

1. Une discipline de types statique, cest--dire impose par le compilateur, garantit, avantlexcution du programme, labsence de certaines erreurs. Par exemple, on ne peut pasfournir par erreur un argument entier une fonction qui attend un tableau dentiers.Cest en principe un avantage norme vis--vis des langages typs dynamiquement :cela signifie que ces erreurs sont dtectes avant la livraison, chez le fournisseur ducomposant logiciel, et non pas aprs la livraison, chez le client.

2. Si les types sont vrifis par le compilateur, alors ils constituent un langage formel, prcis,de description des donnes et des comportements. Ce ne sont pas des commentaires : leurexactitude est vrifie par le compilateur. Ils offrent donc une documentation prcise, jour, sans erreur.

3. Enfin, comme nous lavons expliqu plus haut, dans un langage de programmation typstatiquement, on peut employer un type abstrait pour imposer une abstraction, tandisque dans un langage typ dynamiquement, cet outil nexiste pas. En bref, les types nousinterdisent certaines oprations, ce qui pourrait sembler nfaste ; mais ils interdisentaussi nos adversaires certaines oprations, ce qui est clairement souhaitable dans unesituation o on ne fait pas confiance au code crit par dautres.

Cela dit, une discipline de types statique peut tre lourde ou restrictive : il peut tre pniblevoire impossible dexpliquer au compilateur , laide de dfinitions de types bien senties,pourquoi un programme est correct. Cest pourquoi les langages de programmation typsdynamiquement offrent lavantage dune plus grande flexibilit. 1

Au sens o nous venons demployer ce mot, abstraire, cest cacher. Pour construire uneabstraction, on dlimite une frontire entre intrieur et extrieur, cest--dire entre fournisseuret utilisateur dun composant logiciel. Labstraction va donc de pair avec le dcoupage dunprogramme en diffrents composants, et implique une relative isolation entre composants,chacun ignorant la faon dont les autres sont construits. Cette isolation bnficie tous. Dupoint de vue du fournisseur, labstraction empche le monde extrieur de perturber le bonfonctionnement du composant. Par exemple, si le composant implmente des ensembles laide darbres binaires de recherche quilibrs, alors, parce que le type ensemble est abstrait,il est impossible, de lextrieur, de construire de toutes pices un arbre non quilibr. Linvariantde bon quilibre est garanti, et ce, quelle que soit la manire dont le composant est utilis. Onpeut dailleurs effectuer un test unitaire pour vrifier que linvariant de bon quilibre est bel etbien respect. Du point de vue de lutilisateur, labstraction permet de remplacer facilement uncomposant par un autre de mme type. Si une implmentation du type abstrait ensemble laide darbres quilibrs nest pas satisfaisante, par exemple pour des raisons de performance,alors il est possible de la remplacer par une implmentation base sur des tables de hachage.Cette nouvelle implmentation fournit en apparence le mme type abstrait ensemble etles mmes oprations, donc les deux implmentations sont interchangeables. Labstractionfavorise ainsi lvolution des logiciels, ainsi que leur construction partir de composantsstandardiss. Au lieu dabstraction, on parle parfois dencapsulation ou dinformation hiding.

Cependant, le mot admet galement un autre sens : abstraire, cest gnraliser ; abstraire,cest paramtrer. En mathmatiques, par exemple, le thorme fondamental de larithmtique,

1. propos du dbat entre partisans des deux bords, jaime beaucoup cette phrase de Reynolds (Three approachesto type structure, 1985) : The divis