0

Table des matières

1 Présentation du langage ML 7 1.1 Rappel du noyau ML . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.2 Sémantiques opérationnelles . . . . . . . . . . . . . . . . . . . . . . . . 8

1.2.1 Sémantique à grands pas . . . . . . . . . . . . . . . . . . . . . . 9 1.3 Typage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.4 Le système de type de ML . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.5 Propriétés du typage . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2 Sémantique à petits pas 15 2.1 Sémantique à petits pas . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.2 Correction du typage vis à vis de la sémantique . . . . . . . . . . . . . 19 2.3 Quelques extensions “gratuites” du langage . . . . . . . . . . . . . . . . 24

3 Ajout de constructions impératives. 29 3.1 Constructions impératives . . . . . . . . . . . . . . . . . . . . . . . . . 29 3.2 Une sémantique à réduction pour les objets mutables . . . . . . . . . . 30 3.3 Typage des références . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 3.4 Correction de la sémantique . . . . . . . . . . . . . . . . . . . . . . . . 34 3.5 Les autres formalismes . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

3.5.1 Le typage des fermetures . . . . . . . . . . . . . . . . . . . . . . 41 3.5.2 Les régions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

3.6 D’autres constructions impératives . . . . . . . . . . . . . . . . . . . . 42 3.6.1 Les opérations de contrôle . . . . . . . . . . . . . . . . . . . . . 43

4 Les enregistrements polymorphes 45 4.1 Des enregistrements déclarés aux enregistrements extensibles . . . . . . 45 4.2 Principe du typage des enregistrements extensibles . . . . . . . . . . . 47 4.3 Algèbres d’enregistrements . . . . . . . . . . . . . . . . . . . . . . . . . 50 4.4 Synthèse de type . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 4.5 Correction de la sémantique . . . . . . . . . . . . . . . . . . . . . . . . 51 4.6 Les variantes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 5 Typage avec contraintes 57

5.1 Sous-typage sur les types sans-variables . . . . . . . . . . . . . . . . . . 59 5.2 Contraintes avec variables . . . . . . . . . . . . . . . . . . . . . . . . . 61

5.2.1 Types récursifs . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 5.2.2 Implication de contraintes . . . . . . . . . . . . . . . . . . . . . 65

5.3 Un système de typage avec contraintes . . . . . . . . . . . . . . . . . . 66 5.4 Sûreté du typage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 5.5 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

5.5.1 Simplification des contraintes . . . . . . . . . . . . . . . . . . . 74

6 Introduction aux Objets 79

6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 6.1.1 Pourquoi la programmation à objets ? . . . . . . . . . . . . . . 79 6.1.2 Un style de programmation . . . . . . . . . . . . . . . . . . . . 81 6.1.3 Objets et Classes avec des enregistrements extensibles . . . . . . 84 6.1.4 Les notions délicates . . . . . . . . . . . . . . . . . . . . . . . . 88 6.1.5 Typage et sous-typage : une nécessité, des difficultés . . . . . . 91

6.2 Objets et classes dans le langage Ocaml . . . . . . . . . . . . . . . . . . 92 6.2.1 Présentation du langage Ocaml . . . . . . . . . . . . . . . . . . 92 6.2.2 Génération automatique de types . . . . . . . . . . . . . . . . . 99

6.3 Les Objets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 6.3.1 Un contre exemple . . . . . . . . . . . . . . . . . . . . . . . . . 100 6.3.2 Les objets, formellement . . . . . . . . . . . . . . . . . . . . . . 102 6.3.3 Les objets en général . . . . . . . . . . . . . . . . . . . . . . . . 104

6.4 Les Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 6.4.1 Les classes en Objective Caml . . . . . . . . . . . . . . . . . . . 106 6.4.2 Pourquoi des classes ? . . . . . . . . . . . . . . . . . . . . . . . 106 6.4.3 L’héritage n’est pas du sous-typage . . . . . . . . . . . . . . . . 108 6.4.4 Pré-méthodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 6.4.5 Liaison tardive et typage . . . . . . . . . . . . . . . . . . . . . . 110 6.4.6 Héritage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 6.4.7 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 6.4.8 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113

7 D’autres extensions du langage 117

7.1 Extensions horizontales . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 7.1.1 Types dynamiques . . . . . . . . . . . . . . . . . . . . . . . . . 117 7.1.2 Types existentiels . . . . . . . . . . . . . . . . . . . . . . . . . . 119 7.1.3 Types universels . . . . . . . . . . . . . . . . . . . . . . . . . . 121

7.2 Extensions verticales . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 7.2.1 Et si les types étaient récursifs . . . . . . . . . . . . . . . . . . . 121 7.2.2 Types d’ordre supérieur . . . . . . . . . . . . . . . . . . . . . . 122 7.2.3 Types intersection . . . . . . . . . . . . . . . . . . . . . . . . . 123 TABLE DES MATIÈRES 3 A Solutions des exercices 125