**Lecturer: Robin Cockett**

Why is functional programming important ....

- It promotes the view of programming as a mathematical
activity.

- It promotes programming with abstractions (generic code).
- It is type safe .... the Hindley-Milner polymorphic type checker.

- It allows fast accurate prototyping for complex programs.
- It has datatypes and monads!

**COURSE OUTLINE:**

There will be a midterm exam and a final exam. The course will cover the following topics in roughly this order:

- Introduction to data, maps, and folds in Haskell (3 lectures
+
assignment)

- Monads, classes, and other topics (3 lectures + assignment)
- Introduction to the lambda calculus (5 lectures)
- Introduction to rewriting theory (4 lectures + assignment)
- Types and programming (5 lectures + assignment)

**READING (recommended):
**

- Benjamin Pierce "Types and Programming Languages" MIT Press.
- Graham Hutton "Programming in Haskell" Cambridge University Press.

**LECTURE NOTES **(as they become available)**:**

- Introduction: functional programming, Haskell, and HUGS.
- Introduction: on proofs in general.
- An example of the use of the state monad (substitution
of expressions)

- A programming approach to the lambda calculus.
- The typed lambda calculus with fixed points.
- Notes on rewriting.

- [Due September 21] Getting going with Haskell (8%) (previous years: 2006 assignment 1, 2003 assignment 1).
- [Due October 19]
Searching (see some notes here)-
sudoku
(14%)

- [Due November 16] A lambda calculus reducer (8%).
- [Due December] Type inference for the lambda calculus (15%).

- Midterm exam (20%) (2005 and answers) previous midterms (2002)
and 2007 exercise sheet!

- Final exam (35%), previous finals (2002).

Please find the lab. notes here.

**HASKELL LINKS:**

- The Haskell home page has many useful subsidiary links (in particular to the various HUGS systems which you can download) .... well worth a visit.
- The definitive text on the lambda calculus (the theory underlying functional programming) is written by Henk Barendregt: there is now a revised edition of the book.
- Here is the main Journal on Functional programming.
- Here is a classic paper by John Hughes on "Why Functional Programming Matters".
- Here is a guide to functional programming on the Web compiled by Philip Wadler who is a cool guy and has many interesting links on his home page. Check out functional programming in the real world. An example of an expository paper is "History of logic and programming languages", this is of special interest (to me!) as it points to the close link between proof theory and programming languages.
- The main conference in the area is "The International Conference on Functional Programming (ICFP)" . Of particular interest is the functional programming contest (here for example is the 2001 contest ) which is held each year.
- For functional programming in general, a place to start is the `FAQ', http://www.cs.nott.ac.uk/Department/Staff/gmh/faq.html which gives details of all functional programming languages, as well as more general information and indeed answers to frequently asked questions about the basics of functional programming.
- There have been many applications and extensions to (particular ) Haskell implementations.
- Paul Hudak's homepage.
- John Hughes links for
tutorials
on functional programming.

- John Harrison's notes on functional programming.
- Larry Paulson's notes
on a programming approach to the lambda calculus.

- A basic introduction to the untyped Lambda Calculus by Ken Slonneger.
- Here is are of Barendregt's notes on functional programming and the lambda calculus.
- Claus Reinke's page on functional programming.
- Here is a lambda calculus reduction workbench written by Peter Sestoft. The reducer is written in Moscow ML and allows one to explore different reduction strategies.

- On the monad
laws.

- Dr. Seuss on Parser Monads: well some good fun for those who have kids (who are still kids)!
- All about monads: Jeff Newbern
- Monadic parsing: Graham Hutton and Erik Meijer

OTHER LINKS

- Ten reasons why you really should not take any course like this (here)

- Yet another language geek (here)