| 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 19-4-2004 t/m 2-7-2004; herkansing week 35)
|
| Participants: | up till now 18 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. Type inferencing
is the subject of the course Type Systems, in this course we concern ourselves
mainly with the other two. 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: | As in 2002-2003, we use 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. Answers to selected exercises
from the book are available on paper. |
| Course form: | Lectures and practical assignments. |
| Exam form: | Four practical assignments: a large one which includes programming (40% of the final
grade), and three smaller ones (on paper, each worth 20% of the final grade) which concern themselves with one of the three main subjects of the course.
The weighted average of the grades should be at least 5.5, but none of the grades
may be smaller than 4.0. You get only one chance to improve a grade by doing
another assignment which is hence only given to those who have at most one grade less than 4.0.
This means that anyone having more than one grade below 4.0, must
do the entire course again next year. |
| Minimum effort to qualify for 2nd chance exam: | Om aan de aanvullende toets te mogen meedoen is ontbreken van ten hoogte 1 toetsactiviteit toegestaan. |
| 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 final subject of the course 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.
If time permits, attention will be paid to an application of the material treated
within research done within the ST group.
Elements of program language semantics, lattice theory and the like are introduced
as necessary. |
