Spring 2000, CSE 428: Test 3

Question 1 (Grammars)

The following grammar generates the language of Types of mini ML:

   Type ::= TVar | Type -> Type | Type * Type

Where: Type and TVar are non-terminals. "->" and "*" are terminals. TVar is assumed to generate a set of names (the Type variables) "alpha", "beta", "gamma", etc. The productions for TVar are not represented here.

Show that this grammar is ambiguous by giving two derivation trees for each of the following type expressions:
```
   alpha -> beta -> gamma
   alpha -> beta * gamma
   alpha * beta * gamma
```
Modify the grammar so to obtain an unambiguous grammar, generating the same language, by enforcing the following properties:
1. -> is right associative
2. * has higher priority than ->
3. * is left associative

Question 2 (Memory management)

For each of the following procedure declarations in C++, say whether its execution leaves dangling pointers and/or memory leaks. If it leaves dangling pointers, specify whether they are to the heap or to the stack. Assume that p is a global variable declared as a pointer to int and initialized to NULL. Also, in the last two questions, assume that foo is called with argument p.

void foo() { int x; p = &x; }
void foo() { int *q; q = new int; p = q; }
void foo() { int *q; q = new int; p = q; delete q; }
int* foo() { int *q; q = new int; return q; }
void foo(int* r) { int *q; q = new int; r = q; }
void foo(int* &r) { int *q; q = new int; r = q; }

Question 3 (Java)

Consider the following class declaration in Java:

   class C {
      private int x;
      private int y;

      public C(int n) { x = n; y = 0; }
      public int get_x() { return x; }
      public synchronized int get_y() { if (y==0) wait(); return y; } //ignore synchronizedExceptions
      public synchronized void set_y(int n) { y = n; notify(); }
   }

For each of the following statements, say whether it is true or false

There is a lock associated to class C
There is a lock associated to each synchronized method of class C
There is a lock associated to each object of class C
For each object of class C there are two locks, one for each synchronized method of class C
It's not necessary to declare get_y() synchronized
We should declare synchronized also get_x()
We should declare synchronized also the constructor method C(int)
We should substitute "notify()" with "notifyAll()"
A thread will need to acquire the lock each time it calls a synchronized method of C
A thread will need to acquire the lock each time it calls a method of C
If the intention is that get_y() returns only values different from 0, then the "if" should be a "while"
A thread which executes the "wait()" releases the lock
A thread which was in wait() will continue the execution of get_y() as soon as it receives a notification

Question 4 (ML)

Define in ML a datatype 'a tree representing trees whose nodes contain information of type 'a, and have an arbitrary number of children.
Define the function pre_trav: 'a tree -> 'a list which gives the list of nodes obtained by the preorder traversal of the tree. You can define auxiliary functions if you wish.

Question 5 (Higher-Order)

Define a function altnfold which takes two functions f, g: int -> int , an integer (natural number) n, and an integer number x and computes:
```
   f(g(f(g(f(...f(g(x))...)))))
   <-- 2n calls -->
```
That is, the applications of f and g should alternate and there should be n calls to each (2n calls total).
Consider the function reduce : ('a * 'b -> 'b) -> 'b -> 'a list -> 'b:
```
   fun reduce f v [] = v
     | reduce f v (x::l) = f(x, reduce f v l);
```
For each of the following expressions, say what is the result of its evaluation in ML. Also, give a informal description of what's the effect of reduce (on a generic list) for the given parameters f and v.
1. reduce (op +) 0 [1,2,3]
2. reduce (op *) 1 [1,2,3]
3. reduce (op @) [] [[1],[2,3],[]]
4. reduce (op <) true [1,2,3]
5. reduce (fn (x,y) => x=0 orelse y) false [1,2,3]
6. reduce (fn (x,y) => if x>0 then x::y else y) [] [1,2,3]

Question 6 (Types)

For each of the following ML definitions of the function f, say what is its type.

fun f g x = g(x,x)
fun f g x y = g(x,y)
fun f g x y = (g x) y
fun f g x y = g (x y)

fun f g [] = 0
  | f g (a::L) = g a :: f g L

fun f g 0 = []
  | f g n = (g n) :: f g (n-1)

Question 7 (Prolog)

A binary tree, in prolog, can be represented by a term, like in ML. For instance, we can stipulate to use the name "nod" for the node constructor, and "emp" for the empty tree. With this convention, the following terms

   T1 = nod(nod(emp,1,emp),2,nod(emp,3,emp))
   T2 = nod(nod(emp,a,emp),b,nod(nod(emp,c,emp),d,emp))
   T3 = nod(nod(nod(nod(emp,a,emp),b,emp),c,emp),d,nod(nod(emp,e,emp),f,nod(emp,g,emp)))

represent the following trees::

      T1                T2                 T3
    
      2                 b                  d
     / \               / \                / \
    1   3             a   d              c   f
                         /              /   / \
                        c              b   e   g
                                      /
                                     a

Define a predicate in(X,T) which holds if X is a node in T.
Define a predicate in_trav(T,L) which holds if L is the list of nodes obtained by the inorder traversal of T
Define a predicate sum_tree(T,N) which holds if T is a tree of integers and N is their sum

Define a predicate symmetric(T,U) which holds if T and U are "symmetric", for instance:

      T             U

      a             a
     / \           / \
    b   c         c   b
   / \               / \
  d   e             e   d
     /               \
    f                 f

Note: for the first 3 questions, assume that the predicate is called with T instantiated. For the last questions assume that either T or U are instantiated. Make sure that, under these assumptions, your program does not loop or give error.