Abstract Interpretation and Program Transformation

This course is the second half of a 10-point course on implementing functional languages. The first half of the course covered compiled graph reduction, and was taught by Thomas Johnsson. This half of the course covers program analysis and transformation. The draft course plan on which the entire course is based is available here.

Teaching Form

The lecture times and presentation times are available.

Examination

• Implement a program analysis phase and accompanying optimisation in the compiler you have developed in the first half of this course (see this).
• Implement a program transformation phase in your compiler, or construct a program generator by partial evaluation.
• Give a presentation of a relevant article to the other participants.

Participants

md2oven@mdstud.chalmers.se,henrikp,pareto,nazari,oloft,tato,ahlberg,bengtj,bond,heldal,masa,agat,pollack,andrew,gustavss,gustun,fede,frito,johank@ce.chalmers.se,nafun-6@mdstud.chalmers.se,johnsson,ilya

(Addresses which caused errors: csguest2)

Course Materials

• Abstract Interpretation: a Semantics-Based Tool for Program Analysis, N D Jones and F Nielson, in Handbook of Logic in Computer Science, Oxford University Press, 1994, 527-629.

  Summary: This is a broad overview of Abstract Interpretation, to be a large chapter (around 100 pages) in the above-mentioned handbook. It consists of three main parts: an Introduction with motivation and Descriptions of the main methods used in the field; a mathematical development of the logical relations approach with several applications; and short descriptions of a broad spectrum of Semantics-Based Program Analyses.

• Partial Evaluation 1996, the draft proceedings of the 1996 Dagstuhl workshop on PE. A collection of 23 papers. Torben Mogensen's paper looks to give a very nice introduction to the area.