“doc” (Col. : Science Sup 17x24) — 2007/7/19 — 18:18 — page vi — #2
i
i
i
i
i
i
i
i
vi
Table des matières
Chapitre 2 La programmation déclarative . . . . . . . . . . . . . . . . . . . . . . . .
25
2.1 Définir un langage de programmation pratique . . . . . . . . . . . . . . .
27
2.2 La mémoire à affectation unique . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
40
2.3 Le langage noyau déclaratif . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
47
2.4 La sémantique du langage noyau. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
55
2.5 La gestion de mémoire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
73
2.6 Du langage noyau au langage pratique . . . . . . . . . . . . . . . . . . . . . . .
81
2.7 Les exceptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
93
2.8 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
Chapitre 3 Techniques de programmation déclarative . . . . . . . . . . . . 105
3.1 La déclarativité c’est quoi ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
3.2 Le calcul itératif . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
3.3 Le calcul récursif . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
3.4 La programmation avec la récursion . . . . . . . . . . . . . . . . . . . . . . . . . . 123
3.5 Les types de données abstraits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
3.6 L’efficacité en temps et en espace . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
3.7 Les besoins non déclaratifs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
3.8 La programmation à petite échelle . . . . . . . . . . . . . . . . . . . . . . . . . . . 166
3.9 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
Chapitre 4 La programmation concurrente dataflow . . . . . . . . . . . . . 183
4.1 Le modèle concurrent dataflow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185
4.2 La programmation de base avec les fils . . . . . . . . . . . . . . . . . . . . . . . 193
4.3 Les flots . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203
4.4 Les principales limitations de la programmation déclarative . . . . 208
4.5 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215
Chapitre 5 La programmation avec état explicite . . . . . . . . . . . . . . . . . 219
5.1 L’état c’est quoi ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222
5.2 L’état et la construction de systèmes . . . . . . . . . . . . . . . . . . . . . . . . . . 224
i
i
i
i
i
i
i
i
vi
Table des matières
Chapitre 2 La programmation déclarative . . . . . . . . . . . . . . . . . . . . . . . .
25
2.1 Définir un langage de programmation pratique . . . . . . . . . . . . . . .
27
2.2 La mémoire à affectation unique . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
40
2.3 Le langage noyau déclaratif . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
47
2.4 La sémantique du langage noyau. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
55
2.5 La gestion de mémoire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
73
2.6 Du langage noyau au langage pratique . . . . . . . . . . . . . . . . . . . . . . .
81
2.7 Les exceptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
93
2.8 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
Chapitre 3 Techniques de programmation déclarative . . . . . . . . . . . . 105
3.1 La déclarativité c’est quoi ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
3.2 Le calcul itératif . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
3.3 Le calcul récursif . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
3.4 La programmation avec la récursion . . . . . . . . . . . . . . . . . . . . . . . . . . 123
3.5 Les types de données abstraits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
3.6 L’efficacité en temps et en espace . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
3.7 Les besoins non déclaratifs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
3.8 La programmation à petite échelle . . . . . . . . . . . . . . . . . . . . . . . . . . . 166
3.9 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
Chapitre 4 La programmation concurrente dataflow . . . . . . . . . . . . . 183
4.1 Le modèle concurrent dataflow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185
4.2 La programmation de base avec les fils . . . . . . . . . . . . . . . . . . . . . . . 193
4.3 Les flots . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203
4.4 Les principales limitations de la programmation déclarative . . . . 208
4.5 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215
Chapitre 5 La programmation avec état explicite . . . . . . . . . . . . . . . . . 219
5.1 L’état c’est quoi ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222
5.2 L’état et la construction de systèmes . . . . . . . . . . . . . . . . . . . . . . . . . . 224