CSE 428: Solutions of exercises on scope, parameter passing, dynamic allocation and deallocation

The superscript "(d)" stands for "difficult". Exercises similar to those marked with "(d)" might appear in candidacy exams, but not in the standard exams of CSE 428.
  1. Consider the following sequence of declarations: 
       z : integer;
   procedure p (x:integer) < body >;
    Write a < body > for p so that the following piece of code 
       z := 1; p(z); write(z)
    will have all different outcomes in case of pass by value, pass by reference, and pass by value-result.

    Solution

    A possible such body could be: 
       x := x+1 ; z := z+2
    The outcome of the code would be:

  2. Consider a procedure declaration with two parameters x and y of type integer passed by value-result: 
       procedure p(value-result x, y : integer); < body >
    If we have a language that does not allow call by value-result, but only call by reference, how can we define the procedure p so that it has the same effect as the above one?

    Hint: To see the difference between call by value-result and call by reference, consider, for example, the case in which the body consists of the commands 

        x:=x+1; y:=y+1
    and the call associates x and y to the same actual parameter.

    Another case in which we observe a difference is when one of the actual parameters (say, z) occurs in the body as a non-local (or global) parameter, and the body contains instructions which modify z.

    Solution

       procedure p(var x1, y1 : integer); 
      var x,y : integer;
      begin
      x := x1;
      y := y1;

      < body >

      x1 := x;
      y1 := y
      end;
    Where x1 and y1 are two fresh variables, not occurring in < body >.

  3. Consider the following procedure declaration: 
       procedure p; 
      x: integer; 
      procedure q; 
         begin x := x+1 end; 
      procedure r; 
         x: integer; 
         begin x := 1; q; write(x) end; 
      begin 
      x:= 2; 
      r 
      end;
    What is the output produced by calling p in
    1. A language with static scope
    2. A language with dynamic scope

    Solution

    1. In a language with static scope the output would be 1
    2. In a language with dynamic scope the output would be 2

  4. Consider the following program in C++:
    5.    #include < stdio.h > 
   int x=0; 
   void p(int,int); 
   void main(){
      int x = 1;
      p(x,x);
   } 
   void p(int y, int z){
      x = x+1; 
      y = y+1; 
      z = z+1; 
      printf("%d\n",x+y+z);
   }
    1. What is the value printed? (Remember that C++ has static scope.)
    2. Suppose that we modify the declaration of p so to pass the parameters by reference. Namely, we write the declaration as p(int &y, int &z){...} . What is the value printed in this case?

    Solution

    1. The value printed is 5 (Since C++ has static scope, the x in the body of p is the global variable, which has value 1 when the print instruction is executed.)
    2. With call-by-reference the value printed is 7: at the moment in which the print instruction is executed, in fact, x has still value 1, while y and z point to the x local in main and have value 3.

  5. Consider the following fragment of code in Pascal: 
       var p,q : ^integer;
   begin
   new(p);
   q := p;
   p^ := 1;
   q^ := p^ + 1;
   write(p^);
   dispose(p);
   foo;
   write(q^)
   end
    where foo is a procedure call (whose body does not contain occurrences of either p or q).
    1. What is the value printed by write(p^)?
    2. Describe the situation (environment and state) relative to q after the execution of dispose(p). You can use a drawing if you want.
    3. Discuss what can happen when write(q^) is executed.

    Solution

    1. The value printed by write(p^) is 2
    2. After the execution of dispose(p), q becomes becomes a dangling reference. More precisely: q is associated to a location L which contains the address of the location L' (in the heap) which was previously pointed by p. With dispose(p), such location L' has been deallocated, i.e. is considered free for further allocations. At the moment, L' should still contain the value 2.
    3. We have two cases:
      • If the execution of foo uses the same location L' (which in Pascal can only happen with dynamic allocation, i.e. if foo executes an instruction of the form new(r))) then we cannot predict what value is printed with the instruction write(q^), since the value of L' might have been changed by foo. The same could happen in case of parallel processes allowed to access the same heap and using L'.
      • Otherwise, the value printed should be 2.

  6. Consider the following procedure declaration in C:
    7.    void p() {int x; q = &x; *q = 1;}
    where q is a global variable declared as pointer to int and initialized by q = new int;. What output can we expect to be produced by the following piece of code: 
       *q = 0; p(); r(); printf("%d\n",*q);
    where r is a procedure which does not mention q.

    Solution

    We cannot predict the effect of printf("%d\n",*q): When the procedure p terminates, x is deallocated and the reference to it (namely q) becomes dangling. Such location could be re-used for the local variables of r, and its value might have changed by the time we execute printf("%d\n",*q).