Subclasses do not generate subtypes

As suggested earlier, binary methods cause problems with subtypes because the interpretation of the MyType parameter of the binary method in the subclass is ``smaller'' than the interpretation in the superclass (varies covariantly), in contrast to the rules for subtyping of functions, which require only contravariant changes to parameters. Thus if a class has a binary method, its subclasses will not generate subtypes!

We can make this problem more concrete by showing how our type system would be unsafe if we assumed that ${\it {DoubleNodeType}}$ were a subtype of ${\it {NodeType}}$. As expected, the problem arises with a binary method, ${\it {attachRight}}$. Suppose we write the simple procedure ${\it {breakit}}$ in Figure 13.

  

Figure 13: Procedure illustrating that subclasses need not generate subtypes.

If ${\it {n1}}$ is of type ${\it {NodeType}}$, then ${\it {n1.attachRight}}$ has type ${\it {Proc({\rm{\it MyType}})[NodeType / {\rm{\it MyType}}]}}$ = ${\it {Proc(NodeType)}}$. Since ${\it {n2}}$ also has type ${\it {NodeType}}$, ${\it {n1.attachRight(n2)}}$ type checks correctly.

Now suppose that we make the call ${\it {breakit(dn,n)}}$ where ${\it {dn}}$ is of type ${\it {DoubleNodeType}}$ and ${\it {n}}$ is of type ${\it {NodeType}}$. When the message ${\it {attachRight}}$ is sent to ${\it {dn}}$, a parameter of type ${\it {DoubleNodeType}}$ is expected. Instead the parameter ${\it {n}}$ of type ${\it {NodeType}}$ is provided. When the code of ${\it {attachRight}}$ from class ${\it {DoubleNode}}$ is executed, first the method ${\it {setNext}}$ is sent to self, causing no problems. However the method ${\it {setPrev}}$ is then sent to the actual parameter ${\it {n}}$. Because ${\it {n}}$ has no method with this name, the procedure would crash at this point.

What could have gone wrong? Since the code of the procedure appears to type check correctly, it must be the call which is not correct. Here the problem is the assumption that ${\it {DoubleNodeType}}$ is a subtype of ${\it {NodeType}}$! If they were not subtypes, it would be illegal to make the call of ${\it {breakit}}$ with ${\it {dn}}$ as a parameter.

As a result we see that, unlike the case before we introduced MyType, subclasses no longer need generate subtypes. Thus we will have to come up with a revised definition of subtyping which handles types with MyType correctly.