Transcript Subtyping and Inheritance - University of Virginia, Department of

Lecture 12:
Subtyping and
Inheritance
CS201j: Engineering Software
University of Virginia
Computer Science
David Evans
http://www.cs.virginia.edu/evans
Menu
• Subtyping
• Inheritance
• What is Object-Oriented Programming
9 October 2003
CS 201J Fall 2003
2
Subtyping
Cell
ConwayLifeCell is a subtype of Cell
Cell is a supertype of ConwayLifeCell
ConwayLifeCell ≤ Cell
ConwayLifeCell
9 October 2003
CS 201J Fall 2003
3
Inheritance
• To implement a subtype, it is often useful
to use the implementation of its supertype
• This is also called “subclassing”
• In Java:
class B extends A
B is a subtype of A
B inherits from A
class C implements F
C is a subtype of F
9 October 2003
CS 201J Fall 2003
both subtyping and inheritance
just subtyping
4
Inheritance and Subtyping
public class ExtremeLifeCell extends Cell {
public CellState getNextState ()
// EFFECTS: Returns the next state for this cell.
// The next state will be alive if this cell or any of its neighbors
//
is currently alive.
{
if (countAliveNeighbors () > 0) {
return CellState.createAlive ();
} else {
ExtremeLifeCell is a subtype of Cell
return getState ();
- anywhere a Cell is expected, we can
}
use an ExtremeLifeCell
}
ExtremeLifeCell inherits from Cell
}
- the rep of an ExtremeLifeCell includes
the rep of Cell
- all public methods and constructors
of Cell are also available for ExtremeLifeCell
9 October 2003
CS 201J Fall 2003
5
Method Dispatch
• B is a subtype of A
• If both A and B have a method display
which method should be called?
A a = new A ();
B b = new B ();
a.display ();
b.display ();
a = b;
a.display ()
9 October 2003
Calls class A’s display method
Calls class B’s display method
Calls class B’s display method
CS 201J Fall 2003
6
Dynamic Dispatch
• Search for the method up the type
hierarchy, starting from the actual
(dynamic) type of the object
apparent type
A
A a = new A ();
B b = new B ();
a
actual type
B
b
apparent type
a.display ();
b.display ();
actual type
9 October 2003
CS 201J Fall 2003
7
Dynamic Dispatch
• Search for the method up the type
hierarchy, starting from the actual
(dynamic) type of the object
apparent type
A
A a = new A ();
B b = new B ();
a
actual type
B
b
apparent type
Now: apparent type of a is A,
actual type of a is B
actual type
9 October 2003
a.display ();
b.display ();
a = b;
CS 201J Fall 2003
8
public class Grid {
/*@non_null@*/ Cell [][] cells;
…
public void step ()
// MODIFIES: this
// EFFECTS: Executes one step for each cell in the grid.
{
CellState [][] nextStates = new CellState [rows][columns];
// Since we need to update all cells synchronously, we first calculate the next
// state for each cell, and store it in a temporary array. Then, we update all cells.
for (int i = 0; i < rows; i++) {
for (int j = 0; j < columns; j++) {
nextStates [i][j] = cells[i][j].getNextState (); } }
}
for (int i = 0; i < rows; i++) {
for (int j = 0; j < columns; j++) {
cells[i][j].setState (nextStates[i][j]); } }
}}
9 October 2003
CS 201J Fall 2003
apparent type: Cell
actual type: any subtype of Cell
(could be ConwayLifeCell)
9
Apparent and Actual Types
• Apparent types are associated with
declarations: they never change
• Actual types are associated with object:
they are always a subtype of the apparent
type
• Compiler does type checking using
apparent type
• Virtual Machine does method dispatch
using actual type
9 October 2003
CS 201J Fall 2003
10
Downcasting
java.util.Vector:
public Object elementAt (int i);
public class StringSet {
Vector elements;
public String choose () {
String s = elements.elementAt (0);
String s = (String) elements.elementAt (0);
Casting changes the apparent type.
return s;
}
9 October 2003
The VM must check that the actual type
is a subtype of the cast type.
CS 201J Fall 2003
11
Downcasting
java.util.Vector:
public Object elementAt (int i);
public class StringSet {
Vector elements;
public String choose () {
String s = elements.elementAt (0);
String s = (String) elements.elementAt (0);
Casting changes the apparent type.
return s;
}
9 October 2003
The VM must check that the actual type
is a subtype of the cast type.
CS 201J Fall 2003
12
A Type Hierarchy
Shape
Quadrangle
Triangle
Equilateral
Parallelogram
Rhombus
Rectangle
EquilateralTriangle
What are the supertypes of Square?
Square
9 October 2003
What are the subtypes of Parallelogram?
CS 201J Fall 2003
13
A Class Hierarchy
Shape
Quadrangle
Triangle
Equilateral
Parallelogram
Rhombus
Rectangle
EquilateralTriangle
Square
9 October 2003
CS 201J Fall 2003
14
Reusing Implementations
• Shapes should have a setColor method
• Change Shape, Quadrangle,
Parallelogram, Triangle, Equilateral,
EquilateralTriangle, Rhombus, Rectangle,
Square, etc.
• Change Shape others inherit new attribute
and method automatically
9 October 2003
CS 201J Fall 2003
15
Add isEquilateral method
class Shape {
public bool isEquilateral () {
return false; }
}
class Equilateral {
public bool isEquilateral () {
return true; }
}
9 October 2003
CS 201J Fall 2003
16
Is a Rhombus equilateral?
isEquilateral () { return false; }
Shape
isEquilateral () {
Equilateral
return true;
}
Quadrangle
Parallelogram
Inheritance can be
tricky!
Rhombus
isEquilateral?
9 October 2003
CS 201J Fall 2003
17
Solutions
• Java
– Allow multiple supertypes using interfaces,
but only one implementation
– Pro: Safe and Simple, Con: Limits Reuse
• C++
– Allow it, let programmers shoot themselves if
they want
• Eiffel
– Explicit renaming or hiding (error if not done)
9 October 2003
CS 201J Fall 2003
18
Java’s Solution: Interfaces
• Define a type with no implementation
• Classes can implement many interfaces:
class B extends A implements I1, I2, I3 {
…
}
means B is a subtype of A, I1, I2, and I3
B inherits the implementation of A
9 October 2003
CS 201J Fall 2003
19
Example Interface
public interface Comparable {
int compareTo (Object o) {
// EFFECTS: Compares this object with the specified
// object for order. Returns a negative integer, zero,
// or a positive integer as this object is less than,
// equal to, or greater than the specified object.
}
9 October 2003
CS 201J Fall 2003
20
Java’s Sorting Routines
public class java.util.Arrays {
public static void sort (Object[] a, int fromIndex,
int toIndex)
// REQUIRES: All elements in a between
//
fromIndex and toIndex must
//
implement the Comparable interface.
// EFFECTS: Sorts the elements of a between
//
fromIndex and toIndex into ascending
//
order, according to the natural ordering of
//
its elements (defined by compareTo).
9 October 2003
CS 201J Fall 2003
21
PS3 sortonce implementation
public class WordTally {
private TallyRecord [] entries;
private boolean isSorted;
private /*@spec_public@*/ int numEntries;
public String getRankedWord(int n) {
if (!isSorted) {
java.util.Arrays.sort (entries, 0, numEntries);
isSorted = true;
}
}
if (n <= numberOfWords()) {
return entries[n-1].word;
} else {
return null;
}
9 October 2003
CS 201J Fall 2003
22
Implementing Comparable
class TallyRecord implements Comparable {
/*@non_null@*/ String word;
int tally;
//@invariant tally > 0;
public TallyRecord(/*@non_null@*/ String p_word, int p_tally)
//@requires p_tally > 0;
{ word = p_word; tally = p_tally; }
}
public int compareTo (Object o) throws RuntimeException {
if (o instanceof TallyRecord) {
TallyRecord t2 = (TallyRecord) o;
if (tally > t2.tally) { return -1; }
else if (tally == t2.tally) { return word.compareTo (t2.word); }
else { return 1; }
} else {
throw new RuntimeException ("Comparison to non-TallyRecord: " + o);
}
9 October 2003
CS 201J Fall 2003
23
ObjectOriented
Programming
9 October 2003
CS 201J Fall 2003
24
What is an Object?
• Packaging state and procedures
– state: the rep
• What a thing is
– procedures: methods and constructors
• What you can do with it
9 October 2003
CS 201J Fall 2003
25
What is Object-Oriented
Programming?
9 October 2003
CS 201J Fall 2003
26
Bjarne Stroustrup’s Answer
“Object-oriented programming is programming
with inheritance. Data abstraction is
programming using user-defined types. With few
exceptions, object-oriented programming can and
ought to be a superset of data abstraction. These
techniques need proper support to be effective.
Data abstraction primarily needs support in the
form of language features and object-oriented
programming needs further support from a
programming environment. To be general
purpose, a language supporting data abstraction
or object-oriented programming must enable
effective use of traditional hardware.”
9 October 2003
CS 201J Fall 2003
27
“I invented the term Object-Oriented
and I can tell you I did not have C++
in mind.”
Alan Kay
9 October 2003
CS 201J Fall 2003
28
Programming Language History
• Before 1954: twidling knobs, machine
code, assembly code
• FORTRAN (John Backus, UVa dropout,
1954) – Formula Translation
• Algol (Peter Naur, Alan Perlis, et. al.,
1958-1960)
– Most influential programming language
– Many of the things Algol did first (types, while,
blocks) are in Java
9 October 2003
CS 201J Fall 2003
29
Programming Language History
• Simula (Dahl and Nygaard, 1962-7)
– First language with subtyping and inheritance
• CLU (Liskov et. al., 1970s)
– First language with good support for data
abstraction (but no subtyping or inheritance)
• Smalltalk (Kay et. al., 1970s)
– First successful language and programming
system to support subtyping and inheritance
9 October 2003
CS 201J Fall 2003
30
Object-Oriented Programming
• Object-Oriented Programming is a state of mind
where you program by thinking about objects
• It is difficult to reach that state of mind if your
language doesn’t have:
– Mechanisms for packaging state and procedures
• Java has class
– Subtyping
• Java has extends (subtype and subclass) and implements
(subtype)
• Other things can help: dynamic dispatch,
implementation inheritance, automatic memory
management, mixins, good Indian food, Krispy
Kremes, etc.
9 October 2003
CS 201J Fall 2003
31
Who was the first
object-oriented programmer?
9 October 2003
CS 201J Fall 2003
32
By the word operation, we mean any process which
alters the mutual relation of two or more things, be this
relation of what kind it may. This is the most general
definition, and would include all subjects in the universe.
Again, it might act upon other things besides number,
were objects found whose mutual fundamental relations
could be expressed by those of the abstract science of
operations, and which should be also susceptible of
adaptations to the action of the operating notation and
mechanism of the engine... Supposing, for instance,
that the fundamental relations of pitched sounds in the
science of harmony and of musical composition were
susceptible of such expression and adaptations, the
engine might compose elaborate and scientific pieces of
music of any degree of complexity or extent.
Ada, Countess of Lovelace, around 1830
9 October 2003
CS 201J Fall 2003
33
Charge
• PS4 due Thursday, Oct 16
• Exam 1 out Thursday, Oct 16
• Exam review in section tomorrow
– Bring your questions
• Next week:
– When is it safe to say B is a subtype of A?
9 October 2003
CS 201J Fall 2003
34