M1 2017/2018 : Programmation Fonctionnelle Avancée

Université Paris-Diderot, UFR d'Informatique

Salles et Horaires

Cours : Mercredi, 16h30-18h30, salle 2011 bâtiment Sophie Germain.

TP : Vendredi, 15h30-17h30, salle 2031, bâtiment Sophie Germain.

Projet

Voir sur le git.

Les TP

Les feuilles de TP sont maintenant disponibles sur ce répertoire git.

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 13/09 Chapitre 0 : Introduction, rappels OCaml [Transparents] [Examples utilisés en cours]
2 20/09 Chapitre 1 : Le système de modules : structures, signatures [Transparents] [Examples utilisés en cours]
3 27/09 Chapitre 2 : Structures fonctionnelles efficaces: Les Zippers [Transparents] [Examples utilisés en cours]
4 04/10 Chapitre 3 : Structures fonctionnelles efficaces: files et arbres red-black, analyse de coût amorti [Transparents] [Examples utilisés en cours]
5 11/10 Chapitre 4 : Évaluation paresseuse [Transparents] [Examples utilisés en cours]
6 18/10 Chapitre 5 : Structures fonctionnelles efficaces : la paresse maîtrisée [Transparents] [Examples utilisés en cours]
7 25/10 Chapitre 6 : Structures partagées : le hashconsing [Transparents] [Examples utilisés en cours]
- 01/11 férié
8 08/11 Chapitre 7 : Inférence de types, polymorphie et traits impératifs. [Transparents] [Examples utilisés en cours]
9 15/11 Chapitre 8 : Usages avancés du système de type : variants polymorphes et sous-typage. [Transparents] [Examples utilisés en cours]
10 22/11 Chapitre 9 : Usages avancés du système de type : types phantomes et GADTs [Transparents] [Examples utilisés en cours]
11 29/11 Chapitre 10 : Combinateurs
12 06/12 Chapitre 11 : Introduction à la programmation monadique
13 13/12 Chapitre 12 : Monades et Compréhensions

Contrôle de connaissance

La note finale de la première session est composée par un tiers par la note du projet, et deux tiers par la note d'écrit. Lors de la deuxième session, la note est le maximum entre la note d'ecrit et 1/3 de la note du projet plus 2/3 de la note d'écrit.

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