What
This is the central web page for Programming III, a course about Functional Programming. Copies of the lecture slides will appear here, alongside a collection of potentially useful links and other bits of information.
You might like to look at the Unit description for this course.
Who
Your lecturer is Guy McCusker.
When
There are three hours of lectures per week for this course.
- Wednesday, 11.15, 8W2.1
- Friday, 16.15 and 17.15, 3E2.1
Coursework
The assessed coursework assignment was set on October 19th 2007 and is due by December 13th 2007. It is worth 25% of the total mark for this unit.
Books
There are a great many books about Lisp, functional programming, the lambda-calculus and so on. You might consider looking at:
- Structure and Interpretation of Computer Programs by Abelson and Sussman. An outstanding introduction to many aspects of computer science and programming, based on Scheme. The full text is on the web.
- The Little Schemer and The Seasoned Schemer by Friedman and Felleisen. Quirky books which explain a lot about programming in Lisp/Scheme in an entertaining way. I have borrowed examples from these books for the lectures.
- The Lambda-Calculus: its Syntax and Semantics by Barendregt. The classic text in the lambda-calculus, telling you everything you might need to know in full mathematical detail.
- How to design programs by Felleisen, Findler, Flatt and Krishnamurthi. Another general programming book based on Scheme, with full text online.
Other resources
- Russell Bradford's lecture notes for an old version of this courses and a Lisp course he used to teach. The notes come with a warning: "There are definitely bugs and typos in these notes, so beware!"
- Russell Bradford's simple Lisp exercises with sample solutions.
- Sources for Euscheme and some starter notes on using it.
- Chris Archer has
compiled a version of EuScheme for Windows XP. You can get it from
his page, or my copy. Make sure to
read the
readme.txtfile. - PLT Scheme is a family of Scheme implementations, including drScheme and mzScheme, which you can install on your own machines. There are some other worthwhile resources on the site, too.
- 99 Lisp problems for you to try. Good practice!
Lecture notes
- Topic 1: Getting started with Lisp (3-up pdf)
- Topic 2: Recursion, recursion, recursion (3-up pdf)
- Topic 3: Recursion on other data (3-up pdf)
- Topic 4: Map, lambda, filter (3-up pdf)
- Topic 5: Folding (3-up pdf)
- Topic 6: Sorting (3-up pdf)
- Topic 7: Fixed-point combinator (3-up pdf)
- Topic 8: introduction to lambda-calculus (3-up pdf)
- Topic 9: reduction, evaluation, equivalence (3-up pdf)
- A note on inconsistency
- Topic 10: programming in the lambda-calculus (3-up pdf)
- Topic 11: types in the lambda-calculus (3-up pdf)
- Topic 12: introduction to Haskell (3-up pdf)
- Revision lecture (3-up pdf)
Exercises, solutions and sample code
- Code to reverse a list
- Code for other recursive functions from topic 2
- An exercise: a compiler and interpreter for arithmetic expressions (3-up pdf), and sample code for the interpreter.
- An exercise: map, filter and list comprehensions
- Code for the sieve of Eratosthenes.
- Sorting code
- Lisp Quiz and answers
- Introductory lambda-calculus exercises and some solutions
- Lambda-calculus programming exercises
- More Lambda-calculus programming exercises: encoding lists