Testing, and Debugging
Some reflections from TAs in office hours regarding struggling students:
¡ñ ¡°I feel like they get stuck trying to figure it out by looking at their code instead of trying to get proactive and poke at their code¡±
¡ñ ¡°They’re checking that their code makes sense; sometimes they can’t see the bug until it’s being run.¡±
In lab 3, we talked about how debugging should be a scientific process.
¡ñ Reading and re-reading your code is very very slow. It¡¯s like trying to chop down a tree with a nail file. Yes, you¡¯ll eventually succeed, but there are much better tools.
Using the debugger (especially with tests!) is incredibly important.
datastructur.es
CS61B, 2021
Lecture 9: More Inheritance!
¡ñ Implementation Inheritance: Extends ¡ñ Encapsulation
¡ñ Casting
¡ñ Higher Order Functions in Java
datastructur.es
Implementation Inheritance: Extends
datastructur.es
The Extends Keyword
When a class is a hyponym of an interface, we used implements. ¡ñ Example: SLList
instead of an interface
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:
¡ñ rotateRight(): Moves back item the front.
Example: Suppose we have [5, 9, 15, 22]. ¡ñ After rotateRight: [22, 5, 9, 15]
List61B
AList
SLList
RotatingSLList
datastructur.es
RotatingSLList
public class RotatingSLList
Blorp oldBack = removeLast();
addFirst(oldBack);
}
}
Because of extends, RotatingSLList inherits all members of SLList:
¡ñ All instance and static variables.
¡ñ All methods.
¡ñ All nested classes.
Constructors are not inherited.
… but members may be private and thus inaccessible! More after midterm.
datastructur.es
Another Example: VengefulSLList
Suppose we want to build an SLList that:
¡ñ Remembers all Items that have been destroyed by removeLast.
¡ñ Has an additional method printLostItems(), which prints all deleted
items.
public static void main(String[] args) {
VengefulSLList
vs1.addLast(5);
vs1.addLast(10);
vs1.addLast(13);
vs1.removeLast();
vs1.removeLast();
System.out.print(“The fallen are: “);
vs1.printLostItems(); /* Should print 10 and 13. */
}
/* [1, 5, 10, 13] */
/* 13 gets deleted. */
/* 10 gets deleted. */
datastructur.es
Another Example: VengefulSLList
public class VengefulSLList
public VengefulSLList() {
deletedItems = new SLList
@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.
datastructur.es
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].
¡ñ Idea: If every VengefulSLList is-an SLList, every VengefulSLList must be set up like an SLList.
¡ð If you didn¡¯t call SLList constructor, sentinel would be null. Very bad.
¡ñ You can explicitly call the constructor with the keyword super (no dot).
¡ñ If you don¡¯t explicitly call the constructor, Java will automatically do it for you.
These constructors are exactly equivalent.
public VengefulSLList() { deletedItems = new SLList
}
public VengefulSLList() {
super(); must come first! deletedItems = new SLList
}
datastructur.es
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); calls SLList(Item x)
deletedItems = new SLList
public VengefulSLList(Item x) { deletedItems = new SLList
}
Not equivalent! Code to the right makes implicit call to super(), not super(x).
datastructur.es
The Object Class
As it happens, every type in Java is a descendant of the Object class.
¡ñ VengefulSLList extends SLList.
¡ñ SLList extends Object (implicitly).
String
String[]
Object
IntList
WorkingDog
DrugDog
List61B
Dog SLList
ShowDog VengefulSLList
Documentation for Object class:
https://docs.oracle.com/javase/9/ docs/api/java/lang/Object.html
Interfaces don¡¯t extend Object:
http://docs.oracle.com/javase/specs/jls/se7/html/jls-9.html#jls-9.2
SledDog
datastructur.es
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).
¡ñ Possible to subclass SLList to build a Set, but conceptually weird, e.g. get(i) doesn¡¯t make sense, because sets are not ordered.
SLList
SLList
Set extends
SLList
VengefulLSLList
extends SLList
printLostItems()
This is an abomination.
datastructur.es
Encapsulation
datastructur.es
Complexity: The Enemy
When building large programs, our enemy is complexity. Some tools for managing complexity:
¡ñ Hierarchical abstraction.
¡ð Create layers of abstraction, with clear abstraction barriers!
¡ñ ¡°Design for change¡± (D. Parnas)
¡ð Organize program around objects.
¡ð Let objects decide how things are done.
¡ð Hide information others don¡¯t need.
Managing complexity supremely important for large projects (e.g. project 2).
datastructur.es
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.
addLast(Item x)
removeLast()
ArrayDeque
size()
…
datastructur.es
A Cautionary Tale
Interesting Piazza questions from proj1gold from a few years ago.
datastructur.es
Abstraction Barriers
As the user of an ArrayDeque, you cannot observe its internals.
¡ñ Even when writing tests, you don¡¯t (usually) want to peer inside.
addLast(Item x)
removeLast()
ArrayDeque
size()
…
Java is a great language for enforcing abstraction barriers with syntax.
{5, 3, 1, 7, 22}
datastructur.es
Implementation
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.
¡ñ Instance variables private. Methods like resize private.
¡ñ As we¡¯ll see: Implementation inheritance (e.g. extends) breaks encapsulation!
addLast(Item x)
removeLast()
ArrayDeque
size()
…
datastructur.es
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.java
bark()
Dog
barkMany(int N)
datastructur.es
Implementation Inheritance Breaks Encapsulation
We could just as easily have implemented methods as shown below.
¡ñ From the outside, functionality is exactly the same, it¡¯s just a question of aesthetics.
public void bark() { barkMany(1);
}
public void barkMany(int N) {
for (int i = 0; i < N; i += 1) {
System.out.println("bark");
}
}
Dog.java
bark()
Dog
barkMany(int N)
datastructur.es
http://yellkey.com/point
What would vd.barkMany(3) output?
a. As a dog, I say: bark bark bark
b. bark bark bark
public void bark() { System.out.println("bark");
}
public void barkMany(int N) {
for (int i = 0; i < N; i += 1) { bark();
} }
Dog.java
c. Something else. (assuming vd is a Verbose Dog)
bark()
Dog
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
VerboseDog.java
}
bark()
VerboseDog
barkMany(int N)
}
datastructur.es
Implementation Inheritance Breaks Encapsulation
What would vd.barkMany(3) output?
a. As a dog, I say: bark bark bark
public void bark() { System.out.println("bark");
}
public void barkMany(int N) {
for (int i = 0; i < N; i += 1) { bark();
} }
Dog.java
b. bark bark bark
c. Something else.
(assuming vd is a Verbose Dog)
bark()
Dog
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
VerboseDog.java
}
bark()
VerboseDog
barkMany(int N)
}
datastructur.es
http://yellkey.com/soon
What would vd.barkMany(3) output?
a. As a dog, I say: bark bark bark
b. bark bark bark
public void bark() { barkMany(1);
}
public void barkMany(int N) {
for (int i = 0; i < N; i += 1) { System.out.println("bark");
} }
Dog.java
c. Something else. (assuming vd is a Verbose Dog)
bark()
Dog
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
VerboseDog.java
}
bark()
VerboseDog
barkMany(int N)
}
datastructur.es
Implementation Inheritance Breaks Encapsulation
What would vd.barkMany(3) output?
c. Something else.
¡ñ Gets caught in an infinite loop! (assuming vd is a Verbose Dog)
@Override
public void barkMany(int N) { System.out.println("As a dog, I say: "); for (int i = 0; i < N; i += 1) {
public void bark() { barkMany(1);
}
public void barkMany(int N) {
for (int i = 0; i < N; i += 1) { System.out.println("bark");
} }
Dog.java
bark()
Dog
barkMany(int N)
}
bark();
calls inherited bark method
VerboseDog.java
bark()
VerboseDog
barkMany(int N)
}
datastructur.es
Type Checking and Casting
datastructur.es
Dynamic Method Selection and Type Checking Puzzle
For each line of code, determine:
¡ñ ¡ñ
vsl sl
Does that line cause a compilation error?
Which method does dynamic method selection use?
public static void main(String[] args) { VengefulSLList
new VengefulSLList
sl.addLast(50);
sl.removeLast();
sl.printLostItems();
VengefulSLList
}
Static Type
VengefulSLList
SLList
Dynamic Type
VengefulSLList
VengefulSLList
Vengeful
SLList
SLList
Reminder: VengefulSLList overrides removeLast and provides a new method called printLostItems.
datastructur.es
Reminder: Dynamic Method Selection
Also called dynamic type.
If overridden, decide which method to call based on run-time type of variable.
¡ñ
sl¡¯s runtime type: VengefulSLList.
vsl sl
Static Type
VengefulSLList
SLList
Dynamic Type
VengefulSLList
VengefulSLList
Vengeful
SLList
SLList
Reminder: VengefulSLList overrides removeLast and provides a new method called printLostItems.
datastructur.es
public static void main(String[] args) { VengefulSLList
new VengefulSLList
sl.addLast(50);
sl.removeLast();
VengefulSLList doesn¡¯t override, uses SLList¡¯s.
Uses VengefulSLList¡¯s.
}
Compile-Time Type Checking
Also called static type.
Compiler allows method calls based on compile-time type of variable.
¡ñ ¡ñ
vsl sl
sl¡¯s runtime type: VengefulSLList. But cannot call printLostItems.
Static Type
VengefulSLList
SLList
Dynamic Type
VengefulSLList
VengefulSLList
Vengeful
SLList
SLList
Reminder: VengefulSLList overrides removeLast and provides a new method called printLostItems.
datastructur.es
public static void main(String[] args) { VengefulSLList
new VengefulSLList
sl.addLast(50);
sl.removeLast();
sl.printLostItems();
}
Compilation error!
Compile-Time Type Checking
Also called static type.
Compiler allows method calls based on compile-time type of variable.
¡ñ ¡ñ
vsl sl
sl¡¯s runtime type: VengefulSLList. But cannot call printLostItems.
Static Type
VengefulSLList
SLList
Dynamic Type
VengefulSLList
VengefulSLList
Vengeful
SLList
SLList
Compiler also allows assignments based on compile-time types.
¡ñ Even though sl¡¯s runtime-type is VengefulSLList, cannot assign to vsl2.
¡ñ Compiler plays it as safe as possible with type checking.
datastructur.es
public static void main(String[] args) { VengefulSLList
new VengefulSLList
sl.addLast(50);
sl.removeLast();
sl.printLostItems();
Compilation errors!
VengefulSLList
}
Compile-Time Types and Expressions
Expressions have compile-time types:
¡ñ An expression using the new keyword has the specified compile-time type.
SLList
¡ñ Compile-time type of right hand side (RHS) expression is VengefulSLList.
¡ñ A VengefulSLList is-an SLList, so assignment is allowed. VengefulSLList
¡ñ Compile-time type of RHS expression is SLList.
¡ñ An SLList is not necessarily a VengefulSLList, so compilation error results.
Compilation error!
datastructur.es
Compile-Time Types and Expressions
Expressions have compile-time types:
¡ñ Method calls have compile-time type equal to their declared type.
public static Dog maxDog(Dog d1, Dog d2) { … } ¡ñ Any call to maxDog will have compile-time type Dog!
Example:
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.
datastructur.es
Casting
Java has a special syntax for specifying the compile-time type of any expression.
¡ñ Put desired type in parenthesis before the expression. ¡ñ Examples:
maxDog(frank, frankJr);
¡ð Compile-time type Poodle: (Poodle) maxDog(frank, frankJr);
¡ð Compile-time type Dog:
Tells compiler to pretend it sees a particular type.
Compilation OK!
RHS has compile-time type Poodle.
Poodle frank = new Poodle(“Frank”, 5);
Poodle frankJr = new Poodle(“Frank Jr.”, 15);
Dog largerDog = maxDog(frank, frankJr);
Poodle largerPoodle = (Poodle) maxDog(frank, frankJr);
datastructur.es
Casting
Casting is a powerful but dangerous tool.
¡ñ Tells Java to treat an expression as having a different compile-time type.
¡ñ In example below, effectively tells the compiler to ignore its type checking
duties.
¡ñ Does not actually change anything: sunglasses don¡¯t make the world dark.
Poodle frank = new Poodle(“Frank”, 5);
Malamute frankSr = new Malamute(“Frank Sr.”, 100);
Poodle largerPoodle = (Poodle) maxDog(frank, frankSr);
If we run the code above, we get a ClassCastException at runtime. ¡ñ So much for .class files being verifiably type checked…
datastructur.es
Dynamic Method Selection and Casting Puzzle
datastructur.es
Is it Overriding? Overloading?
public class Bird {
public void gulgate(Bird b) {
System.out.println(“BiGulBi”); }}
public class Falcon extends Bird { public void gulgate(Falcon f) {
System.out.println(“FaGulFa”);}}
Bird bird = new Falcon(); Falcon falcon = (Falcon) bird; bird.gulgate(falcon); falcon.gulgate(falcon);
What gets printed?
a. BiGulBi BiGulBi
b. BiGulBi FaGulFa
c. FaGulFa BiGulBi
d. FaGulFa FaGulFa
datastructur.es
Is it Overriding? Overloading?
public class Bird {
public void gulgate(Bird b) {
System.out.println(“BiGulBi”); }}
public class Falcon extends Bird { public void gulgate(Falcon f) {
System.out.println(“FaGulFa”);}}
Casting causes no change to the bird variable, nor to the object the bird variable points at!
Bird bird = new Falcon(); Falcon falcon = (Falcon) bird; bird.gulgate(falcon); falcon.gulgate(falcon);
What gets printed?
b. BiGulBi FaGulFa
datastructur.es
Why does BiGulBi get printed first?
An earlier version of this slide said ¡°since there is no overriding.¡±
public class Bird {
public void gulgate(Bird b) {
System.out.println(“BiGulBi”); }}
public class Falcon extends Bird { public void gulgate(Falcon f) {
System.out.println(“FaGulFa”);}}
Bird bird = new Falcon(); Falcon falcon = (Falcon) bird; bird.gulgate(falcon);
Remember: The compiler chooses the most specific matching method signature from the static type of the invoking class.
¡ñ Falcon is overloading the gulgate method, not overriding.
¡ñ Compiler basically thinks ¡°does Bird class have a gulgate method? Yes! I¡¯ll use
that¡±. Since there is no overriding, no dynamic method selection occurs.
datastructur.es
Higher Order Functions (A First Look)
datastructur.es
Higher Order Functions
Higher Order Function: A function that treats another function as data. ¡ñ e.g. takes a function as input.
Example in Python:
def tenX(x): return 10*x
def do_twice(f, x): return f(f(x))
print(do_twice(tenX, 2))
200
datastructur.es
Higher Order Functions in Java 7
Old School (Java 7 and earlier)
¡ñ Fundamental issue: Memory boxes (variables) cannot contain pointers to functions.
Can use an interface instead. Let¡¯s try it out.
def tenX(x): return 10*x
def do_twice(f, x): return f(f(x))
print(do_twice(tenX, 2))
IntUnaryFunction
apply(int)
TenX
apply(int)
datastructur.es
Higher Order Functions in Java 7
Old School (Java 7 and earlier)
¡ñ Fundamental issue: Memory boxes (variables) cannot contain pointers to functions.
Can use an interface instead: Java code below is equivalent to given python code.
public interface IntUnaryFunction { int apply(int x);
}
public class TenX implements IntUnaryFunction { public int apply(int x) {
return 10 * x; }
}
def tenX(x): return 10*x
datastructur.es
Example: Higher Order Functions Using Interfaces in Java
datastructur.es
def tenX(x): return 10*x
def do_twice(f, x): return f(f(x))
print(do_twice(tenX, 2))
public interface IntUnaryFunction { int apply(int x);
}
public class TenX implements IntUnaryFunction { public int apply(int x) {
return 10 * x; }
}
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));
} }
Example: Higher Order Functions in Java 8 or Later
In Java 8, new types were introduced: now can can hold references to methods.
¡ñ You¡¯re welcome to use these features, but we won¡¯t teach them.
¡ñ Why? The old way is still widely used, e.g. Comparators (see next lecture).
public class Java8HoFDemo {
public static int tenX(int x) {
return 10*x; }
public static int doTwice(Function
}
public static void main(String[] args) {
int result = doTwice(Java8HoFDemo::tenX, 2);
System.out.println(result);
}
}
datastructur.es
Implementation Inheritance Cheatsheet
VengefulSLList extends SLList means a VenglefulSLList is-an SLList. Inherits all members!
¡ñ Variables, methods, nested classes.
¡ñ Not constructors.
¡ñ Subclass constructor must invoke superclass constructor first.
¡ñ Use super to invoke overridden superclass methods and constructors.
Invocation of overridden methods follows two simple rules:
¡ñ Compiler plays it safe and only lets us do things allowed by static type.
¡ñ For overridden methods the actual method invoked is based on dynamic type
of invoking expression, e.g. Dog.maxDog(d1, d2).bark();
¡ñ Can use casting to overrule compiler type checking.
Does not apply to overloaded methods!
datastructur.es
Extra Problem Just For Fun
datastructur.es
Type Checking Quiz!
1. What is the static type of Dog.maxDog(dogC, dog D)? 2. Which (if any), will compile:
3. How many memory boxes are there in the code below? What are the dynamic types of their contents?
datastructur.es
Citations
https://wikids-life.wikispaces.com/file/view/LadybirdInheritance.jpg/16045115 3/604×297/LadybirdInheritance.jpg
datastructur.es
Actual truth:
size items
5
5
3
1
7
22
-1
3
0
…
0
0
0
0 1 2 3 4 5 6 7 97 98 99
datastructur.es