CS 303E: Type Chasing in Assignment #1001 (Fall 2004)

This document is still in preparation! You are welcome to read what there is, but it is subject to radical change.

Quite a few students reported problems with one of the two core concepts involved in Assignment #1001. These two concepts are: (A) Recursively-defined data structures; and (B) Extending a collaboration of classes. Most students seemed to understand the first concept, as used in the class Phrase specified in Assignment #1000. Further, most students understood how to extend a single class as was specified for class CognatePair in the same assignment. However, when it came time to implement class CognatePhrases from the next assignment, many students got lost and the reason appears to be that CognatePhrases is extended as part of a collaboration with CognatePair. I'll call this type of problem type chasing, and it is associated with two key questions: (A) What type (aka, class) of instance am I really using? and (B) What method am I really calling?

Before continuing with the specifics of Assignment #1001, I'm going to bring together the definitions of inheritance and collaboration so as to tie them to the assignment. Our textbook defines inheritance in a semi-formal fashion. I'll simply elaborate this definition. However, our textbook leaves the notion of collaboration unspecified, leaving it to your intuition to understand it. Although it is fairly intuitive and the definition that I gave in class (two or more classes that work together) is fine, I'll elaborate the definition further.

Collaboration

Two or more classes are said to collaborate if they work together to perform computation or to build a data structure. A fundamental example is that of a list. A list contains items in some order. You don't have a list unless both aspects (items and order) are specified, and the way these two aspects are implemented is (usually) as two classes that collaborate to build a list. One class represents the type of items in the list, and the other class represents the order. In our recent assignments, the classes Phrase and Word collaborate to build a list data structure that represents a phrase. The items are represented by the Word class, which, in our assignments, is a wrapper class wrapping a String that is required to satisfy properties defining legal words (non-null, non-empty, and no embedded whitespace). For the order aspect, we have Phrase, a recursively-defined class which specifies that a leading word must occur before a suffix phrase.

In many collaborations, it happens that one class refers to the other class(es) without being referenced in return. When this happens, the referring class is said to use the other class(es), and the collaboration is called a "uses" relationship. In our class definitions, class Phrase uses class Word.

Inheritance

One Java class (the sub-class) is said to directly inherit from a base class (aka, super-class) when the extends keyword is used to specify this. For example, a Java class header such as class Child extends Parent specifies that Child is a sub-class of another class named Parent. Indirect inheritance from a super-class to a sub-class occurs when there is a chain of direct inheritance relationships that leads from the sub-class to the super-class. For example, if two classes are defined with headers as shown below

class Child extends Parent 
class Parent extends GrandParent

then class Child inherits indirectly from class GrandParent.

There are two parts to inheritance: Implementation sharing, and the "is a" relationship.

Implementation sharing means that some members (instance variables and/or methods) of the super-class are automatically made available in the sub-class (not the other way around). In general, we say that the sub-class inherits members from the super-class, and, if we're referring to a specific member such as "instance variable a", we say that the sub-class inherits a from the super-class. Changing our viewpoint, we can also say that a super-class' member is inherited by the sub-class. In Java, all instance variables are inherited by a sub-class, and all instance non-private methods are also inherited by a sub-class. Note that this is different than access! It's perfectly possible (and common for data fields) for a sub-class to inherit a member without being able to access it directly. For example, an instance variable may be declared private in the super-class, therefore preventing the sub-class from directly accessing the field. Yet, that instance variable is still inherited by the the sub-class, and, if a getter method is accessible by the sub-class, the getter can be used to access the instance variable.

The second part of inheritance is the "is a" relationship, and this can be more subtle. When a sub-class inherits from a super-class, we say that an instance of the sub-class "is an" instance of the super-class. This means that a sub-class instance can occur anywhere an instance of the super-class can be used. In Assignment #1000, the CognatePair class extends Word, which means that a CognatePair instance can be used as a Word anywhere a Word can occur. If a method has a parameter of type Word, then that method can be invoked with an argument of type CognatePair as that Word parameter. Further, if a method is declared with return type Word, then that method can be defined to return an instance of type CognatePair. This is not true for constructors, and it's one of the biggest differences between methods and constructors. A constructor is pre-defined by its enclosing class definition to build exactly an instance of that class. It's not possible for a constructor to build a sub-class instance.

These two defining properties of inheritance can be confusing unless cold-blooded reasoning is used to take them to their logical conclusion.

In BlueJ class diagrams, classes are shown as labeled boxes, and some of the key relationships between classes are shown via arrows. A solid arrow with a hollow arrowhead indicates inheritance, while a dashed arrow indicates a uses relationship. Now, let's consider a class diagram for the classes that should be defined after Part 1 of Assignment #1001. is completed. That class diagram, except for the package hierarchy, is shown below:

This diagram shows three "uses" relationships: (A) Phrase uses Word; (B) CognatePhrases uses CognatePair; and (C) PigLatin uses PigLatinCognate. All of these relationships have the same core. They're all structurally the same as the Phrase to Word relationship. The Phrase to Word relationship is a list collaboration, where Word defines the list items, while Phrase defines the list order.

