Cours Avancé de Langages de Programmation
Contenu du cours.
PAGE NON DEFINITIVE ... A JAMAIS
le contenu du programme, les références, et les transparents seront mis à jour au fur et à mesure
Dans ce cours, nous étudions plusieurs aspects "de haut-niveau" des langages de programmation. Nous introduisons de nouveaux concepts qui complémentent la formation en programmation (modules, objets, sous-typage, concurrence) ainsi que des techniques qui enrichissent la vision des différents paradigmes de programmation (transformations monadiques pour différents types d'effets).
Le langage de référence pour le cours est OCaml, mais nous utiliserons aussi des extraits de code Haskell, Scala, Perl 6, C#, Java, Erlang, Pascal, Python, Basic, CDuce, Xslt, Go, ... . L'idée étant de mettre l'accent sur les concepts de la programmation plus que sur la programmation dans un langage particulier.
  • Sytèmes de modules
    - 1. Introduction à la Modularité. - 2. Modules (simples) en ML. - 3. Foncteurs.
  • Classes vs. Modules
    - 4. Modularité dans les langages objets - 5. Mixins - 6. Dispatch multiple - 7. Les classes en OCaml - 8. Les Typeclasses d'Haskell - 9. Generics
  • Transformation de programmes
    - 10. A propos de la pureté - 11. Rappels de sémantique opérationnelle - 12. Closure conversion - 13. Defonctionalisation - 14. Exception passing style - 15. State passing style - 16. Continuations, générateurs et co-routines - 17. Continuation passing style
  • Programmation Monadique
    - 18. Votre première monade - 19. Exemples de monades - 20. Les lois monadiques - 21. Transformation de programmes et monades - 22. Monades comme technique de programmation - 23. Monades et foncteurs
  • Sous-typage
    - 24. Sous-typage des types simples - 25. Extensions: produits, enregistrements, références - 26. Types ensemblistes: unions, intersections et négations - 27. Covariance et contra-variance - 28. Filtrage par types ensemblistes: XML et CDuce - 29. Reconstruction de types : le typage de ML
  • Programmation XML
    - 30. XML concepts de base - 31. Types ensemblistes - 32. Exemples en Perl - 33. Covariance et contravariance - 34. Programmation XML en CDuce - 35. Toolkit -
  • Concurrence
    - 36. Notions de concurrence - 37. Multi-threading préemptif - 38. Mutexes, Conditional Variables, Monitors - 39. Travailler sans exclusion mutuelle - 40. Multi-threading coopératif - 41. Communication par canaux - 42. Software Transactional Memory
Bibliographie essentielle
  1. Emmanuel Chailloux,Pascal Manoury,Bruno Pagano. Développement d'applications avec Objective Caml
  2. Philip Wadler Monads for fuctional Programming In Advanced Functional Programming, Proceedings of the Baastad Spring School, May 1995, Springer Verlag Lecture Notes in Computer Science 925.
  3. Giuseppe Castagna. Covariance and Contravariance: a fresh look at an old issue.
  4. Tim Harris. A Pragmatic Implementation of Non-Blocking Linked-Lists DISC 2001
Pour aller plus loin :
  1. P. Sestoft and H Hansen. C# Precisely.
    A nice book on C#
  2. Bryan O'Sullivan, Don Stewart, and John Goerzen Real World Haskell.
    Online book for advanced programming in Haskell
  3. Dean Wampler, Alex Payne. Programming Scala. O'Reilly.
    Online book on Scala
  4. G. Castagna and A. Frisch. A Gentle introduction to Semantic Subtyping. Proceedings of PPDP '05, the 7th ACM SIGPLAN International Symposium on Principles and Practice of Declarative Programming, pages 198-208, ACM Press (full version) and ICALP '05, 32nd International Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science n. 3580, pages 30-34, Springer (summary), July, 2005. Joint ICALP-PPDP keynote talk.
    A simple introduction to semantic subtyping. Much more digestible than the next reference
  5. A. Frisch, G. Castagna and V. Benzaken. Semantic Subtyping: dealing set-theoretically with function, union, intersection, and negation types . Journal of the ACM 55(4):1-64, 2008.
    The most complete reference about semantic subtyping
  6. V. Benzaken, G. Castagna, and A. Frisch. CDuce: an XML-Centric General-Purpose Language. In ICFP '03, 8th ACM International Conference on Functional Programming, pag. 51―63, ACM Press, 2003.
    Reference paper about CDuce
  7. P.-L. Curien, G. Ghelli. Coherence of subsumption, minimum typing and type-checking in Fsub. Mathematical Structures in Computer Science, 2(1):55-91, 1992.
    Subtyping systems and algorithms for explicit polymorphic functions.
  8. T. Griffin. A Formulæ-as-Types Notion of Control. POPL 1990.
    It explains the logical role of callcc and CPS.
  9. Andrzej Filinski. Representing Monads. In Proceedings of the 21st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages,
    It nicely explains the relation between Monads and CPS
  10. K. Fraser and T. Harris. Concurrent programming without locks. ACM Transactions on Computer Systems (TOCS), 25(2):146-196, May 2007
    Lock-free programming
  11. Vladimir Gapeyev, Michael Y. Levin, Benjamin C. Pierce. Recursive Subtyping Revealed. Journal of Functional Programming, 12:511-548, 2002.
    Subtyping recursive types is not an easy matter. This very pedagagical paper explains all you need to know about it.
  12. Maurice Herlihy, Nir Shavit. The Art of Multiprocessor Programming. Morgan-Kaufmann Elsevier.
    Reference for various algorithms presented in the concurrency part of the couse
Travaux dirigés
Les travaux dirigés sont assurés par David Baelde et leur contenu se trouve sur cette page.