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.


The following topics will be studied:

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


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

  • Implementation of programming languages
  • Software generation


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


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.


Your grade will be determined by

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


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.


The course will be given in Period 2. See for details on meeting rooms.


The course is thaught by Eelco Visser