Course Description

Tiger in Stratego -- Compilation by Program Transformation

Appel writes in the preface to Modern Compiler Implementation in ML:

Over the past decade there have been several shifts in the way compilers are built. New kinds of programming languages are being used: object-oriented languages with dynamic methods, functional languages with nested scope and first class function closures; and many of these languages require garbage collection. New machines have large register sets and a high penalty for memory access, and can often run much faster with compiler assistance in scheduling instructions and managing instructions and data for cache locality.

In this course you will learn about the ingredients of modern compilers through a project in which you will build a compiler for the Tiger language using the Stratego program transformation language. The emphasis of the course is on the middle- and back-end components of the compiler; the front-end will be provided. The project will be guided by means of weekly project and theory reviews.

Content

The following topics will be studied:

Review of compiler architecture
Translation to intermediate code
Instruction selection
Register allocation
Dataflow analysis
Program optimization
Memory hierarchy

Requirements

In order to enter this course you should have succesfully finished the following courses:

Implementation of programming languages
Software generation

Literature

Andrew W. Appel. Modern compiler implementation in ML. Cambridge University Press, 1998.

Activities

The driving force of the course is the compiler project in which you build a compiler (together with another student). At the end of the course you hand in the complete compiler together with a report describing the implementation.

There will be two seminar meetings each week and two lab meetings. In the seminar meetings you give one or two presentations about one of the chapters in the book. In the lab sessions you have an opportunity to get assistance with the compiler project. Note that you will have to spend more time on the implementation of the compiler than just the lab sessions.

Assessment

Your grade will be determined by

(60%) compiler implementation + report
(40%) presentations

Software

The compiler will be built using the program transformation tools in the XT package, in particular Stratego, a language for the specification of program transformation systems. This package runs on Unix and Linux platforms.

Schedule

The course will be given in Period 2. See http://www.cs.uu.nl/education/vak.php?vak=hpc for details on meeting rooms.

Teacher

The course is thaught by Eelco Visser