M1 2016/2017 : Programmation Fonctionnelle Avancée

Université Paris-Diderot, UFR d'Informatique

Salles et Horaires

Cours : Jeudi, 16h00-18h00, salle 1008 bâtiment Sophie Germain. Premier cours : Jeudi septembre 15.
Cours du 15 décembre: 14h-16h, salle 1008.

TP : Vendredi, 15h30-17h30, salle 2001, bâtiment Sophie Germain. Premier TP : Vendredi septembre 16.

Projet

Le projet est en ligne ! Tous les détails dans ce dépôt git, voir en particulier le README.md. Vous devez travaillez dans un clone de ce dépôt, et nous y donner accès.

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 15/9 Chapitre 0 : Introduction, rappels OCaml [transparents] [exemples]
-- 22/9 pas de cours cette semaine
2 29/9 Chapitre 1 : Le système de modules : structures, signatures [transparents] [exemples]
3 6/10 Chapitre 2 : Structures fonctionnelles efficaces: Les Zippers [transparents] [exemples]
4 13/10 Chapitre 3 : Structures fonctionnelles efficaces: files et arbres red-black, analyse de coût amorti [transparents] [exemples]
5 20/10 Chapitre 4 : Évaluation paresseuse [transparents] [exemples]
6 27/10 Chapitre 5 : Structures fonctionnelles efficaces : la paresse maîtrisée [transparents] [exemples]
-- 3/11 semaine de pause M1
7 10/11 Chapitre 6 : Structures partagées : le hashconsing [transparents] [exemples]
8 17/11 Chapitre 7 : Inférence de types, polymorphie et traits impératifs. [transparents] [exemples]
9 24/11 Chapitre 8 : Usages avancés du système de type : variants polymorphes et sous-typage. [transparents] [exemples]
10 1/12 Chapitre 9 : Usages avancés du système de type : types phantomes et GADTs [transparents] [exemples]
11 8/12 Chapitre 10 : Combinateurs [transparents] [exemples]
12 15/12 Chapitre 11 : Introduction à la programmation monadique [transparents] [exemples]

Feuilles de TP

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.

Mooc

Join our Mooc Introduction to functional programming in OCaml. Start: September 26, 2016.

Livres et polycopiés

Équipe pédagogique

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

Valid HTML 4.01 Transitional