This old page is kept for historical purposes only; the current 2011/2012 course page is here.

PFA is a course about advanced aspects of functional programming. It is part of the Master 2 Spécialité Programmation et Logiciels Sûrs of Institut Galilée, Université Paris Nord.

This year I teach classes (CM), while Jean-Yves Moyen manages the lab exercises (TP). With some fine-tuning and changes, my lessons are based on what Jean-Vincent Loddo and Jean-Yves did last year; of course all mistakes in what I do or write remain mine.

Even if I speak French in class, I maintain these pages in English. There are essentially three reasons:

• English is easier for me to use, and I can update the page much faster this way. Don't expect to read a new Shakespeare on the course page, but at least this thing will be up-to-date.
• I'd like these pages to be be useful to other people who don't understand French. English is much more widely spoken.
• The most important reason is that you are expected to work with English-only documentation. As Master-level students you have to speak English: please get at least used to read it.

Project

Jean-Yves Moyen has prepared a really, really nice project based on TrivialML. You can find the text here on his home page; the text also contains a link to the tarball you have to download.

Written exam (2010-12-17), with solution

You can find everything here.

Written exam (rattrapage, 2011-06-16), with solution

You can find everything here.

Last year's written exam

I've published here a copy of last year's written exam (by Jean-Vincent Loddo et Jean-Yves Moyen), including solutions.

Compared to last year, this year we have let you do more exercises on functors; we have also spoken about the runtime, so expect a question or two about that. About the rest, the questions will be similar to what you see here.

Erreur à localiser

J'ai trouvé un bug : la version courante de TrivialML accepte le programme suivant, clairement pas bien typé :

let x : int = 1 in x + True

In September 2010 I made a course mailing list, used for communications and answering questions: if you are a PFA student you are strongly advised to subscribe using this simple web interface. You can send a message to all subscribers (including Jean-Yves Moyen and me, of course) by writing to the address pfa@lipn.univ-paris13.fr . You are free to use a nickname instead of your real name on the list, if you prefer so.

We will use the Objective Caml language, also called OCaml; you are expected to become fluent in it.
You don't really need to buy books about the language unless you prefer the paper format, as the documentation you find on the Net is really good; in several cases the same text is available on paper and in electronic form.

Of course, you should always have available the official OCaml documentation, particularly the default interface library. We also recommend the following texts, all of which are available online:

• Emmanuel Chailloux, Pascal Manoury, Bruno Pagano, Developing Applications With Objective Caml. Available in English and in French.
• Pierre Weis and Xavier Leroy, Le langage Caml, Dunod, 1999. Despite the fact that it doesn't use the current Objective Caml language because of its age, we recommend this book for its excellent programming examples. In French.
• Jean-Vincent recommends this draft of an OCaml book by Jason Hickey.
• A student told me he likes this online course in French by Maxence Guesdon [link updated in 2015].
• I still fondly remember the book from which I learnt functional programming many years ago, Functional programming using Caml Light by Michel Mauny. The language used in the book is the older Caml Light dialect instead of OCaml (there are differences in modules, and some minor syntactic aspects such as infix operators, and Caml Light lacks the object-oriented features), but essentially all the exposition remains valid.

• CM1: introduction to functional programming and OCaml
  • Introduction to functional programming and OCaml.
  • Very informal introduction to static typing, type inference and parametric polymorphism.
  • Introduction to sum types.
  Relevant handout: Syntaxe simplifiée (et idéalisée) de OCaml avec sémantique informelle by Jean-Vincent Loddo.
• CM2: more programming in OCaml: sum types, polymorphism
  • Something I couldn't cover in CM1 for lack of time: let blocks.
  • Practical OCaml programming, with many examples involving parametric polymorphism and higher-order.
  • Sum types explained again, with extensive examples.
  • A student asked a question about the = operator, which gave me the opportunity to quickly hint at ad-hoc polymorphism.
  The source code I have written on my computer while talking is available here.
• CM3: modules and functors
  • Easy topic for warming up: exceptions.
  • Introduction to environments (revisiting Jean-Yves's example from last TP), and to the idea of closures.
  • Separation between interface and implementation, abstract data types.
  • Modules, signatures and functors, with examples. Implemented an environment abstract data type in three different ways (list, function, application of the Map.Make functor), always using the same interface. Shown how to use the OCaml library documentation.
  Relevant handout: Modules et foncteurs en OCaml by Jean-Vincent Loddo.
  The source code I have written on my computer while talking is available here.
• CM4: interpreters
  • Easy topic for warming up: records.
  • From mathematical semantics to executable semantics: formal syntax and semantics of TrivialML.
  • Using OCaml as a meta-language: implement TrivialML by closely following mathematical syntax and semantics.
  • Quick introduction to lexer and parser generators. Adapted on the fly the frontend which I have prepared for the final project. Written a printer.
  Relevant handout: The "TrivialML" language, written by me.
  The final version of the source code I have written or modified on my computer while talking is available here.
• CM5: static typing
  • With static typing we can catch many errors before ever starting execution.
  • Understanding sequent calculus rules and proofs.
  • Typing rules for TrivialML expressions. Typing some language forms not in TrivialML (while and for loops, pair construction and selection).
  • Type checking: why it's easier than type inference. Type checking in a different style: abstract interpretation (on the computer)
  • A simple extension: adding pairs to TrivialML. How to modify domains, parser, type-checker, interpreter.
  • Exercise: finish implmenting unary operators (I've spoken about the left and right selectors for pairs, but you can also implement boolean not). I've already modified the parser.
  Relevant handout: Typing "TrivialML", written by me. Please pay attention to its errata if you have a paper copy (sorry for the confusion).
  The final version of the source code I have written or modified on my computer while talking is available here (to be read on the web) or in compressed form to download: trivialml-after-cm5.tar.gz. You can compile our interpreter by running the script: ./GO
  The script produces the TrivialML interpeter as an executable file, called a.out
  To run the interpreter interactively type ./a.out , write a TrivialML program on the terminal and push Ctrl+D to terminate.
  If you want to run the example, you can use input redirection: ./a.out < EXAMPLE
• CM6: runtime
  • Object life time: stack allocation vs. heap allocation
  • Tagging and boxing: low-level data representation
    • Why we can avoid some tagging when we use static typing
  • Introduction to automatic memory management
    • Reference counting
    • Tracing garbage collection
    • Mark-and-sweep
    • Semispace (handwaving a little)
  There was no programming this time, and I used a Beamer presentation. My slides are available in two versions, for viewing on screen and for printing: runtime-presentation.pdf, runtime-presentation--to-print.pdf. I've clarified some minor points in the presentation on 2010-12-08.

Here you can find electronic copies of what I distribute on paper in class, and copies of my projector presentations.

• The original version of The "TrivialML" language which I distributed on paper contained a small obvious mistake in the first equation of the expression semantics: a c was missing at the very end. This is fixed in the version you find here.
• I discovered in class while explaining typing rules for TrivialML that the version of Typing "TrivialML" which I had just distributed on paper contained a nasty error (the [λ] rule was wrong) and missed the [if] rule.
  Of course I've written the correct rules on the blackboard and I've very explicitly called attention to the problem, but I think one person may have left early and missed my correction.
  The electronic version you find here has been fixed in the morning of 2010-12-01; please re-download it if you got it on 2010-11-30.
  I apologize for the confusion.

Here you can find copies of the ML files I write in class on my computer. Some of them weren't originally supposed to be published as they are not particularly well-written: I use them as exercises or examples writing them while I speak; anyway some students requested a copy, so here they are.

You can find TPs on Jean-Yves Moyen's page.

Back to my home page...