|Website:||website containing additional information|
|Period:||periode 4 (week 17 t/m 27, dwz 23-4-2007 t/m 6-7-2007; herkansing week 35)|
|Participants:||up till now 22 subscriptions|
|Schedule:||Dit is een oud rooster!
|Contents:||Every professional compiler performs an analysis of the source code of the program, to attempt to make the generated code more efficient, or to validate some aspects of the source code. Instances of this problem are type inferencing, data flow analysis (dead-code analysis) and control flow analysis. In addition, we also deal with Abstract Interpretation, a viewpoint on the semantics of programming languages and program execution within which we can also fit much of data and control flow analysis. Finally, we consider Type And Effect Systems which generalize the type inferencing part of the course Implementation Of Programming Languages.|
Principles of Program Analysis|
Nielson, Flemming, Nielson, Hanne R., Hankin, Chris
Corr. 2nd printing, ISBN: 3-540-65410-0.
The 1st edition of this book can also be used. I have been told the differences are not large. The details for this book are similar: Principles Of Programming Analysis by Nielson, Nielson and Hankin published by Springer Verlag, ISBN 3-540-65410-0.
Sheets for the course shall be published on the website.
|Course form:||Lectures and practical assignments, all of which takes place during the combi sessions. Lectures and work on practical assignments are alternated, starting with a lot of lectures, and gradually moving to fewer lectures and more practice hours.|
|Exam form:||The final grade consists of a weighted average of all the assignments to be computed as follows
|Minimum effort to qualify for 2nd chance exam:||As a consequence of the above: if more than one grade is below 4, then you are not allowed to do a 2nd chance exam (which is never an exam in this course, but an additional assignment).|
|Description:||Data flow analysis tries to determine properties of the values that
variables in a program may have in any execution. We consider a number of analyses and an encompassing framework
for a small imperative programming language. However, almost all analyses on the behaviour
of a program, are undecidable because of the Halting Problem. In this course, we deal with this
fact by computing approximations to the 'real' answer. However, we try to ensure that
any definite answer our analysis may give is in fact correct (but not necessarily complete).
Safety and correctness are important aspects of analysis which are often easily forgotten
yielding compilers that transform programs into non-equivalent ones.
Control flow analysis tries to determine what the possible execution paths in a program are. This is especially needful for higher order functional programming languages. The approach is constraint-based. Again safety and correctness are an issue.
The third subject consists of large parts of Chapter 5 of the book: Type and Effect Systems. These are similar to the type rules encountered in Implementation Of Programming Languages.
The final subject of the course from the book is abstract interpretation where program analysis is viewed as a special kind of program execution. The use of abstract interpretation is that it helps us to decide whether an analysis is correct with respect to the semantics of the programming languages.
Elements of program language semantics, lattice theory and the like are introduced as necessary.