## CSE 428, Summer 99: Solution of Final

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