babel
Advanced Programming course
Contents.
WORK PERMANENTLY IN PROGRESS: THIS PAGE HAS BEEN CHANGING SINCE ITS CREATION

In this course we study several "high level" aspects of programming languages. We introduce new concepts that complete the curricula on programming concepts (modules, objects, subtyping, concurrency) as well as some techniques (e.g., monadic transformations for different effect systems) that allow us to compare different programming paradigms.
While the reference language of the course will be OCaml, we will use code excerpts of Haskell, Scala, Perl 6, C#, Java, Erlang, Pascal, Python, Basic, CDuce, Xslt, Go, ... . The idea is that we want to focus more on programming concepts rather than on programming in a particular language.
  • Module systems
    - 1. Introduction to modularity. - 2. ML simple modules. - 3. Functors.
  • Classes vs. Modules
    - 4. Modularity in OOP. - 5. Mixin Composition - 6. Multiple dispatch - 7. OCaml Classes - 8. Haskell’s Typeclasses - 9. Generics
  • Computational effects.
    - 10. Exceptions. - 11. Imperative features. - 12. Continuations
  • Program transformations
    - 13. The fuss about purity - 14. A Refresher Course on Operational Semantics - 15. Closure conversion - 16. Defunctionalization - 17. Exception passing style - 18. State passing style - 19. Continuations, generators, and coroutines - 20. Continuation passing style
  • Abstract Machines
    - 21. A simple stack machine - 22. The SECD machine - 23. Adding Tail Call Elimination - 24. The Krivine Machine - 25. The lazy Krivine machine - 26. Eval-apply vs. Push-enter - 27. The ZAM - 28. Stackless Machine for CPS terms
  • Monadic Programming
    - 29. Invent your first monad - 30. More examples of monads - 31. Monads and their laws - 32. Program transformations and monads - 33. Monads as a general programming technique - 34. Monads and ML Functors
  • Subtyping
    - 35. Subtyping of simple types - 36. Extensions: products, records, references - 37. Set-theoretic types: unions, intersections and negations - 38. Covariance and contra-variance - 39. Pattern matching for set-theoretic types: XML and CDuce - 40. Type reconstruction: the typing of ML
  • XML Programming
    - 41. XML basics - 42. Set-theoretic types - 43. Examples in Perl - 44. Covariance and contravariance - 45. XML Programming in CDuce - 46. Toolkit
  • Concurrency
    - 47. Notions of concurrency - 48. Preemptive multi-threading - 49. Mutexes, Conditional Variables, Monitors - 50. Doing without mutual exclusion - 51. Cooperative multi-threading - 52. Channeled communication - 53. Software Transactional Memory
Essential bibliography
  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
Advanced bibliography
  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. 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
  8. 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
  9. Simon Peyton Jones. The Spineless Tagless G machine. 1992
    The original presentation of the STG virtual machine for Haskell, now outdated.
  10. 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.
  11. T. Griffin. A Formulæ-as-Types Notion of Control. POPL 1990.
    It explains the logical role of callcc and CPS.
  12. 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
  13. K. Fraser and T. Harris. Concurrent programming without locks. ACM Transactions on Computer Systems (TOCS), 25(2):146-196, May 2007
    Lock-free programming
  14. 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.
  15. Maurice Herlihy, Nir Shavit. The Art of Multiprocessor Programming. Morgan-Kaufmann Elsevier.
    Reference for various algorithms presented in the concurrency part of the couse
Slides presented at the course
Versions with all slides transitions (unfit to be printed)
  1. Module Systems (in French)
  2. Classes vs. Modules (in English)
  3. Computational effects (in French)
  4. Program Transformations (in English)
  5. Abstract Machines (in English)
  6. Monads (in English)
  7. Subtyping (in English)
  8. XML Programming (in English)
  9. Concurrency (in English)
For a printable version (no slide transition but less content) you can download all slides in a single file.
Tutorials
Practical works are provided by David Baelde and their contents can be found in this page.

Powered by CDuce

XHTML Strict valid!

CSS valid!

Site map
This site was generated by two CDuce programs: the first transforms BibTeX files into an XML document while the second generates from this and few other XML documents a set of statically certified XHTML-strict pages with table of contents, list of references, non-dangling internal links, etc. More details can be found here.Français fr