Studio 10 on 14 April 2008

CSE 431S (Spring 2008)

Studio 10: Type Hierarchies and subtype tests

Preparation (2 hours, before studio)

Read through the following materials:

Java types
Conversions and promotions (excludes generics)
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
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.
[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:
- ppt overview of the approach
- PDF of the paper

Studio Sessions Overview:

We gather as a community in studio session to learn from each other. Our community includes:
- Instructor
- TAs
- Students
Our community is egalitarian in terms of learning: all of us will have questions and all of us should try to provide answers.
The idea is to challenge each other and to share what we discover.
You are free (downright encouraged) to collaborate in this session:
- Primarily within your small group of 2-3 people
- Secondarily with any group in the class
- As much as you like with the instructor and TAs
In studio, the instructor's mission is to observe, interact, and work with groups.
- How you think, work, and arrive at a solution is more important than getting the right answer. Thus, the instructor and TAs will observe you throughout the exercise and offer constructive feedback.
- The help you receive may be incomplete at any given time, so that you can work through more of the solution on your own. Do not hesitate to ask for more help.
In studio, the student's mission is to acquire new knowledge and skills by the collaborative solving of problems.
- You are not graded on whether you get wrong or right answers on this exercise.
- You are graded on your level of participation in studio.
Participation is defined as
- Asking questions, at any level, of any person in the studio
- Discussing possible solutions with people in the studio
- Helping somebody in the studio solve a problem
- Presenting or demonstrating your solution to people in the studio
- Documenting your group's experiences in studio
Please eliminate external stimuli (cell phones, IM, Facebook) during studio. Please devote yourself to learning, mastering, and extending the material for the session.

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)

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.
Download this zip file.
Install said zip file as usual: as an existing eclipse project from a zip archive file.
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:

Why is the type hierarchy a forest and not just a tree?
How would you determine if a given type widens or narrows another type?
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

A copy of your TeamHierarchy code, with authors' names thereon.
A console printout of the final runs you did.

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

CSE 431S (Spring 2008) Studio 10: Type Hierarchies and subtype tests

CSE 431S (Spring 2008)