CS61B, 2022

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<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()

}

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<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.

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<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);

}

​

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(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);

}

​

datastructur.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<String> list) {

...

}

​

public static String longest(SLList<String> list) {

...

}

​

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 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.

​

​

datastructur.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)

​

animal

omnivore

herbivore

carnivore

feline

canine

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

SLList

AList

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<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

datastructur.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<Item> implements List61B<Item>{

...

public void addLast(Item x) {

...

List61B

SLList

AList

datastructur.es

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);

​

datastructur.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 class AList<Item> implements List61B<Item>{

...

public void addLast(Item x) {

...

public interface List61B<Item> {

public void addLast(Item y);

...

​

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.

datastructur.es

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<Item> implements List61B<Item>{

...

​

@Override

public void addLast(Item x) {

...

List61B

SLList

AList

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

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!

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.

​

Interface inheritance is a powerful tool for generalizing code.

• WordUtils.longest works on SLLists, ALists, and even lists that have not yet been invented!

Collection61B

List61B

SLList

AList

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<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?

datastructur.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<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?

datastructur.es

Question: https://www.yellkey.com/quite

Will the code below compile? If so, what happens when it runs?

1. Will not compile.
2. Will compile, but will cause an error at runtime on the new line.
3. 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.
4. 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<String> someList = new SLList<String>();

someList.addFirst("elk");

}

​

datastructur.es

Question

Will the code below compile? If so, what happens when it runs?

• Will not compile.
• Will compile, but will cause an error at runtime on the new line.
• 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.
• 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<String> someList = new SLList<String>();

someList.addFirst("elk");

}

​

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<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();

}

}

datastructur.es

Question: https://www.yellkey.com/catch

Is the print() method efficient?

1. Inefficient for AList and SLList
2. Efficient for AList, inefficient for SLList
3. Inefficient for AList, efficient for SLList
4. Efficient for both AList and SLList

public interface List61B<Item> {

...

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?

• Inefficient for AList and SLList
• Efficient for AList, inefficient for SLList
• Inefficient for AList, efficient for SLList
• Efficient for both AList and SLList

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.

datastructur.es

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<Item> implements {

@Override

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<String> someList = new SLList<String>();

someList.addLast("elk");

someList.addLast("are");

someList.addLast("watching");

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<String> someList = new SLList<String>();

someList.addLast("elk");

someList.addLast("are");

someList.addLast("watching");

someList.print();

}

​

datastructur.es

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”.

• 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.

​

​

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.

datastructur.es

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.

​

​

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.

datastructur.es

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.

​

​

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.

datastructur.es

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.

​

​

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

datastructur.es

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.

​

​

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

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”.

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

datastructur.es

Note on Changes to DMS Scope in 61B

Older Versions of 61B

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.

• Even older versions went even deeper, showing what happens when subclasses have variables with the same name as their superclass.

​

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.

• Example, the infamous Bird/Falcon/gulgate problem from Spring 2017: https://hkn.eecs.berkeley.edu/examfiles/cs61b_sp17_mt1.pdf
• If you are doing problems where the behavior of the DMS is highly counterintuitive, it is probably out of scope.
• See the following slides or bonus video A, then bonus video B if you’re curious.

datastructur.es

DMS Corner Case:

Signature Selection and

Dynamic Method Selection (Bonus Content)

Not covered on Exams

Dynamic Method Selection Puzzle: 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 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);

​

Before we start, let’s explicitly show the methods that are inherited by the Dog class.

datastructur.es

Dynamic Method Selection Puzzle: 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 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);

​

Note: default methods in the Dog class is shown grayed out to indicate they are inherited.

datastructur.es

Dynamic Method Selection Puzzle: 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 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);

​

Note: default methods in the Dog class is shown grayed out to indicate they are inherited.

datastructur.es

Dynamic Method Selection Puzzle: 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 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);

​

Note: default methods in the Dog class is shown grayed out to indicate they are inherited.

datastructur.es

Dynamic Method Selection Puzzle: 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 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);

Note: default methods in the Dog class is shown grayed out to indicate they are inherited.

datastructur.es

Dynamic Method Selection Puzzle: 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 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”

Why?

​

praise is overloaded, not overridden!

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.

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);

​

Note there are TWO sniff(Animal) methods.

​

Paul Hilfinger calls these a “Dynamic Method Set”.

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

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)

Results of rule 1 shown in figure to the right as comments

datastructur.es

Dynamic Method Selection Puzzle: 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 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)

​

Invoking object is a.

​

Dynamic type of a is Dog

• So use Dog’s greet(Animal)

