代写代考 CS61B Lecture #25: Java Generics

程序代写 CS代考 / compiler, Java代写代考

CS61B Lecture #25: Java Generics
Last modified: Fri Oct 25 14:33:03 2019 CS61B: Lecture #25 1

The Old Days

Copyright By PowCoder代写 加微信 powcoder

• Java library types such as List didn’t used to be parameterized. All Lists were lists of Objects.
• So you’d write things like this:
for (int i = 0; i < L.size(); i += 1) { String s = (String) L.get(i); ... } • That is, must explicitly cast result of L.get(i) to let the compiler know what it is. • Also, when calling L.add(x), was no check that you put only Strings into it. • So, starting with 1.5, the designers tried to alleviate these per- ceived problems by introducing parameterized types, like List.
• Unfortunately, it is not as simple as one might think.
Last modified: Fri Oct 25 14:33:03 2019 CS61B: Lecture #25 2

Basic Parameterization
• From the definitions of ArrayList and Map in java.util:
public class ArrayList implements List { public Item get(int i) { … }
public boolean add(Item x) { … }
public interface Map {
Value get(Key x);
• First (blue) occurrences of Item, Key, and Value introduce formal type parameters, whose “values” (which are reference types) get substituted for all the other occurrences of Item, Key, or Value when ArrayList or Map is “called” (as in ArrayList, or ArrayList, or Map>).
• Other occurrences of Item, Key, and Value are uses of the formal types, just like uses of a formal parameter in the body of a function.
Last modified: Fri Oct 25 14:33:03 2019 CS61B: Lecture #25 3

Type Instantiation
• Instantiating a generic type is analogous to calling a function.
• Consider again
public class ArrayList implements List { public Item get(int i) { … }
public boolean add(Item x) { … }
• When we write ArrayList, we get, in effect, a new type,
somewhat like
public String ArrayList implements List { public String get(int i) { … }
public boolean add(String x) { … }
• And then, likewise, List refers to a new interface type as well.
Last modified: Fri Oct 25 14:33:03 2019 CS61B: Lecture #25 4

Parameters on Methods
• Functions (methods) may also be parameterized by type. Example of use from java.util.Collections:
/** A read-only list containing just ITEM. */
static List singleton(T item) { … } /** An unmodifiable empty list. */
static List emptyList() { … }
The compiler figures out T in the expression singleton(x) by look- ing at the type of x. This is a simple example of type inference.
• In the call
List empty = Collections.emptyList();
the parameters obviously don’t suffice, but the compiler deduces the parameter T from context: it must be assignable to String.
Last modified: Fri Oct 25 14:33:03 2019 CS61B: Lecture #25 5

• Consider the definition of something that counts the number of times something occurs in a collection of items. Could write this as
/** Number of items in C that are equal to X. */
static int frequency(Collection c, Object x) { int n; n = 0;
for(Ty:c) {
if (x.equals(y))
return n; }
• But we don’t really care what T is; we don’t need to declare anything of type T in the body, because we could write instead
for (Object y : c) {
• Wildcard type parameters say that you don’t care what a type pa- rameter is (i.e., it’s any subtype of Object):
static int frequency(Collection c, Object x) {…}
Last modified: Fri Oct 25 14:33:03 2019 CS61B: Lecture #25 6

Subtyping (I)
• What are the relationships between the types
List, List, ArrayList, ArrayList?
• We know that ArrayList ≼ List and String ≼ Object (using ≼ for “is a subtype of”). . .
• . . . So is List ≼ List?
Last modified: Fri Oct 25 14:33:03 2019 CS61B: Lecture #25 7

List LObj = LS; int[]A= { 1,2 }; LObj.add(A);
String S = LS.get(0);
// Legal, since A is an Object
// OOPS! A.get(0) is NOT a String, // but spec of List.get // says that it is.
Subtyping (II)
• Consider this fragment:
List LS = new ArrayList();
• So, having List ≼ List would violate type safety: The compiler is wrong about the type of a value.
• So in general for T1 ≼ T2, must have X = Y.
• But what about T1 and T2?
Last modified: Fri Oct 25 14:33:03 2019 CS61B: Lecture #25 8

Subtyping (III)
• Now consider
ArrayList ALS = new ArrayList();
List LS = ALS; // OK?? • In this case, everything’s fine:
– The object’s dynamic type is ArrayList.
– Therefore, the methods expected for LS must be a subset of
those for ALS.
– And since the type parameters are the same, the signatures of
those methods will be the same.
– Therefore, all the legal calls on methods of LS (according to the
compiler) will be valid for the actual object pointed to by LS. • In general, T1 ≼ T2 if T1 ≼ T2.
Last modified: Fri Oct 25 14:33:03 2019 CS61B: Lecture #25 9

A Java Inconsistency: Arrays
• The Java language design is not entirely consistent when it comes to subtyping.
• For the same reason that ArrayList ̸≼ ArrayList, you’d also expect that String[] ̸≼ Object[].
• And yet, Java does make String[] ≼ Object[].
• And, just as explained above, one gets into trouble with
String[] AS = new String[3]; Object[] AObj = AS;
AObj[0] = new int[] { 1, 2 }; // Bad
• So in Java, the Bad line causes an ArrayStoreException—a (dy- namic) runtime error instead of a (static) compile-time error.
• Why do it this way? Basically, because otherwise there’d be no way to implement, e.g., ArrayList.
Last modified: Fri Oct 25 14:33:03 2019 CS61B: Lecture #25 10

Type Bounds (I)
• Sometimes, your program needs to ensure that a particular type pa- rameter is replaced only by a subtype (or supertype) of a particular type (sort of like specifying the “type of a type.”).
• For example,
class NumericSet extends HashSet { /** My minimal element */
T min() { … }
Requires that all type parameters to NumbericSet must be subtypes of Number (the “type bound”). T can either extend or implement the bound, as appropriate.
Last modified: Fri Oct 25 14:33:03 2019 CS61B: Lecture #25 11

Type Bounds (II)
• Another example:
/** Set all elements of L to X. */
static void fill(List L, T x) { … }
means thatLcan be aListfor anyQas long asTis a subtype of
(extends or implements) Q.
• Why didn’t the library designers just define this as
/** Set all elements of L to X. */
static void fill(List L, T x) { … } ?
Last modified: Fri Oct 25 14:33:03 2019
CS61B: Lecture #25 12

Type Bounds (II)
• Another example:
/** Set all elements of L to X. */
static void fill(List L, T x) { … }
means thatLcan be aListfor anyQas long asTis a subtype of
(extends or implements) Q.
• Why didn’t the library designers just define this as
/** Set all elements of L to X. */
static void fill(List L, T x) { … } ?-
• Consider
static void blankIt(List L) { fill(L, ” “);
This would be illegal if L were forced to be a List.
Last modified: Fri Oct 25 14:33:03 2019 CS61B: Lecture #25 13

Type Bounds (III)
• And one more:
/** Search sorted list L for KEY, returning either its position (if * present), or k-1, where k is where KEY should be inserted. */
static int binarySearch(List> L, T key)
• Here, the items of L have to have a type that is comparable to T’s or to some supertype of T.
• Does L have to be able to contain the value key?
• Why does this make sense?
Last modified: Fri Oct 25 14:33:03 2019 CS61B: Lecture #25 14

Type Bounds (III)
• And one more:
/** Search sorted list L for KEY, returning either its position (if * present), or k-1, where k is where KEY should be inserted. */
static int binarySearch(List> L, T key)
• Here, the items of L have to have a type that is comparable to T’s or to some supertype of T.
• Does L have to be able to contain the value key?
• Why does this make sense?
• As long as the items in L can be compared to key, it doesn’t really matter whether they might include key (not that this is often use- ful).
Last modified: Fri Oct 25 14:33:03 2019 CS61B: Lecture #25 15

Dirty Secrets Behind the Scenes
• Java’s design for parameterized types was constrained by a desire for backward compatibility.
• Actually, when you write
class Foo { T x;
T mogrify(T y) { … } Java really gives you
class Foo { Object x;
Object mogrify(Object y) { … }
That is, it supplies the casts automatically, and also throws in some additional checks. If it can’t guarantee that all those casts will work, gives you a warning about “unsafe” constructs.
Foo q = new Foo();
Integer r = q.mogrify(s);
Foo q = new Foo();
Integer r =
(Integer) q.mogrify((Integer) s);
Last modified: Fri Oct 25 14:33:03 2019 CS61B: Lecture #25 16

Limitations
Because of Java’s design choices, there are some limitations to generic programming:
• Since all kinds of Foo or List are really the same,
– L instanceof List will be true when L is a List.
– Inside, e.g., class Foo, you cannot write new T(), new T[], or x instanceof T.
• Primitive types are not allowed as type parameters.
– Can’t have ArrayList, just ArrayList.
– Fortunately, automatic boxing and unboxing makes this substitu- tion easy:
int sum(ArrayList L) { intN; N=0;
for(intx:L) { N+=x; }
return N; }
– Unfortunately, boxing and unboxing have significant costs.
Last modified: Fri Oct 25 14:33:03 2019 CS61B: Lecture #25 17

程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts