Spring 99, CSE 428: Solution of Assignment 4 Distributed: Feb 11. Due: Feb 18 in class. Total maximum score: 100 points. The purpose of this assignment is to provide experience with activation records, tail recursion, and dynamic storage management (pointers). 1.[Points 10] Assume that an imperative language has static scope, but does not allow nested declarations of procedures or functions (e.g. C). Is the static link necessary for this language? Motivate briefly your answer. Answer: Static links are not necessary because all the non-locals in a procedure or function are global. In other words, the static links would all point to the top-level environment 2.[Points 20] Consider the following procedure declaration: procedure p(x:integer); var y:integer; /* declaration of a variable y local to p */ procedure q; /* declaration of a procedure q local to p */ procedure r; /* declaration of a procedure r local to q */ var x:integer; /* declaration of a variable x local to r */ begin /* begin body of r */ x := 0; q end; /* end body of r */ begin /* begin body of q */ if x = y then begin y := y - 1; r end else print(y) end; /* end body of q */ begin /* begin body of p */ y := x; q end; /* end body of p */ Assume that at a certain point, the main program contains a call of the form p(1); Show the stack snapshot (i.e. the configuration of the activation records on the stack) at the moment in which the instruction print(y) is executed for the first time. In particular, show the static and the control links. You can use a drawing. main p I top (which in Pascal coincides with main) ^ ------------------ ^ CL |___|_ | | | | | ------------------ | | _|______| SL | | ------------------ |-->| ----- |<-----|----| | | x | 1 | | | | | | ----- | | | | | y | 0 | | | | | | ----- | | | CL | ------------------ | | | | | | q I | | | ------------------ | | |___|_ | | | | | | | ------------------ | | | _|______| SL | | | | ------------------ | |-->| |<-----| | | | | | | | | | | | CL | ------------------ | | | | | | r I | | | ------------------ | | |___|_ | | | | | | | ------------------ | | | _|______| SL | | | | ------------------ | |-->| ----- | | | | x | 0 | | | | | ----- | | CL | ------------------ | | | | Q II | | ------------------ | |___|_ | | | | | ------------------ | | _|___________| SL | | ------------------ | | | | | | ------------------ CL = Control Link SL = Static Link 3.[Points 10] For each of the following recursive procedures and functions, say whether it is tail-recursive or not. Note:Each of them could be rewritten equivalently as a tail-recursive procedure or function, but this does not imply that it is tail-recursive. Tail-recursion is a property of the way the code is written, not of its possible rearrangements. 1. function fibo(n:integer):integer; begin if n = 0 then fibo := 0 else if n = 1 then fibo := 1 else fibo := fibo(n-1) + fibo(n-2) end; Answer: It is not a tail-recursive because the last operation executed is +. 2. function greatest(i:integer): integer; /* greatest element in an array A with n+1 positions */ begin /* containing non-negative numbers (call: greatest(0)) */ if i > n then greatest := 0 else greatest := max(A[i],greatest(i+1)) end; where max is the function declared as function max(x,y:integer): integer; begin if x > y then max := x else max := y end; Answer: It is not a tail-recursive because the last operation executed is the call of max(...). 3. procedure inc(i:integer); /* adds 1 to all elements of an array A with n+1 pos. */ begin if n > i then begin inc(i+1); A[i] := A[i] + 1 end end; Answer: It is not a tail-recursive because the last statement executed is A[i] := ... . 4. procedure sum(i:integer); /* adds all elements of an array A with n+1 positions */ begin if n > 1 then begin A[i+1] := A[i] + A[i+1]; sum(i+1) end end; Answer: It is tail-recursive 5. function last(l:list):integer; /* Last element of a non-empty list of integers */ begin /* "^" is the dereferencing operator in Pascal */ if l^.next = nil then last := l^.info else last := last(l^.next) end; Answer: It is tail-recursive 4.[Points 10] Given an array A with n+1 integer elements, write a tail-recursive function which (when called with a suitable parameter) gives the position of the last zero element, i.e. the greatest index i such that A[i] = 0. Say also what how the function should be called (i.e. with what parameter) so that it gives the intended result. Assume that the indexes range from 0 to n and that the array contains at least one 0. You can use either C or Pascal. In Pascal function max_index_of_0 (i:integer):integer begin if A[i]=0 then max_index_of_0 := i else max_index_of_0 := max_index_of_0(i-1) end; In C int max_index_of_0(int i) { if (A[i]==0) return i; else return max_index_of_0(i-1); } in both cases, the call should be: max_index_of_0(n) Note: a test on i < 0 is not necessary, because we are assuming that the array contains at least one 0 element. 5.[Points 20] Consider the following fragment of code in Pascal: var p,q,r: ^integer; /* declaration of p, q and r as pointers to int */ begin new(p); p^ := 1; q := p; q^ := p^ + 1; print(p^); dispose(q); new(r); r^ := 1; p^ := p^ + 1; print(r^); end 1.What is the value printed by the instruction print(p^)? Answer: The value printed is 2. 2.Discuss the possible states (of p, q, r, and the heap) which we might have just before the execution of print(r^). You can use drawings to illustrate these possibilities. What are the possible values printed by the instruction print(r^)? Answer: p is dangling Possibility 1: The instruction new(r) does not allocate the location which p is pointing to. The value printed is 1. _____ p--->| 3 | dangling reference ----- _____ r--->| 1 | the value printed is 1 ----- Possibility 2: The instruction new(r) does allocate the same location which p is pointing to. The value printed is 2. _____ p----->| 2 | dangling reference |-> ----- | r-- the value printed is 2 6.[Points 30] For each of the following procedure declarations (in C or C++), say whether or not the call foo() causes memory leaks and/or dangling references. Say also, for each of them, what is the value printed, if known. 1. void foo(){ int x = 5; int *p = &x; *p = *p + 1; printf("%d",*p); } Answer: No dangling reference because the variable p is deallocated at the end of the procedure execution together with its pointed location (the location of x). No memory leak because the variable x is deallocated at the end of the procedure execution. result: 6 2. void foo(){ int x = 5; p = &x; /* p is a global variable with a declaration of the form int *p */ x = x + 1; printf("%d",*p); } Answer: Dangling reference (p) which points to the location of x allocated at the beginning of the procedure execution and deallocated at the end of the procedure execution. No memory leak. result: 6 3. void foo(){ int *p; p = new int; /* this instruction corresponds to new(p) in Pascal */ *p = 5; p = p + 1; printf("%d",*p); delete(p); /* this instruction corresponds to dispose(p) in Pascal */ } Answer: If the location with address p + 1 is not currently allocated then after the call foo() we have no dangling reference. During the call, in a sense we have a dangling reference, but is not harmful because we don't modify the value of the location pointed by p. If the the location with address p + 1 is currently allocated and it is pointed, say, by a global variable q, then we have a dangling reference also after the call (q becomes dangling as a consequence of delete(p).) We have memory leak because what is deallocated by delete(p) is not the same location initially allocated by p = new int. Result: In general we don't know. If the heap is initialized to 0, and the location with address p + 1 has newer been allocated, then it will be 0. Otherwise we can't say anything. 4. void foo(){ int *p; int **q; /* q is declared as a pointer to a pointer to int */ q = &p; p = new int; *p = 5; **q = **q + 1; printf("%d",**q); } Answer: No dangling reference. We have memory leak because the location allocated by p = new int is not deallocated at the end. Result: 6