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.
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
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.
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
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
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
Slides presented at the course
Versions with all slides transitions (unfit to be printed)