Note

Following a national ballot, the union, UCU, that represents staff in the higher education sector has called a strike on three days in late November, and also "action short of a strike" during a period that starts on Wednesday, 23 November. During this period, colleagues are invited to take various actions, including abstaining from voluntary activities. I view the maintenance of Spivey's Corner as an activity I undertake voluntarily and not part of any contract of employment, and I cannot guarantee that it will remain accessible during the period of the dispute. In addition, some materials on the site may pertain to lectures that are cancelled by myself or others as part of the strike, and we are asked not to make them available online. Further details of the reasons for the strike and how it affects teaching in Oxford are on a brief FAQ page.

# Compilers

An operator tree for x := a[i]

This course will show you one way to build a compiler for an ordinary programming language (like Pascal or C) that generates reasonably good code for a modern machine (the ARM).

To make the task manageable, we will write the compiler in a functional style in quite a high-level language (OCaml), and we will use power tools (Lex and Yacc) to automate the easy part – analysing the syntax of the input language. The designs we create can also be used to implement hand-crafted compilers without the benefit of these power tools.

Our compiler will be organised for clarity, being structured as the functional composition of many small passes, each carrying out one part of the compiling task. This organisation allows us to focus on the representations of the program being compiled that are handed from one pass to the next, understanding each pass in terms of the transformation it must achieve.

The course doesn't aim to be a survey of all the ways the task might be done, though occasionally we will pause to mention other choices we might have made. Because we will be building a big-ish program, we will naturally want to deploy some of the technical means to deal with large-scale software development: a version control system to keep track of the changes we make, automated building (using Make), and automated testing against a stored corpus of test cases.

The course will bring us into contact with some of the major theoretical and practical ideas of Computer Science. On the theoretical side, we will be using regular expressions and context free grammars to describe the structure of source programs (though relying on automated tools to construct recognisers for us), and we will find a use for many algorithms and data structures. Practically speaking, we will need to deal with the target machine at the level of assembly language, using registers, addressing modes and calling conventions to make a correct and efficient translation of source language constructs.

## The coursebook

Everything you need to follow the course is contained in one handy coursebook, including

• Notes for the lectures.
• Problems for the classes.
• Instructions for the lab exercises.
• Appendices containing extra information about the OCaml language and the Keiko and ARM machines.
• Listings of relevant parts of the compilers used for the lab exercises.

## The tutorials and labs

As a Core course, Compilers will be supported by tutorials organised by colleges. There will also be a sequence of four lab exercises, leading up to a practical assessment carried out during the Christmas vacation.

• The tutorial exercises are contained in the coursebook, and for convenience they are also accessible as a separate document on another page, with some advice about what problems are appropriate for each tutorial.
• Instructions for the labs are also contained in the coursebook, and practical arrangements are set out on their own page.

## The Christmas assignment

To encourage participants to develop practical skills, and to give them an opportunity to demonstrate them, the course culminates in a practical assignment done over the Chritmas vacation. Another page has a sample write-up, the assignments set in previous years, and Mike's solutions to each of them.

## The burning questions

There is a page of frequently asked questions that contains the answers to all your questions (or will do so shortly after you ask them).

• In addition, a glossary gives definitions of terms used in the course. Feel free to suggest new entries!

## The reading list

• The coursebook contains most of what you need to know to follow the course, including notes on the lectures, instructions for the practical exercises, and appendices describing the instruction sets of the Keiko machine and the ARM, together with listings of relevant modules of the lab compilers.

Some other books:

• The book Modern Compiler Implementation in ML by Andrew Appel (Cambridge) is closest to this course, except that the ML dialect he uses is Standard ML, and not OCaml. There are two translations of the book that use respectively Java and C as the implementation language, but in each case something is lost in the translation.
• The classic text Compilers: principles, techniques and tools by Aho, Hopcroft and Ullman (Addison–Wesley). Either the original 1977 edition or the second edition of 2006 (with Monica Lam) will do. I've been referring to the 1977 edition, but as far as I can see, little of the common material has changed in the second edition.
• Although it differs in many details, Richard Bornat's classic book is close to the course in spirit. I recommend it for supplementary reading.
• In later parts of the course, you might like to look at the reference manual for the ARM architecture. (This edition is not the latest, but it is the first to describe the ARMv6 instruction set we shall target. Later editions have become steadily more complicated as each describes a greater number of variants of the ARM than the one before it.)
• The Revised Report on Algol 60 is the first significant language description to use context free grammars to define the syntax of a programming language. Knuth's paper The remaining trouble spots in Algol 60 fixes the very few problems in the Revised Report.
• For tutorial material on OCaml, there is a copy online of the O'Reilly book Real World OCaml by Yaron Minsky, Anil Madhavapeddy and Jason Hickey.