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.

The superscript "(s)" stands for "solution provided". You can find the solution of these exercises here.

1. ^(s) 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:

   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.)
2. ^(s) 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. ^(s) 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
   

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) ?
4. ^(s) 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:
   • let v1 be the result of the evaluation of e1 in env and s,
   • let v2 be the result of the evaluation of e2 in env and s,
   • put v1 and v2 in the locations associated to x1 and x2 respectively
   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).
5. ^(s) 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 either recursion or data structures like arrays and lists.
6. ^(s) 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 either recursion or data structures like arrays and lists.
7. ^(s) 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.
8. Exercise 4.2 in Sethi
9. Write a procedure which prints all the prime numbers from 2 to n (if n is smaller than 2, then it doesn't print anything). Remember that a number is prime if it is not divisible by any number except 1 and itself.)
10. Write a procedure which prints all the factorials of the numbers from 0 to n (if n is negative, then it doesn't print anything). Remember that the factorial of a natural number k is the product of all the numbers from 1 to k if k is positive, and it is 1 if k is 0.