Exercise 1

1. template < class A> class stack : public stack_or_queue< A > { 
      public: 
         void push(A x) { 
            first = new element(x,first); 
         }
   }
   

2. template < class A > class queue : public stack_or_queue< A > {
      private:
         element *last;
      public: 
         queue(){last = first = NULL; }//not necessary: it's enough to init. first
         void insert(A x) {
            if (is_empty()) { first = last = new element(x,NULL); }
            else { last = last->next = new element(x,NULL); }
         }
   
   /* If we use the pop of stack_or_queue, popping the last element will 
      cause last to become a dangling reference. In this particular case 
      this dangling reference would not be harmful, since the next insert 
      will redefine last correctly, and we don't use last otherwise. 
      However, for the sake of a "clean programming style", we redefine
      (override) pop so to delete last when the queue is emptied. */
   
         A pop(){                             
            A inf = stack_or_queue< A >::pop();
            if (first==NULL) { last = NULL; } 
            return inf;
         } 
   }
   

3. The following is a possible solution. Note that a complete deallocation of an object in stack_or_queue< A > is ensured only under the assumption that also the class which replaces < A > has a destructor.

   ~element() { if (next != NULL) delete next; }
   ~stack_or_queue() { if (first != NULL) delete first; } 
   

Exercise 2

1. • (a) Not correct. One cause of incorrectness is the following: Assume that two consumers are in the wait set as the result of performing the get(), and assume that they are reached by the notification sent by a producer. Sooner or later one consumer will be scheduled and will get the datum. The other consumer will also be scheduled eventually, and, since it will restart the get() from the instruction after the if (is_empty) wait(), it will retrieve (erroneously) the datum as well.
   • (b) Not correct. The synchronization of run is not a solution to the interference problem on the buffer, since the synchronization of run() would only ensure that "the same philopher does not have a parallel life". Furthermore the wait() instruction in the run() would cause a philopher to block forever, because the only notification that would "wake him up" can only be sent by himself (later in the method run()).
2. • (a) Still deadlock-free. Only one thread can be in the wait set at a time (either the producer or the consumer, depending on the value of is_empty). Hence notify() has exactly the same result as notifyAll().
   • (b) In general the notification should be sent after all possible wait() instructions. In fact, wait() releases the lock, hence we cannot guarrantee that the condition will be changed before other threads will test it. Therefore any notification sent before the wait() might be lost. This problem might cause deadlocks and also incorrect behaviour. However, in this particular case, sending the notification before the wait() will not be harmful, because the consumer performs a cycle, and next time it will attempts to execute the get() it will send the notification as the first thing. So the waiting threads will be notified eventually, even if they lost the "right" notification.
3. A simple solution consist in using two fields so that we can hold two informations at the same time, and in moving data between the two fields when performing the operations of put() and get(), so to implement a FIFO discipline. We will call Buffer2 the class of a buffer with two positions.

   class Buffer2 {
     private int content1, content2;
     private boolean is_empty1, is_empty2;
     public Buffer2() { is_empty1 = is_empty2 = true; }
     public synchronized void put(int k) throws InterruptedException {    
       while (!is_empty1) wait();
       if (is_empty2) { // buffer empty
         content2 = k;
         is_empty2 = false;
         notifyAll(); 
       }
       else { content1 = k; is_empty1 = false; }
     }
     public synchronized int get() throws InterruptedException {
       while (is_empty2) wait();
       int k = content2;
       if (!is_empty1) { // buffer full
         content2 = content1;
         is_empty1 = true;
         notifyAll(); 
       }
       else { is_empty2 = true; }
       return k;
     }
   }
   

   A more elegant solution consists in defining Buffer2 as an object containing two objects of type Buffer1 (buffers with only one position) fisrt and second, and a little thread "demon". A put() on Buffer2 will cause a put() on first, and a get() on Buffer2 will cause a get() on second. The demon will take care of moving data from first to second.

   class Buffer2 {
     private Buffer1 first, second; 
     private class Demon extends Thread {
       private Buffer1 from, to; 
       public Demon(Buffer1 f, Buffer1 t){ from = f; to = t; }
       public void run() {
         try { 
           while (!isInterrupted()) { 
             synchronized (from) { int k = from.get();  to.put(k); }
           } 
         } catch (InterruptedException e) { return; }
       }
     }
     public Buffer2(){
       first = new Buffer1();
       second = new Buffer1();
       new Demon(first,second).start(); 
     }
     public void put(int k) throws InterruptedException {    
       first.put(k);
     }
     public int get() throws InterruptedException {
       return second.get();
     }
   }
   

Exercise 3

1. fun count(x,[]) = 0
     | count(x,y::l) = (if x=y then 1 else 0) + count(x,l);
   

2. The type cannot be made more general, because we need to check equality between the element x and the elements of the list.

Exercise 4

1. datatype 'a tree = emptyt | const of 'a * 'a tree list;

2. fun height t = let fun max(x,y) = if x>y then x else y;
                      fun max_heights [] = 0
                        | max_heights (emptyt::l) = max_heights l
                        | max_heights (const(n,k)::l) =
                                      max(1 + max_heights k, max_heights l)
                   in max_heights [t]
                  end;
   

   Another, more elegant solution for height is:

   fun height emptyt = 0
     | height (const(n,[])) = 1
     | height (const(n,t::l)) = let fun max(x,y) = if x>y then x else y
                                 in max(1 + height t, height(const(n,l)))
                                end;
   

   Finally, we give also a more interesting solution using the map function

   fun map f [] = []
     | map f (x::l) = (f x) :: (map f l);
   
   fun height emptyt = 0
     | height (const(n,l)) = let fun max(x,y) = if x>y then x else y;
                                 fun maxlist [] = 0
                                   | maxlist (a::k) = max(a, maxlist k)
                              in 1 + maxlist(map height l)
                             end;