## CSE 428, Spring 99: Solution of Final

### 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.

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
5. not allowed, since C3 is not a base class (neither direct, nor indirect) for C2

### Exercise 5

In the text below, the underlined text represents the code to be added for the multithreaded use of the queue.
```   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 1: notify() (instead of notifyAll()) is sufficient here, because only consumers can be in the wait set.

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;
}
}
```
In other words, they propose to simulate a lock mechanism, instead of using the lock mechanism available in Java (via the synchronized mode). This solution cannot work in Java, because there is no guarrantee that the two consecutive instructions while (in_use) wait(); in_use = true; are executed atomically. In other words, the simulation of a lock mechanism presents the same problem of interference as the methods which update a shared object.

### Exercise 6

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

### Exercise 7

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

### Exercise 8

1. Typeable. The type is ('a -> 'a -> 'b) -> 'a -> 'b
2. Not typeable, because of the self-application of x
3. Typeable. The type is ('a * 'a -> 'b) -> 'a -> 'b

### Exercise 9

```   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).
```
NOTE: the test not(X=Y), in the second clause of occurs, serves to eliminate repetitions of the answer.