M1 2020/2021 : Programmation Fonctionnelle Avancée

Université de Paris, Faculté des Sciences, Campus des Grands Moulins, UFR d'Informatique

Contenu du cours

La programmation fonctionnelle est née presque en même temps que la programmation impérative, avec le langage Lisp à la fin des années 1950. Utilisée comme paradigme de programmation privilégié dans les années 1970 à 1990 pour l'Intelligence Artificielle, elle demandait des machines puissantes et chères, et paraissait être réservée à des usages très spécialisés. Depuis les années 1990, on dispose de langages fonctionnels avancés qui sont à la fois puissants, expressifs et efficaces. La famille des langages ML (comme OCaml, Haskell, SML/NJ) dispose en plus de méchanismes de typage puissants et sûrs, et d'abstractions qui permettent une programmation concise, comme la définition par cas, les types algébriques, les modules paramétriques, et, dans le cas d'OCaml, aussi un support complet pour la programmation objet. Avec l'essor du Web, des grandes masses de données et des applications distribuées, la programmation fonctionnelle commence à être reconnue comme un des paradigmes les plus adaptés pour construire de façon concise et simple des applications distribuées dans le Cloud. Il suffit de penser au schèma MapReduce popularisé par Google, qui n'est autre qu'une combinaison de deux primitives fonctionnelles connues depuis longtemps.

Ce cours se propose d'approfondir les connaissances des étudiants sur la programmation fonctionnelle, en utilisant pour cela toutes les fonctionnalités du langage OCaml. Système de modules, structures de données fonctionnelles efficaces, calcul paresseux, programmation monadique, usages avancés du système de type, combinateurs, transformations de programmes seront abordés systématiquement dans le cours.

Planning indicatif du cours

Numéro Date Cours Contenu
1 Chapitre 0 : Introduction, rappels OCaml
2 Chapitre 1 : Le système de modules : structures, signatures
3 Chapitre 2 : Structures fonctionnelles efficaces: Les Zippers
4 Chapitre 3 : Structures fonctionnelles efficaces: files et arbres red-black, analyse de coût amorti
5 Chapitre 4 : Évaluation paresseuse
6 Chapitre 5 : Structures fonctionnelles efficaces : la paresse maîtrisée
7 Chapitre 6 : Structures partagées : le hashconsing
8 Chapitre 7 : Combinateurs
9 Chapitre 8 : Inférence de types, polymorphie et traits impératifs.
10 Chapitre 9 : Usages avancés du système de type : variants polymorphes et sous-typage.
11 Chapitre 10 : Usages avancés du système de type : types phantomes et GADTs
12 Chapitre 11 : Monades

Contrôle de connaissance

Ressources et Bibliographie

Référence du langage OCaml

Forums et listes de discussion

Une liste de forums dédiés à OCaml est maintenue sur le site d'Inria.

Livres et polycopiés

Équipe pédagogique

Ralf Treinen(Cours)
Pierre Letouzey (TD/TP)

Valid HTML 4.01 Transitional