NDAK16005U Program Analysis and Transformation (PAT)

Volume 2018/2019
Education

MSc Programme in Computer Science

Content

The automated processing of program texts is central to Computer Science. The prime example of such processing is traditional compilation of high-level to low-level languages ­–  including the necessary supporting analyses, whether for error-detection purposes, or in support of efficiency-improving program optimisations. But other instances of program analysis and/or transformation abound in both core programming-language work, and in support of adjoining disciplines, such as algorithmics or security.

The course introduces students to the principles and practice of automated program processing, covering both mainstream application areas, and selected more exotic applications.

Learning Outcome

At course completion, the successful student will have:

Knowledge of

  • Static program analysis paradigms, including abstract interpretation and type-based analyses.
  • Applications areas of automated program analysis, including optimisation, verification, and information security.
  • Principles of semantics-based program transformation.
  • Applications of program transformation, including translation, synthesis, and maintenance.
  • Software systems and tools supporting analyses and transformations.
  • Selected examples of advanced analyses and/or transformations.

 

Skills to

  • Decide and argue correctness and other properties of a range of analysis and transformation algorithms.
  • Concretely realise analysis and transformation algorithms from their abstract descriptions.

 

Competences to

  • Design and implement systems for automated processing of programs expressed in both general-purpose and domain-specific languages.

 

Literature

Articles and notes. See Absalon after the course it set up.

Basic knowledge of the principles of programming language implementation (as found in an undergraduate-level compilers course), operational semantics and type systems (e.g. "Semantics and Types" or similar), and practical programming skills in a functional language (e.g., Haskell, as used in "Advanced Programming") will be expected.
Lectures, exercises, mandatory assignments.
  • Category
  • Hours
  • Exercises
  • 16
  • Lectures
  • 30
  • Preparation
  • 60
  • Project work
  • 100
  • Total
  • 206
Written
Oral
Individual
Credit
7,5 ECTS
Type of assessment
Continuous assessment
Continuous evaluation based on 4-6 assignments, covering both theory and programming. Assignments are assessed as a whole.
Aid
All aids allowed
Marking scale
7-point grading scale
Censorship form
No external censorship
Several internal examiners.
Re-exam

  1. Same as ordinary exam + 30 minutes oral examination without preparation. Assignments are assessed as a whole.

  2. The student assigments must be submitted, no later than two weeks before the re-exam, in order for the assignments to be approved, and for the student to qualify for the re-exam.

Criteria for exam assesment

See Learning Outcomes.