| Website: | website containing additional information |
| Course code: | INFOAPA |
| Credits: | 7.5 ECTS (=5.25 old credit points) |
| Period: | periode 4 (week 17 t/m 27, dwz 25-4-2005 t/m 8-7-2005; herkansing week 35)
|  |
| Timeslot: | C |
| Participants: | up till now 11 subscriptions |
| Schedule: | Dit is een oud rooster!
|
| Contents: | A professional compiler cannot avoid doing 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 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.
|
| 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
'werkcolleges'.
|
| Exam form: | Four practical assignments: a large one split into two parts, which is basically a programming assignment (40% of the final
grade), and four smaller ones (on paper, the first two worth 20% of the final grade, the second pair each worth %10; the latter two may be combined into one).
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.
In order to receive a passing grade, there will be a 30 minute individual oral examination to make sure that you have participated enough in doing the
assignments (which are done in pairs).
|
| Minimum effort to qualify for 2nd chance exam: | To be allowed to participate in the extended exam, it should be the case that replacing your lowest mark (which might 0 because you did not hand it in),
by the highest possible grade makes it possible to pass the course.
|
| 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 is 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 few lectures we pay attention to program analysis done within
the ST group. This amounts to the material in Chapter 5 of the book.
Elements of program language semantics, lattice theory and the like are introduced
as necessary.
|
