FOP image

School of Computer Science
University of Nottingham
Jubilee Campus, Wollaton Road
Nottingham NG8 1BB, UK

T: +44(0) 115 9514251
F: +44(0) 115 9514254

HMU cover

Foundations of Programming studies some of the fundamental mathematical concepts that underlie modern programming languages, including aspects of recent and current research. Example topics include: basic lambda calculus; operational semantics; types and type systems; and domain theory. You’ll spend around two hours per week in lectures studying for this module.

The FPP mini project provides you with the opportunity to deepen your understanding of the mathematical foundations of programming languages by studying in depth a specific topic related to your course. You’ll discuss your topic with your supervisor, choosing from a list of proposed topics. You’ll be required to write a report on your chosen topic and give a presentation on its central aspects.


The main textbook for the module is Types and Programming Languages by Benjamin C. Pierce (I will refer to it by TPL from now on). You must write down careful notes during the lectures, since not all the material is covered by the book. (In particular, the book doesn't cover denotational semantics.)

Two other excellent references are: The Formal Semantics of Programming Languages by Glynn Winskel; Lambda Calculi with Types by Henk Barendregt and Denotational Semantics by R. D. Tennent, respectively in Volume 2 and 3 of the Handbook of Logic in Computer Science.

Outline of lectures

In this section you will find, after each lecture, a list of topics that were taught and references to the chapters of the textbook.

1. 29 Sept 2014 Introduction: What FOP is about
Denotational and Operational Semantics
Language of Arithmetic Expressions
Notes for Lecture 1
TPL Chapters 1 and 3
2. 3 Oct 2014 Reduction and Congruence Rules
Evaluation Strategies: Eager and Lazy
Notes for Lecture 2
3. 6 Oct 2014 Untyped λ-calculus
Church Numerals
Notes for Lecture 3
TPL Chapter 5
4. 10 Oct 2014 Abstract Syntax Trees
Free Variables and Substitution
Booleans and Pairs
Notes for Lecture 4
5. 13 Oct 2014 Iteration and Recursion
λ-terms for lists
Non-normalizing terms
Notes for Lecture 5
6. 17 Oct 2014 The Y combinator, Streams
Confluence, Evaluation Strategies
Notes for Lecture 6
7. 20 Oct 2014 Introduction to type systems
The simply typed λ-calculus
Notes for Lecture 7
TPL Chapters 8, 9
8. 24 Oct 2014 Programming with simple types
Properties of simple types
System T
Notes for Lecture 8
9. 27 Oct 2014 Programming in system T
Ackermann Function
Notes for Lecture 9
10. 31 Oct 2014 Interactive session
Programming in system T
Fibonacci Numbers
Haskell implementation of:
Church Numerals
System T
11. 3 Nov 2014 Type constructors: Products, Sums
Inductive Types: Lists, Trees
Notes for Lecture 11
TPL Chapter 11, TPL Chapter 20
12. 7 Nov 2014 Two questions from the Quiz
The μ operator
Notes for Lecture 12
13. 10 Nov 2014 Inductive types with μ
System F
Notes for Lecture 13
TPL Ch.22: 22.1-2, Ch.23: 23.1-3
14. 14 Nov 2014 Polymorphic Functions
Naturals and Lists in System F
Notes for Lecture 14
15. 17 Nov 2014 Coinductive Types
Stream Coalgebras
Notes for Lecture 15
(TPL Chapter 21: 21.1-2)
16. 21 Nov 2014 Infinite Trees Notes for Lecture 16
17. 24 Nov 2014 Mapping trees to streams
General coinductive types
Notes for Lecture 17
18. 28 Nov 2014 Exam Preparation
Past Exam, Question 1
Exam Paper Spring 2014
19. 1 Dec 2014 Exam preparation
Past Exam, Question 2
20. 8 Dec 2014 Exam preparation
Past Exam, Questions 3, 4
21. 12 Dec 2014 G54FPP presentations ...
End of lectures

Coursework and Feedback

The coursework consists in three short tests on Moodle. Every three weeks you will find a quiz on the Moodle page. The quiz consists of 10 short questions; you have 30 minutes to answer them all. Access to the quiz will be open for the whole specified day. You can choose at what time you want to do it, but once you start you have half hour to complete it. You must solve it by yourself with no help from others. Be sure to read carefully the regulations about plagiarism in the student handbook. Each quiz will cover the material of the lectures up to the quiz's date.

Your coursework mark will be the average sum of the scores of all the tests; it counts for 25% of your final mark.

On the Moodle page there is a forum. You can use it to ask for feedback on any topic from the lectures and on the tests.

Thu 16 Oct 2014 Test 1 Lectures 1-5
Thu 6 Nov 2014 Test 2 Lectures 6-11
Thu 27 Nov 2014 Test 3 Lectures 12-17

Contacting the teacher

If you don't understand something or have any issues with the topics, don't be shy and ask. The first place to look for answers to questions about the module is the FOP forum on Moodle.

I will have office hours on Monday and Friday from 10:00 to 12:00. My office is A07 in the Computer Science Building. You can come and ask any question about the material explained in the lectures.

You can contact me by e-mail: put G54FOP/FPP in the subject line, so I know immediately that it is about this module.

G54FPP mini project

The purpose of the optional mini-project, formally the module G54FPP Foundations of Programming Mini-Project, is to provide G54FOP students with the opportunity to deepen their understanding of the mathematical foundations of programming languages by an in-depth study of a specific topic related to what is covered in G54FOP. I will give you a list of suggested topics with references. However, it is not exclusive: feel free to discuss other topics or amended versions of the suggested ones with the G54FOP/FPP convener.

After choosing a topic, your task is to

The report should be targeted at your fellow students; i.e., you can assume the reader will know the basics of operational semantics, lambda-calculus, etc. The expected length is around 10 pages, which is about 3000 to 4000 words excluding diagrams, code, references, or any appendices you feel have to be enclosed.

The deadline for the report is 16 January 2015.
You can send it directly to me by e-mail.
The presentation will be on 12 December 2014.

The front cover of the report should clearly state:

Be sure to read carefully the regulations about submission of coursework and plagiarism in the student handbook.

Marking criteria

In the 10-pages FPP project report, you must explain a topic at a level that should be understandable to your classmates in G54FOP. The presentation will be given during the last FOP lecture and all the FOP students will attend it and have the opportunity to ask questions. You don't need to do an extensive review of the literature: I just point you to one or two articles or book chapters that you shuld refer to. You must read them, understand them (they are at a fairly advanced level) and then manage to synthesise the main ideas and some of the content in your report and presentation. You will be marked on the understanding that you show, the capacity to explain complex notions, the clarity and correctness of your exposition. I don't ask you to do original work, but simply to demonstrate insight about the material and ability to explain it clearly.

List of topics

Here is a list of topics from which you can choose your mini-project. For each topic I suggest a reference (article or book chapter) from which you can start learning it. From there you should expand your horizon and consult related material. Once you've decided to do the project, send me an email with the title G54FPP project preferences containing a single line with your name and the numbers of the projects in order of preference. For example, if I sent the message Venanzio Capretta, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, it would mean that Functional Programming with Streams is my first choice for a project topic, while Deriving Programs from Specifications is the one I like the least. I will then use an algorithm to assign projects in a way that maximises preferences. (You will always be allowed to discuss a change with me if you're not happy with the topic.)

  1. Functional Programming with Streams

    Lazy functional programming allows the definition of infinite sequences, called streams. You will study how we can program with them and the mathematical theory to reason about them.

    Reference: Ralf Hinze, Functional pearl: streams and unique fixed points.

  2. The Barendregt Cube

    The most important variants of typed λ-calculi can be classified according to the presence of three characteristics: polymorphism, dependent types, higher sorts. So they can be arranged into a cube of systems.

    Reference: Henk Barendregt, Lambda calculi with types.

  3. Stream Differential Equations

    There is a nice similarity between operations on streams (infinite sequence) and traditional differential calculus. You will study how we can define functions on streams by giving differential equations on them and under what conditions they can be solved.

    Reference: Kupke, Niqui and Rutten, Stream Differential Equations: concrete formats for coinductive definitions.

  4. Labelled transition systems and bisimulation

    Labelled transition systems model very simple processes that may run forever. Bisimulation is the correct notion of equality on them: it characterizes when the behaviour of two processes is the same.

    Reference: Davide Sangiorgi, Introduction to Bisimulation and Coinduction, Chapters 1 and 2.

  5. Data types in system F

    Most recursive data types can be defined in the purely functional language of system F by using polymorphism, that is, the quantification over all types.

    Reference: Böhm and Berarducci, Automatic synthesis of typed Λ-programs on term algebras.

  6. Infinite objects and proofs in type theory

    In an earlier module you studied the proof assistant Coq. Now you will learn how it is possible to define infinite data structures and propositions with infinite proofs.

    Reference: Bertot and Casteran, Interactive Theorem Proving and Program Development, Chapter 13.

  7. The calculus of communicating systems

    You will study a formal system called CCS, invented by Robin Milner, to model independent processes that can interact with each other through communication channels.

    Reference: Davide Sangiorgi, Introduction to Bisimulation and Coinduction, Chapter 3.

  8. Hoare Logic

    Tony Hoare invented an elegant logical system to reason about imperative programs. It is based on the notion of invariant for loops. With it, you can specify properties of programs and prove them formally.

    Reference: Huth and Ryan, Logic in Computer Science, Chapter 4.

  9. The Pi Calculus

    The Pi calculus is a formal system that describes mobile components that communicate and change their structure. It provides a conceptual framework for understanding mobility and mathematical tools for expressing systems and reasoning about their behaviours.

    Sangiorgi and Walker, The pi-calculus: a Theory of Mobile Processes, Chapter 1 and part of Chapter 2.

  10. Deriving Programs from Specifications

    Functional programs are given by equations defining functions. So they may be manipulated by equational reasoning. We use this style of reasoning to calculate programs, in the same way that one calculates numeric values in arithmetic. A program can thus be derived from its specification by an equational derivation.

    Gibbons, Calculating functional programs.