COMS20007
Programming Languages and Computation
Welcome to the home of COMS20007: Programming Languages and Computation, or Prog Lang and Comp for short. This unit introduces you to computability theory and to the theory of programming languages, which are two core areas of theoretical computer science.
- Part I: Computability theory is about the limits of computation.
- Part II: The theory of programming languages is about how languages express computation.
In Part I we will try to understand how to classify computational problems according to whether or not they can be solved algorithmically, that is, by some computational process. To do this we will introduce a very simple machine model of computation due to Alan Turing. We will argue that this model, though completely impractical, is sufficient to solve any problem that can be solved by an algorithm.
In practice, we usually express computation through a program in some language. In Part II we will try to understand how programming languages give rise to computation. To do this we will introduce the syntax and semantics of some simple programming languages. We will study how different features of the languages interact to tame the kinds of computations that can be described.
Staff
The unit is run by Steven Ramsay (Part I) and François Dupressoir (Part II). The labs are staffed by some excellent TAs: Samantha Frohlich, Eddie Jones, David Kenna, Mutalib Mohammed, Alex Welsh and Alessio Zakaria.
| Steven Ramsay | François Dupressoir |
|---|---|
 |
 |
Technology
We will be using Microsoft Teams for all the interactive parts of the unit. You should have already been invited to the COMS20007 team. Within the team you will find the following channels:
- General: announcements appear here and all the unit teaching materials can be accessed from the tabs.
- Discussion Board: post your questions here and we will try to answer them asap.
- Drop-in Hour: the lecturer Q&A sessions are held here and, afterwards, the recordings will be linked from the channel conversation.
- Front Desk: the TAs are waiting at the front desk to help you during the labs.
- Table nn: a place to meet with others and work on the problem sheets/lab exercises.
You should receive calendar invites for the Q&A sessions closer to the time. These invites will link you directly into Teams and so supercede the generic timetabling info that may currently occupy the same slots in your calendar. For the labs, just rock up at your reserved table or join one of the open tables 1–5.
Schedule
This is a 20 credit unit, so you should expect to around 13 hours per week working on it. There are 5 main activities:
- Prerecorded lectures. At the start of each week, three prerecorded lectures will be posted on the unit website which you need to watch in your own time.
- Online labs. Labs occur online every Wednesday 9am-11am and Friday 2pm-5pm, but will only be staffed by TAs for a subset of those hours, see Labs
- Problems. You will only learn on this unit by completing the problem sheets and exercises. There is one sheet released each week.
- Lecturer Q&A. Each week there will be a one-hour Q&A with the lecturer, online at 1pm on every Tuesday.
- Reading/Revising. You will often benefit from alternative explanations of the same concepts, which would not fit into the time available for lectures. You will need to spend time revising and rethinking topics before you can solve the associated problems.
See the home pages for Part I and Part II for more information on what these activities look like in each component of the unit.
The two parts will be slightly interleaved as a consequence of time constraints on the teaching times of the lecturers. The following is provisional and will be updated according to circumstances:
| Weeks | Topic |
|---|---|
| 1 – 3 | Part I: Computation |
| 4 – 5 | Part II: Programming Languages |
| 6 – 7 | Part I: Computation |
| 8 – | Part II: Programming Languages |
Assessment
This unit is assessed by a written exam in the January assessment period and again in the August/September assessment period. The date of the former is 22 January at 09:45 GMT, the date of the latter is 23 August at 09:45 BST. Both exams follow the same format, described below.
The exam consists of two questions of 50 marks each, and each question is the same format as a problem sheet. You must answer both questions. One question is on Part I and the other on Part II. You have three hours to complete your solutions. You may use the lecture materials, but you must not collaborate. You will not be required to write any Haskell code in the exam.
Shortly before the exam, a Blackboard assessment point will be created on the Blackboard page for this unit. At the time of the exam you should navigate to this assessment point where you will be able to download a copy of the paper in PDF format. You may start the exam immediately. You will have three hours to write your solutions and a further period of additional time (which is yet to be standardised across the department) in which to upload your solutions back to the assessment point (e.g. after scanning or photographing them). See here for the University’s guidance on uploading handwritten materials.
There is a practice paper available here so that you can familarise yourself with the format: