Interface and Implementation Inheritance
1
Lecture 8 (Inheritance 1)
CS61B, Fall 2023 @ UC Berkeley
Slides credit: Josh Hug
The Desire for Generality
Lecture 8, CS61B, Fall 2023
Interface Inheritance
Implementation Inheritance
Static and Dynamic Type
Using Inheritance Safely
AList and SLList
After adding an additional “insert” method. Our AList and SLList classes from lecture 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.
Demo: Using ALists and SLLists
This example usage of the longest method works fine.
public static String longest(SLList<String> list) {
...
}
public static void main(String[] args) {
SLList<String> someList = new SLList<>();
someList.addLast("elk");
someList.addLast("are");
someList.addLast("watching");
System.out.println(longest(someList));
}
watching
WordUtils.java
Demo: Using ALists and SLLists
What if somebody placed their list of words in an AList instead of an SLList?
public static String longest(SLList<String> list) {
...
}
public static void main(String[] args) {
AList<String> someList = new AList<>();
someList.addLast("elk");
someList.addLast("are");
someList.addLast("watching");
System.out.println(longest(someList));
}
AList instead of SLList.
WordUtils.java
Demo: Using ALists and SLLists
What if somebody placed their list of words in an AList instead of an SLList?
public static String longest(SLList<String> list) {
...
}
public static void main(String[] args) {
AList<String> someList = new AList<>();
someList.addLast("elk");
someList.addLast("are");
someList.addLast("watching");
System.out.println(longest(someList));
}
Compiler error:
SLList cannot be applied to AList.
WordUtils.java
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) {
...
}
Possible solution: Copy-paste the same method body into two methods with different signatures.
The Downsides
While overloading works, it is a bad idea in the case of longest. Why?
Hypernyms and Hyponyms
Lecture 8, CS61B, Fall 2023
Interface Inheritance
Implementation Inheritance
Static and Dynamic Type
Using Inheritance Safely
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.
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
Interface and Implements Keywords
Lecture 8, CS61B, Fall 2023
Interface Inheritance
Implementation Inheritance
Static and Dynamic Type
Using Inheritance Safely
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 insert(Item x, int position);
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 int size();
}
List61B.java
List61B
Step 2: Implementing the List61B Interface
We’ll now:
public class AList<Item> implements List61B<Item> {
...
public void addLast(Item x) {
...
List61B
AList
Step 2: Implementing the List61B Interface
We’ll now:
public class SLList<Blorp> implements List61B<Blorp>{
...
public void addLast(Blorp 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);
Demo: Interface and Implements Keywords
Our longest method now takes in a List61B (not a SLList or AList).
public static String longest(List61B<String> list) {
...
}
public static void main(String[] args) {
SLList<String> someList = new SLList<>();
someList.addLast("elk");
someList.addLast("are");
someList.addLast("watching");
System.out.println(longest(someList));
}
watching
WordUtils.java
…including SLList.
You can pass in any object that implements List61B…
Demo: Interface and Implements Keywords
Our longest method now takes in a List61B (not a SLList or AList).
public static String longest(List61B<String> list) {
...
}
public static void main(String[] args) {
AList<String> someList = new AList<>();
someList.addLast("elk");
someList.addLast("are");
someList.addLast("watching");
System.out.println(longest(someList));
}
watching
WordUtils.java
…including AList.
You can pass in any object that implements List61B…
Overriding vs. Overloading
Lecture 8, CS61B, Fall 2023
Interface Inheritance
Implementation Inheritance
Static and Dynamic Type
Using Inheritance Safely
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)
public void makeNoise()
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
Lecture 8, CS61B, Fall 2023
Interface Inheritance
Implementation Inheritance
Static and Dynamic Type
Using Inheritance Safely
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
Is-a-relationships
Recall: A memory box can only hold 64 bit addresses for the appropriate type.
public static String longest(List61B<String> inputList) {
int maxDex = 0;
for (int i = 0; i < inputList.size(); i += 1)
...
public static void main(String[] args) {
AList<String> a1 = new AList<String>();
a1.addLast("horse");
WordUtils.longest(a1);
}
Allowed! An AList is a List61B.
Question: yellkey.com/TODO
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");
}
Default Methods
Lecture 8, CS61B, Fall 2023
Interface Inheritance
Implementation Inheritance
Static and Dynamic Type
Using Inheritance Safely
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.
Coding Demo: Default Methods
public interface List61B<Item> {
public Item get(int i);
public int size();
/** Prints out the entire list. */
public void print() {
}
}
List61B.java
If we try to write a method like we normally do in a class, we get an error:
"Interface methods cannot have body"
Coding Demo: Default Methods
public interface List61B<Item> {
public Item get(int i);
public int size();
/** Prints out the entire list. */
default public void print() {
}
}
List61B.java
If we add the default keyword, the error goes away. Now we can write a method body in the interface.
Coding Demo: Default Methods
public interface List61B<Item> {
public Item get(int i);
public int size();
/** Prints out the entire list. */
default public void print() {
for (int i = 0; i < size(); i += 1) {
}
}
}
List61B.java
Coding Demo: Default Methods
public interface List61B<Item> {
public Item get(int i);
public int size();
/** Prints out the entire list. */
default public void print() {
for (int i = 0; i < size(); i += 1) {
System.out.print(get(i) + " ");
}
}
}
List61B.java
Coding Demo: Default Methods
public interface List61B<Item> {
public Item get(int i);
public int size();
/** Prints out the entire list. */
default public void print() {
for (int i = 0; i < size(); i += 1) {
System.out.print(get(i) + " ");
}
System.out.println();
}
}
List61B.java
Coding Demo: Default Methods
public class IsADemo {
public static void main(String[] args) {
List61B<String> someList = new SLList<>();
someList.addFirst("elk");
someList.addLast("dwell");
someList.addLast("on");
someList.addLast("existential");
someList.addLast("crises");
someList.print();
}
}
IsADemo.java
elk dwell on existential crises
SLLists don't have a print method, but the print method still works.
The default print method in the List61B interface is executed.
Default Method Example: print()
public interface List61B<Item> {
public void insert(Item x, int position);
public void addFirst(Item x);
public void addLast(Item x);
public Item getFirst();
public Item getLast();
public Item get(int i);
public int size();
public Item removeLast();
default public void print() {
for (int i = 0; i < size(); i += 1) {
System.out.print(get(i) + " ");
}
System.out.println();
}
}
Question: yellkey.com/TODO
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();
}
}
Overriding Default Methods
Lecture 8, CS61B, Fall 2023
Interface Inheritance
Implementation Inheritance
Static and Dynamic Type
Using Inheritance Safely
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 SLLists.
Coding Demo: Overriding Default Methods
public class SLList<Blorp> implements List61B<Blorp> {
/** A print method that overrides
* List61B's inefficient print method. */
public void print() {
}
}
SLList.java
Coding Demo: Overriding Default Methods
public class SLList<Blorp> implements List61B<Blorp> {
/** A print method that overrides
* List61B's inefficient print method. */
@Override
public void print() {
}
}
SLList.java
Coding Demo: Overriding Default Methods
public class SLList<Blorp> implements List61B<Blorp> {
/** A print method that overrides
* List61B's inefficient print method. */
@Override
public void print() {
for (Node p = sentinel.next; p != null; p = p.next) {
}
}
}
SLList.java
Coding Demo: Overriding Default Methods
public class SLList<Blorp> implements List61B<Blorp> {
/** A print method that overrides
* List61B's inefficient print method. */
@Override
public void print() {
for (Node p = sentinel.next; p != null; p = p.next) {
System.out.print(p.item + " ");
}
}
}
SLList.java
Coding Demo: Overriding Default Methods
public class SLList<Blorp> implements List61B<Blorp> {
/** A print method that overrides
* List61B's inefficient print method. */
@Override
public void print() {
System.out.println("The boss doesn't know what he's doing!");
for (Node p = sentinel.next; p != null; p = p.next) {
System.out.print(p.item + " ");
}
}
}
SLList.java
Coding Demo: Default Methods
public class IsADemo {
public static void main(String[] args) {
List61B<String> someList = new SLList<>();
someList.addFirst("elk");
someList.addLast("dwell");
someList.addLast("on");
someList.addLast("existential");
someList.addLast("crises");
someList.print();
}
}
IsADemo.java
The boss doesn't know what he's doing!
elk dwell on existential crises
Now we're running the print method in SLList, not the print method in List61B.
Overriding Default Methods
If you don’t like a default method, you can override it.
public class SLList<Blorp> implements List61B<Blorp> {
@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
Lecture 8, CS61B, Fall 2023
Interface Inheritance
Implementation Inheritance
Static and Dynamic Type
Using Inheritance Safely
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();
}
Technically requires a “cast”. See next lecture.
LivingThing
Fox
Static Type
Dynamic Type
Animal
Fox
lt1
a1
LivingThing
Animal
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.
This term is a bit obscure.
List61B
List61B
SLList
Static Type
Dynamic Type
public static void main(String[] args) {
LivingThing lt1;
lt1 = new Fox();
Animal a1 = lt1;
Fox h1 = new Fox();
lt1 = new Squid();
}
Changes to Scope in 61B
Lecture 8, CS61B, Fall 2023
Interface Inheritance
Implementation Inheritance
Static and Dynamic Type
Using Inheritance Safely
Older Versions of 61B (pre-2018)
In older versions of this class, the section on Dynamic Method Selection included a tricky corner case where a subclass overloads (rather than overrides) a superclass method.
Students spent a great deal of time on something that isn’t ultimately very important. This is not a class about Java minutiae, so I cut this material.
Using Inheritance Safely
Lecture 8, CS61B, Fall 2023
Interface Inheritance
Implementation Inheritance
Static and Dynamic Type
Using Inheritance Safely
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