Computer Laboratory

Course pages 2014–15

Advanced Functional Programming

Principal lecturers: Dr Anil Madhavapeddy, Dr Jeremy Yallop
Additional lecturers: Prof Alan Mycroft, Dr Leo White
Taken by: MPhil ACS, Part III
Code: L28
Hours: 16
Prerequisites: Students wishing to take the module should have some experience of a typed functional programming language and an understanding of type inference.

Aims

This module aims to teach students how to use the features of modern typed functional programming languages (e.g. OCaml, Haskell) to design and implement libraries and DSLs. It aims to demonstrate how such techniques can improve both correctness and efficiency.

Students wishing to take the module should have some experience of a typed functional programming language and an understanding of type inference.

Syllabus

Part 1: Types in functional languages.

  • The Curry-Howard isomorphism. Hindley-Milner type inference and beyond. Introduction to OCaml.
  • Higher-rank polymorphism. Duality of existentials and universals.
  • Records, variants, and row polymorphism.
  • Modules, signatures, and functors.
  • Phantom types and generalised algebraic data types.

Part 2: Programming in functional languages.

  • Typeful interfaces and domain-specific languages.
  • Monads and related abstractions.
  • Type-indexed values.
  • Staging and metaprogramming.

Objectives

On completion of this module students should be able to:

  • Understand extensions to Hindley-Milner type systems common in modern typed functional programming languages (e.g. OCaml, Haskell).
  • Apply modern approaches to designing libraries and DSLs, with appropriate use of monads, arrows, and related abstractions.
  • Use advanced type system features to specify precise typed interfaces.
  • Understand staging for metaprogramming.

Coursework

Coursework will consist of three take-home problem sets.

Practical work

In addition to the take-home problem sets there will be (unassessed) interactive exercises to accompany many of the lectures.

Assessment

Three take-home problem sets, each accounting for approximately a third of the marks.

Recommended reading

Minsky, Y. & Madhavapeddy, A. and Hickey, J. (2013). Real World OCaml. O'Reilly Media (1st edition). (Also available online.) We'll assume familiarity with the concepts introduced in chapters 1--6.
Pierce, B. C. (2002). Types and Programming Languages. The MIT Press (1st edition). Pierce's book will be a useful reference for some of the concepts introduced in the first half of the course, although we'll be taking a less formal approach.