1 of 43

CSE331�Lecture 16.1

Subtypes: Java details, equals redux, and alternatives

Ardi Madadi �Summer 2021�(Based on slides by Kevin Zatloukal, Mike Ernst, Dan Grossman, and many others)

2 of 43

SUBTYPES VS SUBCLASSES

3 of 43

Substitution principle for classes

If B is a subtype of A, then a B can always be substituted for an A

Any property guaranteed by A must be guaranteed by B

anything provable about an A is provable about a B
if an instance of subtype is treated purely as supertype (only supertype methods/fields used), then the result should be consistent with an object of the supertype being manipulated

B is permitted to strengthen properties and add properties

an overriding method must have a stronger (or equal) spec
fine to add new methods (that preserve invariants)

B is not permitted to weaken the spec

no overriding method with a weaker spec
no method removal

CSE 331 Summer 2021

4 of 43

Substitution principle for methods

Constraints on methods

For each supertype method, subtype must have such a method

(could be inherited or overridden)

Each overridden method must strengthen (or match) the spec:

ask nothing extra of client (“weaker precondition”)

requires clause is at most as strict as in supertype’s method

guarantee at least as much (“stronger postcondition”)

effects clause is at least as strict as in the supertype method
no new entries in modifies clause
promise more (or the same) in returns & throws clauses

cannot change return values or switch between return and throws

CSE 331 Summer 2021

5 of 43

Spec strengthening: argument/result types

For method inputs:

argument types in A’s foo could be �replaced with supertypes in B’s foo
places no extra demand on the clients
but Java does not have such overriding

these are different methods in Java!

For method outputs:

result type of A’s foo may be replaced by�a subtype in B’s foo
no new exceptions (for values in the domain)
existing exceptions can be replaced with subtypes�(none of this violates what client can rely on)

CSE 331 Summer 2021

LibraryHolding

Book

Shape

Circle

Rhombus

6 of 43

Recall: Subtyping Example

