Course outline
Aim of the course: to investigate the semantics of programming languages by writing interpreters in Haskell that work on abstract syntax trees.
This page gives an outline of the course, supplemented by several kinds of document:
- Lecture notes, containing listings of the interpreters we study. Individual handouts are offered below with the lectures to which they relate, but if you want to view them on the screen, you may prefer to use a version where all the notes are formatted as a single document, with helpful indexes and extensive hyperlinks between the chunks of Haskell code.
- Problem sheets: Each sheet is listed after the lectures to which it refers, but you should be able to do at least some of the problems before we have finished all the lectures that precede it. Each problem sheet comes with model solutions that are accessible only to tutors.
The functional language Fun
[1] Introducing Fun, with familiar examples rewritten in the language.
[2] The concrete and abstract syntax of Fun.
[3] A recursive interpreter for Fun. Examples of evaluation.
[4] Defunctionalization: a first-order interpreter for a higher-order language.
Adding memory, introducing monads
[5] Changing the interpreter to support assignable variables, with references as expressible values (like ML).
[6] Implementing while by recursion. Styles of semantics
[7] Changing the interpreter to support output; extracting common features of memory and output.
[8] Interpreters in monadic form.
- Lecture notes 2.
- Problem sheet 2
- Lab one: Functional vs Imperative.
Semantic variations
[9] Review: a language with exceptions.
[10] The language Fungol, where identifiers are bound to assignable variables, and derefencing is implicit.
[11] Call by value and call by reference.
- Lecture notes 3.
- Problem sheet 3.
- Lab two: Memory and call-by-name.
Continuations
[12] Introducing continuations.
[13] Continuation-based interpreters.
[14] Continuations for exceptions and coroutines.
- Lecture notes 4.
- Problem sheet 4.
- Lab three: Loops with exit.
Appendices
These appendices contain supporting code: the library Parsing that contains tools for building interactive parsers; the definitive abstract syntax (FunSyntax) and parser (FunParser) for the Fun language with all the extensions included; and implementations of Environment and Memory. Tangled copies of this code appear packaged with the interpreters throughout the course, but here it is gathered together in all its gory detail.
Some of the code provided here is boring and routine, and some is just a compilation of fragments of syntax needed at different times during the course. But actually, the Parsing library is quite interesting because it uses continuations to allow parsers to suspend themselves and request more input interactively.