Introduction to Object Oriented Programming, 3rd Ed

Timothy A. Budd

Chapter 10 Subclasses and Subtypes

Outline

Other Material

A printer friendly version of all slides

Intro OOP, Chapter 10, Outline

Roadmap

In this chapter we will explore the relationships between the two concepts of subclass and subtype.

To assert that one class is a subclass of another is to simply say it was built using inheritance. It is a statement concerning how it was constructed.
To assert that one class is a subtype of another is to say that it preserves the purpose of the original. It is a statement concerning meaning.

Intro OOP, Chapter 10, Slide 01

Subtype, Subclass and Substitution

The distinction between subtype and subclass is important because of their relationship to substitution.

Recall the argument that asserted a child class has the same behavior as the parent, and thus a variable declared as the parent class should in fact be allowed to hold a value generated from a child class.

But does this argument always hold true?

Intro OOP, Chapter 10, Slide 02

What is a type?

What do we mean when we use the term type in describing a programming language?

A set of values. (The type int, for example, describes -2147483648 to 2147483647)
A set of operations. (We can do arithmetic on ints, not on booleans).
A set of properties. (If we divide 8 by 5 we are not surprized when the result is 1, and not 1.6).

What about when we consider classes (or interfaces) as a system for defining types?

Intro OOP, Chapter 10, Slide 03

The Problem of Defining Types

Consider how we might define a Stack ADT:

interface Stack {
	public void push (Object value);
	public Object top ();
	public void pop ();
}

Notice how the interface itself says nothing about the LIFO property, which is the key defining feature of a stack. Is the following a stack?

class NonStack implements Stack {
	public void push (Object value) { v = value; }
	public Object top () { return v; }
	public void pop () { v = null; }

	private Object v = null;
}

Intro OOP, Chapter 10, Slide 04

The Definition of Subtype

So now we can better understand the concept of a subtype.

A subtype preserves the meaning (purpose, or intent) of the parent.

Problem, meaning is extremely difficult to define. Think about how to define the LIFO characteristics of the stack.

Intro OOP, Chapter 10, Slide 05

Subclasses are not Necessarily Subtypes

It is easy to create a subclass that is not a subtype -- think of NonStack.

It is also possible to create subtypes that are not subclasses. Think of Array in Smalltalk. This class is characterized by the following interface:

	at: input put: value
	at: int
	size

But class Dictionary will also support the same interface, and perform similar actions -- but Dictionary is not a subclass of Array.

Intro OOP, Chapter 10, Slide 06

The Substitution Paradox

There is a curious paradox that lies at the heart of most strongly typed object-oriented programming languages.

Substitution is permitted, based on subclasses. That is, a variable declared as the parent type is allowed to hold a value derived from a child type.
Yet from a semantic point of view, substitution only makes sense if the expression value is a subtype of the target variable.

If substitution only makes sense for subtypes and not for all subclasses, why do programming languages based the validity of assignment on subclasses?

Intro OOP, Chapter 10, Slide 07

The Undecidability of the Subtype Relationship

It is trivial to determine if one class is a subclass of another.

It is extremely difficult to define meaning (think of the Stack ADT), and even if you can it is almost always impossible to determine if one class preserves the meaning of another.

One of the classic corollaries of the halting problem is that there is no procedure that can determine, in general, if two programs have equivalent behavior.

Intro OOP, Chapter 10, Slide 08

Is This a Problem?

What does it take to create a subclass that is not a subtype?

The new class must override at least one method from the parent
It must preserve the type signatures
But it must violate some important property of the parent

Is this common? Not likely. But it shows you where to look for problem areas.

Intro OOP, Chapter 10, Slide 09

Chapter Summary

To say a class is a subclass of another simply asserts that is was built using inheritance.
By itself, the subclass relationship says nothing about the behavior of the child in relation to the parent.
The term subtype is used to describe a class that matches the behavior of another class.
It is easy to build subclasses that are not subtypes. It is possible (although not as easy) to build subtypes that are not subclasses.