|Fees||Look up fees|
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.
- 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.
Intended learning outcomes
INTENDED LEARNING OUTCOMES (ILO)
On completion of this subject, students should have the following skills:
- Describe standard approaches to program analysis and program transformation
- Solve mathematical problems relevant to reasoning about program runtime properties
- Design and build non-trivial program analysis/transformation tools
- Adapt and apply existing program analysis tools to the needs of a project
- Explain the limits of program analysis as applied to specific languages, and use this to inform decisions about which languages to use in programming projects
On completion of the subject, students should have the following skills:
- Analytical skills
- Reasoning and problem-solving skills
- Ability to apply knowledge of science and engineering fundamentals
- Capacity for creativity and innovation
- Ability to undertake problem identification, formulation and solution
- Ability to utilise a systems approach to complex problems and to design for performance.
Last updated: 3 November 2022