BSc Computer Science and Mathematics

Programming languages provide abstractions such as `functions’ which are supposed to allow us to reason about the code at a high level---without running it in our heads. However, these abstractions don’t necessarily behave in the way their names suggest.

In this unit we show that a mathematical theory of program meanings can be developed which encompasses the counter-intuitive behaviour of computations, but preserves our ability to reason abstractly. The machinery required is significant, and delicate at times, and the unit will introduce the fundamental technical tools which help us cope with these complications.

COMP11120 or MATH10111
 

The unit is based on the idea that programs can be assigned a formal meaning. This allows one to reason about them rigorously in an abstract manner. Standard technical tools used in this area are also introduced.

On the successful completion of the course, students will be able to:

• Describe and analyse the behaviour of terms in the various models of computation studied
• Compute the denotations of programs and types
• Prove selected results about programs using structural induction
• Apply fundamental theoretical results about programming languages and particular techniques to reason about programs
• Prove equivalence of programs in a suitable programming language making use of appropriate techniques and models
   

• Untyped lambda calculus
• Simply typed lambda calculus
• Proof method: logical relations
• Observational equivalence of programs
• The function model of the simply typed lambda calculus
• PCF — the core of modern functional languages
• Denotational semantics of PCF
• Taster of advanced topics (perhaps polymorphism or concurrency)

The unit is based on detailed lecture notes including numerous exercises. They go beyond the material we assess by providing rigorous arguments for all the results given, as well as the relevant mathematical background. The notes are supported by videos that explain key concepts and ideas.

The approach to learning is blended: Key ideas are explored by the learners via introductory activities in the workshops, with support from unit staff, and plenary discussions take place to confirm the learners’ understanding and to correct any misconceptions. This prepares the students for the directed reading, supported by short videos, for the week. Students are asked to carry out formative exercises and they receive feedback via solutions that are released the following week.

There are coursework exercises in the form of take home tests which assess all ILOs, but only cover the first two languages taught. Further exercises are made available to prepare students for the questions they can expect for the exam.

Feedback is provided in a number of ways, via the self-assessment quizzes, via solutions provided for unassessed exercises, via the weekly study sessions where students can query their understanding, and via feedback provided on the two pieces of coursework.