CSE 428: Solutions of exercises on Imperative Programming

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. In C and C++ the concepts of "expression" and "command" are not as separated as in other languages. For instance, --x is an expression, in the sense that it returns a result, and also a command, in the sense that it changes the state of x. (The exact meaning of --x is: evaluate x-1 and let v be the result, then store v in the location associated to x, and return the value v.) Expression whose evaluation might affect the state are called "expressions with side effects", and require special care by the programmer as they cannot be regarded as "pure values". Consider for instance the following (incorrect) definition of the factorial function:
    2.    int fact(int x) { 
       if (x == 0) 
          return 1;
       else return fact(--x) * x;
   }
    1. What is the result returned by the call fact(3) ?
    2. Would the definition become correct if we substitute the command return fact(--x) * x; with {int y = x; return fact(--x) * y;} ?
    3. Would the definition become correct if we substitute the expression fact(--x) * x; with x * fact(--x); ? (This last question is quite tricky and it is just for curiosity: it would not be given at the exam.)

    Solution

    1. The call fact(3) will return 0
    2. Yes, the definition becomes correct.
    3. What happens with the expression x * fact(--x) depends on the compiler. For instance, with the g++ compiler on Unix the call fact(3) will still return 0
      4. . This is probably due to the fact that, in the evaluation of an expression of the form e1 + e2, if e1 is a variable then the compiler uses its location (instead of its value) for computing the sum. I also tried substituting fact(--x) * x; with the expressions 
       
   (x+x-x) * fact(--x);
      and 
       
   identity(x) * fact(--x);
      where "identity" is the identity function defined as 
       
   int identity(int x){return x;}
      and, in both these cases, I obtained the correct result (fact(3) returned 6)

      Finally, I tried substituting fact(--x) * x; with the expression 

       
   (1+x-1) * fact(--x);
      and I got the wrong result (fact(3) returned 0). Apparently, the compiler is able to recognize that (1+x-1) is the same as x, and to make an optimization, while it is not able to recognize that (x+x-x) is equivalent to x. Isn't it amazing? Anyway, these surprising results show that expressions with side effects require a lot of attention by the programmer.

  2. Consider the following command c: 
       begin
      x, y : integer
   in
      x := 1;
      y := 1;
      begin
         x : integer
      in
         x := 2;
         y := x
      end;
      print(x + y)
   end
    Assume that env and s are the initial environment and state (immediately before the execution of c). Describe (using a drawing if you want):
    1. The state and environment immediately after the execution of y := 1
    2. The state and environment immediately after the execution of y := x
    3. What is the value printed by the instruction print(x + y) ?

    3. Solution

    1. After the execution of y := 1 the environment is env[L1/x][L2/y], where L1 and L2 are fresh locations. The state is s[1/L1][1/L2].
    2. After the execution of y := x the environment is env[L1/x][L2/y][L3/x], where L3 is a fresh location. The second update [L3/x] on the environment "shelters" the first [L1/x]; i.e. in this environment the location associated to x is L3. The state is s[1/L1][2/L2][2/L3].
    3. The value printed by the instruction print(x + y) is 3 (the environment where this instruction is executed is env[L1/x][L2/y])

  3. Consider the following command 
       begin
      x : integer
   in x := 1;
      begin
         y : integer
      in y := 2;
         begin 
            x : integer
         in x := y;
            print(x)
         end;
         y := x;
         print(y)
      end
   end
    4. Assume that env and s are the initial environment and state. Describe (using a drawing if you want):
    1. The state and environment immediately after the execution of y := 2
    2. The state and environment immediately after the execution of x := y
    3. What are the value printed by the instructions print(x) and print(y) ?

    Solution

    1. After the execution of y := 2 the environment is env[L1/x][L2/y] where L1 and L2 are fresh locations. The state is s[1/L1][2/L2].
    2. After the execution of x := y the environment is env[L1/x][L2/y][L3/x], where L3 is a fresh location. The second update [L3/x] on the environment "shelters" the first [L1/x]; i.e. in this environment the location associated to x is L3. The state is s[1/L1][2/L2][2/L3].
    3. The value printed by the instruction print(x) is 2; The value printed by print(y) is 1. Note that immediately before the instruction y := x the environment is env[L1/x][L2/y], hence the instruction y := x changes the value of y into 1.

  4. Some imperative languages allow the so-called multiple assignment, namely a command of the form 
       x1 , x2 := e1 , e2
    The meaning is: Given the initial environment env and state s, the final state is obtained as follows:
    1. Find a particular case of e1, e2 for which the above command is semantically different from the following concatenation: x1 := e1 ; x2 := e2
    2. Assume having a language with blocks (and declarations inside blocks) and the (single) assignment, but not the multiple assignment. Write in this language a command semantically equivalent to x1 , x2 := e1 , e2. If you prefer, you can define a procedure
    3. Use the multiple assignment to write a command which exchanges the values of two variables x and y (swap).

    Solution

    1. The concatenation: x1 := e1 ; x2 := e2 gives a different result whenever the expression e2 contains x1. Assume for instance that the initial values of x1 and x2 are 1 and 2 respectively. Then, after the execution of x1,x2 := 0,x1 the value of x1 would be 0 and the value of x2 would be 1, while, with the command x1 := 0 ; x2 := x1, the value of both x1 and x2 would become 0
    2. An equivalent command could be written by using two auxiliary variables: 
         begin 
      aux1, aux2 : integer
   in aux1 := e1;
      aux2 := e2;
      x1 := aux1;
      x2 := aux2
   end
      Note: we could actually write it by using one auxiliary variable only.
    3. The swap of x1 and x2 could be done as follows: 
      x1 , x2 := x2 , x1

  5. The Fibonacci function can be defined recursively in Pascal as: 
       function fibo(n:integer):integer;
      begin
      if n < 0 
         then fibo := 0 /* error */
         else if n = 0 
                 then fibo := 0
                 else if n = 1 
                         then fibo := 1
                         else fibo := fibo(n-1) + fibo(n-2)
      end;
    Write an equivalent iterative implementation of this function in C or in Pascal using only the basic commands of the mini-imperative language (while, if_then_else, assignment). Don't use recursion or data structures like arrays and lists.

    6. Solution

    We write the function in C: 
       int fibo(int n){
       if (n<0) 
          return 0; /* error */
       else {
          int k,f1,f2,aux;
          k = 0;
          f1 = 0;
          f2 = 1;
          while (k < n){
             k = k+1;
             aux = f2;
             f2 = f1 + f2;
             f1 = aux;
          }
          return f1;
       }
   }

  6. The following is a recursive function in Pascal computing the Greatest Common Divisor of two positive natural numbers x and y , based on the Euclid's algorithm: 
       function GCD(x,y:integer):integer;
      begin
      if x < 1 or y < 1 
         then GCD := 0 /* error */
         else if x = y
                 then GCD := x
                 else if x < y 
                         then GCD(x,y-x)
                         else GCD(x-y,y)
      end;
    1. Is this function tail-recursive?
    2. Write an equivalent iterative function in C or in Pascal using only the basic commands of the mini-imperative language (while, if_then_else, assignment). Don't use recursion or data structures like arrays and lists.

    Solution

    1. Yes, the function is tail-recursive
    2. We write the function in Pascal: 
         function GCD(x,y:integer):integer; 
      begin
      if x < 1 or y < 1 
         then GCD := 0 /* error */
         else begin
              while not(x=y) do
                 if x > y then x := x-y else y := y-x;
              GCD := x
              end
      end;

  7. For each of the following three while commands, say for which initial values of x it eventually terminates. Assume that x is declared as an integer variable. 
       (1) while x > 0 do x := x - 1
   (2) while not (x = 0) do  x := x - 1
   (3) while x > 0 do x := x + 1
    Note1: we say that a while command "terminates" if the condition eventually becomes false. This includes the case in which the condition is immediately false and the body is never executed.
    Note2: do not consider the case of "anomalous termination" due to overflow of the value of x.

    Solution

    1. The command teminates for every initial value of x.
    2. The command teminates if and only if the initial value of x is non negative.
    3. The command teminates if and only if the initial value of x is negative or 0.