class Product {

private int price; // in cents

public int getPrice() {

return price;

}

public int getTax() {

return (int)(getPrice() * 0.086);

}

class SaleProduct extends Product {

private float factor;

public int getPrice() {

return (int)(super.getPrice()*factor);

}

CSE 331 Summer 2021

7 of 43

Substitution exercise

Suppose we have a method which, when given one product, recommends another:

class Product {� Product recommend(Product ref);

}

Which of these are possible forms of this method in SaleProduct (a true subtype of Product)?

Product recommend(SaleProduct ref);

SaleProduct recommend(Product ref);

Product recommend(Object ref);

Product recommend(Product ref)

throws NoSaleException;

CSE 331 Summer 2021

// good

// good, but in Java is overloading

// bad

8 of 43

Java subtyping

Java types:

defined by classes, interfaces, primitives

Java subtyping stems from B extends A and �B implements A declarations

In a Java subtype, each corresponding method has:

same argument types

if different, then overloading — unrelated methods

compatible return types
no additional declared exceptions

CSE 331 Summer 2021

9 of 43

Java subtyping guarantees

A variable’s run-time type (i.e., the class of its run-time value) is a Java subtype of its declared type

Object o = new Date(); // OK

Date d = new Object(); // compile-time error

If a variable of declared (compile-time) type T1 holds a reference to an object of actual (runtime) type T2,�then T2 must be a Java subtype of T1

Corollaries:

objects always have implementations of the methods specified by their declared type
if all subtypes are true subtypes, then all objects meet the specification of their declared type

Rules out a huge class of bugs

CSE 331 Summer 2021

10 of 43

Java subtyping non-guarantees

Java subtyping does not guarantee that overridden methods

have smaller requires
have smaller modifies
have stronger postconditions

Java only checks the return type not the postcondition
could compute a completely different function

have stronger effects
have stronger throws (& only for the same cases as before)
have no new unchecked exceptions

CSE 331 Summer 2021

11 of 43

EQUALS WITH SUBCLASSES

12 of 43

equals specification

public boolean equals(Object obj) should be:�

reflexive: for any reference value x, x.equals(x) == true

symmetric: for any reference values x and y,�x.equals(y) == y.equals(x)

transitive: for any reference values x, y, and z, if x.equals(y) and y.equals(z) are true, then x.equals(z) is true

consistent: for any reference values x and y, multiple invocations of x.equals(y) consistently return true or consistently return false (provided neither is mutated)

For any non-null reference value x, x.equals(null) should return false

CSE 331 Summer 2021

13 of 43

Really fixed now

public class Duration {

@Override

public boolean equals(Object o) {

if (!(o instanceof Duration))

return false;

Duration d = (Duration) o;� return this.min==d.min && this.sec==d.sec;� }

}

Correct and idiomatic Java
Gets null case right (null instanceof C always false)
Cast cannot fail

CSE 331 Summer 2021

14 of 43

Two subclasses

class CountedDuration extends Duration {

public static numCountedDurations = 0;

public CountedDuration(int min, int sec) {

super(min,sec);

++numCountedDurations;

}

class NanoDuration extends Duration {

private final int nano;

public NanoDuration(int min, int sec, int nano){

super(min,sec);

this.nano = nano;

}

public boolean equals(Object o) { … }

…

}

CSE 331 Summer 2021

15 of 43

CountedDuration is (probably) fine

CountedDuration does not override equals

inherits Duration.equals(Object)

Will (implicitly) treat any CountedDuration like a Duration when checking equals

o instanceof Duration is true if o is CountedDuration

Any combination of Duration and CountedDuration objects can be compared

equal if same contents in min and sec fields
works because o instanceof Duration is true when o is an instance of CountedDuration

CSE 331 Summer 2021

16 of 43

NanoDuration is (probably) not fine

If we don’t override equals in NanoDuration, then objects with different nano fields will be equal

Using what we have learned:

@Override

public boolean equals(Object o) {

if (!(o instanceof NanoDuration))

return false;

NanoDuration nd = (NanoDuration) o;

return super.equals(nd) && nano == nd.nano;

}

But we have violated the equals contract

Hint: Compare a Duration and a NanoDuration

CSE 331 Summer 2021

17 of 43

The symmetry bug

public boolean equals(Object o) {

if (!(o instanceof NanoDuration))

return false;

NanoDuration nd = (NanoDuration) o;

return super.equals(nd) && nano == nd.nano;

}

This is not symmetric!

Duration d1 = new NanoDuration(5, 10, 15);

Duration d2 = new Duration(5, 10);

d1.equals(d2);

d2.equals(d1);

CSE 331 Summer 2021

// false

// true

18 of 43

Fixing symmetry

This version restores symmetry by using Duration’s equals if the argument is a Duration (and not a NanoDuration)

public boolean equals(Object o) {

if (!(o instanceof Duration))

return false;

// if o is a normal Duration, compare without nano if (!(o instanceof NanoDuration))

return super.equals(o);

NanoDuration nd = (NanoDuration) o;

return super.equals(nd) && nano == nd.nano;

}

Alas, this still violates the equals contract

Transitivity…

CSE 331 Summer 2021

19 of 43

The transitivity bug

CSE 331 Summer 2021

Duration d1 = new NanoDuration(1, 2, 3);

Duration d2 = new Duration(1, 2);

Duration d3 = new NanoDuration(1, 2, 4);

d1.equals(d2);

d2.equals(d3);

d1.equals(d3);

NanoDuration

min

sec

nano

Duration

min

sec

NanoDuration

min

sec

nano

20 of 43

The transitivity bug

CSE 331 Summer 2021

Duration d1 = new NanoDuration(1, 2, 3);

Duration d2 = new Duration(1, 2);

Duration d3 = new NanoDuration(1, 2, 4);

d1.equals(d2);

d2.equals(d3);

d1.equals(d3);

NanoDuration

min

sec

nano

Duration

min

sec

NanoDuration

min

sec

nano

// true

21 of 43

The transitivity bug

CSE 331 Summer 2021

Duration d1 = new NanoDuration(1, 2, 3);

Duration d2 = new Duration(1, 2);

Duration d3 = new NanoDuration(1, 2, 4);

d1.equals(d2);

d2.equals(d3);

d1.equals(d3);

NanoDuration

min

sec

nano

Duration

min

sec

NanoDuration

min

sec

nano

// true

22 of 43

The transitivity bug

CSE 331 Summer 2021

Duration d1 = new NanoDuration(1, 2, 3);

Duration d2 = new Duration(1, 2);

Duration d3 = new NanoDuration(1, 2, 4);

d1.equals(d2);

d2.equals(d3);

d1.equals(d3);

NanoDuration

min

sec

nano

Duration

min

sec

NanoDuration

min

sec

nano

// true

// false!

23 of 43

No perfect solution

Effective Java says not to (re)override equals like this

(unless superclass is non-instantiable)
generally good advice
but there is one way to satisfy equals contract (see below)

Two less-than-perfect approaches on next two slides:

Don’t make NanoDuration a subclass of Duration

fact that equals should be different is a hint it’s not a subtype

Change Duration’s equals so only Duration objects that are not (proper) subclasses of Duration are equal

CSE 331 Summer 2021

24 of 43

Option 1: avoid subclassing

Choose composition over subclassing (Effective Java)

often good advice in general (we’ll discuss more later on)
many programmers overuse subclassing

public class NanoDuration {

private final Duration duration;

private final int nano;

…

}

Solves some problems:

clients can choose which type of equality to use

Introduces others:

can’t use NanoDurations where Durations are

expected (since it is not a subtype)

CSE 331 Summer 2021

25 of 43

Option 2: the getClass trick

Check if o is a Duration and not a subtype:

@Overrides�public boolean equals(Object o) { // in Duration

if (o == null)

return false;

if (!o.getClass().equals(getClass()))

return false;

Duration d = (Duration) o;

return d.min == min && d.sec == sec;

}

But this breaks CountedDuration!

subclasses do not “act like” instances of superclass because behavior of equals changes with subclasses
generally considered wrong to “break” subtyping like this

CSE 331 Summer 2021

26 of 43

Subclassing summary

Subtypes should be useable wherever the type is used

Liskov substitution principle

Unresolvable tension between

what we want for equality: treat subclasses differently
what we want for subtyping: treat subclasses the same

No perfect solution for all cases...
Choose whether you want subtyping or not

in former case, don’t override equals (make it final)
in latter case, can still use composition instead

this matches the advice in Effective Java and from us (later)

almost always best to avoid getClass trick

CSE 331 Summer 2021

27 of 43

DESIGNING FOR INHERITANCE

28 of 43

Inheritance can break encapsulation

public class InstrumentedHashSet<E>

extends HashSet<E> {

private int addCount = 0; // count # insertions

public InstrumentedHashSet(Collection<? extends E> c){

super(c);

}

public boolean add(E o) {

addCount++;

return super.add(o);

}

public boolean addAll(Collection<? extends E> c) {

addCount += c.size();

return super.addAll(c);

}

public int getAddCount() { return addCount; }

}

CSE 331 Summer 2021

29 of 43

Solutions

Change spec of HashSet

indicate all self-calls
less flexibility for implementers

Avoid spec ambiguity by avoiding self-calls

“re-implement” methods such as addAll

more work

use composition not inheritance

no longer a subtype (unless an interface is handy)
bad for equality tests, callbacks, etc.

CSE 331 Summer 2021

30 of 43

Dependence on implementation

What does this code print?

InstrumentedHashSet<String> s =

new InstrumentedHashSet<String>();

System.out.println(s.getAddCount());

s.addAll(Arrays.asList("CSE", "331"));

System.out.println(s.getAddCount());

Answer depends on implementation of addAll in HashSet

different implementations may behave differently!
if HashSet’s addAll calls add, then double-counting

AbstractCollection’s addAll specification:

“adds all elements in the specified collection to this collection.”
does not specify whether it calls add

Lesson: subclassing typically requires designing for inheritance

self-calls is not the only example… (more in future lectures)

31 of 43

Dependence on implementation

What does this code print?

InstrumentedHashSet<String> s =

new InstrumentedHashSet<String>();

System.out.println(s.getAddCount());

s.addAll(Arrays.asList("CSE", "331"));

System.out.println(s.getAddCount());

Answer depends on implementation of addAll in HashSet

different implementations may behave differently!
if HashSet’s addAll calls add, then double-counting

AbstractCollection’s addAll specification:

“adds all elements in the specified collection to this collection.”
does not specify whether it calls add

Lesson: subclassing typically requires designing for inheritance

self-calls is not the only example… (more in future lectures)

// 0

32 of 43

Dependence on implementation

What does this code print?

InstrumentedHashSet<String> s =

new InstrumentedHashSet<String>();

System.out.println(s.getAddCount());

s.addAll(Arrays.asList("CSE", "331"));

System.out.println(s.getAddCount());

Answer depends on implementation of addAll in HashSet

different implementations may behave differently!
if HashSet’s addAll calls add, then double-counting

AbstractCollection’s addAll specification:

“adds all elements in the specified collection to this collection.”
does not specify whether it calls add

Lesson: subclassing typically requires designing for inheritance

self-calls is not the only example… (more in future lectures)

// 0

// 4?!

33 of 43

Solution: composition

public class InstrumentedHashSet<E> {

private final HashSet<E> s = new HashSet<E>();

private int addCount = 0;

public InstrumentedHashSet(Collection<? extends E> c){

this.addAll(c);

}

public boolean add(E o) {

addCount++; return s.add(o);

}

public boolean addAll(Collection<? extends E> c) {

addCount += c.size();

return s.addAll(c);

}

public int getAddCount() { return addCount; }

// ... and every other method specified by HashSet<E>

}

CSE 331 Summer 2021

34 of 43

Solution: composition

public class InstrumentedHashSet<E> {

private final HashSet<E> s = new HashSet<E>();

private int addCount = 0;

public InstrumentedHashSet(Collection<? extends E> c){

this.addAll(c);

}

public boolean add(E o) {

addCount++; return s.add(o);

}

public boolean addAll(Collection<? extends E> c) {

addCount += c.size();

return s.addAll(c);

}

public int getAddCount() { return addCount; }

// ... and every other method specified by HashSet<E>

}

CSE 331 Summer 2021

Delegate

35 of 43

Solution: composition

public class InstrumentedHashSet<E> {

private final HashSet<E> s = new HashSet<E>();

private int addCount = 0;

public InstrumentedHashSet(Collection<? extends E> c){

this.addAll(c);

}

public boolean add(E o) {

addCount++; return s.add(o);

}

public boolean addAll(Collection<? extends E> c) {

addCount += c.size();

return s.addAll(c);

}

public int getAddCount() { return addCount; }

// ... and every other method specified by HashSet<E>

}

CSE 331 Summer 2021

The implementation no longer matters

Delegate

36 of 43

Composition (wrappers, delegation)

Implementation reuse without inheritance

Easy to reason about. Self-calls are irrelevant

Example of a “wrapper” class

Works around badly-designed / badly-specified classes

Disadvantages (may be worthwhile price to pay):

does not preserve subtyping
sometimes tedious to write
may be hard to apply to equality tests, callbacks, etc.

(although we already saw equals is hard for subclasses)

CSE 331 Summer 2021

37 of 43

Composition does not preserve subtyping

InstrumentedHashSet is not a HashSet anymore

so can't easily substitute it

It may be a true subtype of HashSet

but Java doesn't know that!
Java requires declared relationships
not enough just to meet specification

Interfaces to the rescue

can declare that we implement interface Set
if such an interface exists

CSE 331 Summer 2021

38 of 43

Interfaces reintroduce Java subtyping

public class InstrumentedHashSet<E> implements Set<E> {

private final Set<E> s = new HashSet<E>();

private int addCount = 0;

public InstrumentedHashSet(Collection<? extends E> c){

this.addAll(c);

}

public boolean add(E o) {

addCount++;

return s.add(o);

}

public boolean addAll(Collection<? extends E> c) {

addCount += c.size();

return s.addAll(c);

}

public int getAddCount() { return addCount; }

// ... and every other method specified by Set<E>

}

CSE 331 Summer 2021

39 of 43

Interfaces reintroduce Java subtyping

public class InstrumentedHashSet<E> implements Set<E> {

private final Set<E> s = new HashSet<E>();

private int addCount = 0;

public InstrumentedHashSet(Collection<? extends E> c){

this.addAll(c);

}

public boolean add(E o) {

addCount++;

return s.add(o);

}

public boolean addAll(Collection<? extends E> c) {

addCount += c.size();

return s.addAll(c);

}

public int getAddCount() { return addCount; }

// ... and every other method specified by Set<E>

}

CSE 331 Summer 2021

normal Java style

40 of 43

Interfaces and abstract classes

Provide interfaces for your functionality

client code to interfaces rather than concrete classes
allows different implementations later
facilitates composition, wrapper classes

basis of lots of useful, clever techniques
we'll see more of these later

Consider also providing helper/template abstract classes

makes writing new implementations much easier
not necessary to use them to implement an interface, so retain freedom to create radically different implementations

CSE 331 Summer 2021

41 of 43

Java library interface/class example

// root interface of collection hierarchy

interface Collection<E>

// skeletal implementation of Collection<E>

abstract class AbstractCollection<E>

implements Collection<E>

// type of all ordered collections

interface List<E> extends Collection<E>

// skeletal implementation of List<E>

abstract class AbstractList<E>

extends AbstractCollection<E>

implements List<E>

// an old friend...

class ArrayList<E> extends AbstractList<E>

CSE 331 Summer 2021

42 of 43

Why interfaces instead of classes?

Java design decisions:

a class has exactly one superclass
a class may implement multiple interfaces
an interface may extend multiple interfaces

Observation:

multiple superclasses are difficult to use and to implement
multiple interfaces, single superclass gets most of the benefit

CSE 331 Summer 2021

43 of 43

Pluses and minuses of inheritance

Inheritance is a powerful way to achieve code reuse

Inheritance can break encapsulation

a subclass may need to depend on unspecified details of the implementation of its superclass

e.g., pattern of self-calls

subclass may need to evolve in tandem with superclass

okay when implementation of both is under control of the same programmer

this is tricky to get right and is a source of subtle bugs

Effective Java:

either design for inheritance or else prohibit it
favor composition (and interfaces) to inheritance

CSE 331 Summer 2021