| Website: | website containing additional information |
| Course code: | INFAPA |
| Credits: | 6 ECTS (=4.2 old credit points) |
| Period: | periode 2 (week 44 t/m 51, dwz 28-10-2002 t/m 20-12-2002; herkansing week 10)
|
| Participants: | up till now 21 subscriptions |
| Schedule: | Dit is een oud rooster!
|
| Contents: | Een professionele compiler ontkomt er niet aan om door middel van
de analyse van de broncode van een programma, een poging te doen de uiteindelijke
code van het programma te optimaliseren. In dit vak draait het allemaal om
de analyses die door de jaren heen zijn bedacht en uitgevoerd.
We concentreren ons hierbij op dataflow analyse, controlflow analyse
en abstracte interpretatie ten einde informatie te verzamelen over programma's.
Dataflow analyse houdt zich bezig met het nagaan hoe informatie zich binnen
een programma beweegt. We doen dit aan de hand van een imperatieve programmeertaal.
Een voorbeeld is nagaan wanneer een variabele niet meer gebruikt wordt,
welke delen van de heap wanneer vrijgegeven zouden kunnen worden,
maar ook het detecteren van ongebruikte stukken code en welke parameters in
een Haskell programma uiteindelijk altijd berekend moeten worden.
Control flow analyse passen we toe op een simpele functionele programmeertaal.
Control flow analyse houdt zich simpelgezegd bezig met wat de mogelijke paden
door de source code van je programma zijn.
Abstracte Interpretatie is een poging lijn te brengen in het scala van
bestaande programma analyses zoals de bovenstaande twee. Het kernidee van
Abstracte Interpretatie is dat eigenschappen van programma's benaderend
worden bepaald, dit door het kiezen van het voor het probleem juiste
semantische domein. We kunnen een programma namelijk niet doorrekenen
voor alle mogelijke inputs, maar gegeven de juiste abstractie kunnen
willen we in eindige tijd uitkomsten krijgen die altijd te vertrouwen,
maar misschien niet volledig zijn, in de zin dat de antwoorden soms
niet de best mogelijke zijn. Een voorbeeld is dat we tijdens de abstracte
interpretatie van een programma niet voor elke variabele bijhouden welke
waarden hij aan kan nemen, maar alleen of hij negatief, positief of beide
kan zijn.
|
| Literature: | Dit jaar gebruiken we het boek
Principles Of Programming Analysis van Nielson, Nielson en Hankin uitgegeven
bij Springer Verlag, ISBN 3-540-65410-0.
Sheets over het vak komen op de website, uitwerkingen van de opgaven zijn
voor een groot deel beschikbaar.
|
| Course form: | hoorcollege met practicum en werkgroep |
| Exam form: | Open-boektentamen (60%) en praktikum (40%). Beide afzonderlijke cijfers
moeten voldoende zijn.
|
| 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: | Enigszins onder voorbehoud: na een overzicht van het gebied van programma analyse,
behandelen we data flow analyse, control flow analyse
en abstracte interpretatie. In het boek
wordt veel aandacht geschonken aan de wijze waarop de verschillende
bestaande analyses in een theoretisch raamwerk gepast kunnen worden, zodat
er gewerkt kan worden met generieke procedures voor het berekenen van
resultaten. Deze methode leent zich uitstekend voor een implementatie in
een hogere order functionele programmeertaal.
Praktikum: een projectje waarbij Monotone Frameworks geimplementeerd
moeten worden. De te analyseren programmeertaal is een zelf te maken
uitbreiding op de While taal uit hoofdstuk 2 van het boek.
De programmeertaal is zelf te kiezen uit de volgende twee: Java of Haskell.
De opdracht dient in tweetallen te worden gemaakt.
Bij wijze van test van de implementatie van het Monotone Framework dienen dan
twee analyses te worden geimplementeerd: eentje uit het boek en een nog nader
te bepalen andere analyse.
Vervolgens komt er nog een opgave over hoofdstuk 3 uit het boek,
Constraint Based Analysis, welke gebruikt wordt voor de control flow analyse
van een functionele programmeertaal.
|
