Handbook home
Program Analysis and Transformation (COMP90053)
Graduate courseworkPoints: 12.5Not available in 2019
Overview
| Fees | Look up fees |
|---|
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.
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
Generic skills
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
Eligibility and requirements
Prerequisites
One of the following:
| Code | Name | Teaching period | Credit Points |
|---|---|---|---|
| COMP30020 | Declarative Programming | Semester 2 (On Campus - Parkville) |
12.5 |
| COMP90048 | Declarative Programming | Semester 1 (On Campus - Parkville) |
12.5 |
OR admission into one of the following courses:
- MC-IT Master of Information Technology, 100 or 150 point program in Distributed Computing
- MC-IT Master of Information Technology, 100 point program in Computing
Corequisites
None
Non-allowed subjects
None
Recommended background knowledge
Basic proficiency in discrete mathematics.
Inherent requirements (core participation requirements)
The University of Melbourne is committed to providing students with reasonable adjustments to assessment and participation under the Disability Standards for Education (2005), and the Assessment and Results Policy (MPF1326). Students are expected to meet the core participation requirements for their course. These can be viewed under Entry and Participation Requirements for the course outlines in the Handbook.
Further details on how to seek academic adjustments can be found on the Student Equity and Disability Support website: http://services.unimelb.edu.au/student-equity/home
Last updated: 3 November 2022
Assessment
Additional details
- A 45-minute mid-semester written test around Week 7, requiring approximately 13 - 15 hours of work (10%), addressing Intended Learning Outcomes (ILO)s 1 and 2.
- A programming project during semester (30%), requiring approximately 35 - 40 hours of work, addressing ILOs 3 and 4.
- A 2-hour end-of-semester written examination (60%), addressing ILOs 1, 2, and 5.
Hurdle requirement: To pass the subject, students must obtain:
- 15/30 in project work
- 35/70 in the mid-semester test and end-of-semester written examination combined.
Last updated: 3 November 2022
Dates & times
Not available in 2019
Time commitment details
200 hours
Last updated: 3 November 2022
Further information
- Texts
Prescribed texts
None
- Subject notes
LEARNING AND TEACHING METHODS
The subject involves two 1-hour lectures per week followed by a 1-hour workshop. Weekly tutorial problems are assigned and discussed in class. The programming project is pivotal, as the subject relies heavily on learning-by-doing. Students work in small groups to implement a sophisticated program analysis tool of practical value. Students are encouraged to share ideas and artefacts, such as developed test data. More generally, “contributing student pedagogy” is utilised as a community-building tool. Accordingly, in-plenum discussion of the project is allowed, and encouraged.
INDICATIVE KEY LEARNING RESOURCES
The subject uses online reading materials and an online discussion forum. It offers advance access to teaching materials, including slides used in lectures.
CAREERS / INDUSTRY LINKS
Semantics-based formal approaches are increasingly important in software engineering and software development, in particular for security- and safety-critical applications.
- Related Handbook entries
This subject contributes to the following:
Type Name Course Master of Science (Computer Science) Specialisation (formal) Distributed Computing Specialisation (formal) Computing Specialisation (formal) Software - Available through the Community Access Program
About the Community Access Program (CAP)
This subject is available through the Community Access Program (also called Single Subject Studies) which allows you to enrol in single subjects offered by the University of Melbourne, without the commitment required to complete a whole degree.
Entry requirements including prerequisites may apply. Please refer to the CAP applications page for further information.
Additional information for this subject
Subject coordinator approval required
- Available to Study Abroad and/or Study Exchange Students
This subject is available to students studying at the University from eligible overseas institutions on exchange and study abroad. Students are required to satisfy any listed requirements, such as pre- and co-requisites, for enrolment in the subject.
Last updated: 3 November 2022