| Website: | website containing additional information |
| Course code: | INFOAPA |
| Credits: | 7.5 ECTS |
| Period: | periode 3 (week 6 t/m 16, dwz 4-2-2008 t/m 18-4-2008; herkansing week 22)
|  |
| Timeslot: | D |
| Participants: | up till now 17 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 Compiler Construction.
|
| Literature: | We use
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. On average expect 4 hours of lectures and 3 hours of practical assistance per week.
|
| Exam form: | The final grade consists of a weighted average of all the assignments to be computed as follows
- 25% for the dataflow analysis assignment
- 40% for the control flow programming assignment
- 20% for the type and effect assignment
- 15% for the abstract interpretation assignment.
subject to the condition that none of the grades is lower than 4.0. You have passed the course if the average
is 5.5 or higher. In some cases the lecturer can demand an oral examination at the end to validate the given grade.
|
| Minimum effort to qualify for 2nd chance exam: | At most one of the assignments may have a grade lower than 4. Not handing in anything for a particular assignment defaults to the grade 0.
|
| 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.
|
