Part II: Programming Languages

This page contains all the information specific to Part II.

1. Part II: Programming Languages
   1. Schedule
   2. Problem Sheets
   3. Materials

Schedule

This part will cover the semantics of programming languages in theory and in practice.

• We start by introducing the untyped lambda calculus as an alternative model of computation, exploring its (simple) abstract syntax, and defining and implementing some of its (very simple) semantics.
• We will then look towards a much more earthly imperative language—IMP—and its semantics, which we’ll animate as they are, and perhaps extend.
• We will think about the logical and mathematical tools we need to reason about a language’s semantics, and a program’s correctness.
• We will define and animate the semantics of a small stack machine, and define a translation from IMP to its language. We will implement this translation as a compiler.

You will know enough to start the problem sheet for a given Week after listening to the first two lectures of the same Week. The problem sheet and Lecture 3 of a given Week will often be designed to be looked at together.

In the above table, a lecture or part being marked as (Optional) means that it is not necessary to have watched it to pass the unit or get a low first. Some top-range marks might assume some exposure to the material.

A lecture or part being marked as (Unassessed) means that even top-range marks won’t be touching the concepts the lecture or part introduces.

Problem Sheets

The problem sheets will appear here, along with Haskell templates, when ready. They will also be uploaded to the Files tab of the General channel in the COMS20007 Team.

For the programming tasks, we will assume a barebones Haskell that gives you access to a reasonable version of Cabal.

We provide a Vagrantfile, for use with Vagrant and VirtualBox. The recipe uses ghcup to set up Haskell, Cabal, as well as Alex and Happy, which I will sometimes use for writing lexers and parser.

We’ve also prepared a docker container, tested to work with both docker and podman. You can run docker run fdupress/coms20007lab, with appropriate options to mount the problem files and start the command you want. The container uses an Alpine base image and will lack creature comforts even if you put some effort into expanding it. The idea here is to use the container as a thin wrapper around Haskell tools, rather than a full-blown system in which you’ll do your work.

Materials

We will refer to the following two texts:

• Benjamin Pierce’s Types and Programming Languages. (We will use only Chapters 5 and 6, but Chapters 1 to 4 are a generally useful read.) We refer to this as “Pierce”.
• Nielson and Nielson’s Semantics with Applications: A Formal Introduction. (The plan calls only for Chapters 1 to 3, but we might foray into Chapters 5 and 6 if time and biology cooperate.) We refer to this as “Nielsons”.

In the following table, Lectures are indexed as Week.Lecture (not part) to avoid ambiguities in case of interruptions in the schedule.