Home             Education

What is Automatic Program Analysis?

Before optimizing transformations can be applied to computer programs, it is first necessary to analyse a program to compute various properties of a program. For example, a compiler only needs to generate code for lines that can be reached from the beginning of the program. However, it is not always obvious whether some part of the code is reachable or not. Another example is type checking and type inferencing. This is also an analysis of a program, which should lead to more efficient generated code. In both cases it also gives some idea of the correctness of the program.

Another application of automatic program analysis has to do with verifying that written code adheres to certain programming guidelines. For instance: in a company people might be wary of memory leaks. For this reason there is a programming guide line that says that memory allocated in a given procedure ought to be released before the end of the procedure.

The basic idea of program analysis is to compute information from programs automatically in finite time. In many cases we run into the limits of what is computable (like the Halting Problem), so our answers will only be approximate. We do generally insist that answers are sound: if some definite answer is given, then it must be true.

All of these examples are instances of Abstract Interpretation, where instead of the standard semantics of a programming language (for which we can compute only very little), we are interested in a computable approximation to the meaning of the program. This approximation should always be sound/safe with respect to the original semantics.

Courses about Automatic Program Analysis

Does the above pigue your interest? If so: there is a single course about the subject. For more information about the course and a list of literature on the subject please consult the Automatic Program Analysis (Automatische Programma Analyse) webpage.

Master Projects to be done

A list of Master projects can be found here. Related to these are a number of Bachelor projects.

Improving type error messages

Within the context of automatic program analysis, Bastiaan Heeren is doing a PhD on the subject of improving type error messages for functional programming languages. He has a webpage on the subject, including a list of references to papers in this area. Technical reports of Bastiaan Heeren can be found here.
© Jurriaan Hage