Approche fonctionnelle de la programmation
 |
PrésentationPar Guy Cousineau et Michel Mauny ISBN: 2-84074-114-8. Publié en 1995 par McGraw-Hill. 428 pages. |
Table des matières
- Expressions
- Structures de données
- Sémantique
- Aspects impératifs
- Arithmétique exacte
- Termes formels, filtrage, unification
- Arbres équilibrés
- Graphes et résolution de problèmes
- Analyse syntaxique
- Géométrie et dessins
- Évaluation
- Compilation
- Typage
Ce livre est principalement issu du cours de programmation donné par le premier auteur à l'école normale supérieure depuis 1991. Il utilise le langage CAML un peu à la facon dont le livre d'Abelson et Sussman utilise SCHEME, c'est-à-dire comme support d'un cours introductif aux concepts de la programmation.
Le livre est divisé en trois parties. La première est une introduction progressive à CAML et à l'esprit de la programmation fonctionnelle. On introduit le noyau de CAML c'est-à-dire la structure fonctionnelle et les types de données puis on pose les principes de l'évaluation par réécriture et on introduit la notion de stratégie avant d'aborder les preuves de programmes. Enfin, une fois posés les principes de la programmation fonctionnelle, on décrit aussi les aspects non-fonctionnels de CAML.
La seconde partie du livre est consacrée à la description d'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 et applications), les arbres équilibrés pour la représentation d'ensembles et de dictionnaires, les algorithmes d'exploration de graphes avec application à des jeux à un joueur (âne rouge, solitaire), l'analyse lexicale et l'analyse syntaxique, le dessin 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 en abordant succintement les problèmes de gestion de la mémoire, et enfin la synthèse de types. Il ne s'agit pas décrire de facon exhaustive 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 demandent assez naturellement "comment ca peut marcher". La description du synthétiseur de types est cependant très proche de celui de CAML.