|Website:||website containing additional information|
|Credits:||7.5 ECTS (=5.25 old credit points)|
|Period:||periode 4 (week 17 t/m 27, dwz 24-4-2006 t/m 7-7-2006; herkansing week 35)|
|Participants:||up till now 13 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 less lectures and more practice hours.|
|Exam form:||Four practical assignments: a programming assignment (40% of the final
grade), and three on paper, the first of these is worth 30% of the final grade, and the final two %15 each.
The weighted average of the grades should be at least 5.5, but none of the grades may be smaller than 4.0. You may only improve your lowest grade, and you may improve only one of them. Hence if you have more than one grade lower than 4.0, then you cannot pass the course, and have to redo it entirely next year.
|Minimum effort to qualify for 2nd chance exam:||As a consequence of the above: if you more than one grade 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 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.
In the final lectures, we consider parts of Chapter 5 of the book: Type and Effect Systems. These are similar to the type rules encountered in Implementation Of Programming Languages.
Elements of program language semantics, lattice theory and the like are introduced as necessary.