Recall that a type is a set of values — a (potentially unbounded) set of possible primitive values or objects. If we think about all possible List values, some are ArrayLists and others are LinkedLists. A subtype is simply a subset of the supertype.
“B is a subtype of A” means “every B object is also an A object.”
In terms of specifications, “every B object satisfies the specification for A.”
Substitution principle: Subtypes must be substitutable for their supertypes. In particular, a subtype must fulfill the same contract as its supertype, so that clients designed to work with the supertype can use the subtype objects safely.
An example of subtyping may occur in role-playing game. One might have a variety of characters so we could define a type Character. Characters may be be wizards, muggles, elves, droids, etc. If a Wizard has all the properties that a Character has and also supports the same operations then a Wizard may be a subtype of Character. A Wizard may have more properties than a generic character, and may be able to do more (example: cast a spell) but as long as a Wizard can pass off as a basic Character too, we would be able to establish a parent type and subtype relationship.
Subclassing, written with the extends keyword class B extends A, is one way to declare a subtyping relationship in Java. It is not the only way: other ways include implementing an interface (class B implements A) or one interface extending another (interface B extends A).
Subclassing
Some of you may want to watch this video on subclassing, in Java. This feature is also known as inheritance, in object-oriented languages.
Whenever we declare that B is a subtype of A, the Java type system allows us to use a B object whenever an A object is expected.
That is, when the declared type of a variable or method parameter is A, the actual runtime type can be B.
To understand the distinction between declared and runtime types, here is an example:
In the example, q has declared type Queue<Integer> but its runtime type is LinkedList<Integer>. Java permits this because LinkedList<Integer> is a subtype of Queue<Integer>.
In Effective Java by Joshua Bloch, Item 16: Favour composition over inheritance:
[Subclassing] is a powerful way to achieve code reuse, but it is not always the best tool for the job. Used inappropriately, it leads to fragile software.
Within one module, where the subclass and superclass implementations are under the control of the same programmer and maintained and evolved in tandem, subclassing may be appropriate. But subclassing in general is not safe, and here’s why:
Subclassing breaks encapsulation.
Bloch again:
In other words, a subclass depends on the implementation details of its superclass for its proper function.
The superclass’s implementation may change from release to release, and if it does, the subclass may break, even though its code has not been touched.
As a consequence, the subclass must evolve in tandem with its superclass, unless the superclass’s authors have designed and documented it specifically for the purpose of being extended.
Let’s look at several examples to see what can go wrong with careless subclassing.
Example from the Java library: java.util.Properties
1 publicclassPropertiesextendsHashtable{ 2 3 // Hashtable is an old library class that implements 4 // Map<Object,Object>, so Properties inherits methods like: 5 publicObjectget(Objectkey){...} 6 publicvoidput(Objectkey,Objectvalue){...} 7 8 // rep invariant of Properties: 9 // all keys and values are Strings10 // so provide new get/set methods to clients:11 publicStringgetProperty(Stringkey){12 return(String)this.get(key);13 }14 publicvoidsetProperty(Stringkey,Stringvalue){15 this.put(key,value);16 }17 }
The Properties class represents a collection of String key/value pairs. It’s a very old class in the Java library: it predates generics, which allow you to write Map<String,String> and have the compiler check that all keys and values in the Map are Strings. It even predates Map.
But at the time, the implementor of Properties did have access to Hashtable, which in modern terms is a Map<Object,Object>.
So Properties extends Hashtable, and provides the getProperty(String) and setProperty(String, String) methods shown above. What could go wrong?
Inherited superclass methods can break the subclass’s rep invariant.
Example: CountingList
This is a good point to learn about overriding from the Oracle/Sun Java tutorial. Pay attention to the use of the @Override annotation that helps us easily detect problems.
Let’s suppose we have a program that uses an ArrayList. To tune the performance of our program, we’d like to query the ArrayList as to how many elements have been added since it was created. This is not to be confused with its current size, which goes down when an element is removed.
To provide this functionality, we write an ArrayList variant called CountingList that keeps a count of the number of element insertions and provides an observer method for this count. The ArrayList class contains two methods capable of adding elements, add and addAll, so we override both of those methods:
1 publicclassCountingList<E>extendsArrayList<E>{ 2 3 // total number of elements ever added 4 privateintelementsAdded=0; 5 6 @Overridepublicbooleanadd(Eelt){ 7 elementsAdded++; 8 returnsuper.add(elt); 9 }10 11 @OverridepublicbooleanaddAll(Collectionc){12 elementsAdded+=c.size();13 returnsuper.addAll(c);14 }15 }
What if ArrayList.addAll works by calling addn times?
What if ArrayList.addAll sometimes calls addn times, and sometimes does it a different way, depending on the type of the input collection c?
When a subclass overrides superclass methods, it may depend on how the superclass uses its own methods.
Example: Photo Organizer
Here’s version 1.0 of a class to store photo albums:
Now version 2.0 of the photo organizer comes out, with a new feature for keeping track of the people in our photos. It has a new version of the Album class:
1 publicclassAlbum{2 protectedSet<Photo>photos;3 protectedMap<Person,Photo>photosContaining;4 // rep invariant: all Photos in the photosContaining map5 // are also in the photos set6 // ...7 }
The MyAlbum subclass breaks this new representation invariant.
When a class is subclassed, either it must freeze its implementation forever, or all its subclasses must evolve with its implementation.
Subtyping vs. Subclassing
Substitution principle
Subtypes must be substitutable for their supertypes.
The subtype must not surprise clients by failing to meet the guarantees made by the supertype specification (postconditions), and the subtype must not surprise clients by making stronger demands of them than the supertype does (preconditions).
B is only a subtype of A if B’s specification is at least as strong as A’s specification.
The Java compiler guarantees part of this requirement automatically: for example, it ensures that every method in A appears in B, with a compatible type signature.
Class B cannot implement interface A without implementing all of the methods in the interface.
And class B cannot extend class A and then override some method to return a different type or throw new checked exceptions.
But Java does not check every aspect of the specification: preconditions and postconditions we’ve written in the spec are not checked!
If you declare a subtype to Java — e.g. by declaring class B to extend class A — then you should make it substitutable.
Violating the substitution principle: mutability
Here’s an example of failing to provide substitutability:
By making it a subclass, we’ve declared to Java that MutableRational is a subtype of Rational… but is MutableRational truly a subtype of Rational?
Clients that depend on the immutability of Rational may fail when given MutableRational values. For example, an immutable expression tree that contains Rational objects — suddenly it’s mutable. A function that memoizes previously-computed values in a HashMap — suddenly those values are wrong.
Multithreaded code that uses the same Rational values in different threads, as we’ll see in a future class, is also in trouble.
MutableRational fails to meet guarantees made by Rational.
Specifically, the spec of Rational says that the value of objects will never change (immutability). The spec of MutableRational is not at least as strong as that of Rational.
In general, mutable counterparts of immutable classes should not be declared as subtypes. If you want a mutable rational class (perhaps for performance reasons), then it should not be a subtype of Rational.
String and StringBuilder (and StringBuffer, which is safe for multiple threads) offer an example of how to do it right. The mutable types are not subtypes. Instead, they provide operations to create a mutable StringBuilder/Buffer from an immutable String, mutate the text, and then retrieve a new String.
Violating the substitution principle: adding values
Another example, starting with a class for positive natural numbers:
1 /** Represents an immutable natural number ≥ 0. */2 publicclassBigNat{3 publicBigNatplus(BigNatthat){...}4 publicBigNatminus(BigNatthat){...}5 }
Now we need to write a program that deals with large integers, but both positive and negative:
1 /** Represents an immutable integer. */2 publicclassBigIntextendsBigNat{3 privatebooleanisNegative;4 }
BigInt just adds a sign big to BigNat. Makes sense, right? But is BigInt substitutable for BigNat?
Abstractly, it doesn’t make any sense.
We need to be able to say “every BigInt is a BigNat,” but not every integer is a positive natural! The abstract type of BigInt is not a subset of the abstract type of BigNat. It’s nonsense to declare BigInt a subtype of BigNat.
Practically, it’s risky.
A function declared to take a BigNat parameter has an implicit precondition that the parameter is ≥ 0, since that’s part of the spec of BigNat.
For example, we might declare
java
public double squareRoot(BigNat n);
but now it can be passed a BigInt that represents a negative number. What will happen? BigInt fails to make guarantees made by BigNat. Specifically, that the value is not negative. Its spec is not at least as strong.
One will need to be very comfortable with the distinction between overriding and overloading. Overloading is the act of creating multiple functions/methods with the same name. You should also read the Java tutorial regarding defining methods and overloading.
Violating the substitution principle: specifications
Here’s a subclass that is a proper subtype: immutable square is a subtype of immutable rectangle:
But what about mutable square and mutable rectangle? Perhaps MutableRectangle has a method to set the size:
1 publicclassMutableRectangle{2 // ...3 /** Sets this rectangle's dimensions to w x h. */4 publicvoidsetSize(intw,inth){...}5 }6 7 publicclassMutableSquareextendsMutableRectangle{8 // ...
Let’s consider our options for overriding setSize in MutableSquare:
1 /** Sets all edges to given size.2 * Requires w = h. */3 publicvoidsetSize(intw,inth){...}
No. This stronger precondition violates the contract defined by MutableRectangle in the spec of setSize.
1 /** Sets all edges to given size.2 * Throws BadSizeException if w != h. */3 voidsetSize(intw,inth)throwsBadSizeException{...}
No. This weaker postcondition also violates the contract.
1 /** Sets all edges to given size. */2 voidsetSize(intside);
No. This overloadssetSize, it doesn’t override it. Clients can still break the rep invariant by calling the inherited 2-argument setSize method.
Declared subtypes must truly be subtypes
Design advice: when you declare to Java that “B is a subtype of A,” ensure that B actually satisfies A’s contract.
B should guarantee all the properties that A does, such as immutability.
B’s methods should have the same or weaker preconditions and the same or stronger postconditions as those required by A.
This advice applies whether the declaration was made using subclassing (class B extends A) or interface implementation (class B implements A) or interface extension (interface B extends A).
Bloch’s advice in Item 16:
If you are tempted to have a class B extend a class A, ask yourself the question: “is every B really an A?” If you cannot answer yes to this question, B should not extend A. If the answer is no, it is often the case that B should contain a private instance of A and expose a smaller and simpler API: A is not an essential part of B, merely a detail of its implementation.
Even if the answer to this question is yes, you should carefully consider the use of extends, because — as we saw in the example of CountingList — the implementation of the subclass may not work due to unspecified behaviour of the superclass. In that example, the subclass’s methods broke because the superclass’s methods have an implicit dependence between them which is not in the superclass specification. Before using extends, you should be able to convince yourself that dependences amongst the superclass methods will not impact subclass behaviour.
Use composition rather than subclassing
Here’s Bloch’s recommendation from Item 16:
Instead of extending an existing class, give your new class a private field that references an instance of the existing class. This design is called composition because the existing class becomes a component of the new one.
Each instance method in the new class invokes the corresponding method on the contained instance of the existing class and returns the results. This is known as forwarding, [(or delegation)]. The resulting class will be rock solid, with no dependencies on the implementation details of the existing class.
The abstraction barrier between the two classes is preserved.
Favour composition over subclassing.
Let’s apply this approach to the Properties class:
1end-delete}
2public class Properties {
3 private final Hashtable table;
4 // ...
5}
6</code></pre>
7 8And to `CountingList`:
910```java
11 public class CountingList<E> implements List<E> {
12 private List<E> list;
13 public CountingList<E>(List<E> list) { this.list = list; }
14 // ...
15 }
16 '''
1718 `CountingList` is an instance of the **wrapper pattern**:
1920 + A wrapper modifies the behaviour of another class without subclassing.
21 + It also decouples the wrapper from the specific class it wraps --- `CountingLi\
22 st` could wrap an `ArrayList`, `LinkedList`, even another `CountingList`.
2324 A wrapper works by taking an existing instance of the type whose behaviour we wi\
25 sh to modify, then implementing the contract of that type by forwarding method c\
26 alls to the provided instance, delegating the work.
2728 So in `CountingList` we might see:
2930 ```java
31 public class CountingList<E> implements List<E> {
32 private List<E> list;
33 private int elementsAdded = 0;
3435 public CountingList<E>(List<E> list) { this.list = list; }
3637 public boolean add(E elt) {
38 elementsAdded++;
39 return list.add(elt);
40 }
41 public boolean addAll(Collection c) {
42 elementsAdded += c.size();
43 return list.addAll(c);
44 }
45 // ...
46 }
When subclassing is necessary, design for it.
Define a protected API for your subclasses, in the same way you define a public API for clients.
Document for subclass maintainers how you use your own methods (e.g. does addAll() call add()?).
Don’t expose your rep to your subclasses, or depend on subclass implementations to maintain your rep invariant.
Keep the rep private.
You can find more discussion of how to design for subclassing in Effective Java under Item 17: Design and document for inheritance or else prohibit it.
Interfaces and abstract classes
Java has two mechanisms for defining a type that can have multiple different implementations: interfaces and abstract classes.
An abstract class is a class that can only be subclassed, it cannot be instantiated.
There are two differences between the two mechanisms:
Abstract classes can provide implementations for some instance methods, while interfaces cannot.
New in Java 8 is a mechanism for providing “default” implementations of instance methods in interfaces.
To implement the type defined by abstract class A, class Bmust be a subclass of abstract class A (declared with extends). But any class that defines all of the required methods and follows the specification of interface I can be a subtype of I (declared with implements).
In Effective Java, Bloch discusses the advantages of interfaces in Item 17: Prefer interfaces to abstract classes:
Existing classes can be easily retrofitted to implement a new interface.
All you have to do is add the required methods if they don’t yet exist and add an implements clause to the class declaration.
Existing classes cannot, in general, be retrofitted to extend a new abstract class. If you want to have two classes extend the same abstract class, you have to place the abstract class high up in the type hierarchy where it subclasses an ancestor of both classes.
… but such a change can wreak havoc with the hierarchy.
With interfaces, we can build type structures that are not strictly hierarchical. Bloch provides an excellent example:
For example, suppose we have an interface representing a singer and another representing a songwriter:
In real life, some singers are also songwriters. Because we used interfaces rather than abstract classes to define these types, it is perfectly permissible for a single class to implement both Singer and Songwriter. In fact, we can define a third interface that extends both Singer and Songwriter and adds new methods that are appropriate to the combination:
A class Troubadour that implementsSingerSongwriter must provide implementations of sing, compose, and actSensitive, and Troubadour instances can be used anywhere that code requires a Singer or a Songwriter.
If we are favouring interfaces over abstract classes, what should we do if we are defining a type that others will implement, and we want to provide code they can reuse?
A good strategy is to define an abstract skeletal implementation that goes along with the interface. The type is still defined by the interface, but the skeletal implementation makes the type easier to implement. For example, the Java library includes a skeletal implementation for each of the major interfaces in the collections framework: AbstractList implements List, AbstractSet for Set, etc. If you are implementing a new kind of List or Set, you may be able to subclass the appropriate skeletal implementation, saving yourself work and relying on well-tested library code instead.
The skeletal implementation can also be combined with the wrapper class pattern described above. If a class cannot extend the skeleton itself (perhaps it already has a superclass), then it can implement the interface and delegate method calls to an instance of a helper class (which could be a private inner class) which does extend the skeletal implementation.
Writing a skeletal implementation requires you to break down the interface and decide which operations can serve as primitives in terms of which the other operations can be defined. These primitive operations will be left unimplemented in the skeleton (they will be abstract methods), because the author of the concrete implementation must provide them. The rest of the operations are implemented in the skeleton, written in terms of the primitives.
For example, the Java Map interface defines a number of different observers:
which returns a set of Map.Entry objects representing key/value pairs.
To make it easier to implement a new kind of Map, Java provides AbstractMap.
The documentation says:
> To implement an unmodifiable map, the programmer needs only to extend this class and provide an implementation for the entrySet method, which returns a set-view of the map’s mappings.
So:
1 publicclassMyMap<K,V>extendsAbstractMap<K,V>{2 publicSet<Map.Entry<K,V>>entrySet(){3 // my code here to return a set of key/value pairs in the map4 }5 // ...6 }
And the skeletal implementation, written for us by the authors of Map, implements the other methods in terms of entrySet:
1 publicclassAbstractMap<K,V>implementsMap<K,V>{ 2 publicbooleancontainsKey(Objectkey){ 3 // simplified version, actual code must handle null :( 4 for(Map.Entry<K,V>entry:this.entrySet()){ 5 if(entry.getKey().equals(key)){returntrue;} 6 } 7 returnfalse; 8 } 9 publicbooleancontainsValue(Objectvalue){10 // simplified version, actual code must handle null :(11 for(Map.Entry<K,V>entry:this.entrySet()){12 if(entry.getValue().equals(value)){returntrue;}13 }14 returnfalse;15 }16 publicSet<K>keySet(){17 // return a set of just the keys from this.entrySet()18 }19 publicCollection<V>values(){20 // return a collection of just the values from this.entrySet()21 }22 // ...23 }
Summary
In this reading we’ve seen some risks of subclassing: subclassing breaks encapsulation, and we must use subclassing only for true subtyping.
The substitution principle says that B is a true subtype of A if and only if B objects are substitutable for A objects anywhere that A is used. Equivalently, the specification of B must imply the specification of A. Preconditions of the subtype must be the same or weaker, and postconditions the same or stronger. Violating the substitution principle will yield code that doesn’t make semantic sense and contains lurking bugs.
Favour composition over inheritance from a superclass: the wrapper pattern is an alternative to subclassing that preserves encapsulation and avoids the problems we’ve seen in several examples. Since subclassing creates tightly-coupled code that lacks strong barriers of encapsulation to separate super- from subclasses, composition is useful for writing code that is safer from bugs, easier to understand, and more ready for change.
Test Yourself
Subclassing in Java
Question 1
Given the following classes, fill in the definition of the Cat class so that when greet() is called, the label “Cat” (instead of “Animal”) is printed to the screen. Assume that a Cat will make a “Meow!” noise, and that this is all caps for cats who are less than 5 years old.
```java
public class Animal {
protected String name, noise; protected int age;
public Animal(String name, int age) { this.name = name;
this.age = age;
this.noise = “Huh?”;
Assume that Animal and Cat are defined as above. What will be printed at each of the indicated lines?
```java
public class TestAnimals {
public static void main(String[] args) {
1 Animal a = new Animal("Scooby", 10);
2 Cat c = new Cat("Checkers", 6);
3 Dog d = new Dog("Beethoven", 4);
4 a.greet(); // Line A
5 c.greet(); // Line B
6 d.greet(); // Line C
7 a=c;
8 a.greet(); // Line D
9 ((Cat) a).greet(); // Line E
10 }
}
public class Dog extends Animal {
public Dog(String name, int age) {
super(name, age);
noise = “Bow wow!”;
}
In the example above, consider what would happen we added the following to the bottom of main:
java
a = new Dog("Ideefix", 10);
d = a;
Why would this code produce a compiler error? How could we fix this error?
Question 4
In the code segment below, which lines would cause compile-time errors and which ones would cause runtime errors? If you removed the lines that will result in errors, what would the output of main be?
Aside: The purpose of this question is to illustrate Java subclassing and its corner cases. It is not indicative of how one should use this feature of Java.
1 classA{ 2 publicintx=5; 3 4 publicvoidm1(){ 5 System.out.println("Am1-> "+x); 6 } 7 8 publicvoidm2(){ 9 System.out.println("Am2-> "+this.x);10 }11 12 publicvoidupdate(){13 x=99;14 }15 }16 17 classBextendsA{18 publicintx=10;19 20 publicvoidm2(){21 System.out.println("Bm2-> "+x);22 }23 24 publicvoidm3(){25 System.out.println("Bm3-> "+super.x);26 }27 28 publicvoidm4(){29 System.out.print("Bm4-> ");30 super.m2();31 }32 }33 34 classCextendsB{35 publicinty=x+1;36 37 publicvoidm2(){38 System.out.println("Cm2-> "+super.x);39 }40 41 publicvoidm3(){42 System.out.println("Cm3-> "+super.super.x);43 }44 45 publicvoidm4(){46 System.out.println("Cm4-> "+y);47 }48 49 publicvoidm5(){50 System.out.println("Cm5-> "+super.y);51 }52 }53 54 classD{55 publicstaticvoidmain(String[]args){56 Ba0=newA();57 a0.m1();58 Ab0=newB();59 System.out.println(b0.x);60 b0.m1();// class B hides a field in class A. 61 b0.m2();// you should never hide fields.62 b0.m3();// as you’ll see, it’s confusing!63 Bb1=newB();64 b1.m3();65 b1.m4();66 Ac0=newC();67 c0.m1();68 Cc1=(A)newC();69 Aa1=(A)c0;70 Cc2=(C)a1;71 c2.m4();72 c2.m5();73 ((C)c0).m3();// very tricky!74 (C)c0.m3();75 b0.update();76 b0.m1();77 b0.m2();78 }79 }
Subtyping
Question 1
You’ve been hired to create a design the new Student Information System for UBC. The application needs a class to represent a student list containing the list of students registered in a course.
You’ve started to create a small class to do this and so far here’s what it looks like:
```java
public class StudentList {
private List<Student> students;
1 /** Create new empty student list */2 publicStudentList(){3 students=newArrayList<String>();4 }5 6 /** Add an item to the student list */7 publicvoidadd(Studentstudent1){8 students.add(student1);9 }
}
The co-op student from SFU, Todd Tweedledum, says that your code would be much better and shorter if you used subclassing instead of composition, and the whole job could be done with a single line of code:
java
public class StudentList extends ArrayList<Student> { }
```
Both versions “work” in the sense that they provide a way of storing a list of items. Is one of them better than the other? If so which one? Why?
Question 2
Does the following code snippet represent valid subtyping?
+ Why or why not?
+ Will the Java compiler detect any problems?
1 publicclassEmployee{ 2 ... 3 4 /** 5 * @param salary: the amount we want to set as base salary for the employee; 6 * salary should be greater than 100 7 */ 8 privatesetBaseSalary(intsalary){ 9 ...10 }11 ...12 }13 14 publicclassDeanextendsEmployee{15 ...16 17 /**18 * @param salary: the amount we want to set as base salary for the Dean;19 * salary should be greater than 100020 */21 @Overrides22 privatesetBaseSalary(intsalary){23 ...24 }25 ...26 27 }