Implements vs. Extends
On Monday, a student asked after class ¡°how do you know whether to use implements or extends?¡±
Somehow I didn¡¯t explicitly mention the difference between ¡°implements¡± and ¡°extends¡± during lecture.
¡ñ You must use ¡°implements¡± if the hyperym is an interface and the hyponym is a class (e.g. hypernym List, hyponym AList).
¡ñ You must use ¡°extends¡± in all other cases.
There¡¯s no choice that you have to make, the Java designers just picked a different keyword for the two cases.
datastructur.es
Announcements
Reminder drop deadline is today.
¡ñ If you are not done with project 1A, you are in deep danger.
Come to lab this week.
¡ñ Requires checkoff (last one until week 14).
datastructur.es
CS61B
Lecture 10: Subtype Polymorphism vs. HoFs
¡ñ Dynamic Method Selection Puzzle
¡ñ Subtype Polymorphism vs. Explicit HoFs
¡ñ Application 1: Comparables
¡ñ Application 2: Comparators
Dynamic Method Selection Puzzle (Online Only)
A Typing Puzzle
Suppose we have two classes:
¡ñ Dog: Implements bark() method.
¡ñ ShowDog: Extends Dog, overrides bark method. Summarizing is-a relationships, we have:
¡ñ Every ShowDog is-a Dog
¡ñ Every Dog is-an Object.
¡ð All types in Java are a subtype of Object.
Object
bark()
Dog
bark()
ShowDog
datastructur.es
A Typing Puzzle
For each assignment, decide if it causes a compile error.
For each call to bark, decide whether: 1. Dog.bark() is called, 2. ShowDog.bark() is called, or 3. A syntax error results.
The rules:
¡ñ Compiler allows memory box to hold any subtype.
¡ñ Compiler allows calls based on static type.
¡ñ Overridden non-static methods are selected at
run time based on dynamic type.
¡ð Everything else is based on static type,
including overloaded methods. Note: No overloaded methods for problem at left.
datastructur.es
A Typing Puzzle
String s = ¡°35¡±;
Integer x = (Integer) s; // THIS CAST WILL FAIL x.floatValue()
Variable or expression
Showdog¡¯s bark
ShowDog¡¯s bark ShowDog¡¯s bark
o2
sdx
dx
((Dog) o2)
o3
Static Type
Object
ShowDog
Dog
Dog
Object
Dynamic Type
ShowDog
ShowDog
ShowDog
ShowDog
ShowDog
datastructur.es
A Typing Puzzle
String s = ¡°35¡±;
Integer x = (Integer) s; // THIS CAST WILL CAUSE A COMPILE ERROR x.floatValue()
Object
String
Number
Integer
Number x = new Double(3.5);
Integer z = (Integer) x; // this cast is OK at compile time
// Josh what it would do at runtime. It¡¯s a little weird.
datastructur.es
A Typing Puzzle
For each assignment, decide if it causes a compile error.
For each call to bark, decide whether: 1. Dog.bark() is called, 2. ShowDog.bark() is called, or 3. A syntax error results.
Showdog¡¯s bark
ShowDog¡¯s bark
ShowDog: o2 ¡ñ Mortimer
Static Type
Object
ShowDog
Dog Dog
Dynamic Type
ShowDog
ShowDog
ShowDog
Object
ShowDog
Dog
¡ñ Corgi ¡ñ 25
¡ñ 512.2
sdx
dx ((Dog) o2)
ShowDog
datastructur.es
Dog
Static Type vs. Dynamic Type
Every variable in Java has a ¡°compile-time type¡±, a.k.a. ¡°static type¡±. ¡ñ This is the type specified at declaration. Never changes!
Variables also have a ¡°run-time type¡±, a.k.a. ¡°dynamic type¡±.
¡ñ This is the type specified at instantiation (e.g. when using new).
¡ñ Equal to the type of the object being pointed at. lt1
a1 h1
Static Type
LivingThing Squid Animal Fox Fox Fox
Dynamic Type
LivingThing
Animal
Fox
datastructur.es
Static Methods, Variables, and Inheritance
You may find questions on old 61B exams, worksheets, etc. that consider:
¡ñ What if a subclass has variables with the same name as a superclass?
¡ñ What if subclass has a static method with the same signature as a
superclass method?
¡ð For static methods, we do not use the term overriding for this.
These two practices above are called ¡°hiding¡±.
¡ñ It is bad style.
¡ñ There is no good reason to ever do this.
¡ñ The rules for resolving the conflict are a bit confusing to learn.
¡ñ I decided last year to stop teaching it in 61B.
¡ñ But if you want to learn it, see
https://docs.oracle.com/javase/tutorial/java/IandI/override.html
datastructur.es
Subtype Polymorphism
Subtype Polymorphism
The biggest idea of the last couple of lectures: Subtype Polymorphism
¡ñ Polymorphism: ¡°providing a single interface to entities of different types¡±
a.k.a. compile-time type
Consider a variable deque of static type Deque:
¡ñ When you call deque.addFirst(), the actual behavior is based on the
dynamic type.
¡ñ Java automatically selects the right behavior using what is sometimes called
¡°dynamic method selection¡±.
Curious about alternatives to subtype polymorphism? See wiki or CS164.
a.k.a. run-time type
http://www.stroustrup.com/glossary.html#Gpolymorphism
datastructur.es
Subtype Polymorphism vs. Explicit Higher Order Functions
Suppose we want to write a program that prints a string representation of the
larger of two objects.
Sometimes called a ¡°callback¡±.
def print_larger(x, y, compare, stringify): if compare(x, y):
return stringify(x) return stringify(y)
Explicit HoF Approach
def print_larger(x, y): if x.largerThan(y):
return x.str() return y.str()
Subtype Polymorphism Approach
Not to be confused with the amazing Dr. Ernest Kaulbach, who taught my Old English class.
datastructur.es
DIY Comparison
shoutkey.com/TBA
Suppose we want to write a function max() that returns the max of any array, regardless of type.
5
3
1
7
7
Sture 9 lbs
0123
012
Elyse 3 lbs
max
max
Benjamin 15 lbs
datastructur.es
yellkey.com/left
Suppose we want to write a function max() that returns the max of any array,
regardless of type. How many compilation errors are there in the code shown?
A. 0 B. 1 C. 2 D. 3
public static void main(String[] args) {
Dog[] dogs = {new Dog(“Elyse”, 3), new Dog(“Sture”, 9),
new Dog(“Benjamin”, 15)}; Dog maxDog = (Dog) max(dogs);
maxDog.bark();
}
DogLauncher.java
datastruc
public static Object { int maxDex = 0;
for (int i = 0; i < items.length; i += 1) {
max(Object[] items)
if (items[i] > items[maxDex]) { maxDex = i; }}
return items[maxDex];
}
Maximizer.java
tur.es
Writing a General Max Function
and give up on our dream of a one true max function
Objects cannot be compared to other objects with >
¡ñ One (bad) way to fix this: Write a max method in the Dog class.
public static void main(String[] args) {
Dog[] dogs = {new Dog(“Elyse”, 3), new Dog(“Sture”, 9),
new Dog(“Benjamin”, 15)}; Dog maxDog = (Dog) max(dogs);
maxDog.bark();
}
DogLauncher.java
datastruc
public static Object max(Object[] items) { int maxDex = 0;
for (int i = 0; i < items.length; i += 1) {
if (items[i] > items[maxDex]) { maxDex = i; }}
return items[maxDex];
}
Maximizer.java
tur.es
Dog.maxDog
One approach to maximizing a Dog array: Leave it to the Dog class. ¡ñ What is the disadvantage of this?
/** Returns maximum of dogs. */
public static Dog maxDog(Dog[] dogs) {
if (dogs == null || dogs.length == 0) {
return null; } Dog maxDog = dogs[0]; for (Dog d : dogs) {
if (d.size > maxDog.size) { maxDog = d; }}
return maxDog; }
Dog[] dogs = new Dog[]{d1, d2, d3}; Dog largest = Dog.maxDog(dogs);
d
atastructur.es
The Fundamental Problem
Objects cannot be compared to other objects with >
¡ñ How could we fix our Maximizer class using inheritance / HoFs?
public static void main(String[] args) {
Dog[] dogs = {new Dog(“Elyse”, 3), new Dog(“Sture”, 9),
new Dog(“Benjamin”, 15)}; Dog maxDog = (Dog) max(dogs);
maxDog.bark();
}
DogLauncher.java
datastruc
public static Object max(Object[] items) { int maxDex = 0;
for (int i = 0; i < items.length; i += 1) {
if (items[i] > items[maxDex]) { maxDex = i; }}
return items[maxDex];
}
Maximizer.java
tur.es
Solution
interface inheritance says what a class can do, in this case compare.
Create an interface that guarantees a comparison method.
¡ñ Have Dog implement this interface.
¡ñ Write Maximizer class in terms of this interface.
public static OurComparable max(OurComparable[] items) { …
OurComparable
compareTo(Object)
Dog
compareTo(Object)
datastructur.es
The OurComparable Interface
public interface OurComparable { int compareTo(Object obj);
}
Specification, returns:
Could have also been OurComparable. No meaningful difference.
¡ñ Negative number if this is less than obj.
¡ñ 0 if this is equal to object.
¡ñ Positive number if this is greater than obj.
datastructur.es
General Maximization Function Through Inheritance
atastructur.es
public interface OurComparable { int compareTo(Object obj);
}
public class Dog implements OurComparable { public int compareTo(Object obj) {
/** Warning, cast can cause runtime error! */
Dog uddaDog = (Dog) obj;
return this.size – uddaDog.size; } …
public class Maximizer {
public static OurComparable max(OurComparable[] a) { …
}
Dog[] dogs = new Dog[]{d1, d2, d3};
Dog largest = (Dog) Maximizer.max(dogs);
d
General Maximization Function Through Inheritance
Benefits of this approach:
¡ñ No need for array maximization code in every custom type (i.e. no Dog.maxDog(Dog[]) function required).
¡ñ Code that operates on multiple types (mostly) gracefully, e.g.
OurComparable[] objs = getItems(¡°somefile.txt¡±);
return Maximizer.max(objs);
datastructur.es
Interfaces Quiz #1: yellkey.com/baby
public class DogLauncher {
public static void main(String[] args) {
…
Dog[] dogs = new Dog[]{d1, d2, d3}; System.out.println(Maximizer.max(dogs));
} }
Q: If we omit compareTo(), which file will fail to compile?
A. DogLauncher.java B. Dog.java
C. Maximizer.java
D. OurComparable.java
datastructur.es
public class Dog implements OurComparable {
…
public int compareTo(Object o) {
Dog uddaDog = (Dog) o; return this.size
– uddaDog.size;
} …
public class Maximizer { public static OurComparable
…
int cmp = items[i].
compareTo(items[maxDex]);
…
}…
){
max(
OurComparable[] items
Interfaces Quiz #2: yellkey.com/itself
public class DogLauncher {
public static void main(String[] args) {
…
Dog[] dogs = new Dog[]{d1, d2, d3}; System.out.println(Maximizer.max(dogs));
} }
Q: If we omit implements OurComparable, which file will fail to compile?
A. DogLauncher.java B. Dog.java
C. Maximizer.java
D. OurComparable.java
datastructur.es
public class Dog implements OurComparable {
…
public int compareTo(Object o) {
Dog uddaDog = (Dog) o; return this.size
– uddaDog.size;
} …
public class Maximizer { public static OurComparable
…
int cmp = items[i].
compareTo(items[maxDex]);
…
}…
){
max(
OurComparable[] items
Answers to Quiz
Problem 1: Dog will fail to compile because it does not implement all abstract methods required by OurComparable interface. (And I suppose DogLauncher will fail as well since Dog.class doesn¡¯t exist)
Problem 2: DogLauncher will fail, because it tries to pass things that are not OurComparables, and Maximizer expects OurComparables.
datastructur.es
Comparables
The Issues With OurComparable
Two issues:
¡ñ Awkward casting to/from Objects.
¡ñ We made it up.
¡ð No existing classes implement OurComparable (e.g. String, etc).
¡ð No existing classes use OurComparable (e.g. no built-in max function
that uses OurComparable)
atastructur.es
public class Dog implements OurComparable { public int compareTo(Object obj) {
/** Warning, cast can cause runtime error! */
Dog uddaDog = (Dog) obj;
return this.size – uddaDog.size; } …
Dog[] dogs = new Dog[]{d1, d2, d3};
Dog largest = (Dog) Maximizer.max(dogs);
d
The Issues With OurComparable
Two issues:
¡ñ Awkward casting to/from Objects.
¡ñ We made it up.
¡ð No existing classes implement OurComparable (e.g. String, etc).
¡ð No existing classes use OurComparable (e.g. no built-in max function
that uses OurComparable)
The industrial strength approach: Use the built-in Comparable interface.
¡ñ Already defined and used by tons of libraries. Uses generics.
public interface OurComparable {
public int compareTo(Object obj);
}
public interface Comparable
public int compareTo(T obj);
}
datastructur.es
Comparable vs. OurComparable
OurComparable
compareTo(Object)
Comparable
compareTo(Dog)
Dog
compareTo(Object)
Dog
compareTo(Dog)
datastructur.es
Comparable Advantages
¡ñ Lots of built in classes implement Comparable (e.g. String).
¡ñ Lots of libraries use the Comparable interface (e.g. Arrays.sort)
¡ñ Avoids need for casts.
Much better!
Implementing Comparable allows library functions to compare custom types (e.g. finding max).
public class Dog implements Comparable
return this.size – uddaDog.size; }
public class Dog implements OurComparable { public int compareTo(Object obj) {
Dog uddaDog = (Dog) obj;
return this.size – uddaDog.size;
} …
Dog[] dogs = new Dog[]{d1, d2, d3};
Dog largest = Collections.max(Arrays.asList(dogs)); datastructur.es
Comparators
Natural Order
The term ¡°Natural Order¡± is sometimes used to refer to the ordering implied by a Comparable¡¯s compareTo method.
¡ñ Example: Dog objects (as we¡¯ve defined them) have a natural order given by their size.
¡°Doge¡±, size: 5
¡°Grigometh¡±, size: 200 ¡°Clifford¡±, size: 9000
datastructur.es
Natural Order
May wish to order objects in a different way. ¡ñ Example: By Name.
¡°Doge¡±, size: 5
¡°Grigometh¡±, size: 200
¡°Clifford¡±, size: 9000
datastructur.es
Subtype Polymorphism vs. Explicit Higher Order Functions
Suppose we want to write a program that prints a string representation of the larger of two objects according to some specific comparison function.
def print_larger(x, y, compare, stringify): if compare(x, y):
return stringify(x) return stringify(y)
Explicit HoF Approach
def print_larger(T x, T y): if x.largerThan(y):
return x.str() return y.str()
Subtype Polymorphism Approach??
Can simply pass a different compare function.
datastructur.es
Subtype Polymorphism vs. Explicit Higher Order Functions
Suppose we want to write a program that prints a string representation of the larger of two objects according to some specific comparison function.
def print_larger(x, y, compare, stringify): if compare(x, y):
return stringify(x) return stringify(y)
Explicit HoF Approach
def print_larger(T x, T y, comparator
return x.str() return y.str()
Subtype Polymorphism Approach
Can simply pass a different compare function.
datastructur.es
Additional Orders in Java
In some languages, we¡¯d write two comparison functions and simply pass the one we want :
¡ñ sizeCompare() ¡ñ nameCompare()
The standard Java approach: Create sizeComparator and nameComparator classes that implement the Comparator interface.
¡ñ Requires methods that also take Comparator arguments (see project 1B).
public interface Comparator
int compare(T o1, T o2);
}
datastructur.es
Dogs and Comparators
Dog not related by inheritance to any of the classes below.
public interface Comparator
int compare(T o1, T o2);
}
Dog
compare(T, T)
Comparator
compare(Dog,
Dog)
NameComparator
compare(Dog,
Dog)
SizeComparator
datastructur.es
Example: NameComparator
Comparator
d1.bark(); } else {
d3.bark();
Result: If d1 has a name that comes later in the alphabet than d3, d1 barks.
}
da
public class Dog implements Comparable
private int size;
public static class NameComparator implements Comparator
return d1.name.compareTo(d2.name); }
}
… }
tastructur.es
Comparable and Comparator Summary
Interfaces provide us with the ability to make callbacks:
¡ñ Sometimes a function needs the help of another function that might not have been written yet.
¡ð Example: max needs compareTo
¡ð The helping function is sometimes called a ¡°callback¡±.
¡ñ Some languages handle this using explicit function passing.
¡ñ In Java, we do this by wrapping up the needed function in an interface (e.g.
Arrays.sort needs compare which lives inside the comparator
interface)
¡ñ Arrays.sort ¡°calls back¡± whenever it needs a comparison.
¡ð Similar to giving your number to someone if they need information.
¡ð See Project 1B to explore how to write code that uses comparators.
datastructur.es