Ok, so how do these three collaborations differ?

First, the Phrase class can work with any Word sub-class, including Word itself. Further, Phrase implicitly defines the order relationship between Word instances by specifying leading word references to precede suffix phrase references. Since direct instances of the base class Word (not its sub-classes) only contain members referring to a single base language (English in our assignments), Phrase is deliberately defined so as not to refer to a cognate language. As a result, the Phrase to Word collaboration works with a single language.

Second, the next level, where class CognatePhrases uses class CognatePair, introduces another language and specifies a defining property for legal collaborations. However, this level collaborates in the same way as the base Phrase to Word collaboration. A CognatePhrases instance will be composed of a sequence of CognatePair instances in the same way: A leading word precedes a suffix phrase in that order. Therefore, we re-use that collaboration by defining both CognatePair and CognatePhrases to inherit from Word and Phrase, respectively and in parallel. There are three parts remaining in the implementation at this level. We add a cognate language by introducing a new instance variable and supporting methods in CognatePair. Then, the constructors of CognatePhrases are defined so that only CognatePair instances can be used to build instances of CognatePhrases. Finally, we ensure that all words in a CognatePhrases instance have the same cognate language by making that check in the appropriate CognatePhrases constructor.

Therefore, when an instance of CognatePhrases exists, it is guaranteed to be an instance of Phrase (because of inheritance), and every Word in this instance is really a CognatePair!

Third, the Pig Latin level further extends the basic phrase/word collaboration with an additional property: The cognate language is Pig Latin! Again, this is enforced by constructors that allow only that possibility.

Focus on CognatePair and CognatePhrases: Most of the confusion on Assignment #1001 seemed to occur with the second level: The collaboration of CognatePhrases with CognatePair. That's where I'll focus, and I'll start by narrowing our class diagram to just those classes and their immediate super-classes, Phrase and Word. Refer to the modified class diagram below:

The modified diagram organizes these four classes by both collaboration and inheritance. The rows show the collaborations: Row #1 is the Phrase to Word collaboration which defines the basic structure for one language; and row #2 is the CognatePhrases to CognatePair collaboration which extends the basic collaboration to include another cognate language. The columns show the inheritance hierarches: Column #1 contains the classes involving one word and column #2 contains the classes combining multiple words into phrases.

When writing code, we'll use this diagram to help ourselves keep track of the class(es) we're referencing, and that, in turn, will help us determine which methods to invoke and/or implement. To do this, we have to continually ask ourselves the following questions:

• How many languages are involved? Answering this determines the row of our diagram.
• How many words are involved? Answering this determines the column of our diagram.

Once we've answered these two questions, we've determined the class that we're working with. Next, when seeking an instance method or instance variable, we often must ask a third question: In which classes can this method or instance be defined? Since implementation sharing can only occur with inheritance, we need only examine classes in the same column! In fact, we must not allow ourselves to jump from column to column when seeking instance members.

Type Chasing: These are the fundamental questions of type-chasing, which I'll define as determining where the hell I'm supposed to access/define this method/variable. Let me give the simplest example that was a sticking point for most students: Implementing method toPhraseString() in class CognatePhrases. Those students who, during office hours, worked out a solution to this example were generally able to continue on to successful implementations of methods toCognateString() and toString(), which, successively, introduce more complications.

We'll start with the part that, because of its placement in the instructions, is almost too stupid to consider further: Determining where this method should be defined. We ask the two or three questions from above. We examine the name, toPhraseString(), which alludes to a phrase. Therefore, it's in the multiple-word column. Further, it only involves the base language, so it's in the one language row. The conclusion? This method should be defined in class Phrase! Ironically, the instructions imply, by their placement though not their wording, that this method should be in class CognatePhrases, instead. It is, indeed, possible to implement this method in CognatePhrases and most students took this approach. The reason that this is possible is that CognatePhrases inherits all the necessary methods from Phrase. Strictly speaking, though, the best placement is in class Phrase, and a couple of students worked this out.

We'll proceed by implementing toPhraseString() in class CognatePhrases, even though this isn't the best place for it. Implementing it in Phrase would be essentially similar, except that one key part would be simpler.

Let's start our implementation by outlining the method. In this outline, we'll place comments and "..." describing the steps we want to take. Later, we'll finish our implementation by substituting real code for the "...". Here's our outline:

public String toPhraseString() {

    // We'll build the String to return in two steps.
    //
    // In the first step, we'll initialize it to a String
    // representing the English form of the leading Word.
    //
    String result = ... ;

    // In the second step, which we'll do only if the suffix
    // is non-null, we'll append the English form of the suffix.
    // We'll include a space separator, of course.
    //
    if (getSuffix() != null) {

        // If there is a suffix, convert it to a String,
        // then append it to the result with a space separator:

        result += " " + ... ;
    }

    return result ;
}

