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 nonterminals. ">" 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:
 > is right associative
 * has higher priority than >
 * 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 (HigherOrder)
 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.
 reduce (op +) 0 [1,2,3]
 reduce (op *) 1 [1,2,3]
 reduce (op @) [] [[1],[2,3],[]]
 reduce (op <) true [1,2,3]
 reduce (fn (x,y) => x=0 orelse y) false [1,2,3]
 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 (n1)
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.