Program Analysis and Transformation (COMP90053)

AIMS

In the 1930s, Alan Turing and Konrad Zuse independently proposed designs of computing machines based on the idea that storage used for data and storage used for instructions be indistinguishable. This “stored-program” model formed the blueprint for all modern computers. The ability to treat programs as data turned out to be very powerful, as it meant that a program could be designed to read, generate, analyse and/or transform other programs, and even modify itself while running. This subject is concerned with meta-programs - programs that work on other programs, possibly generating programs as output. People routinely read, generate, analyse, test, and transform programs. For example, a programmer may look through code for potential buffer overruns, and may add runtime tests to avoid the security problems that could result. It is preferable, however, to automate such activity as far as we can, partly because that makes programmers more productive, and partly because computers generally are better at these tasks, avoiding human oversights and mistakes. This subject introduces the main techniques and applications of program analysis and transformation, including methods used by modern optimizing compilers and allied tools.

INDICATIVE CONTENT

• Syntax and semantics: Program representations, operational and denotational semantics.
• Fixed point theory: Order, lattices, functions and fixed points
• Program analysis: The monotone framework, constraint-based analysis, collecting semantics, abstract interpretation, widening, inter-procedural analysis, analysis of functional and logic programs
• Meta-programming: Interpreters, meta-interpreters, program instrumentation, source-to-source program transformation, including fold/unfold and partial evaluation
• Other topics may be covered via the project, for example, analysis for violations of safety and/or security policies, or analysis and transformation for finding and implementing parallelism.