Stuff you want to cover on Wednesday, September 20

• Casting
• DMS (static and dynamic types) - 2 votes
• Summary and comparison of all Lists
• Higher-order functions, syntax of calling them
• How to approach skeleton code

Monday, September 18 pre-lecture 11 Q&A

• Hardest question on the midterm?
• The bonus question. Worth 0 points.
• Hard to say more, since we've seen the midterm.
• What do students struggle with the most?
• The topics on the previous slide is a good shortlist.
• Template(?) of the midterm
• There's a logistics post on Ed
• Do we need to know the syntax for writing test cases?
• If needed, we will provide syntax.

Casting and Dynamic Method Selection (DMS)

When we press "play" on a Java program, two separate steps happen:

Compilation (all errors here are compiler errors):

• Checks for syntax errors
• Puts together a list of methods/attributes of every class
• If a class extends another class, inherit all the methods that aren't overridden
• If a class implements an interface, inherit all the default methods, and check to make sure that all abstract methods are overridden
• If a method is overloaded, both versions are kept (overrides must have the same name AND the same arguments, which collectively forms the function signature)
• Assigns a static type to every variable
• Usually the type that the variable was declared as
• But if a typecast occurs (and it's theoretically possible), use the casted type

Casting and Dynamic Method Selection (DMS)

When we press "play" on a Java program, two separate steps happen:

Compilation (all errors here are compiler errors):

• Checks for syntax errors
• Puts together a list of methods/attributes of every class
• Assigns a static type to every variable
• Checks each line in isolation to see if there's a way to run that line
• Assumes the static type of every variable
• Assigns a function signature from the calling class to each function call
• If calling an overloaded method, assign the most specific signature that applies
• If "most specific" is ambiguous, error. (Out of scope)
• After all checks, converts the code to a computer-friendly language so it can actually be run.
• Note: Only happens once normally. After compiling once, you can run the same code repeatedly without going through the checks above, so it's faster

Casting and Dynamic Method Selection (DMS)

When we press "play" on a Java program, two separate steps happen:

Runtime (all errors here are Runtime Errors)

• Actually runs the program
• Relies on the dynamic type of the object (what the object was created as)
• On a function call, uses the method in the dynamic type's class with the same signature locked in during compilation
• Finds any illegal actions that can't be found by static type analysis
• If we lied in compilation about a typecast (ex. (Poodle) new Dog()), error
• Array out of bounds errors, out of memory errors, etc.

Note: The hardest parts of DMS are considered out of scope for this class. Discussion teaches a single-pass approach with a flowchart, while we show here a two-pass approach (compiler, then runtime). In general, the single pass is wrong on a few edge cases, while the two-pass approach works always. I believe that the flowchart yields the same results as the two-pass approach on any example we consider in scope. But this is closer to what actually happens.

Example

https://drive.google.com/file/d/1S_Fyvyz50DFikHwMcOBcRuFGIZoQMmGK/view

​

https://drive.google.com/file/d/1ooKS9xu6ojQ926axtwdsHM5vbBUh3ylh/view?pli=1

​

A List of Lists

Two main types:

Linked List:

• "Naked" Linked List
• Consists of a value, and a pointer to the next element
• Deprecated; almost never used in Java
• Singly Linked List
• Stores a naked Linked List in an internal Node class, then "clothes" the List in the List interface
• Only lets you move forward in the list, so less useful than DLL
• Adds a sentinel so you don't need to worry about "empty list" edge case
• Doubly Linked List
• Same as SLL, except each element stores a previous as well

A List of Lists

Two main types:

Linked List:

• Singly Linked List
• Doubly Linked List

Array List:

• Default array
• Natively supported by Java (not a class)
• Need to specify the length before using, and can't change that length
• Not a List (because it can't grow indefinitely)
• ArrayList
• List type that uses an array in the backend
• Requires resizing periodically in order to account for the List interface
• On average, constant time access (instead of linear time access in Linked List)

A List of Lists

List-like Interfaces (Not all in scope yet):

• List: get, set, size
• Queue: Like a list, except you can only take from the front and put in the back (think a queue of people)
• Stack: Like a list, except you can only take from the front and put in the front (think a stack of papers)
• Deque: Double-ended queue: Like a list, except you can take from/add to the front and back

Example (+ How to approach Skeleton Code)

https://drive.google.com/file/d/14-IEeTJsYHvK6Ogyro4xcDT8KH_KbB9A/view

​

Higher Order Functions

Unlike Python, Java has no native support for HOFs (at least the version we teach; later versions introduce lambdas).

Instead, we create a "dummy" class whose sole purpose is to run a function.

Ex. We create a class UnaryFunction<K,V> that has one method: public V apply(K input)

To create the equivalent of Python's lambda x: x*x, we make a class SquareFunction implements UnaryFunction<Integer, Integer> with the apply function: public Integer apply(Integer x) {return x*x;}

Two main types of HOFs we talk about: Comparators and Iterators

Comparators

Designed to compare two values: either a < b, a = b, or a > b.

• For ease of use, comparisons return an int, negative if a < b, 0 if a = b, and positive if a > b

Two comparison-based interfaces:

Comparable<T> if you want to compare to a particular type

• Also useful to make a "default" comparison method.
• ex. public class Dog implements Comparable<Dog> creates a Dog class that can compare itself against other dogs

Comparator<T> if you want a machine that can compare two items of a given type

• Often used when there's no "canonical ordering" of the items
• ex. You can order Dogs by size, by name, or by any number of things, so you make a new Comparator machine for each ordering you want.
• Often declared as inner classes

Comparators

In order for comparators to be considered valid, it must follow the following well-ordering principles:

• If a < b, then b > a. If a = b, then b = a (symmetry)
• a = a (reflexivity)
• If a < b and b < c, then a < c (transitivity)

Don't worry too much about this for now, but it'll be relevant once we get into sorts (if these aren't true, there's not necessarily a valid way to sort a set of values)

Iterators

Designed to iterate over a collection of values

• Used in the enhanced for loop (for(int i: intlist))

Two iteration-based interfaces:

Iterable<T>

• Tells the compiler that this class can be iterated over (and used in enhanced for loops)
• Requires only one function: public Iterator<T> iterator(), which returns an iterator on the elements of the class.

Iterator<T>

• The actual machine that iterates over objects
• Requires two functions:
• public boolean hasNext(), which returns if there's more to return
• public T next(), which returns the next item
• Similar to generators in Python, and can also be used in the same way (without a corresponding iterable object)

Example

https://drive.google.com/file/d/1-pPuHGuw0anqwnLh3nc_8z2Alqqcnpi5/view

Note: Iterators are sometimes covered after MT1 in past semesters of 61B.

So they tend to be in MT2, and then used in combination with other MT2 content.