Exercise 1

1. The grammar is ambiguous. There are two kinds of ambiguities, respectively related to the associativity of the application and to the precedence between application and abstraction. Below we draw two different derivation trees ((1) and (2)) for the string x y z , and two different derivation trees ((3) and (4)) for the string fn x => y z.

          (1)             (2)               (3)                    (4)
   
          Exp             Exp            __ Exp                    Exp
         /   \           /   \          / /  |  \                /     \
       Exp   Exp       Exp   Exp      fn Ide => Exp         __ Exp      Exp
      /   \    \       /    /   \        |     /   \       / /  |  \     |
    Exp   Exp  Ide   Ide  Exp   Exp      x   Exp   Exp   fn Ide => Exp  Ide
     |    |     |     |    |     |            |     |        |      |    |
    Ide  Ide    z     x   Ide   Ide          Ide   Ide       x     Ide   z
     |    |                |     |            |     |               |
     x    y                y     z            y     z               y
   

2. The following is a possible solution:

      Exp ::= A | fn Ide => Exp
        A ::= B | A fn Ide => Exp
        B ::= C | B C
        C ::= Ide | (Exp)
    
      Ide ::= x | y | z
   

   NOTE: most of the students wrote a solution like

      Exp ::= B | fn Ide => Exp
        B ::= C | B C
        C ::= Ide | (Exp)
    
      Ide ::= x | y | z
   

   This second solution is almost correct, but not completely, since it does not allow to generate strings like x fn y => y, while they are generated by the grammar given in the text. However, since, admittedly, this case was tricky to recognize, no points of penalty have been given for this error.

Exercise 2

1. 4
2. 6
3. 2

Exercise 3

1. No memory leaks, one dangling pointer (p points to the address of x, which is deallocated at the end of foo)
2. No memory leaks, no dangling pointers
3. No memory leaks, one dangling pointer (p points to the cell allocated by q = new int, and made free again with delete q)

Exercise 4

1.           C
            / \
          C1   C3
           |
          C2
   

2. allowed, since C2 is a (indirect) derived class of C
3. not allowed, since x1 is a private member of C1
4. allowed, since C2 has access to its own private members
5. not allowed, since C3 is not a base class (neither direct, nor indirect) for C2

Exercise 5

   class Queue 
   {  
      private class Element
      { 
         int info;
         Element next;
         Element(int n) { info = n; next = null; }
       }
       private Element first;
       private Element last;
       Queue() { first = null; }
       public synchronized boolean is_empty()
       {      ------------                          
          return (first == null);
       }    
       public synchronized void insert(int n)
       {      ------------                       
          if (first == null) 
            { first = last = new Element(n); notify(); } 
          else                               ---------
            { last = last.next = new Element(n); }
       }    
       public synchronized int pop() throws InterruptedException
       {      ------------           ---------------------------
          while (is_empty()) wait();
          --------------------------
          int n = first.info;
          first = first.next;
          return n;
       }
   }  

NOTE 2: The assumption that the consumers checks is_empty() before calling pop() is not sufficient, because in a multi-threaded context such checks needs to be done atomically (i.e. in a critical section) with the consumption. Hence the necessity of the instruction while (is_empty()) wait(); and of the instruction notify();.

NOTE 3: Several students wrote a solution of the following kind:

   class Queue 
   {  
      private class Element
      { 
         int info;
         Element next;
         Element(int n) { info = n; next = null; }
       }
       private Element first;
       private Element last;
       private boolean in_use;
       -----------------------
       Queue() { first = null; in_use = false; }
                               ---------------
       public boolean is_empty()
       {  
          return (first == null);          
       }    
       public void insert(int n)
       {                            
          while (in_use) wait(); 
          ----------------------
          in_use = true;  
          --------------                          
          if (first == null) 
            { first = last = new Element(n); } 
          else                               
            { last = last.next = new Element(n); }
          in_use = false; notifyAll();
          ----------------------------
       }    
       public int pop()
       {    
          while (in_use) wait(); 
          ----------------------
          in_use = true;  
          --------------                          
          int n = first.info;
          first = first.next;
          in_use = false; notifyAll();
          ----------------------------
          return n;
       }
   }  

   fun sum_bintree(leaf(x)) = x
     | sum_bintree(node(t1,t2)) = sum_bintree(t1) + sum_bintree(t2);

   fun map_fun_list [] _  = []
     | map_fun_list (f::l) x = (f x)::(map_fun_list l x);

   delete_repetitions([],[]).
   delete_repetitions([X|L],K) :- occurs(X,L), delete_repetitions(L,K).
   delete_repetitions([X|L],[X|K]) :- not(occurs(X,L)), delete_repetitions(L,K).
   
   occurs(X,[X|_]).
   occurs(X,[Y|L]) :- not(X=Y), occurs(X,L).