Subtype polymorphism

Subtype polymorphism

• Subtype polymorphism

• Subtyping vs. subclassing

• Liskov Substitution Principle (LSP)

• Function subtyping

• Java subtyping

• Composition: an alternative to inheritance

Subtype polymorphism – the ability to use a subclass where a superclass is expected

• Subtype polymorphism – the ability to use a subclass where a superclass is expected

• Thus, dynamic method binding
• class A { void m() { … } }
• class B extends A { void m() { … } }
• class C extends A { void m() { … } }
• Client: A a; … a.m(); // Call a.m() can bind to any of A.m, B.m or C.m at runtime!

• Subtype polymorphism is the essential feature of object-oriented languages

• Java subtype: B extends A or B implements I
• A Java subtype is not necessarily a true subtype!

Example: Application draws shapes on screen

• Example: Application draws shapes on screen

• Possible solution in C:

• enum ShapeType { circle, square };

• struct Shape { ShapeType t };

• struct Circle

• { ShapeType t; double radius; Point center; };

• struct Square

• { ShapeType t; double side; Point topleft; };

Enables extensibility and reuse

• Enables extensibility and reuse

• In our example, we can extend Shape hierarchy with no modification to the client of hierarchy, DrawAll
• Thus, we can reuse Shape and DrawAll

• Subtype polymorphism enables the Open/closed principle

• Software entities (classes, modules) should be open for extension but closed for modification
• Credited to Bertrand Meyer

“Science” of software design teaches Design Patterns

• “Science” of software design teaches Design Patterns

• Design patterns promote design for extensibility and reuse

• Nearly all design patterns make use of subtype polymorphism

Subtype polymorphism

• Subtype polymorphism

• Subtyping vs. subclassing

• Liskov Substitution Principle (LSP)

• Function subtyping

• Java subtyping

• Composition: an alternative to inheritance

Subtyping, conceptually

• Subtyping, conceptually

• B is subtype of A means every B is an A
• In other words, a B object can be substituted where an A object is expected

• The notion of true subtyping connects subtyping in the real world with Java subtyping

Subset subtypes

• Subset subtypes

• int is a subtype of real
• range [0..10] is a subtype of range [-10…10]

• Other subtypes

• Every book is a library item
• Every DVD is a library item
• Every triangle is a shape
• Etc.

Subtypes are substitutable for supertypes

• Subtypes are substitutable for supertypes

• Instances of subtypes won’t surprise client by requiring “more” than the supertype
• Instances of subtypes won’t surprise client by returning “less” than its supertype

• Java subtyping is realized through subclassing

• Java subtype is not the same as true subtype!

Subtyping and substitutability --- specification notions

• Subtyping and substitutability --- specification notions

• B is a subtype of A if and only if a B object can be substituted where an A object is expected, in any context

• Subclassing and inheritance --- implementation notions

• B extends A, or B implements A
• B is a Java subtype of A, but not necessarily a true subtype of A!

We say that (class) B is a true subtype of A if B has a stronger specification than A

• We say that (class) B is a true subtype of A if B has a stronger specification than A

• Heed when designing inheritance hierarchies!

• Java subtypes that are not true subtypes are confusing and dangerous

