Spring 99, CSE 428: Assignment 2 Solution

Distributed: Jan 28. 
Due: Feb 4 in class. 

Total maximum score: 100 points. 


The purpose of this assignment is to provide experience with 
interpretation of expressions and simple commands, and with the
notion of scope. 

1.[Points 20] Consider the following boolean expressions: 

       (1) if x = 0 then true else (x = 1 or x > 1 or 1/x > 1).

       (2) x = 0 or x = 1 or x > 1 or 1/x > 1

  Assuming that x is declared as an integer, and that at the 
  moment in which the expressions are evaluated x is associated
  to a non-negative number, say what are  the results (true, 
  false or error), depending on the value of x, of (1) and (2) when 
    
  (a) "or" is interpreted as a strict operator 

      (1) True for all values of x
      (2) Error when x is 0; True for all other values of x

 
  (b) "or" is interpreted as a non-strict operator (short-circuit) 

      (1) True for all values of x
      (2) True for all values of x



2.[Points 10] Say what is the result of the following expression 

       let x = 0
        in let x = 1 
            in x 
           end
           + x
       end

    Note: the above expression could be written in ML, but not, 
          for instance, in C. However in C we can write a corresponding
          expression as a function call  f() where f is defined as: 

                   int f() { int x; x = 0; return g() + x; }

          and g is defined as 

                   int g() { int x; x = 1; return x; }   



    The result of this expression is 1.



3.[Points 20] Assume that we want to enrich the language of boolean
  expressions with the boolean operator "implies" (logical implication),
  by adding the production 

          Exp ::= Exp implies Exp

      and with the following meaning: 


          r |- e1  eval  false 
       ---------------------------
         r |- (e1 implies e2) eval true


          r |- e1  eval  true     r |- e2  eval  v 
       ------------------------------------------------
                  r |- (e1 implies e2)  eval v

  Say what is the result (true, false or error) of the following 
  expression, where x is declared as an integer: 

         x > 0 implies (x = 1 or x > 1 or 1/x > 1)



The result is True for every value of x.


4.[Points 30] 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
          
           The command always teminates.

       (2) while not (x = 0) do  x := x - 1


           The command teminates if and only if 
           the initial value of x is non negative.

       (3) while x > 0 do x := x+1

           The command teminates if and only if 
           the initial value of x is negative or 0.

Note: we say that a while command "terminates" when the 
condition is or becomes false (sooner or later). 


5.[Points 20] Say what values are printed by the following 
  command: 

       begin
       var x
       in x := 1;
          begin
          var y
          in y := 2;
             begin 
             var x 
             in  x := y;
                 print(x)
             end;
             y := x;
             print(y)
          end;
       end



   Result: 
             2

             1

----------------------------------------