Exercise 1

1. The grammar is ambiguous due to
   1. associativity problem with the "->" operator: alpha -> beta -> gamma has two diffrent derivation trees
   2. precedence problem between the "list" and the "->" operators: alpha -> beta list has two different derivation trees
   The full solution should include the drawing of the trees
2. The following is a possible solution:

      Type ::= A -> Type | A
         A ::= A list | B
         B ::= TVar | (Type)
    
      TVAr ::= alpha | beta | gamma
   

Exercise 2

1. infinite loop (caused by the evaluation of the actual parameter f(0))
2. error (because pass-by-name requires the actual parameter to be a variable)
3. prints 0 (because the call of f(0) is never evaluated)

Exercise 3

1. No memory leaks, no dangling pointers
2. A memory leak, no dangling pointers
3. No memory leaks, one dangling pointer

Exercise 4

1.           C
             |
             C1   
            / \
          C2   C3
   

2. allowed
3. not allowed
4. allowed
5. not allowed

Exercise 5

   class Stack 
   {  
      private class Element
      { 
         int info;
         Element next;
         Element(int n) { info = n; next = null; }
         Element(int n, Element nxt) { info = n; next = nxt; }
       }
       private Element first;
       Stack() { first = null; }
       public synchronized boolean is_empty() { return (first == null); }    
       public synchronized void push(int n) { 
          if (first == null) 
             { first = new Element(n); notify(); } 
          else                              
             { first = new Element(n,first); }
       }    
       public synchronized int pop() throws InterruptedException { 
          while (is_empty()) wait();
          int n = first.info;
          first = first.next;
          return n;
       }
   }  

Exercise 6

   datatype 'a three_tree = emptyt 
                          | const of 'a 
                                   * 'a three_tree 
                                   * 'a three_tree
                                   * 'a three_tree;

   fun non_zero (emptyt) = 0
     | non_zero (const(x,t1,t2,t3)) = (if x=0 then 0 else 1)
                                      + non_zero(t1)
                                      + non_zero(t2)
                                      + non_zero(t3);

Exercise 7

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

Exercise 8

1. Typeable. The type is ('a -> 'a -> 'b) -> 'a -> 'b
2. Typeable. The type is ('a list -> 'b) -> 'a -> 'b
3. Not typeable, because of the application of g to itself

Exercise 9

   occurrences(_,[],0).
   occurrences(X,[X|L],N) :- occurrences(L,M), N is M+1.
   occurrences(X,[Y|L],N) :- not(X=Y), occurrences(L,M).