Studio 10: Type Hierarchies and subtype tests

Preparation (2 hours, before studio)

Read through the following materials:
  1. Java types
  2. Conversions and promotions (excludes generics)
  3. It may not be readily apparent, but the PrimType and RefType classes implement the Type interface, and are therefore suitable as instances of a Type object in the description below.

    Convince yourself from the JavaDoc that the above is the case

  4. Take a look at the HierarchyInterface , and the following description thereof.

    At compile time, it will be necessary to tell the relationship between two types, say t1 and t2, which will always yield one of the following (the examples below are based on how normal Java would behave):

    1. narrows(t1, t2): is true iff t1 is a direct or indirect subclass of t2.

      For example,

      • narrows(new RefType("java.lang.String"), new RefType("java.lang.Object"))
        should return true.
      • narrows(new RefType("java.lang.Short"), new RefType("java.lang.Object"))
        should return true, even though there is java.lang.Number in between the two classes.
      • narrows(new RefType("java.lang.Object"), new RefType("java.lang.String"))
        should return false, because Object does not narrow String
      • narrows(new PrimType("boolean"), new PrimType("int"))
        should return false.
      • narrows(new PrimType("int"), new PrimType("boolean"))
        should return false.
      • narrows(new PrimType("int"), new PrimType("int"))
        should return false.
    2. widens(t1, t2): is true iff t1 is a direct or indirect superclass of t2. For example,
      • widens(new RefType("java.lang.String"), new RefType("java.lang.Object"))
        should return false.
      • widens(new RefType("java.lang.Number"), new RefType("java.lang.Short"))
        should return true.
      • widens(new RefType("java.lang.String"), new RefType("java.lang.Number"))
        should return false.
      • widens(new PrimType("boolean"), new PrimType("int"))
        should return false.
      • widens(new PrimType("int"), new PrimType("boolean"))
        should return false.
      • widens(new PrimType("int"), new PrimType("int"))
        should return false.
    3. Neither of the above, in which case one of the following must be true
      1. t1 and t2 are the same type.
      2. t1 and t2 are incompatible.

    The HierarchyInterface is used as follows.

    1. An instance of the interface is constructed
    2. The assertParentOf method is called as many times as is necessary to create the type hierarchy. In that call, the first parameter is asserted as a parent of the second parameter in the type hierarchy forest. Thus, a call to assertParentOf(a, b) means equivalently:
      • Class b extends class a
      • Class b is a direct subclass of class a
      • narrows(b,a) should be true but narrows(a,b) should be false
      • widens(b,a) should be false but widens(a,b) should be true
    3. At some point, finished is called, at which point no more calls to assertParentOf should be allowed.

      It is important to note that widens. and narrows must always return results consistent with the hierarchy declared at their point-of-call. However, it is possible that your implementation could run more efficiently after finished is called.

  5. [advanced, if you have time; or grab a grad student to be in your group] Take a look at Jan Vitek et al.'s method for a subtype test in constant time:

Studio Sessions Overview:

The results of your studio session are to be reported and documented in a file that you save in your workspace. You are to print and turn in one copy of that report for your group. In the descriptions of the studio exercises, verbs like report and document are indications of activities you should summarize and discuss in your report.

In your groups, take turns documenting results, looking over shoulders, and staffing the keyboard.

It is unacceptable to copy anything without understanding it. At any point, the TA or instructor can point to something you've done and ask you why it works, or change it and ask what would happen with the modification.

Setup (5 minutes)

  1. Form groups as usual; however, if you are a group of two people, I suggest you merge with another group of two or three people.
  2. Download this zip file.
  3. Install said zip file as usual: as an existing eclipse project from a zip archive file.
  4. Try to build it by running the build.xml file

I. Design and implement HierarchyInterface (40 minutes)

Answer the following questions amongst yourself and discuss with others or the TA/Prof before you start implementing:
  1. Why is the type hierarchy a forest and not just a tree?
  2. How would you determine if a given type widens or narrows another type?
  3. How do narrows(a,b) and widens(a,b) work if a and b are the same type?
Next, implement the interface in studio.TeamHierarchy. The code as distributed will test and time your implementation. We will keep track of the best times for a prize.

II. Least common superclass (45 minutes)

Design and implement the following method
  Type lcs(Type a, Type b)
in your TeamHierarchy class that uses your HierarchyInterface implementation to find the least common superclass of types a and b, and returns null if the types have no common superclass.

Talk about your approach with anybody who will listen. Demonstrate that it works with some output that you can print and turn in. You can use the CorrectnessTestChecks code to construct a sample hierarchy.

Turn in

Last modified 08:41:58 CDT 14 April 2008 by Ron K. Cytron