Program Analysis Notes

Topics

The course comprises three large topics

• Dataflow analysis
• Control flow analysis
• Abstract interpretation

In all cases, the goal is to compute in finite time useful information from the source of the program. Examples include strictness analysis, dead code analysis, variable sign analysis, live variables analysis.

Dataflow analysis focuses on an imperative language, control flow analysis is done using a functional language. Abstract Interpretation is more or less language independent, but will be treated as related to the first two.

In addition the following topics will be addressed in a more supporting role and only insofar as needed for treating the three main subjects of the course.

• Structural operational semantics
• Domain theory

Material

• Principles Of Program Analysis by Nielson, Nielson and Hankin, Springer Verlag, parts of chapters 1-4.
• Downloadable texts on e.g. semantics can be obtained as background material
• Lab:
  • implementation of Monotone Frameworks in either Java or Haskell
  • possibly: using the Berkely Analysis Engine to solve sets of constraints

Form

For now we plan to have each week:

• four hours of lecture, which includes one or two hours of making exercises depending on need
• two hours assistance with the practical assignment

Dependencies

• Motivation
  • CourseDescription
• Requires
  • Grammars And Parsing from the Bachelor course
  • [maybe] ImplementationOfProgrammingLanguages
  • something on semantics if available

Lecturer

• JurriaanHage

History

This course has evolved from

• Automatic Program Analysis (2001)

Discussion

• Is Implementation of Programming Language required?
• Should it be Automatic or not?
• See whether using BANE is practical or not