Final exam, CSCI 5535, 18th December 2001

You have 2.5 hours to answer all questions.  Please read all questions
before you start.  Points are divided equally amongst its parts.  Some
questions ask you to give examples in a particular language.  If you
are not sure of the syntax, you may make it up but then you should
explain clearly what your syntax means.

1. [10 points] Let's suppose class T has a method "doPrivate" and its
subclasses, S1 and S2, have methods do1 and do2 respectively.  Clients
of S1 and S2 should invoke only the do1 and do2 methods respectively.
(i) Give the complete code in Modula-3 to accomplish the above.  (ii)
Give the complete code in Java to accomplish the above.  For both
Modula-3 and Java indicate clearly what part of your code will be
visible to clients and what will be private.

2. [10 points] For each of these SML types, give code for a function
with that type.  Explain in your own words why your functions have
these types.  
  (i) bool -> (bool -> bool) -> bool; 
  (ii) ''a list * ''b * list * ''a * ''b -> bool

3. [10 points] Accurate garbage collectors require heap object to have
a type descriptor that gives their type.  Imagine, instead, a scheme
that does not use type descriptors on heap objects;  instead, the
compiler outputs type information only for globals and local
variables and the type graph (i.e., what are the fields in each type
and what type each field points to).  For example, consider:

    class T { int val; U p; };
    class U { T q; }
    T t;

The garbage collector knows that t points to an object of type T
(let's call it ObjT).  Thus the garbage collector can mark or copy
ObjT.  The type graph tells gc that ObjT has two fields, the second of
which is a pointer to a U object (call it ObjU).  Thus, gc can mark or
copy ObjU.  Similarly for ObjT, the type graph tells the gc that ObjU
has one field which is a pointer to T.  And so on.  In other words,
the garbage collector does not need type descriptors on objects
because it traverses the type graph while traversing the objects. (i)
Does this scheme work for weakly-typed languages?  (ii) Does it work
for polymorphic languages?  Give examples in each case to support your
argument. 

4. [10 points] Consider the following Modula-3 class hierarchy:

TYPE A = OBJECT 
           i: INTEGER;
         METHODS
           p ();
         END;

TYPE B = A OBJECT
         OVERRIDES
           p := proc1;
         END;

TYPE C = B OBJECT
         METHODS
           p () := proc2;
         END;
           
Recall that the METHODS section of an object defines new methods and
the OVERRIDES section overrides existing methods.  So, C is a subclass
of B, which in turn, is a subclass of A.  Assume that proc1 and proc2
already exist have the appropriate signatures.  Draw the method suites
for classes A, B, and C.  Make sure that your method suite indicates
which procedure corresponds to which method.

Now, consider the following code fragment:
  VAR anA: A;
      aC: C;
  BEGIN
    anA := NEW (B);
    anA.p ();               (* <- Point 1 *)
  
    NARROW (anA, A).p ();   (* <- Point 2 *)
  
    aC := NEW (C);
    aC.p ();                (* <- Point 3 *)
  
    NARROW (aC, A).p ();    (* <- Point 4 *)
  
    anA := NEW (A);
    anA.p ();               (* <- Point 5 *)
  END;

For each of the 5 points in the code fragment use your method suites
to give the invoked procedure.
 
5. [10 points] Modula-3 has a set of subtyping rules (which dictate
narrowing and widening conversions) and a set of assignment rules.
Java is similar (except it uses the name "assignment conversions" for
assignment rules). Give *two* reasons why a language needs both subtyping
rules and assignment rules?  In other words, why is it not adequate to
simply say that x can be assigned to y if there is a widening
conversion from x to y?   For each of your two reasons, give an example.

6. [4 points] What power does multiple-dispatching give over method
overloading, as found in C++?  Illustrate with an example.

7. [6 points] Imagine that you language supports both exceptions and
continuations.  (i) Give an example where you would use exceptions
instead of continuations.  Explain your choice.  (ii) Give an example
where you would use continuations instead of exceptions.  Explain your
choice.