CSE 428, Spring 2000: Solutions of Final

Exercise 1

  1. (b)        Type                   Type
           / | \                 / | \
          /  |  \               /  |  \
        Type -> Type         Type  -> Type
       / | \     |             |     / | \
      /  |  \    |             |    /  |  \
   Type -> Type TVar         TVar Type -> Type
     |       |   |             |   |       |
     |       |   |             |   |       |
   TVar    TVar gamma       alpha TVar    TVar
     |       |                     |       |
     |       |                     |       |
   alpha   beta                   beta   gamma



(b)        Type                 Type
           /  \                 / | \
          /    \               /  |  \
        Type   list         Type  -> Type
       / | \                  |      /  \
      /  |  \                 |     /    \
   Type -> Type             TVar  Type   list
     |       |                |    |       
     |       |                |    |       
   TVar    TVar            alpha  TVar    
     |       |                     |      
     |       |                     |      
   alpha   beta                   beta   

  2.    Type ::=  A -> Type | A
   A    ::=  A list  | (Type) | TVar

Exercise 2

  1. One DP to the stack, no ML
  2. One ML, no DP
  3. No DP, no ML
  4. One ML, no DP
  5. No DP, no ML
  6. One DP to the heap, no ML

Exercise 3

  1. False
  2. True
  3. False
  4. False: two threads could be executing inc_and_get_y() at the same time.
  5. False: the only modification that can be made on y is to increment it, hence after the first notification the value of y will be always positive.
  6. False
  7. True, because inc_y() is synchronized, hence it does not matter whether the notification is sent before or after the increment on y: No thread can execute get_y() before the increment has been made.
  8. True
  9. True
  10. False. The notification transfers the thread to the runnable state. Only after the thread is scheduled for execution it will go in the running state, and will have to compete for the lock again.

Exercise 4

  1.    
   datatype 'a tree = nod of 'a * 'a tree list;

  2.    fun sum_tree (nod (a,L)) = a + aux L
   and
       aux (nil)  = 0
     | aux (T::L) = sum_tree T + aux L;
    Alternative solution: 
       fun sum_tree (nod(a,nil))  = a
     | sum_tree (nod(a,T::L)) = sum_tree T + sum_tree(nod(a,L));
    Note that in this second solution we use a "clever" trick: we call sum_tree recursively on the tree obtained by pruning the first subtree from the original tree.

    Note that this is very different from the following definition: 

       fun sum_tree (nod(a,nil)) = a
     | sum_tree (nod(a,L))   = a + sum_tree(L);
    This latter definition, indeed, will not even pass compilation. L is a list of trees, and as such cannot be the argument of sum_list.

Exercise 5

  1. The result is [[5],[7,3]].
    reduce (fn (x,y) => if x=[] then y else x::y) [] L eliminates from the list L all the empty lists.

  2. The result is 7.
    reduce (fn (x,y) => if x>y then x else y) [] L returns the greatest element of the list L.

Exercise 6

  1. (alpha -> beta) -> (alpha -> gamma) -> alpha -> beta * gamma
  2. (alpha -> alpha) -> alpha -> int -> alpha
  3. int -> int list -> int list

Exercise 7

The simplest solution is the following: 
   balanced(emp).
   balanced(nod(T1,X,T2)) :- height(T1,N1), height(T2,N2), 
                             diff_within_1(N1,N2),
                             balanced(T1), balanced(T2).

   height(emp,0).
   height(nod(T1,X,T2),N) :- height(T1,N1), height(T2,N2), 
                             max(N1,N2,M), N is M+1.

   max(N1,N2,N1) :- N1 >= N2.
   max(N1,N2,N2) :- N1 < N2.                   

   diff_within_1(N1,N2) :- N1 - N2 =< 1, N2 - N1 =< 1.
However, this solution is not very efficient because the tree is traversed twice: once for deciding whether it is balanced, and the other time for calculating its height. The two tasks could be performed together. Based on this idea, we present another (more efficient) solution. 
   balanced(T) :- aux(T,_).

   aux(emp,0).
   aux(nod(T1,X,T2),N) :- aux(T1,N1), aux(T2,N2), 
                          max_min(N1,N2,M,K), 
                          M - K =< 1, N is M+1.

   max_min(N1,N2,N1,N2) :- N1 >= N2.
   max_min(N1,N2,N2,N1) :- N2 >= N1.