Automatic Program Analysis

Updated for 2021-2022

This course replaces the course on Compiler Construction as given in course years up to 2018-19. Since the content is largely the same, you cannot have both courses on your final course list.

Computer programs are usually written in a so-called high-level programming language, such as C, Java, or Haskell. Execution of such programs requires either a compiler or an interpreter for the language. In its most general form, a compiler is a piece of software that takes as input a program written in a certain (usually: high-level) language and produces as output a translation of that program into another (more low-level) language. Examples include: compilers that translate C programs into machine code for an IA-32 processor; compilers that translate Java programs into bytecode instructions for the Java Virtual Machine; but also: software for translating Latex documents into HTML.

In this course, we study aspects of compilers. We do so by considering some of the language constructs that typically appear in modern imperative and functional programming languages, and by looking at what kind of analyses these constructs require in order to be compiled. We delve into formalisms, tools, and programming techniques that are particulary well-suited for crafting static analyzers.

The course consists largely of the following four advanced topics in compiler construction:

The practical assignments are all to be performed in Haskell, and we expect students to be familiar with that language (for example, by doing our bachelor course on Functional Programming). If you don’t know Haskell you are at very significant disadvantage compared to your fellow students. Familiarity with aspects of parsing and lexing (for example, by doing our bachelor course on Talen en Compilers) may be useful but will not be essential for doing the practicals.

Course structure

We have two lectures a week, on Tuesday and Thursday, at Daltonlaan 500 and is taught by Ivo Gabe de Wolff. After the lecture we also have a working group (werkcollege). The lectures will in principle be only on-location now that the covid measures are relaxed. If you cannot attend a lecture and want to follow it online, let me know and I’ll try to arrange that. The schedule and slides will be published online.

There are two (graded) practical assignments, where you need to implement program analyses. Questions about course structure and material can be asked during the lectures or working groups or via MS Teams.

Grading

The final exam is 40 percent of your grade. The two practical assignments are each 30 percent. The practical assignments we expect students to do in pairs, although individual submissions are allowed. Your average for the labs, and the grade for the exam both have to be 5.0 or higher in order to pass.