class Product {

• class Product {

• private String title;

• private String description;

• private float price;

• public float getPrice() { return price; }

• public float getTax() {

• return getPrice()*0.08f;

• }

• }

• … and we need a class for Products that are on sale

class SaleProduct {

• class SaleProduct {

• private String title;

• private String description;

• private float price;

• private float factor; // extends Product

• public float getPrice() {

• return price*factor; } // extends Product

• public float getTax() {

• return getPrice()*0.08f;

• }

• }

What’s a better way to add this functionality?

• What’s a better way to add this functionality?

Don’t repeat unchanged fields and methods

• Don’t repeat unchanged fields and methods

• Simpler maintenance: fix bugs once
• Differences are clear (not buried under mass of similarity!)
• Modularity: can ignore private fields and methods of superclass

• Can substitute new implementations where old one is expected (the benefit of subtype polymorphism)

• Another example: Timestamp extends Date

Poor planning leads to muddled inheritance hierarchies. Requires careful planning

• Poor planning leads to muddled inheritance hierarchies. Requires careful planning

• If a class is not a true subtype of its superclass, it can surprise client

• If class depends on implementation details of superclass, changes in superclass can break subclass. “Fragile base class problem”

Thus, class Square extends Rectangle { … }

• Thus, class Square extends Rectangle { … }

• But is a Square a true subtype of Rectangle? In other words, is Square substitutable for Rectangle in client code?

• class Rectangle {

• // effects: thispost.width=w,thispost.height=h

• public void setSize(int w, int h);

• // returns: area of rectangle

• public int area();

• }

class Square extends Rectangle { … }

• class Square extends Rectangle { … }

• // requires: w = h

• // effects: thispost.width=w,thispost.height=h

• Choice 1: public void setSize(int w, int h);

• // effects: thispost.width=w,thispost.height=w

• Choice 2: public void setSize(int w, int h);

• // effects: thispost.width=s,thispost.height=s

• Choice 3: public void setSize(int s);

• // effects: thispost.width=w,thispost.height=h

• // throws: BadSizeException if w != h

• Choice 4: public void setSize(int w, int h);

Choice 1 is not good

• Choice 1 is not good

• It requires more! Clients of Rectangle are justified to have Rectangle r; … r.setSize(5,4)
• In formal terms: spec of Square’s setSize is not stronger than spec of Rectangle’s setSize
• Because the precondition of Rectangle’s setSize does not imply precondition of Square’s setSize
• Thus, a Square can’t be substituted for a Rectangle

Choice 4?

• Choice 4?

• It throws an exception that clients of Rectangle are not expecting and not handling
• Thus, a Square can’t be substituted for a Rectangle

• Choice 3?

• Clients of Rectangle can write … r.setSize(5,4). Square works with r.setSize(5)

• Choice 2?

• Client: Rectangle r; … r.setSize(5,4); assert(r.area()==20)
• Again, Square surprises client with behavior that is different from Rectangle’s

Square is not a true subtype of Rectangle

• Square is not a true subtype of Rectangle

• Rectangles are expected to have height and width that can change independently
• Squares violate that expectation. Surprise clients

• Is Rectangle a true subtype of Square?

• No. Squares are expected to have equal height and width. Rectangles violate this expectation

• One solution: make them unrelated

class BallContainer {

• class BallContainer {

• // modifies: this

• // effects: adds b to this container if b is not

• // already in

• // returns: true if b is added, false otherwise

• public boolean add(Ball b);

• …

• }

• class Box extends BallContainer { // good idea?

• // modifies: this

• // effects: adds b to this Box if b is not

• // already in and this Box is not full

• // returns: true if b is added, false otherwise

• public boolean add(Ball b);

• …

• }

Due to Barbara Liskov, Turing Award 2008

• Due to Barbara Liskov, Turing Award 2008

• LSP: A subclass should be substitutable for superclass. I.e., every subclass should be a true subtype of its superclass

• Ensure that B is a true subtype of A by reasoning at the specification level

• B should not remove methods from A
• For each B.m that “substitutes” A.m, B.m’s spec is stronger than A.m’s spec
• Client: A a; … a.m(int x,int y); Call a.m can bind to B’s m. B’s m should not surprise client

class Rectangle {

• class Rectangle {

• // effects: thispost.width=w,thispost.height=h

• public void setSize(int w, int h);

• }

• class Square extends Rectangle { …

• // requires: w = h

• // effects: thispost.width=w,thispost.height=h

• public void setSize(int w, int h);

• }

Java subtypes (realized with extends, implements) must be true subtypes

• Java subtypes (realized with extends, implements) must be true subtypes

• Java subtypes that are not true subtypes are dangerous and confusing

• When B is a Java subtype of A, ensure

• B, does not remove methods from A
• A substituting method B.m has stronger spec than method A.m which it substitutes
• Guarantees substitutability