How is the first step handled? There, we want to get the English form of the leading Word as a String. How do we get the leading Word? Well, there's an accessor named getWord() in Phrase, and CognatePhrases inherits that accessor. However, that method does not return a String. Instead, it returns a Word. So, how is that converted to a String? It's tempting to answer "toString()", but, since inheritance is involved, we first have to ask our type-chasing questions from above.

The second question, "how many words are involved", is easy since the return type of getWord() is a Word. Therefore, we already know that we're dealing with a class in the first column of our diagram. Answering the first question, "how many languages are involved", is a little harder because we have to know if a sub-class of Word can be returned. The answer is "yes", since we're invoking getWord() from within a CognatePhrases instance, which is defined to only allow a CognatePair sub-class as a leading Word, which involves two languages. Therefore, we're really dealing with a CognatePair instance as the return value from getWord().

Now, the temptation from above was to invoke toString() on the leading word in order to get the English form of the word. If we examine the source code of the Word class, we see that, there, toString() is defined to return the English form as a String. However, that won't work for us, because we're really dealing with a CognatePair instance, and toString() was overridden in CognatePair to return some other value. This is an example demonstrating the importance of type-chasing questions when working with inheritance relationships in Java.

The next step is to examine the inheritance hierarchy under Word to determine whether any method of Word returns the English form in all sub-classes. The answer is "yes" and we see that there is another method of Word that is defined to return the English form as a String, yet is never overridden. That method is getWord() in the Word class. Therefore, the correct way, in CognatePhrases, to return the English form of the leading Word is to evaluate getWord().getWord(). Including that expression to implement the first step in our code for toPhraseString() results in the following revised outline, which has only one more "..." to define:

public String toPhraseString() {

    // We'll build the String to return in two steps.
    //
    // In the first step, we'll initialize it to a String
    // representing the English form of the leading Word.
    //
    String result = getWord().getWord() ;

    // In the second step, which we'll do only if the suffix
    // is non-null, we'll append the English form of the suffix.
    // We'll include a space separator, of course.
    //
    if (getSuffix() != null) {

        // If there is a suffix, convert it to a String,
        // then append it to the result with a space separator:

        result += " " + ... ;
    }

    return result ;
}

It remains to implement the second step of this outline. Invoking getSuffix(), when it returns a non-null reference, gives us an instance of type Phrase. How can we convert such an instance to a String representing its English form? Again, it's tempting to invoke toString(), but the wisdom we've gained from the leading word example tells us, again, to ask our type-chasing questions. This time, we again conclude that we really have an instance of CognatePhrases which overrides the toString() method of Phrase. So, again we conclude that toString() will not work, and, again, we investigate other methods available in CognatePhrases. The only other method of CognatePhrases that refers to an English form of the phrase is toPhraseString(), the very method we're implementing! That suggests a recursive invocation of toPhraseString() on the suffix. So, how can we invoke this method on the instance returned by getSuffix()? Remember that getSuffix() has a return type of Phrase, but we're implementing the method toPhraseString() in CognatePhrases, a sub-class of Phrase. So, it won't work to simply say getSuffix().toPhaseString(). That's a compile-time error, since the compiler can't determine when, if ever, getSuffix() really returns an instance of CognatePhrases. Let's first consider the instructions for this method:

"... returns the English form of the represented phrase. If the suffix is null, this returns only the leading word in English. This, again, will probably require you to cast the leading word to a CognatePair in order to invoke an appropriate accessor. If, however, the suffix is non-null, concatenate the English leading word and the English form of the suffix (how do you access this?) with a space separator, and return the result."

The hint provided by these instructions is that of casting a Word to a CognatePair. We did not have to do this on the leading Word (why?), but the hint does apply to both parts of another method, toCognateString(), and it applies to the suffix part of toPhraseString(). That's the answer to the question, "how do you access this?", included in the instructions above. We know, by answering our type-chasing questions, that getSuffix() really returns, when non-null, a reference to an instance of CognatePhrases. Therefore, we can cast that reference to CognatePhases and invoke toPhraseString() on the result. That leads to the following expression:

((CognatePhrases) getSuffix()) . toPhraseString()

When we substitute this expression for the "..." in the second step of our method's outline, we get the following complete definition of toPhraseString() when it's implemented in CognatePhrases:

public String toPhraseString() {

    // We'll build the String to return in two steps.
    //
    // In the first step, we'll initialize it to a String
    // representing the English form of the leading Word.
    //
    String result = getWord().getWord() ;

    // In the second step, which we'll do only if the suffix
    // is non-null, we'll append the English form of the suffix.
    // We'll include a space separator, of course.
    //
    if (getSuffix() != null) {

        // If there is a suffix, convert it to a String,
        // then append it to the result with a space separator:

        result += " " + ((CognatePhrases) getSuffix()) . toPhraseString() ;
    }

    return result ;
}

That's how type-chasing works. Similar reasoning applies to both methods toCognateString() and toString() in class CognatePhrases. Further, and more importantly, the same type of reasoning applies to other inheritance hierarchies, and it's an essential type of reasoning when working with Java and most other object-oriented programming languages.