Announcements
Wednesday lecture has no structured content.
Today’s content is not in scope for the midterm.
My office hours today moved to 3-4 PM (779 Soda).
More Inheritance
2
Lecture 9
CS61B, Spring 2023 @ UC Berkeley
Josh Hug and Justin Yokota
Rotating SLList
Lecture 9, CS61B, Spring 2023
The Extends Keyword
Implementation Inheritance
Type Checking and Casting
Higher Order Functions in Java
The Extends Keyword
When a class is a hyponym of an interface, we used implements.
If you want one class to be a hyponym of another class, you use extends.
We’d like to build RotatingSLList that can perform any SLList operation as well as:
Example: Suppose we have [5, 9, 15, 22].
List61B
SLList
AList
RotatingSLList
instead of an interface
RotatingSLList
Because of extends, RotatingSLList inherits all members of SLList:
Constructors are not inherited.
public class RotatingSLList<Blorp> extends SLList<Blorp>{
public void rotateRight() {
Blorp oldBack = removeLast();
addFirst(oldBack);
}
}
… but members may be private and thus inaccessible! More after midterm.
Vengeful SLList
Lecture 9, CS61B, Spring 2023
The Extends Keyword
Implementation Inheritance
Type Checking and Casting
Higher Order Functions in Java
Another Example: VengefulSLList
Suppose we want to build an SLList that:
public static void main(String[] args) {
VengefulSLList<Integer> vs1 = new VengefulSLList<Integer>();
vs1.addLast(1);
vs1.addLast(5);
vs1.addLast(10);
vs1.addLast(13); /* [1, 5, 10, 13] */
vs1.removeLast(); /* 13 gets deleted. */
vs1.removeLast(); /* 10 gets deleted. */
System.out.print("The fallen are: ");
vs1.printLostItems(); /* Should print 10 and 13. */
}
Another Example: VengefulSLList
public class VengefulSLList<Item> extends SLList<Item> {
private SLList<Item> deletedItems;
public VengefulSLList() {
deletedItems = new SLList<Item>();
}
@Override
public Item removeLast() {
Item oldBack = super.removeLast();
deletedItems.addLast(oldBack);
return oldBack;
}
public void printLostItems() {
deletedItems.print();
}
}
calls Superclass’s
version of removeLast()
Note: Java syntax disallows super.super. For a nice description of why, see this link.
A Boring Constructor Gotcha
Lecture 9, CS61B, Spring 2023
The Extends Keyword
Implementation Inheritance
Type Checking and Casting
Higher Order Functions in Java
Constructor Behavior Is Slightly Weird
Constructors are not inherited. However, the rules of Java say that all constructors must start with a call to one of the super class’s constructors [Link].
public VengefulSLList() {
deletedItems = new SLList<Item>();
}
public VengefulSLList() {
super();
deletedItems = new SLList<Item>();
}
These constructors are exactly equivalent.
must come first!
Calling Other Constructors
If you want to use a super constructor other than the no-argument constructor, can give parameters to super.
public VengefulSLList(Item x) {
super(x);
deletedItems = new SLList<Item>();
}
public VengefulSLList(Item x) {
deletedItems = new SLList<Item>();
}
calls SLList(Item x)
Not equivalent! Code to the right makes implicit call to super(), not super(x).
The Object Class
Lecture 9, CS61B, Spring 2023
The Extends Keyword
Implementation Inheritance
Type Checking and Casting
Higher Order Functions in Java
The Object Class
As it happens, every type in Java is a descendant of the Object class.
Dog
ShowDog
IntList
String[]
Object
String
WorkingDog
SledDog
DrugDog
SLList
VengefulSLList
Documentation for Object class: https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/lang/Object.html
Interfaces don’t extend Object:
http://docs.oracle.com/javase/specs/jls/se7/html/jls-9.html#jls-9.2
List61B
Object Methods
All classes are hyponyms of Object.
Thus every Java class has these methods. Amusingly clone is fundamentally broken.
Won’t discuss or use in 61B.
Coming in another lecture soon.
Coming later.
Is-A vs. Has-A, java.util.Stack
Lecture 9, CS61B, Spring 2023
The Extends Keyword
Implementation Inheritance
Type Checking and Casting
Higher Order Functions in Java
Is-a vs. Has-A
Important Note: extends should only be used for is-a (hypernymic) relationships!
Common mistake is to use it for “has-a” relationships. (a.k.a. meronymic).
SLList
VengefulLSLList extends SLList
printLostItems()
SLList
Set extends SLList
This is an abomination.
Example: Stack
The Stack abstract data type (ADT) supports the following operations:
The Java designers made a grave error when they wrote java.util.Stack.
4
6
2
pop()
Stack
push()
Is-a vs. Has-A
Example of a Has-A error in Java: The Stack class.
List
pop()
Stack extends Vector
push()
Vector
get()
…
A Vector is a slightly different version of an ArrayList.
Stack (if it had been done correctly using has-a)
Stacks are supposed to be simple:
Could have been implemented simply:
public class Stack<T> {
private LinkedList<T> items = new LinkedList<>();
public void push(T x) { items.addLast(x); }
public T pop() { return items.removeLast(); }
public int size() { return items.size();}
}
Stack (because it is-a Vector)
But java.util.Stack is:
Encapsulation
Lecture 9, CS61B, Spring 2023
The Extends Keyword
Implementation Inheritance
Type Checking and Casting
Higher Order Functions in Java
Complexity: The Enemy
When building large programs, our enemy is complexity.
Some tools for managing complexity:
Managing complexity supremely important for large projects (e.g. project 2).
Modules and Encapsulation [Shewchuk]
Module: A set of methods that work together as a whole to perform some task or set of related tasks.
A module is said to be encapsulated if its implementation is completely hidden, and it can be accessed only through a documented interface.
ArrayDeque
addLast(Item x)
removeLast()
size()
...
A Cautionary Tale
Interesting forum questions from extra credit assignment from a few years ago.
Bottom line: Testing a Deque should usually not involve ANY assumptions about how it is implemented beyond what the public interface tells you.
Abstraction Barriers
As the user of an ArrayDeque, you cannot observe its internals.
Java is a great language for enforcing abstraction barriers with syntax.
ArrayDeque
addLast(Item x)
removeLast()
size()
...
{5, 3, 1, 7, 22}
Modules and Encapsulation [Shewchuk]
Module: A set of methods that work together as a whole to perform some task or set of related tasks.
A module is said to be encapsulated if its implementation is completely hidden, and it can be accessed only through a documented interface.
ArrayDeque
addLast(Item x)
removeLast()
size()
...
Implementation Inheritance Breaks Encapsulation
Lecture 9, CS61B, Spring 2023
The Extends Keyword
Implementation Inheritance
Type Checking and Casting
Higher Order Functions in Java
Implementation Inheritance Breaks Encapsulation
Suppose we have a Dog class with the two methods shown.
public void bark() {
System.out.println("bark");
}
public void barkMany(int N) {
for (int i = 0; i < N; i += 1) {
bark();
}
}
Dog
bark()
barkMany(int N)
Dog.java
Implementation Inheritance Breaks Encapsulation
We could just as easily have implemented methods as shown below.
public void bark() {
barkMany(1);
}
public void barkMany(int N) {
for (int i = 0; i < N; i += 1) {
System.out.println("bark");
}
}
Dog
bark()
barkMany(int N)
Dog.java
http://yellkey.com/state
What would vd.barkMany(3) output?
(assuming vd is a Verbose Dog)
bark()
Dog
bark()
barkMany(int N)
VerboseDog
barkMany(int N)
@Override
public void barkMany(int N) {
System.out.println("As a dog, I say: ");
for (int i = 0; i < N; i += 1) {
bark();
}
}
calls inherited bark method
public void bark() {
System.out.println("bark");
}
public void barkMany(int N) {
for (int i = 0; i < N; i += 1) {
bark();
}
}
Dog.java
VerboseDog.java
Implementation Inheritance Breaks Encapsulation
What would vd.barkMany(3) output?
(assuming vd is a Verbose Dog)
bark()
Dog
bark()
barkMany(int N)
VerboseDog
barkMany(int N)
@Override
public void barkMany(int N) {
System.out.println("As a dog, I say: ");
for (int i = 0; i < N; i += 1) {
bark();
}
}
calls inherited bark method
public void bark() {
System.out.println("bark");
}
public void barkMany(int N) {
for (int i = 0; i < N; i += 1) {
bark();
}
}
Dog.java
VerboseDog.java
http://yellkey.com/reveal
What would vd.barkMany(3) output?
(assuming vd is a Verbose Dog)
bark()
Dog
bark()
barkMany(int N)
VerboseDog
barkMany(int N)
@Override
public void barkMany(int N) {
System.out.println("As a dog, I say: ");
for (int i = 0; i < N; i += 1) {
bark();
}
}
calls inherited bark method
public void bark() {
barkMany(1);
}
public void barkMany(int N) {
for (int i = 0; i < N; i += 1) {
System.out.println("bark");
}
}
Dog.java
VerboseDog.java
Implementation Inheritance Breaks Encapsulation
What would vd.barkMany(3) output?
c. Something else.
(assuming vd is a Verbose Dog)
bark()
Dog
bark()
barkMany(int N)
VerboseDog
barkMany(int N)
@Override
public void barkMany(int N) {
System.out.println("As a dog, I say: ");
for (int i = 0; i < N; i += 1) {
bark();
}
}
calls inherited bark method
public void bark() {
barkMany(1);
}
public void barkMany(int N) {
for (int i = 0; i < N; i += 1) {
System.out.println("bark");
}
}
Dog.java
VerboseDog.java
Type Checking and Casting
Lecture 9, CS61B, Spring 2023
The Extends Keyword
Implementation Inheritance
Type Checking and Casting
Higher Order Functions in Java
Dynamic Method Selection and Type Checking Puzzle
For each line of code, determine:
public static void main(String[] args) {
VengefulSLList<Integer> vsl =
new VengefulSLList<Integer>(9);
SLList<Integer> sl = vsl;
sl.addLast(50);
sl.removeLast();
sl.printLostItems();
VengefulSLList<Integer> vsl2 = sl;
}
VengefulSLList
VengefulSLList
Static Type
Dynamic Type
SLList
VengefulSLList
vsl
sl
VengefulSLList
SLList
Reminder: VengefulSLList overrides removeLast and provides a new method called printLostItems.
Reminder: Dynamic Method Selection
If overridden, decide which method to call based on run-time type of variable.
public static void main(String[] args) {
VengefulSLList<Integer> vsl =
new VengefulSLList<Integer>(9);
SLList<Integer> sl = vsl;
sl.addLast(50);
sl.removeLast();
}
Also called dynamic type.
VengefulSLList
VengefulSLList
Static Type
Dynamic Type
SLList
VengefulSLList
vsl
sl
VengefulSLList
SLList
VengefulSLList doesn’t override, uses SLList’s.
Uses VengefulSLList’s.
Reminder: VengefulSLList overrides removeLast and provides a new method called printLostItems.
Compile-Time Type Checking
Compiler allows method calls based on compile-time type of variable.
public static void main(String[] args) {
VengefulSLList<Integer> vsl =
new VengefulSLList<Integer>(9);
SLList<Integer> sl = vsl;
sl.addLast(50);
sl.removeLast();
sl.printLostItems();
}
Compilation error!
Also called static type.
VengefulSLList
VengefulSLList
Static Type
Dynamic Type
SLList
VengefulSLList
vsl
sl
VengefulSLList
SLList
Reminder: VengefulSLList overrides removeLast and provides a new method called printLostItems.
Compile-Time Type Checking
Compiler allows method calls based on compile-time type of variable.
Compiler also allows assignments based on compile-time types.
public static void main(String[] args) {
VengefulSLList<Integer> vsl =
new VengefulSLList<Integer>(9);
SLList<Integer> sl = vsl;
sl.addLast(50);
sl.removeLast();
sl.printLostItems();
VengefulSLList<Integer> vsl2 = sl;
}
Compilation errors!
VengefulSLList
VengefulSLList
Static Type
Dynamic Type
SLList
VengefulSLList
vsl
sl
VengefulSLList
SLList
Also called static type.
Compile-Time Types and Expressions
Expressions have compile-time types:
SLList<Integer> sl = new VengefulSLList<Integer>();
VengefulSLList<Integer> vsl = new SLList<Integer>();
Compilation error!
Compile-Time Types and Expressions
Expressions have compile-time types:
public static Dog maxDog(Dog d1, Dog d2) { … }
Poodle frank = new Poodle("Frank", 5);
Poodle frankJr = new Poodle("Frank Jr.", 15);
Dog largerDog = maxDog(frank, frankJr);
Poodle largerPoodle = maxDog(frank, frankJr);
Compilation error!
RHS has compile-time type Dog.
Example:
Casting
Java has a special syntax for specifying the compile-time type of any expression.
Tells compiler to pretend it sees a particular type.
maxDog(frank, frankJr);
(Poodle) maxDog(frank, frankJr);
Poodle frank = new Poodle("Frank", 5);
Poodle frankJr = new Poodle("Frank Jr.", 15);
Dog largerDog = maxDog(frank, frankJr);
Poodle largerPoodle = (Poodle) maxDog(frank, frankJr);
Compilation OK!
RHS has compile-time type Poodle.
Casting
Casting is a powerful but dangerous tool.
�If we run the code above, we get a ClassCastException at runtime.
Poodle frank = new Poodle("Frank", 5);
Malamute frankSr = new Malamute("Frank Sr.", 100);
Poodle largerPoodle = (Poodle) maxDog(frank, frankSr);
Higher Order Functions in Java
Lecture 9, CS61B, Spring 2023
The Extends Keyword
Implementation Inheritance
Type Checking and Casting
Higher Order Functions in Java
Higher Order Functions
Higher Order Function: A function that treats another function as data.
�
Example in Python:
def tenX(x):
return 10*x
def do_twice(f, x):
return f(f(x))
print(do_twice(tenX, 2))
200
Higher Order Functions in Java 7
Old School (Java 7 and earlier)
Can use an interface instead. Let’s try it out.
IntUnaryFunction
apply(int)
TenX
apply(int)
def tenX(x):
return 10*x
def do_twice(f, x):
return f(f(x))
print(do_twice(tenX, 2))
Higher Order Functions in Java 7
Old School (Java 7 and earlier)
Can use an interface instead: Java code below is equivalent to given python code.
def tenX(x):
return 10*x
public class TenX implements IntUnaryFunction {
public int apply(int x) {
return 10 * x;
}
}
public interface IntUnaryFunction {
int apply(int x);
}
Example: Higher Order Functions Using Interfaces in Java
def tenX(x):
return 10*x
def do_twice(f, x):
return f(f(x))
print(do_twice(tenX, 2))
public class HoFDemo {
public static int do_twice(IntUnaryFunction f, int x) {
return f.apply(f.apply(x));
}
public static void main(String[] args) {
System.out.println(do_twice(new TenX(), 2));
}
}
public class TenX implements IntUnaryFunction {
public int apply(int x) {
return 10 * x;
}
}
public interface IntUnaryFunction {
int apply(int x);
}
Example: Higher Order Functions in Java 8 or Later
In Java 8, new types were introduced: now can can hold references to methods.
public class Java8HoFDemo {
public static int tenX(int x) {
return 10*x;
}
public static int doTwice(Function<Integer, Integer> f, int x) {
return f.apply(f.apply(x));
}
public static void main(String[] args) {
int result = doTwice(Java8HoFDemo::tenX, 2);
System.out.println(result);
}
}
Implementation Inheritance Cheatsheet
VengefulSLList extends SLList means a VenglefulSLList is-an SLList. Inherits all members!
Invocation of overridden methods follows two simple rules:
Does not apply to overloaded methods!
Citations
https://wikids-life.wikispaces.com/file/view/LadybirdInheritance.jpg/160451153/604x297/LadybirdInheritance.jpg