Course outline (Programming Languages)
From Spivey's Corner
| Programming Languages |
| Syllabus |
| Outline |
| Problems |
| Labs |
| Software |
| FAQ |
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 here are all the notes so far formatted as a single document for better cross-references. Note particularly the comprehensive 'index of first lines' at the end.
- 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 who know the 'usual password'.
- Packages of source code for the interpreters. These were developed using the Glasgow Haskell compiler GHC under Linux together with a home-made literate programming system, so the source files are the output of a cutting-and-pasting process that also produces the handouts. That means the code should be identical, but it may cause the appearance of funny formatting codes, especially in comments.
The Windows sources (in ZIP archives) are identical in all respects
to the Unix sources (in Gzipped tar files), except that the common module
Parsing.hs has been adjusted to work with Windows GHC.
Contents |
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.
- Lecture notes 1.
- Source for Fun interpreter: Gzipped tar format, Windows ZIP format, including common modules used in all our interpreters.
- Problem sheet 1, First steps, with solutions.
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.
- Source for FunMem and FunMonad interpreters: Gzipped tar format, Windows ZIP format.
- A note about the semantics of
whileloops. - Problem sheet 2, Memory and monads, with solutions
- 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.
- Source for FunFail interpreter: Gzipped tar format, Windows ZIP format.
- Source for Fungol interpreter: Gzipped tar format, Windows ZIP format.
- Problem sheet 3, Semantic variations, with solutions.
- Lab two: Memory and call-by-name
Continuations
[12] Introducing continuations
[13] Interpreters in continuation-passing style
[14] Continuations for exceptions and I/O
[15] First-class continuations
[16] Continuations and abstract machines
- Lecture notes 4a.
- Lecture notes 4b.
- Source for FunCont, FunIO and FunCont2 interpreters: Gzipped tar format, Windows ZIP format.
- Source for FunMachine interpreter: Gzipped tar format, Windows ZIP format, an interpreter for pure Fun in first-order tail form.
- Problem sheet 4, Continuations, with solutions.
- Lab three: Loops with exit.
Bonus tracks
- Source for FunType type checker: Gzipped tar format, Windows ZIP format, implementing Hindley–Milner type inference for pure Fun.
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.
