Announcements
Exam next week covers material through today.
¡ñ Strongly recommended: Complete project 1 checkpoint.
¡ñ Project 1 gives you tons of practice with the concepts from the previous few
lectures.
datastructur.es
Announcements
How to Study for an Exam:
¡ñ Do practice problems, but…
¡ð Carefully reflect on various techniques for solving them (best through
discussion with peers).
¡ð Don¡¯t look at solutions and try to ¡°understand¡± them, or at least not until
after you¡¯ve already solved and discussed with others.
¡ð Help others work through problems. You learn a lot this way.
¡ñ Draw on the experience of your peers Link 1, Link 2
¡ñ See http://sp21.datastructur.es/materials/guides/study-guide.html for more. datastructur.es
CS61B, 2021
Lecture 8: Interface and Implementation Inheritance
¡ñ The Problem
¡ñ Hypernyms, Hyponyms, and Interface Inheritance
¡ñ Implementation Inheritance: Default Methods
¡ñ Implementation Inheritance: Extends
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
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
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()
}
datastructur.es
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
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.
datastructur.es
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
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);
}
d
atastructur.es
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
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);
}
d
atastructur.es
Method Overloading in Java
Java allows multiple methods with same name, but different parameters. ¡ñ This is called method overloading.
public static String longest(AList
…
}
public static String longest(SLList
…
}
datastructur.es
The Downsides
While overloading works, it is a bad idea in the case of longest. Why?
¡ñ Code is virtually identical. Aesthetically gross.
¡ñ Won¡¯t work for future lists. If we create a QList class, have to make a third
method.
¡ñ Harder to maintain.
¡ð Example: Suppose you find a bug in one of the methods. You fix it in the SLList version, and forget to do it in the AList version.
datastructur.es
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.
¡ñ Dog is a ¡°hypernym¡± of poodle, malamute, yorkie, etc.
Washing your dog:
Washing your poodle: 1. Brush your dog beforWe asbhaintgh.y.o..ur malamute:
1. Brush your poodle befo2r.eUasebaluthk.e.w..arm water.1…Brush your malamute before a bath. … 2.Uselukewarmwater….3.Talktoyourdogina2c.aUlmsevoluicke.w..a.rmwater….
3. Talk to your poodle in a4c.aUlmsevdoigces.h.a..mpoo. …3. Talk to your malamute in a calm voice. … 4. Use poodle shampoo. .5… Rinse well. …
5. Rinse well. …
6. Air-dry. …
7. Reward your poodle.
6. Air-dry. …
7. Reward your dog.
4. Use malamute shampoo. … 5. Rinse well. …
6. Air-dry. …
7. Reward your malamute.
datastruc
tur.es
Hypernym and Hyponym
We use the word hyponym for the opposite type of relationship. ¡ñ ¡°dog¡±: Hypernym of ¡°poodle¡±, ¡°malamute¡±, ¡°dachshund¡±, etc.
¡ñ ¡°poodle¡±: Hyponym of ¡°dog¡±
Hypernyms and hyponyms comprise a hierarchy.
¡ñ A dog ¡°is-a¡± canine.
¡ñ A canine ¡°is-a¡± carnivore.
¡ñ A carnivore ¡°is-an¡± animal.
(for fun: see the WordNet project)
omnivore
canine
animal
carnivore
herbivore
feline
dog
datastructur.es
Simple Hyponymic Relationships in Java
SLLists and ALists are both clearly some kind of ¡°list¡±. ¡ñ List is a hypernym of SLList and AList.
Expressing this in Java is a two-step process:
¡ñ Step 1: Define a reference type for our hypernym (List61B.java).
¡ñ Step 2: Specify that SLLists and ALists are hyponyms of that type. List61B
AList
SLList
datastructur.es
Step 1: Defining a List61B
We¡¯ll use the new keyword interface instead of class to define a List61B.
¡ñ Idea: Interface is a specification of what a List is able to do, not how to do it.
datastructur.es
Step 1: Defining a List61B
We¡¯ll use the new keyword interface instead of class to define a List61B.
¡ñ Idea: Interface is a specification of what a List is able to do, not how to do it.
public interface List61B
public Item removeLast();
public Item get(int i);
public void insert(Item x, int position); public int size();
}
List61B
d
atastructur.es
Step 2: Implementing the List61B Interface
We¡¯ll now:
¡ñ Use the new implements keyword to tell the Java compiler that SLList and AList are hyponyms of List61B.
public class AList
public void addLast(Item x) { List61B …
AList
SLList
datastructur.es
Adjusting WordUtils.java
We can now adjust our longest method to work on either kind of list:
public static String longest(List61B
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);
}
d
AList
a.addLast(¡°egg¡±);
a.addLast(¡°boyz¡±);
longest(a);
atastructur.es
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 interface List61B
public class AList
public void addLast(Item x) { …
AList overrides addLast(Item)
datastructur.es
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.
¡ñ Animal¡¯s subclass Pig overrides the makeNoise() method.
¡ñ Methods with the same name but different signatures are overloaded.
public interface Animal { public void makeNoise();
}
public class Pig implements Animal { public void makeNoise() {
System.out.print(¡°oink¡±);
}
}
Pig overrides makeNoise()
abs is overloaded
datastructur.es
makeNoise is overloaded
public class Dog implements Animal { public void makeNoise(Dog x) {
…
public class Math {
public int abs(int a) public double abs(double a)
Optional Step 2B: Adding the @Override Annotation
In 61b, we¡¯ll always mark every overriding method with the @Override annotation.
¡ñ Example: Mark AList.java¡¯s overriding methods with @Override.
¡ñ The only effect of this tag is that the code won¡¯t compile if it is not actually
an overriding method.
public class AList
List61B
@Override
public void addLast(Item x) { …
AList
SLList
datastructur.es
Method Overriding
If a subclass has a method with the exact same signature as in the superclass, we say the subclass overrides the method.
¡ñ Even if you don¡¯t write @Override, subclass still overrides the method.
¡ñ @Override is just an optional reminder that you¡¯re overriding.
Why use @Override?
¡ñ Main reason: Protects against typos.
¡ð If you say @Override, but it the method isn¡¯t actually overriding
anything, you¡¯ll get a compile error.
¡ð e.g. public void addLats(Item x)
¡ñ Reminds programmer that method definition came from somewhere higher up in the inheritance hierarchy.
datastructur.es
Interface Inheritance
Interface Inheritance
Specifying the capabilities of a subclass using the implements keyword is known as interface inheritance.
¡ñ Interface: The list of all method signatures.
¡ñ Inheritance: The subclass ¡°inherits¡± the interface from a superclass.
¡ñ Specifies what the subclass can do, but not how.
¡ñ Subclasses must override all of these methods!
¡ð Will fail to compile otherwise.
List61B
public interface List61B
public void proo();
}
AList
SLList
If AList doesn¡¯t have a proo() method, AList will not compile!
datastructur.es
Interface Inheritance
Specifying the capabilities of a subclass using the implements keyword is known as interface inheritance.
¡ñ Interface: The list of all method signatures.
¡ñ Inheritance: The subclass ¡°inherits¡± the interface.
¡ñ Specifies what the subclass can do, but not how.
¡ñ Subclasses must override all of these methods!
¡ñ Such relationships can be multi-generational.
¡ð Figure: Interfaces in white, classes in green.
¡ð We¡¯ll talk about this in a later lecture.
Collection61B
List61B
AList Interface inheritance is a powerful tool for generalizing code.
SLList
¡ñ WordUtils.longest works on SLLists, ALists, and even lists that have not yet been invented!
datastructur.es
Copying the Bits
Two seemingly contradictory facts:
¡ñ #1: When you set x = y or pass a parameter, you¡¯re just copying the bits.
¡ñ #2: A memory box can only hold 64 bit addresses for the appropriate type.
¡ð e.g. String x can never hold the 64 bit address of a Dog.
public static String longest(List61B
for (int i = 0; i < list.size(); i += 1)
...
public static void main(String[] args) { AList
}
How can we copy the bits in a1 to list?
datastructu
r.es
Copying the Bits
Answer: If X is a superclass of Y, then memory boxes for X may contain Y.
¡ñ An AList is-a List.
¡ñ Therefore List variables can hold ALList addresses.
public static String longest(List61B
for (int i = 0; i < list.size(); i += 1)
...
public static void main(String[] args) { AList
}
How can we copy the bits in a1 to list?
datastructu
r.es
Question
Will the code below compile? If so, what happens when it runs?
a. Will not compile.
b. Will compile, but will cause an error at runtime on the new line.
c. When it runs, an SLList is created and its address is stored in the someList variable, but it crashes on someList.addFirst() since the List class doesn¡¯t implement addFirst.
d. When it runs, an SLList is created and its address is stored in the someList variable. Then the string ¡°elk¡± is inserted into the SLList referred to by addFirst.
public static void main(String[] args) { List61B
}
datastructur.es
Question
Will the code below compile? If so, what happens when it runs?
a. Will not compile.
b. Will compile, but will cause an error at runtime on the new line.
c. When it runs, an SLList is created and its address is stored in the someList variable, but it crashes on someList.addFirst() since the List class doesn¡¯t implement addFirst.
d. When it runs, an SLList is created and its address is stored in the someList variable. Then the string ¡°elk¡± is inserted into the SLList referred to by addFirst.
public static void main(String[] args) { List61B
}
datastructur.es
Implementation Inheritance: Default Methods
Implementation Inheritance
Interface inheritance:
¡ñ Subclass inherits signatures, but NOT implementation.
For better or worse, Java also allows implementation inheritance. ¡ñ Subclasses can inherit signatures AND implementation.
Use the default keyword to specify a method that subclasses should inherit from an interface.
¡ñ Example: Let¡¯s add a default print() method to List61B.java
datastructur.es
Default Method Example: print()
public interface List61B
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();
}
}
datastructur.es
Question
Is the print() method efficient?
a. Inefficient for AList and SLList
b. Efficient for AList, inefficient for SLList
c. Inefficient for AList, efficient for SLList
d. Efficient for both AList and SLList
public interface List61B
default public void print() {
for (int i = 0; i < size(); i += 1) {
System.out.print(get(i) + " ");
}
System.out.println();
}
}
datastructur.es
Question
Is the print() method efficient?
a. Inefficient for AList and SLList
b. Efficient for AList, inefficient for SLList
c. Inefficient for AList, efficient for SLList
d. Efficient for both AList and SLList
public interface List61B
default public void print() {
for (int i = 0; i < size(); i += 1) {
System.out.print(get(i) + " "); }
} }
datastructur.es
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.
¡ñ Any call to print() on an SLList will use this method instead of default.
¡ñ Use (optional) @Override to catch typos like public void pirnt()
public interface SLList
public void print() {
for (Node p = sentinel.next; p != null; p = p.next) {
System.out.print(p.item + ” “);
}
System.out.println();
}
}
datastructur.es
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?
¡ñ List.print()
¡ñ SLList.print()
public static void main(String[] args) { List61B
someList.print();
}
datastructur.es
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?
¡ñ List.print()
¡ñ SLList.print() : And this is the sensible choice. But how does it work?
¡ð Before we can answer that, we need new terms: static and dynamic type.
public static void main(String[] args) { List61B
someList.print();
}
datastructur.es
Static and Dynamic Type, Dynamic Method Selection
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
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
Static Type
LivingThing null
Dynamic Type
datastructur.es
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
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
Static Type
LivingThing Fox
Dynamic Type
datastructur.es
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
Animal
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
Static Type
LivingThing Fox Animal Fox
Dynamic Type
datastructur.es
public static void main(String[] args) { LivingThing lt1;
lt1 = new Fox();
Animal a1 = lt1;
Fox h1 = new Fox();
lt1 = new Squid(); }
LivingThing
Animal
Fox
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 Fox Animal Fox Fox Fox
Dynamic Type
datastructur.es
public static void main(String[] args) { LivingThing lt1;
lt1 = new Fox();
Animal a1 = lt1;
Fox h1 = new Fox();
lt1 = new Squid(); }
LivingThing
Animal
Fox
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
datastructur.es
Dynamic Method Selection For Overridden Methods
Suppose we call a method of an object using a variable with:
¡ñ compile-time type X
¡ñ run-time type Y
Then if Y overrides the method, Y¡¯s method is used instead.
¡ñ This is known as ¡°dynamic method selection¡±.
This term is a bit obscure.
public static void main(String[] args) { List61B
}
List61B
Static Type Dynamic Type
List61B SLList
datastructur.es
Signature Selection, Dynamic Method Selection
Dynamic Method Selection Puzzle: Try to Predict the Results
Before we start, let¡¯s explicitly show the methods that are inherited by the Dog class.
public interface Animal { default void greet(Animal a) {
print(“hello animal”); } default void sniff(Animal a) {
print(“sniff animal”); } default void praise(Animal a) {
print(“u r cool animal”); }
}
public class Dog implements Animal { @Override
void sniff(Animal a) {
print(“dog sniff animal”); }
void praise(Dog a) {
print(“u r cool dog”); }
}
Animal a = new Dog(); Dog d = new Dog(); a.greet(d); a.sniff(d); d.praise(d); a.praise(d);
datastructur.es
Dynamic Method Selection Puzzle: Try to Predict the Results
Note: default methods in the Dog class is shown grayed out to indicate they are inherited.
public interface Animal { default void greet(Animal a) {
print(“hello animal”); } default void sniff(Animal a) {
print(“sniff animal”); } default void praise(Animal a) {
print(“u r cool animal”); }
}
public class Dog implements Animal { default void greet(Animal a) @Override
void sniff(Animal a) {
print(“dog sniff animal”); }
default void praise(Animal a)
void praise(Dog a) {
print(“u r cool dog”); }
}
Animal a = new Dog(); Dog d = new Dog(); a.greet(d); a.sniff(d); d.praise(d); a.praise(d);
datastructur.es
Dynamic Method Selection Puzzle: Try to Predict the Results
Note: default methods in the Dog class is shown grayed out to indicate they are inherited.
public interface Animal { default void greet(Animal a) {
print(“hello animal”); } default void sniff(Animal a) {
print(“sniff animal”); } default void praise(Animal a) {
print(“u r cool animal”); }
}
public class Dog implements Animal { default void greet(Animal a) @Override
void sniff(Animal a) {
print(“dog sniff animal”); }
default void praise(Animal a)
void praise(Dog a) {
print(“u r cool dog”); }
}
Animal a = new Dog();
Dog d = new Dog();
a.greet(d); // “hello animal” a.sniff(d);
d.praise(d);
a.praise(d);
datastructur.es
Dynamic Method Selection Puzzle: Try to Predict the Results
Note: default methods in the Dog class is shown grayed out to indicate they are inherited.
public interface Animal { default void greet(Animal a) {
print(“hello animal”); } default void sniff(Animal a) {
print(“sniff animal”); } default void praise(Animal a) {
print(“u r cool animal”); }
}
public class Dog implements Animal { default void greet(Animal a) @Override
void sniff(Animal a) {
print(“dog sniff animal”); } default void praise(Animal a) void praise(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.praise(d);
a.praise(d);
datastructur.es
Dynamic Method Selection Puzzle: Try to Predict the Results
Note: default methods in the Dog class is shown grayed out to indicate they are inherited.
public interface Animal { default void greet(Animal a) {
print(“hello animal”); } default void sniff(Animal a) {
print(“sniff animal”); } default void praise(Animal a) {
print(“u r cool animal”); }
}
public class Dog implements Animal { default void greet(Animal a) @Override
void sniff(Animal a) {
print(“dog sniff animal”); } default void praise(Animal a) void praise(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.praise(d); // “u r cool dog” a.praise(d);
datastructur.es
Dynamic Method Selection Puzzle: Try to Predict the Results
Why?
praise is overloaded, not overridden!
public interface Animal { default void greet(Animal a) {
print(“hello animal”); } default void sniff(Animal a) {
print(“sniff animal”); } default void praise(Animal a) {
print(“u r cool animal”); } }
public class Dog implements Animal { default void greet(Animal a) @Override
void sniff(Animal a) {
print(“dog sniff animal”); }
default void praise(Animal a)
void praise(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.praise(d); // “u r cool dog” a.praise(d); // ¡°u r cool animal¡±
datastructur.es
An Alternate Viewpoint: DMS as a Two Step Process
Another way to think about dynamic method selection is as a 2 step process, where step 1 happens at compile time, and step 2 happens at runtime.
These two steps obey rules that are easy to apply, but take time to understand.
¡ñ At compile time: We determine the signature S of the method to be called. ¡ð S is decided using ONLY static types.
¡ñ At runtime: The dynamic type of the invoking object uses its method with this exact signature S.
¡ð By ¡°invoking object¡±, we mean the object whose method is invoked.
datastructur.es
An Alternate Viewpoint: DMS as a Two Step Process
Another way to think about dynamic method selection is as a 2 step process, where step 1 happens at compile time, and step 2 happens at runtime.
These two steps obey rules that are easy to apply, but take time to understand.
¡ñ At compile time: We determine the signature S of the method to be called. ¡ð S is decided using ONLY static types.
¡ñ At runtime: The dynamic type of the invoking object uses its method with this exact signature S.
¡ð By ¡°invoking object¡±, we mean the object whose method is invoked. Let¡¯s do an exercise to understand this first rule.
datastructur.es
Dynamic Method Selection Puzzle
What method signature will be used for each call?
¡ñ Rule 1: The signature is decided using ONLY static types.
¡ñ The signature is the method name and the number and type of its parameters.
public interface Animal {
default void greet(Animal a) default void sniff(Animal a) default void praise(Animal a) {
}
public class Dog implements Animal { default void greet(Animal a)
void sniff(Animal a)
default void praise(Animal a)
void praise(Dog a)
} Animal a = new Dog();
Dog d = new Dog(); a.greet(d); a.sniff(d); d.praise(d); a.praise(d);
datastructur.es
Dynamic Method Selection Puzzle
What method signature will be used for each call?
¡ñ Rule 1: The signature is decided using ONLY static types.
¡ñ The signature is the method name and the number and type of its parameters.
public interface Animal {
default void greet(Animal a) default void sniff(Animal a) default void praise(Animal a) {
}
public class Dog implements Animal { default void greet(Animal a)
void sniff(Animal a)
default void praise(Animal a)
void praise(Dog a)
} Animal a = new Dog();
Dog d = new Dog();
a.greet(d); // greet(Animal a) a.sniff(d);
d.praise(d);
a.praise(d);
datastructur.es
Dynamic Method Selection Puzzle
What method signature will be used for each call?
¡ñ Rule 1: The signature is decided using ONLY static types.
¡ñ The signature is the method name and the number and type of its parameters.
Note there are TWO
sniff(Animal)
methods.
Paul Hilfinger calls these a ¡°Dynamic Method Set¡±.
public interface Animal {
default void greet(Animal a) default void sniff(Animal a) default void praise(Animal a) {
}
public class Dog implements Animal { default void greet(Animal a)
void sniff(Animal a)
default void praise(Animal a)
void praise(Dog a)
} Animal a = new Dog();
Dog d = new Dog();
a.greet(d); // greet(Animal a) a.sniff(d); // sniff(Animal a) d.praise(d);
a.praise(d);
datastructur.es
Dynamic Method Selection Puzzle
What method signature will be used for each call?
¡ñ Rule 1: The signature is decided using ONLY static types.
¡ñ The signature is the method name and the number and type of its parameters.
public interface Animal {
default void greet(Animal a) default void sniff(Animal a) default void praise(Animal a) {
}
public class Dog implements Animal { default void greet(Animal a)
void sniff(Animal a)
default void praise(Animal a)
void praise(Dog a)
} Animal a = new Dog();
Dog d = new Dog();
a.greet(d); // greet(Animal a) a.sniff(d); // sniff(Animal a) d.praise(d); // praise(Dog a) a.praise(d);
datastructur.es
Dynamic Method Selection Puzzle
What method signature will be used for each call?
¡ñ Rule 1: The signature is decided using ONLY static types.
¡ñ The signature is the method name and the number and type of its parameters.
public interface Animal {
default void greet(Animal a) default void sniff(Animal a) default void praise(Animal a) {
}
public class Dog implements Animal { default void greet(Animal a)
void sniff(Animal a)
default void praise(Animal a)
void praise(Dog a)
} Animal a = new Dog();
Dog d = new Dog();
a.greet(d); // greet(Animal a) a.sniff(d); // sniff(Animal a) d.praise(d); // praise(Dog a) a.praise(d); // praise(Animal a)
datastructur.es
An Alternate Viewpoint: DMS as a Two Step Process
Another way to think about dynamic method selection is as a 2 step process, where step 1 happens at compile time, and step 2 happens at runtime.
These two steps obey rules that are easy to apply, but take time to understand.
¡ñ At compile time: We determine the signature S of the method to be called. ¡ð S is decided using ONLY static types.
¡ñ At runtime: The dynamic type of the invoking object uses its method with this exact signature S.
¡ð By ¡°invoking object¡±, we mean the object whose method is invoked.
In the previous exercise, we saw how to apply rule 1. ¡ñ Now let¡¯s see how we then apply rule 2.
datastructur.es
Dynamic Method Selection Puzzle: Try to Predict the Results
Results of rule 1 shown in figure to the right as comments
public interface Animal { default void greet(Animal a) {
print(“hello animal”); } default void sniff(Animal a) {
print(“sniff animal”); } default void praise(Animal a) {
print(“u r cool animal”); }
}
public class Dog implements Animal { default void greet(Animal a) @Override
void sniff(Animal a) {
print(“dog sniff animal”); }
default void praise(Animal a)
void praise(Dog a) {
print(“u r cool dog”); }
}
Animal a = new Dog();
Dog d = new Dog();
a.greet(d); // greet(Animal a) a.sniff(d); // sniff(Animal a) d.praise(d);// praise(Dog a) a.praise(d);// praise(Animal a)
datastructur.es
Dynamic Method Selection Puzzle: Try to Predict the Results
Invoking object is a.
Dynamic type of a is Dog ¡ñ So use Dog¡¯s
greet(Animal)
public interface Animal { default void greet(Animal a) {
print(“hello animal”); } default void sniff(Animal a) {
print(“sniff animal”); } default void praise(Animal a) {
print(“u r cool animal”); }
}
public class Dog implements Animal { default void greet(Animal a) @Override
void sniff(Animal a) {
print(“dog sniff animal”); }
default void praise(Animal a)
void praise(Dog a) {
print(“u r cool dog”); }
}
Animal a = new Dog();
Dog d = new Dog();
a.greet(d); // greet(Animal a) – ¡°hello animal¡± a.sniff(d); // sniff(Animal a)
d.praise(d);// praise(Dog a)
a.praise(d);// praise(Animal a)
datastructur.es
Dynamic Method Selection Puzzle: Try to Predict the Results
Invoking object is a.
Dynamic type of a is Dog ¡ñ So use Dog¡¯s
sniff(Animal)
public interface Animal { default void greet(Animal a) {
print(“hello animal”); } default void sniff(Animal a) {
print(“sniff animal”); } default void praise(Animal a) {
print(“u r cool animal”); }
}
public class Dog implements Animal { default void greet(Animal a) @Override
void sniff(Animal a) {
print(“dog sniff animal”); } default void praise(Animal a) void praise(Dog a) {
print(“u r cool dog”); }
}
Animal a = new Dog();
Dog d = new Dog();
a.greet(d); // greet(Animal a) – ¡°hello animal¡± a.sniff(d); // sniff(Animal a) – ¡°dog sniff animal¡± d.praise(d);// praise(Dog a)
a.praise(d);// praise(Animal a)
datastructur.es
Dynamic Method Selection Puzzle: Try to Predict the Results
Invoking object is d.
Dynamic type of d is Dog ¡ñ So use Dog¡¯s
praise(Dog)
public interface Animal { default void greet(Animal a) {
print(“hello animal”); } default void sniff(Animal a) {
print(“sniff animal”); } default void praise(Animal a) {
print(“u r cool animal”); }
}
public class Dog implements Animal { default void greet(Animal a) @Override
void sniff(Animal a) {
print(“dog sniff animal”); } default void praise(Animal a) void praise(Dog a) {
print(“u r cool dog”); } }
Animal a = new Dog();
Dog d = new Dog();
a.greet(d); // greet(Animal a) – ¡°hello animal¡± a.sniff(d); // sniff(Animal a) – ¡°dog sniff animal¡± d.praise(d);// praise(Dog a) – ¡°u r cool dog¡± a.praise(d);// praise(Animal a)
datastructur.es
Dynamic Method Selection Puzzle: Try to Predict the Results
Invoking object is a.
Dynamic type of a is Dog ¡ñ So use Dog¡¯s
praise(Animal)
public interface Animal { default void greet(Animal a) {
print(“hello animal”); } default void sniff(Animal a) {
print(“sniff animal”); } default void praise(Animal a) {
print(“u r cool animal”); }
}
public class Dog implements Animal { default void greet(Animal a) @Override
void sniff(Animal a) {
print(“dog sniff animal”); } default void praise(Animal a) void praise(Dog a) {
print(“u r cool dog”); }
}
Animal a = new Dog();
Dog d = new Dog();
a.greet(d); // greet(Animal a) – ¡°hello animal¡± a.sniff(d); // sniff(Animal a) – ¡°dog sniff animal¡± d.praise(d);// praise(Dog a) – ¡°u r cool dog¡±
a.praise(d);// praise(Animal a) – ¡°u r cool animal¡±
datastructur.es
Practical Inheritance
Lists
In lecture, we¡¯ve built two types of lists: ALists and SLLists. ¡ñ Similar to Python lists.
List61B
L.addLast(10);
L.addLast(15);
L.print();
L = [] L.append(3) L.append(4) L.append(5) print(L)
$ java ListExample
3 45
$ python list_example.py [3 4 5]
datastructur.es
Lists in Real Java Code
We built a list from scratch, but Java provides a built-in List interface and several implementations, e.g. ArrayList.
For the rest of 61B, we encourage you to use Java¡¯s built in List interface and ArrayList class!
List methods here.
List61B
L.addLast(10);
L.addLast(15);
L.print();
java.util.List
L.add(10);
L.add(15);
System.out.println(L);
datastructur.es
Lists in Real Java Code
By including ¡°import java.util.List¡± and ¡°import java.util.ArrayList¡± at the top of the file, we can make our code more compact.
import java.util.List; import java.util.ArrayList;
public class SimpleBuiltInListExample { public static void main(String[] args) {
List
List
If we import, we can use the ¡°simple name¡± (ArrayList) as opposed to the longer ¡°canonical name¡± (java.util.ArrayList).
}
datas
tructur.es
Interface vs. Implementation Inheritance
Interface vs. Implementation Inheritance
Interface Inheritance (a.k.a. what):
¡ñ Allows you to generalize code in a powerful, simple way.
Implementation Inheritance (a.k.a. how):
¡ñ Allows code-reuse: Subclasses can rely on superclasses or interfaces.
¡ð Example: print() implemented in List61B.java.
¡ð Gives another dimension of control to subclass designers: Can decide
whether or not to override default implementations. Important: In both cases, we specify ¡°is-a¡± relationships, not ¡°has-a¡±.
¡ñ Good: Dog implements Animal, SLList implements List61B.
¡ñ Bad: Cat implements Claw, Set implements SLList.
datastructur.es
The Dangers of Implementation Inheritance
Particular Dangers of Implementation Inheritance
¡ñ Makes it harder to keep track of where something was actually implemented (though a good IDE makes this better).
¡ñ Rules for resolving conflicts can be arcane. Won¡¯t cover in 61B.
¡ð Example: What if two interfaces both give conflicting default methods?
¡ñ Encourages overly complex code (especially with novices). ¡ð Common mistake: Has-a vs. Is-a!
¡ñ Breaks encapsulation!
¡ð What is encapsulation? See next week.
datastructur.es