Announcements
Lab next week:
�Proj1B out Monday, maybe sooner. Study for exam.
Announcements
How to Study for an Exam:
CS61B, 2019
Lecture 8: Interface and Implementation Inheritance
AList and SLList
After adding the insert methods from discussion 3, our AList and SLList classes have the following methods (exact same method signatures for both classes).
public class AList<Item>{
public AList()
public void insert(Item x, int position)
public void addFirst(Item x)
public void addLast(Item i)
public Item getFirst()
public Item getLast()
public Item get(int i)
public int size()
public Item removeLast()
}
public class SLList<Blorp>{
public SLList()
public SLList(Blorp x)
public void insert(Blorp item, int position)
public void addFirst(Blorp x)
public void addLast(Blorp x)
public Blorp getFirst()
public Blorp getLast()
public Blorp get(int i)
public int size()
public Blorp removeLast()
}
Using ALists and SLLists: WordUtils.java
Suppose we’re writing a library to manipulate lists of words. Might want to write a function that finds the longest word from a list of words:
public static String longest(SLList<String> list) {
int maxDex = 0;
for (int i = 0; i < list.size(); i += 1) {
String longestString = list.get(maxDex);
String thisString = list.get(i);
if (thisString.length() > longestString.length()) {
maxDex = i;
}
}
return list.get(maxDex);
}
Observant viewers may note this code is very inefficient! Don’t worry about it.
Using ALists and SLLists: WordUtils.java
If we want longest to be able to handle ALists, what changes do we need to make?
public static String longest(SLList<String> list) {
int maxDex = 0;
for (int i = 0; i < list.size(); i += 1) {
String longestString = list.get(maxDex);
String thisString = list.get(i);
if (thisString.length() > longestString.length()) {
maxDex = i;
}
}
return list.get(maxDex);
}
Using ALists and SLLists: WordUtils.java
If we want longest to be able to handle ALists, what changes do we need to make?
public static String longest(AList<String> list) {
int maxDex = 0;
for (int i = 0; i < list.size(); i += 1) {
String longestString = list.get(maxDex);
String thisString = list.get(i);
if (thisString.length() > longestString.length()) {
maxDex = i;
}
}
return list.get(maxDex);
}
Method Overloading in Java
Java allows multiple methods with same name, but different parameters.
public static String longest(AList<String> list) {
...
}
public static String longest(SLList<String> list) {
...
}
The Downsides
While overloading works, it is a bad idea in the case of longest. Why?
Hypernyms, Hyponyms, and Interface Inheritance
Hypernyms
In natural languages (English, Spanish, Chinese, Tagalog, etc.), we have a concept known as a “hypernym” to deal with this problem.
Washing your poodle:
1. Brush your poodle before a bath. ...
2. Use lukewarm water. ...
3. Talk to your poodle in a calm voice. ...
4. Use poodle shampoo. ...
5. Rinse well. ...
6. Air-dry. ...
7. Reward your poodle.
Washing your malamute:
1. Brush your malamute before a bath. ...
2. Use lukewarm water. ...
3. Talk to your malamute in a calm voice. ...
4. Use malamute shampoo. ...
5. Rinse well. ...
6. Air-dry. ...
7. Reward your malamute.
Washing your dog:
1. Brush your dog before a bath. ...
2. Use lukewarm water. ...
3. Talk to your dog in a calm voice. ...
4. Use dog shampoo. ...
5. Rinse well. ...
6. Air-dry. ...
7. Reward your dog.
Hypernym and Hyponym
We use the word hyponym for the opposite type of relationship.
Hypernyms and hyponyms comprise a hierarchy.
(for fun: see the WordNet project)
animal
omnivore
herbivore
carnivore
feline
canine
dog
Simple Hyponymic Relationships in Java
SLLists and ALists are both clearly some kind of “list”.
Expressing this in Java is a two-step process:
List61B
SLList
AList
Step 1: Defining a List61B
We’ll use the new keyword interface instead of class to define a List61B.
Step 1: Defining a List61B
We’ll use the new keyword interface instead of class to define a List61B.
public interface List61B<Item> {
public void addFirst(Item x);
public void addLast(Item y);
public Item getFirst();
public Item getLast();
public Item removeLast();
public Item get(int i);
public void insert(Item x, int position);
public int size();
}
List61B
Step 2: Implementing the List61B Interface
We’ll now:
public class AList<Item> implements List61B<Item>{
...
public void addLast(Item x) {
...
List61B
SLList
AList
Adjusting WordUtils.java
We can now adjust our longest method to work on either kind of list:
public static String longest(List61B<String> list) {
int maxDex = 0;
for (int i = 0; i < list.size(); i += 1) {
String longestString = list.get(maxDex);
String thisString = list.get(i);
if (thisString.length() > longestString.length()) {
maxDex = i;
}
}
return list.get(maxDex);
}
AList<String> a = new AList<>();
a.addLast(“egg”); a.addLast(“boyz”);
longest(a);
Overriding vs. Overloading
Method Overriding
If a “subclass” has a method with the exact same signature as in the “superclass”, we say the subclass overrides the method.
public class AList<Item> implements List61B<Item>{
...
public void addLast(Item x) {
...
public interface List61B<Item> {
public void addLast(Item y);
...
AList overrides addLast(Item)
Method Overriding vs. Overloading
If a “subclass” has a method with the exact same signature as in the “superclass”, we say the subclass overrides the method.
public class Dog implements Animal {
public void makeNoise(Dog x) {
...
makeNoise is overloaded
public interface Animal {
public void makeNoise();
}
public class Pig implements Animal {
public void makeNoise() {
System.out.print(“oink”);
}
}
Pig overrides makeNoise()
public class Math {
public int abs(int a)
public double abs(double a)
abs is overloaded
Optional Step 2B: Adding the @Override Annotation
In 61b, we’ll always mark every overriding method with the @Override annotation.
public class AList<Item> implements List61B<Item>{
...
@Override
public void addLast(Item x) {
...
List61B
SLList
AList
Method Overriding
If a subclass has a method with the exact same signature as in the superclass, we say the subclass overrides the method.
Why use @Override?
Interface Inheritance
Interface Inheritance
Specifying the capabilities of a subclass using the implements keyword is known as interface inheritance.
List61B
SLList
AList
public interface List61B<Item> {
public void addFirst(Item x);
...
public void proo();
}
If AList doesn’t have a proo() method, AList will not compile!
Interface Inheritance
Specifying the capabilities of a subclass using the implements keyword is known as interface inheritance.
Interface inheritance is a powerful tool for generalizing code.
Collection61B
List61B
SLList
AList
Copying the Bits
Two seemingly contradictory facts:
public static String longest(List61B<String> list) {
int maxDex = 0;
for (int i = 0; i < list.size(); i += 1)
...
public static void main(String[] args) {
AList<String> a1 = new AList<String>();
a1.addLast("horse");
WordUtils.longest(a1);
}
How can we copy the bits in a1 to list?
Copying the Bits
Answer: If X is a superclass of Y, then memory boxes for X may contain Y.
public static String longest(List61B<String> list) {
int maxDex = 0;
for (int i = 0; i < list.size(); i += 1)
...
public static void main(String[] args) {
AList<String> a1 = new AList<String>();
a1.addLast("horse");
WordUtils.longest(a1);
}
How can we copy the bits in a1 to list?
Question: http://yellkey.com/period
Will the code below compile? If so, what happens when it runs?
public static void main(String[] args) {
List61B<String> someList = new SLList<String>();
someList.addFirst("elk");
}
Question
Will the code below compile? If so, what happens when it runs?
public static void main(String[] args) {
List61B<String> someList = new SLList<String>();
someList.addFirst("elk");
}
Implementation Inheritance: Default Methods
Implementation Inheritance
Interface inheritance:
For better or worse, Java also allows implementation inheritance.
Use the default keyword to specify a method that subclasses should inherit from an interface.
Default Method Example: print()
public interface List61B<Item> {
public void addFirst(Item x);
public void addLast(Item y);
public Item getFirst();
public Item getLast();
public Item removeLast();
public Item get(int i);
public void insert(Item x, int position);
public int size();
default public void print() {
for (int i = 0; i < size(); i += 1) {
System.out.print(get(i) + " ");
}
System.out.println();
}
}
Question: yellkey.com/computer
Is the print() method efficient?
public interface List61B<Item> {
...
default public void print() {
for (int i = 0; i < size(); i += 1) {
System.out.print(get(i) + " ");
}
System.out.println();
}
}
Question
Is the print() method efficient?
public interface List61B<Item> {
...
default public void print() {
for (int i = 0; i < size(); i += 1) {
System.out.print(get(i) + " ");
}
System.out.println();
}
}
get has to seek all the way to the given item for SLists.
Overriding Default Methods
If you don’t like a default method, you can override it.
public interface SLList<Item> implements {
@Override
public void print() {
for (Node p = sentinel.next; p != null; p = p.next) {
System.out.print(p.item + " ");
}
System.out.println();
}
}
Question
Recall that if X is a superclass of Y, then an X variable can hold a reference to a Y.
Which print method do you think will run when the code below executes?
public static void main(String[] args) {
List61B<String> someList = new SLList<String>();
someList.addLast("elk");
someList.addLast("are");
someList.addLast("watching");
someList.print();
}
Question
Recall that if X is a superclass of Y, then an X variable can hold a reference to a Y.
Which print method do you think will run when the code below executes?
public static void main(String[] args) {
List61B<String> someList = new SLList<String>();
someList.addLast("elk");
someList.addLast("are");
someList.addLast("watching");
someList.print();
}
Static and Dynamic Type, Dynamic Method Selection
Static Type vs. Dynamic Type
Every variable in Java has a “compile-time type”, a.k.a. “static type”.
�Variables also have a “run-time type”, a.k.a. “dynamic type”.
public static void main(String[] args) {
LivingThing lt1;
lt1 = new Fox();
Animal a1 = lt1;
Fox h1 = new Fox();
lt1 = new Squid();
}
LivingThing
null
Static Type
Dynamic Type
lt1
LivingThing
Technically requires a “cast”. See next lecture.
Static Type vs. Dynamic Type
Every variable in Java has a “compile-time type”, a.k.a. “static type”.
�Variables also have a “run-time type”, a.k.a. “dynamic type”.
public static void main(String[] args) {
LivingThing lt1;
lt1 = new Fox();
Animal a1 = lt1;
Fox h1 = new Fox();
lt1 = new Squid();
}
LivingThing
Fox
Static Type
Dynamic Type
lt1
LivingThing
Technically requires a “cast”. See next lecture.
Static Type vs. Dynamic Type
Every variable in Java has a “compile-time type”, a.k.a. “static type”.
�Variables also have a “run-time type”, a.k.a. “dynamic type”.
public static void main(String[] args) {
LivingThing lt1;
lt1 = new Fox();
Animal a1 = lt1;
Fox h1 = new Fox();
lt1 = new Squid();
}
LivingThing
Fox
Static Type
Dynamic Type
Animal
Fox
lt1
a1
LivingThing
Animal
Technically requires a “cast”. See next lecture.
Static Type vs. Dynamic Type
Every variable in Java has a “compile-time type”, a.k.a. “static type”.
�Variables also have a “run-time type”, a.k.a. “dynamic type”.
public static void main(String[] args) {
LivingThing lt1;
lt1 = new Fox();
Animal a1 = lt1;
Fox h1 = new Fox();
lt1 = new Squid();
}
LivingThing
Fox
Static Type
Dynamic Type
lt1
Animal
Fox
Fox
Fox
a1
h1
LivingThing
Animal
Fox
Static Type vs. Dynamic Type
Every variable in Java has a “compile-time type”, a.k.a. “static type”.
�Variables also have a “run-time type”, a.k.a. “dynamic type”.
public static void main(String[] args) {
LivingThing lt1;
lt1 = new Fox();
Animal a1 = lt1;
Fox h1 = new Fox();
lt1 = new Squid();
}
LivingThing
Squid
Static Type
Dynamic Type
lt1
Animal
Fox
Fox
Fox
a1
h1
LivingThing
Animal
Fox
Dynamic Method Selection For Overridden Methods
Suppose we call a method of an object using a variable with:
�Then if Y overrides the method, Y’s method is used instead.
public static void main(String[] args) {
List61B<String> s1= new SLList<String>();
someList.addLast("elk");
someList.addLast("are");
someList.addLast("watching");
someList.print();
}
This term is a bit obscure.
List61B
List61B
SLList
Static Type
Dynamic Type
More Dynamic Method Selection, Overloading vs. Overriding
Dynamic Method Selection Puzzle
Suppose we have classes defined below. Try to predict the results.
public interface Animal {
default void greet(Animal a) {
print("hello animal"); }
default void sniff(Animal a) {
print("sniff animal"); }
default void flatter(Animal a) {
print("u r cool animal"); }
}
public class Dog implements Animal {
void sniff(Animal a) {
print("dog sniff animal"); }
void flatter(Dog a) {
print("u r cool dog"); }
}
Animal a = new Dog();
Dog d = new Dog();
a.greet(d);
a.sniff(d);
d.flatter(d);
a.flatter(d);
Dynamic Method Selection Puzzle
Suppose we have classes defined below. Try to predict the results.
public interface Animal {
default void greet(Animal a) {
print("hello animal"); }
default void sniff(Animal a) {
print("sniff animal"); }
default void flatter(Animal a) {
print("u r cool animal"); }
}
public class Dog implements Animal {
void sniff(Animal a) {
print("dog sniff animal"); }
void flatter(Dog a) {
print("u r cool dog"); }
}
Animal a = new Dog();
Dog d = new Dog();
a.greet(d); // "hello animal"
a.sniff(d);
d.flatter(d);
a.flatter(d);
Dynamic Method Selection Puzzle
Suppose we have classes defined below. Try to predict the results.
public interface Animal {
default void greet(Animal a) {
print("hello animal"); }
default void sniff(Animal a) {
print("sniff animal"); }
default void flatter(Animal a) {
print("u r cool animal"); }
}
public class Dog implements Animal {
void sniff(Animal a) {
print("dog sniff animal"); }
void flatter(Dog a) {
print("u r cool dog"); }
}
Animal a = new Dog();
Dog d = new Dog();
a.greet(d); // "hello animal"
a.sniff(d); // "dog sniff animal"
d.flatter(d);
a.flatter(d);
Dynamic Method Selection Puzzle
Suppose we have classes defined below. Try to predict the results.
public interface Animal {
default void greet(Animal a) {
print("hello animal"); }
default void sniff(Animal a) {
print("sniff animal"); }
default void flatter(Animal a) {
print("u r cool animal"); }
}
public class Dog implements Animal {
void sniff(Animal a) {
print("dog sniff animal"); }
void flatter(Dog a) {
print("u r cool dog"); }
}
Animal a = new Dog();
Dog d = new Dog();
a.greet(d); // "hello animal"
a.sniff(d); // "dog sniff animal"
d.flatter(d); // "u r cool dog"
a.flatter(d);
Dynamic Method Selection Puzzle
Suppose we have classes defined below. Try to predict the results.
public interface Animal {
default void greet(Animal a) {
print("hello animal"); }
default void sniff(Animal a) {
print("sniff animal"); }
default void flatter(Animal a) {
print("u r cool animal"); }
}
public class Dog implements Animal {
void sniff(Animal a) {
print("dog sniff animal"); }
void flatter(Dog a) {
print("u r cool dog"); }
}
Animal a = new Dog();
Dog d = new Dog();
a.greet(d); // "hello animal"
a.sniff(d); // "dog sniff animal"
d.flatter(d); // "u r cool dog"
a.flatter(d); // “u r cool animal”
flatter is overloaded, not overridden!
The Method Selection Algorithm
Consider the function call foo.bar(x1), where foo has static type TPrime, and x1 has static type T1.
At compile time, the compiler verifies that TPrime has a method that can handle T1. It then records the signature of this method.
At runtime, if foo’s dynamic type overrides the recorded signature, use the overridden method. Otherwise, use TPrime’s version of the method.
We did not see this in our lecture puzzle, but see study guide for more!
Dynamic Method Selection Puzzle
Suppose we have classes defined below. Try to predict the results.
public interface Animal {
default void greet(Animal a) {
print("hello animal"); }
default void sniff(Animal a) {
print("sniff animal"); }
default void flatter(Animal a) {
print("u r cool animal"); }
}
public class Dog implements Animal {
void sniff(Animal a) {
print("dog sniff animal"); }
void flatter(Dog a) {
print("u r cool dog"); }
}
Animal a = new Dog();
Dog d = new Dog();
a.flatter(d);
Compiler asks “Is there a method in Animal that can handle Dog? Yes! flatter(Animal a)”. It then records the signature flatter(Animal a).
Interface vs. Implementation Inheritance
Interface vs. Implementation Inheritance
Interface Inheritance (a.k.a. what):
Implementation Inheritance (a.k.a. how):
Important: In both cases, we specify “is-a” relationships, not “has-a”.
The Dangers of Implementation Inheritance
Particular Dangers of Implementation Inheritance
Terminology Summary
New terms from this lecture: