Cours de Programmation Fonctionnelle Avancée 2013/2014

Master d'Informatique, 1ère année
Roberto Di Cosmo
Laboratoire Preuves, Programmes, Systèmes (PPS)
Université de Paris Diderot Paris 7  
e-mail: roberto@dicosmo.org
WWW: http://www.dicosmo.org


Salle et Horaires

Mercredi, 14h à 16h, salle 247E. Premier cours: mercredi 18 Septembre.

Le TD/TP a lieu les mrecredis de 16h à 18h en salle 2031. Premier TD/TP: le mercredi 18 Septembre.


Public

Ce cours est ouvert à tous les étudiants de la première année du Master Informatique, et il est obligatoire pour suivre la filière Langages de Programmation en deuxième année.
N'oubliez pas de remplir l'enquête en ligne.

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, programmations concurrente et parallèle seront abordés systématiquement dans le cours.

Planning du cours

Le planning sur cette page est indicatif et évoluera pendant le cours: revenez donc ici régulièrement. La date indiquée est celle de la dernière mise à jour des notes.

N'oubliez pas de noter les jours feriés prévus par le Calendrier de l'université.

  1. Introduction, rappels et plan (PDF)tick (19/09/2013)
  2. Le système de modules : structures, signatures et foncteurs (PDF)tick (25/09/2013 et 02/10/2013)
  3. Usages avancés du système de type: types phantomes, variants polymorphes, GADT (PDF, et le code OCaml)tick (09/10/2013 et 16/10/2013)
  4. Programmation avec des combinateurs, map/reduce, optimisations (PDF, le code OCaml de MSS et le code OCaml pour les combinateurs)tick (23/10/2013)
  5. Programmer avec la comprehension (PDF et le code OCaml)tick (30/10/2013)
  6. Monades avec somme (PDF et le code OCaml)tick (06/11/2013)
  7. Structures fonctionnelles efficaces: les Zippers (PDF et le code OCaml)tick (13/11/2013)
  8. Structures fonctionnelles efficaces: files et arbres red-black, analyse de côut amorti (PDF et le code OCaml)tick (27/11/2013)
  9. Evaluation paresseuse et structure fonctionnelles persistantes efficaces (PDF, et le code OCaml)tick (04/12/2013 et 11/12/2013)
  10. Introduction à la programmation monadique: les interpreteurs (PDF, et le code OCaml)tick (11/12/2013)
  11. Transformation de monades
  12. La modade Lwt pour la programmation concurrente collaborative
  13. La programmation avec les continuations

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.

Le projet

Le sujet du projet sera mis en ligne Vous pouvez faire le projet en groupes de deux personnes au maximum; la note sera individuelle. Vous devrez rendre le projet complet au plus tard le Lundi 6 Janvier 2014 à 12h00. Une soutenance sera organisée pendant la semaine des examens.

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

Roberto Di Cosmo (Cours)
Gabriel Scherer (TD/TP, gabriel dot scherer at gmail)
La mailing list m1-13-14-pfav est ouverte pour le cours sur
http://listes.sc.univ-paris-diderot.fr/sympa/info/m1-13-14-pfav
inscrivez-vous de suite.
N'oubliez pas, après l'examen, de remplir le formulaire d'évaluation du cours.

Valid HTML 4.01 Transitional