Giuseppe Castagna: Cours Avancé de Langages de Programmation

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
Effets computationnels.
- 10. Exceptions. - 11. Traits impératifs. - 12. Continuations
Transformation de programmes
- 13. A propos de la pureté - 14. Rappels de sémantique opérationnelle - 15. Closure conversion - 16. Defonctionalisation - 17. Exception passing style - 18. State passing style - 19. Continuations, générateurs et co-routines - 20. Continuation passing style
Machines Abstraites
- 21. Un simple machine à pile - 22. La machine SECD - 23. Implémentation de la recursion terminale - 24. La machine de Krivine - 25. La machine de Krivine paresseuse - 26. Eval-apply vs. Push-enter - 27. La ZAM - 28. Machine sans pile pour les termes CPS
Programmation Monadique
- 29. Votre première monade - 30. Exemples de monades - 31. Les lois monadiques - 32. Transformation de programmes et monades - 33. Monades comme technique de programmation - 34. Monades et foncteurs
Sous-typage
- 35. Sous-typage des types simples - 36. Extensions: produits, enregistrements, références - 37. Types ensemblistes: unions, intersections et négations - 38. Covariance et contra-variance - 39. Filtrage par types ensemblistes: XML et CDuce - 40. Reconstruction de types : le typage de ML
Programmation XML
- 41. XML concepts de base - 42. Types ensemblistes - 43. Exemples en Perl - 44. Covariance et contravariance - 45. Programmation XML en CDuce - 46. Toolkit -
Concurrence
- 47. Notions de concurrence - 38. Multi-threading préemptif - 39. Mutexes, Conditional Variables, Monitors - 50. Travailler sans exclusion mutuelle - 51. Multi-threading coopératif - 52. Communication par canaux - 53. Software Transactional Memory

Bibliographie essentielle

Emmanuel Chailloux,Pascal Manoury,Bruno Pagano. Développement d'applications avec Objective Caml
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.
Giuseppe Castagna. Covariance and Contravariance: a fresh look at an old issue.
Tim Harris. A Pragmatic Implementation of Non-Blocking Linked-Lists DISC 2001

Pour aller plus loin :

P. Sestoft and H Hansen. C# Precisely.
A nice book on C#
Bryan O'Sullivan, Don Stewart, and John Goerzen Real World Haskell.
Online book for advanced programming in Haskell
Dean Wampler, Alex Payne. Programming Scala. O'Reilly.
Online book on Scala
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
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
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
Simon Marlow and Simon Peyton Jones. Making a fast curry: push/enter vs. eval/apply for higher-order languages, ICFP '04 and JFP '06
A nice comparison of different abstract machines for functional languages
Jean-Louis Krivine. A call-by-name lambda-calculus machine. Higher-Order and Symbolic Computation 20(3):199-207 (2007)
The paper presenting the Krivine Machine
Simon Peyton Jones. The Spineless Tagless G machine. 1992
The original presentation of the STG virtual machine for Haskell, now outdated.
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.
T. Griffin. A Formulæ-as-Types Notion of Control. POPL 1990.
It explains the logical role of callcc and CPS.
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
K. Fraser and T. Harris. Concurrent programming without locks. ACM Transactions on Computer Systems (TOCS), 25(2):146-196, May 2007
Lock-free programming
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.
Maurice Herlihy, Nir Shavit. The Art of Multiprocessor Programming. Morgan-Kaufmann Elsevier.
Reference for various algorithms presented in the concurrency part of the couse

Transparents utilisé dans le cours:

Versions avec toutes les transitions (non adaptées à être imprimées)

Pour une version imprimable (pas de transition mais moins d'informations) vous pouvez décharger tous les transparents dans un seul fichier.

Travaux dirigés

Les travaux dirigés sont assurés par David Baelde et leur contenu se trouve sur cette page.