Activation record: vejledende løsninger

Opgave A

I Java kan man kun lave call-by-value, så for at lave ændringer i den globale tilstand indefra en metode må man selve ændre de objekter metoden bliver kaldt med. Dette har jeg illustreret i eksemplet nedenfor.

// build a small class to show call-by-reference
class Swapper{
    public int t;
    // constructor
    Swapper(int val){ t = val; }

    // to alter the Swapper objects go in an alter the objects them self.
    public static void swap(Swapper x, Swapper y){
	int temp = x.t;
	x.t = y.t;
	y.t = temp;
    }
}

// the public class
public class Call{
    // swap the values of x and y, does not work because parameters
    // are passed by value (call-by-value).
    public static void swap(int x, int y){
	int temp = x;
	x = y;
	y = temp;
    }
    
    public static void main(String args[]){
	// call-by-value example
	int a = 10;
	int b = 20;
	System.out.println("Before a: " + a + ", " + "b: " + b);
	swap(a,b);
	System.out.println("Before a: " + a + ", " + "b: " + b);

	// "call-by-refernce" like example
	Swapper sa = new Swapper(10);
	Swapper sb = new Swapper(20);
	System.out.println("Before sa.t: " + sa.t + ", " + "sb.t: " + sb.t);
	Swapper.swap(sa, sb);
	System.out.println("Before sa.t: " + sa.t + ", " + "sb.t: " + sb.t);
    }
}

Opgave B

For MiniJava har vi brug for alle de felter der er beskrevet i kapitel seks med undtagelse af static link feltet. Det vil sige der skal være i activation recorden være felter til

• Gemte registre
• Parametre (som for Java antager vi at alt er call-by-value i MiniJava)
• Return address
• Lokale variable
• En retur værdi

Opgave C

Hvis vi f.eks. vil beregne fib(4) vil kald træet se ud som nedenfor.

Som det fremgår kalder fib(4) først fib(3). Denne kalder så fib(2), som så kalder fib(1). Selve kaldsekvensen fremgår af stakken som vis nedenfor. Val i tegningen er retur værdien og ret adr er retur adressen og så vises input parameteren n.

1. først pushes fib(4) på stakken
2. denne kalder fib(3) som pushes på stakken
3. denne kalder igen fib(2) som pushes på stakken
4. denne kalder igen fib(1) som pushes på stakken, når n==1 har vi en værdi (et) og den returneres (popes fra stakken)
5. her har fib(1) returneret med værdien 1 og denne gemmer vi i val
6. fib(2) kalder så fib(0) som pushes på stakken, når n==0 har vi en værdi (nul) og den returneres (popes fra stakken)
7. fib(0) returnerer med værdien nul, så der sker ingen synligændring til val. fib(2) har vi nu beregnet som fib(1) og fib(0) og vi kan nu returnerer fib(2) retur værdi (1) til fib(3) (popes fra stakken)
8. dette er gjort her og vi gemme fib(2)'s retur værdi (et) i val. Så kalder fib(3) fib(1) som pushes på stakken
9. fib(1) har vi en værdi for (et) så denne fib(1) returnerer (popes fra stakken)
10. her har fib(1) returneret og vi adderer dens retur værdi til val for fib(3) som nu er 2. Fib(3) er nu færdig og returnerer sin værdi til fib(4) (popes af stakken)
11. Vi har nu for fib(4) beregnet fib(3) og mangler så at beregne fib(2)
12. Fib(2) pushes på stakken.
13. denne kalder fib(1) som returnerer værdien 1 (og popes af stakken), 
14. denne værdi gemmes midlertidig i val og fib(2) kalder fib(0)
15. som pushes på stakken. Her har vi en værdi som returneres til fib(2)  og fib(0) popes af stakken.
16. Vi har nu beregnet fib(2) og denne returnerer til fib(4) (popes af stakken)
17. vi har nu beregnet for fib(4) både fib(3) og fib(2) og fib(4) kan returnere til den funktion den var kaldt fra (kaldet main) i figuren.
18. vi er færdige.

Venlig hilsen
Kristian Torp
torp (at) cs (dot) auc (dot) dk