Fall 2005, CS515 Homework Q's on OOPLs

#1. Data Abstraction (This problem comes from the Liskov and Guttag
book on data abstraction) 

a. Give a specification (in CLU) of a STACK abstraction that provides
access to its elements in LIFO order. (That is, write the cluster
definition showing function signatures for each operation with
'effects', 'requires' and 'modifies' as necessary.  Think about
possible exceptions needed.) STACKs are mutable.

b. Sometimes we may need to have access to all elements in a STACK.
We could either provide an iterator that yields elements from the most
recently pushed to the least recently pushed or we could provide a
fetch function that returns the i-th element for i between 1 and the
number of elements in the STACK.  Which is the better choice and why?

#2. Dynamic Dispatch. Examine the following Java program and for each
call, tell what method is the actual target of the call.

class A {  public z(E e) {...} }
class B extends A 
{  public void z(E e){...};
   public void z(F f) {...}'
}
class C extends A
{  public void z(F f){..}
class E{...}
class F extends E{...}

E e = new E();
F ff = new F();
A a = new A();
A ab = new B();
A ac = new C();
B b = new B();
C c = new C();

a.z(e);
ab.z(e);
ac.z(e);
b.z(f);
b.z(e);
c.z(f);
c.z(e);
ab.z(f);
ac.z(f);
c.z(f);

#3. In object-oriented programs, subclasses are "behavioral
subtypes" of their superclasses; that is, if B is a subclass of A,
then B objects can be used in the contexts where A objects are legally
used (e.g., as receiver objects for methods defined in A).  Now,
examine the portion of the class hierarchy rooted at A in problem
#2. from the perspective of exploring inheritance as subtyping.

a. Is C a behavioral subtype of A? Why or why not?

b. Is B a behavioral subtype of A? Why or why not?

#4.  Show a small Java program example for which XTA, RTA, and
points-to would result in different call graphs.