datastructur.es

Dynamic Method Selection Puzzle: 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 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)

​

Invoking object is a.

​

Dynamic type of a is Dog

• So use Dog’s sniff(Animal)

datastructur.es

Dynamic Method Selection Puzzle: 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 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)

​

Invoking object is d.

​

Dynamic type of d is Dog

• So use Dog’s praise(Dog)

datastructur.es

Dynamic Method Selection Puzzle: 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 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”

​

Invoking object is a.

​

Dynamic type of a is Dog

• So use Dog’s praise(Animal)

datastructur.es

Practical Inheritance

Lists

In lecture, we’ve built two types of lists: ALists and SLLists.

• Similar to Python lists.

List61B<Integer> L = new AList<>();

L.addLast(5);

L.addLast(10);

L.addLast(15);

L.print();

​

L = []

L.append(3)

L.append(4)

L.append(5)

print(L)

$ java ListExample

3 4 5

$ 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.

java.util.List<Integer> L = new java.util.ArrayList<>();

L.add(5);

L.add(10);

L.add(15);

System.out.println(L);

List61B<Integer> L = new AList<>();

L.addLast(5);

L.addLast(10);

L.addLast(15);

L.print();

​

For the rest of 61B, we encourage you to use Java’s built in List interface and ArrayList class!

​

List methods here.

​

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<Integer> L = new ArrayList<>();

L.add(5); L.add(10); L.add(15);

System.out.println(L);

​

List<Integer> L2 = Utils.readIntsFromFile(“somedata.csv”);

}

}

​

If we import, we can use the “simple name” (ArrayList) as opposed to the longer “canonical name” (java.util.ArrayList).

datastructur.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

Reflections on Course and

AMA 1

Reassurances Regarding 61B This Semester

Tilt was really hard for students with less experience!

• I hope it wasn’t too discouraging.
• Difficulty is very hard to tune early in the semester when skills are so wide.

​

One major mistake on our part: Not properly taking into account Labor Day. I’m calling this out so you don’t feel like you did something wrong.

• Issue 1: Generics taught on 9/7, but needed for original 9/9 due date for proj1a.
• Issue 2: ALists covered in lab 3, but not taught until the Friday after lab.

​

Unrelated issue: Proj 1a was not supposed to have .equals.

datastructur.es

Pacing

datastructur.es

Exam Studying Tips

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://fa22.datastructur.es/materials/guides/study-guide.html for more.

​

​

datastructur.es

One Last Note on Plagiarism

datastructur.es

Collaboration Policy

We have enumerated very specific rules whose violation will result in being reported to the office of student conduct:

• By You Alone: All project code that you submit (other than skeleton code) should be written by you (or your partner) alone, except for small snippets that solve tiny subproblems (examples in collaboration policy online).
• Do Not Possess or Share Code: Before a project deadline, you should never be in possession of solution code that you did not write (on paper, electronically, etc.). You are equally culpable if you share. DO NOT GIVE YOUR CODE TO ANYONE, EVEN IF THEY ARE DESPERATE. Also, don’t post on GitHub publicly!
• Cite Your Sources: When you receive significant assistance from someone else (with ideas, debugging, code-snippets from stack overflow etc.), you should cite that help somewhere in your source code as a comment that includes “@source”. You will not be penalized for receiving this help. ��

datastructur.es

Permissible But with Extreme Caution

• Helping someone debug (don’t touch their keyboard/mouse/other).
• Looking at someone else’s code to help them.
• Extra Dangerous: Looking at someone else’s code to understand something. If you do this, don’t write code anytime soon after looking at that code, your solution is going to gravitate straight to theirs.
• Ultra Danger: Working on a project alongside another person or group of people. Your code should not substantially resemble anyone else's!

​

Were it enforceable, I’d say no looking at other students’ code at all, but I want you to take these rules seriously (unlike, say, speed limits).

• The effect should be as if you’d never seen anyone’s else code at all.

datastructur.es

Plagiarism will (Probably) be Detected, and Dealt with Harshly

Plagiarism detection software is very sophisticated.

• Also easy to use!

​

​

Every semester we send 50-100 cases to the Office of Student Conduct.

• For some reason people don’t believe me. From 2017 incident reports: “To be honest, when Professor Hug said there is a way to detect plagiarism, I did not believe it. I believed there is no way to detect code similarity. I mean, how is that even possible.”

​

Please contact us if 61B is causing massive disruptions to your life. We are willing to give more slip days and can be flexible to accommodate you.

datastructur.es

datastructur.es

AMA (Time Permitting)

datastructur.es