The need to change parameter and instance variable types in subclasses

Our next example is one in which it would be convenient to change both return types and parameter types of methods. The particular typing problem arises in connection with what are often called binary methods. Binary methods are those methods that have a parameter whose type is intended to be the same as the receiver of the message. Functions reflecting orders, such as ${\it {eq}}$, ${\it {lt}}$, and ${\it {gt}}$,or other familiar binary operations or relations are good examples of such methods. These are written with single parameters in object-oriented languages because the receiver of the message plays the role of the other parameter. Other compelling examples arise in constructing linked structures. Binary methods are notoriously difficult to deal with in statically-typed object-oriented programming languages. See [BCC+96] for an extended discussion of typing problems with binary methods.

Figure 7 is a sample class definition to implement nodes for a singly-linked list. In the class there is one instance variable for the value stored in the node and another to indicate the successor node. There are methods to get and set the values stored in the node, and to get and set the successor of the node.

  

Figure 7: Node class

Notice that function ${\it {getNext}}$ returns a value of type ${\it {NodeType}}$, the type of object generated by class ${\it {Node}}$, while the procedures ${\it {setNext}}$ and ${\it {attachRight}}$ each take a parameter of type ${\it {NodeType}}$. The method ${\it {attachRight}}$ currently just sends the message ${\it {setNext(newNext)}}$ to self, its use will become more apparent in section 5 when it is modified in a subclass.

Suppose we now wish to define a subclass of ${\it {Node}}$, ${\it {DoubleNode}}$, which implements doubly-linked nodes, while taking advantage of the code for methods in ${\it {Node}}$. To do this we need to add to ${\it {Node}}$ an additional instance variable, ${\it { previous}}$, as well as new methods to retrieve and set the ${\it { previous}}$ node. Note that if ${\it {DoubleNodeType}}$ is the type of objects generated from the class, then we will want both the ${\it {next}}$ and ${\it { previous}}$ instance variables to have type ${\it {DoubleNodeType}}$, and the relevant methods to take parameters or return values of type ${\it {DoubleNodeType}}$ rather than ${\it {NodeType}}$.This is particularly important because we do not want to attach a singly-linked node to a doubly-linked node.

Unfortunately in the simple type system described here we have no way of changing these types, either automatically or manually, in the subclass. Thus to get the desired typings, we would have to define ${\it {DoubleNode}}$independently of ${\it {Node}}$, even though much of the code is identical. This is clearly undesirable.