Kompilerkonstruktion: Activation Records

Procedurer og funktioner er centrale begreber i de fleste programmeringssprog og er afgørende for at vi kan udvikle store programmer fordi de tillader at vi indkapsling kompleksitet og kan abstrahere detaljer væk. For at kunne håndtere procedurer og funktioner i en kompiler er det nødvendigt at opsætte en del forskellige data strukturer og regler for hvordan disse datastrukturer anvendes. Disse strukturer og deres anvendelse er denne uges emne.

Bemærk allerede nu, at procedurer og funktioner set fra en kompilers synspunkt håndteres (næste) ens. Folk med en objekt-orienteret tilgang ynder også at bruge fælles betegnelsen metode for procedurer og funktioner. For lige at friske jeres hukommelse op er

• En procedure et separat stykke kode der ikke returnerer nogen værdi, men har en sideeffekt f.eks. at der gemmes i en database eller skrives til en printer.
• En funktion er et separat stykke kode der returnerer en værdi, og som ikke bør have sideeffekter. f.eks. beregne løn ud fra timeløn og antal timer arbejdet.

I Pascal og Ada kan man se forskel på procedurer og funktioner, der anvendes forskellige keywords (procedure og function). I Java, C og C++ er alt funktioner, de funktioner der burde være procedurer returnere en ikke-værdi void.

For ugens tekst kan procedure, funktion og metode anvendes som synonymer.

Litteratur

Læsevejledning

Som for kapitel 5 er kapitel 6 bygget op over mønsteret (1) introducer de centrale begreberne og principperne for emnet første og (2) brug derefter dette i MiniJava projektet. (1) er dækket af sektion 6.0 og 6.1, (2) er dækket af sektion 6.2.

I sektion 6.0 introduceres dagens tekst og der springes over i begrebet Higher-Order Functions i program 6.1 og den efterfølgende tekst. Da higher-order functions er besværlige at implementere i en kompiler skal i blot være klar over hvad det er for et begreb. Brug ikke lang tid på program 6.1 dette er ikke væsentligt for det vi vil se på.

I sektion 6.1 introduceres to centrale begreber (eller data strukturer) for håndtering af procedurer og funktioner: activation records og run-time stacken. Data strukturerne og deres sammenhæng er vist i figur 6.2. Brug tid på at forstå hvad indholdet af en activation record er og hvad reglerne for brugen af stakken er altså hvornår der pushes og popes. Som det fremgår af sektion 6.1 er det nu væsentligt hvilke hardware platform (CPU) den kompiler man udvikler skal køre på, bl.a. snakken om antal registre. I skal give høj prioritet til fra side 118 til og med side 124. Afsnittet Static Links der starter på side 124 har lavere prioritet.

Sektion 6.2 omhandler som sagt hvorledes activation records kan implementeret for MiniJava. Her skal i bemærk, at der arbejdes videre på de kodeskelleter, der vises her i de efterfølgende kapitler. Der er derfor noget af kode som er på et meget højt abstraktionsniveau og kan være svær at følge. Det centrale for koden der implementerer for håndtering af activation records for MiniJava er at den skal være generelt og ikke må blive processorspecifikt.

Opgaver

1. Lav et Java program der illustrer call-by-value og call-by-reference parameter passing for procedure kald.

2. For sproget i jeres eget projekt eller for MiniJava projekt beskriv activation record strukturen som i vil anvende.
3. Tegn et billede med indholdet af jeres activation records og stack frame når i beregner beregner Fibonacci tal, se kode stumpen nedenfor.

// Rekursiv beregning af Fibonacci tal
public int fib(int n){
  if (n<=0){
    return 0;
  }
  else {
    if (n==1){
      return 1;
    }
    else {
      return fib(n-1) + fib(n-2); // recursive calls
    }
  }
}