Spring 99, CSE 428: 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.

  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.

  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;
     
    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;
     
    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;
     
    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;
     
    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;

  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.

  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^)?
    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^)?

  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);
   }
   
    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);
   }
   
    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 */
   }
   
    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);
   }