Approche fonctionnelle de la programmation

Table des matières

1. Expressions
2. Structures de données
3. Sémantique
4. Aspects impératifs
5. Arithmétique exacte
6. Termes formels, filtrage, unification
7. Arbres équilibrés
8. Graphes et résolution de problèmes
9. Analyse syntaxique
10. Géométrie et dessins
11. Évaluation
12. Compilation
13. Typage

Ce livre est principalement issu du cours de programmation donné par lepremier auteur à l'école normale supérieure depuis 1991.Il utilise le langage CAML un peu à la facon dont le livre d'Abelson etSussman utilise SCHEME, c'est-à-dire comme support d'un coursintroductif aux concepts de la programmation.

Le livre est divisé en trois parties. La première est uneintroduction progressive à CAML et à l'esprit de la programmationfonctionnelle. On introduit le noyau de CAML c'est-à-dire la structurefonctionnelle et les types de données puis on pose les principes del'évaluation par réécriture et on introduit la notion de stratégie avant d'aborder les preuves de programmes. Enfin, une foisposés les principes de la programmation fonctionnelle, on décritaussi les aspects non-fonctionnels de CAML.

La seconde partie du livre est consacrée à la descriptiond'applications relevant de différents domaines et susceptibles d'intéresser différents types de lecteurs ou d'étudiants.Les domaines abordés sont l'arithmétique exacte(entiers,rationnels), les algorithmes sur les termes (filtrage, unification etapplications), les arbres équilibrés pour la représentation d'ensembles et de dictionnaires, les algorithmesd'exploration de graphes avec application à des jeux à un joueur(âne rouge, solitaire), l'analyse lexicale et l'analyse syntaxique, ledessin d'arbres et la réalisation de pavages du plan.

Enfin, la troisième partie du livre est consacré à l'implantation. On décrit l'évaluation puis la compilation enabordant succintement les problèmes de gestion de la mémoire, etenfin la synthèse de types. Il ne s'agit pas décrire de faconexhaustive des implantations existantes à destination de futurs "pros"des langages fonctionnels mais plutôt de satisfaire la curiositédes lecteurs qui après avoir appris à aimer CAML se demandentassez naturellement "comment ca peut marcher". La description du synthétiseur de types est cependant très proche de celui de CAML.