Transcript Introduction to Computer Science I

Technische Universität Darmstadt
Telecooperation/RBG
Introduction to Computer Science I
Topic 17: Type Conversions, Generics
Prof. Dr. Max Mühlhäuser
Dr. Guido Rößling
Copyrighted material; for TUD student use only
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
Type Conversions
With static typing, there are many contexts in which
values of a specific type are expected
– In “a = expression”, we expect expression to have a
subtype of the type of a
– In “a + b”, we expect that either a and b are both int, both
float or double, or both Strings
– In “f(a, b)”, we expect the types of the arguments to match
those of the formal parameters
Introduction to Computer Science I: T18
2
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
Kinds of Type Conversions in Java
• Identity conversion – from a type to itself
– It is OK to insert a redundant cast
• Widening primitive conversion – a primitive type to a
‘wider’ type
– e.g., byte to int (without loss of information)
– e.g., int to double (possibly losing information)
• Narrowing primitive conversion – a primitive type to a
‘narrower’ type
– e.g., int to byte (discards higher-order bits)
– e.g., float to int
Introduction to Computer Science I: T18
3
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
Kinds of Type Conversions in Java
• Widening reference conversion
– Given reference types A, B, A can be widened to B iff A is a subtype of
B.
– Widening conversions are always performed at compile time and never
throw an exception.
• Narrowing reference conversion
– Given reference types A, B, A can be narrowed to B iff B is a subtype
of A.
– Narrowing conversions are always checked at run-time and may throw a
runtime exception.
Introduction to Computer Science I: T18
4
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
Kinds of Type Conversions in Java II
• String conversion
– Each type can be converted to String
– Implicitly, the method toString() is called (from java.lang.Object)
– We have used this, e.g. for System.out.println(myObject)
• Boxing and unboxing conversion
– From byte to Byte, int to Integer etc. and vice versa
• Unchecked conversion
– A conversion that may lead to an error or issue a compiler warning
– E.g., convert a “raw type” to a parameterized type
Introduction to Computer Science I: T18
5
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
Conversion contexts
• Assignment conversion: v = expr
– convert the type of expr to the type of v
– Limited to conversions that do not raise exceptions
• Method invocation conversion: expr.method(expr’)
– convert the types of the arguments
– Limited to conversions that do not raise exceptions
• Casting conversion: (T)expr
– convert the type of expr to T
– May also use narrowing reference conversion
• Numeric promotion
– Brings the operands of a numeric operator to a common type so that an
operation can be performed
• Allow identity, primitive widening and unboxing conversion
• e.g., 4 + 2.0  6.0
Introduction to Computer Science I: T18
6
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
Narrowing
• Casting can cause (static) type information to be lost:
// o refers to a Circle; widening is OK
GraphicObject o = new Circle(5, 12, 4);
Circle c1 = o; // compile-time error -- cannot narrow!
• Type information can be recovered at run-time by explicit
tests and casts:
if (o instanceof Circle) { // run-time test
c1 = (Circle)o; // explicit run-time narrowing OK
}
Introduction to Computer Science I: T18
7
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
Collections Revisited
• A Collection should apply to more than one type
– One implementation should be usable for several uses
– Generic collection behavior does not depend on
element type
• It should guarantee a specific element type
– Assume we use a collection only for Person objects
– It should be possible to obtain Person objects
without narrowing from Object
Introduction to Computer Science I: T18
8
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
Collections Revisited
List myIntList = new LinkedList(); // 1
myIntList.add(new Integer(0)); // 2
Integer x = (Integer)myIntList.get(0); // 3
• The cast in line 3 is annoying but essential
– Java only guarantees the result to be of type Object
– It may or may not be of type Integer
• Therefore, we could get a type error without the cast
• In our example, the cast is not checked by instanceof 
• We could be mistaken and receive something else
List myIntList = new LinkedList(); // 1
myIntList.add("Hello World"); // 2’
Integer x = (Integer)myIntList.get(0); // 3
– We now receive a ClassCastException at run-time!
Introduction to Computer Science I: T18
9
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
Expressing Intent Using Generics
• We need to tell Java more about our intention
– “This List will only contain elements conforming to Integer”
• To do so, we need to:
– Adapt the declaration of the List: List<Integer>
– Adapt the construction of the List: new LinkedList<Integer>
• Benefits:
– We can drop the type cast in line 3
– Non-matching types cannot be inserted or retrieved
List<Integer> myIntList = new LinkedList<Integer>(); // 1
myIntList.add(new Integer(0)); // 2
Integer x = myIntList.get(0); // 3
myIntList.add("Hello World"); // compile-time error
Introduction to Computer Science I: T18
10
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
What has Changed?
• myIntList is now a List<Integer>
– Not “some“ List, but a List of Integer instances
– We no longer need to cast the result to Integer
• We can also no longer store other types into the List
myIntList.add("Hello World");
The method add(Integer) in the type List<Integer>
is not applicable for the arguments (String)
• The Java compiler (and Eclipse) will prevent this
Introduction to Computer Science I: T18
11
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
What’s the Big Deal?
• It may seem that we have not accomplished much
– The declaration and construction of the list are longer
– We have only dropped the cast
• However, there is a large difference!
– The compiler can now check the type correctness
– The declaration of myIntList specifies the variable’s type
– The compiler will check that all accesses respect that type
• Why is this different from a simple cast?
– With a cast, the programmer says “the type should conform to
the cast to X here”
• Should be checked by instanceof
– Generic declaration states “this always conforms to type X”
Introduction to Computer Science I: T18
12
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
Lists Again
• Here is how List and Iterator are defined in java.util:
public interface List<E> {
void add(E x);
Iterator<E> iterator();
}
public interface Iterator<E> {
E next();
boolean hasNext();
void remove();
}
• This should look familiar (see T15)
• Except for <E> and E itself
• This is the declaration of the formal type parameter
• You can use these types almost everywhere
Introduction to Computer Science I: T18
13
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
List<Integer> vs. IntegerList
• We used List<Integer>, but there is only a List<E>?
• The E is a formal parameter
– Just like the formal parameters in method signatures
• E is substituted by Integer in all calls
• Intuitively, you might think of this as follows:
public interface IntegerList {
void add(Integer x);
IntegerIterator iterator();
void remove();
}
• This may help in understanding generics
• But it is also misleading
• There is only one List class, not “one per type”
Introduction to Computer Science I: T18
14
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
Generics and Subtyping
• Is the following code legal?
List<String> ls = new
List<Object> lo = ls;
lo.add(new Object());
String s = ls.get(0);
LinkedList<String>(); // 1
// 2
// 3
// 4
• Line 1 is certainly legal
– LinkedList is a subtype of List
– The formal parameters (both String) match
• In line 2, does List<String> conform to List<Object>?
– List is the same class in both operations
– String is a subclass of Object
– The intuitive answer is therefore “yes”
Introduction to Computer Science I: T18
15
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
Generics and Subtyping
• Let us first look at the next lines of code:
List<String> ls = new
List<Object> lo = ls;
lo.add(new Object());
String s = ls.get(0);
LinkedList<String>(); // 1
// 2
// 3
// 4
• Line 2 has aliased the Object and the String list
• We can insert an Object into a List<Object> (line 3)
• However, at the same time, we insert it into ls
• ls is still declared as a List<String>…
• But ls would now also contain other object types
• If the compiler accepts line 2, it cannot detect this
• Therefore, the compiler will reject Line 2
“type mismatch: cannot convert from List<String> to List<Object>”
Introduction to Computer Science I: T18
16
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
Generics, Subtyping, and Intuition
•
•
•
•
•
Assume Y is a subclass of (interface or class) X
G is some generic type declaration (e.g., List<>)
G<Y> is not a subtype of G<X>
Why is this so hard to believe?
Intuitively, we assume a collection does not change
– Of course, this assumption is often wrong
• Assume the student office passes a list of students to
the city’s census office
–
–
–
–
A Student is a Person
Passing List<Student> where List<Person> is expected seems OK
But only if a copy of the list is passed, not a reference!
What happens if the census office adds a non-Student Person???
• The shared (!) student list is now corrupted
Introduction to Computer Science I: T18
17
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
Generics, Subtyping, and Intuition
Collection<Car>
Collection<Vehicle>
Pointwise
Subtyping,
safe
Set<Vehicle>
Set<Car>
Covariant Subtyping
not safe
Introduction to Computer Science I: T18
18
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
Addressing Subtyping By Wildcards
• We want to print all elements in a collection
• Here’s some (working) code without Generics:
void printCollection(Collection c) {
for (Object element: c)
System.out.println(element);
}
• Now we adapt this to Generics:
void printCollection(Collection<Object> c) {
for (Object element: c)
System.out.println(element);
}
• However, this will only accept Collection<Object>
– It will not accept List<Integer>, but only List<Object>
– Remember that List<Integer> is not a subtype of List<Object>
Introduction to Computer Science I: T18
19
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
Addressing Subtyping By Wildcards
• What do we have to do?
– We need a common supertype of all kinds of collections
– This is the “Collection of unknown element type”
– In Java notation: Collection<?> (here: List<?>)
• We can now adapt the code:
void printCollection(Collection<?> c) {
for (Object element: c)
System.out.println(element);
}
• The elements of the list are treated as Object
– Because java.lang.Object is the superclass of all classes
– Thus, any type – even the „unknown type ?“ – fits to Object
Introduction to Computer Science I: T18
20
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
The Unknown Type „<?>“
• The „Unknown Type“ <?> seems very helpful
– We can finally access the elements
– If necessary, we can cast them to whatever we need
• Assuming the cast is legal, of course
• What about the following?
Collection<?> c = new ArrayList<String>();
c.add(new Object());
• c has the “unknown” element type “?”
• The type to be inserted must conform to “?”
–
–
–
–
The compiler does not know the actual type of “?”
It cannot know if adding an Object will be OK
You cannot add an Object to a List<String>!
The only possible element to be added is null
Introduction to Computer Science I: T18
21
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
A Generic Drawing Application
• Assume the following model of a drawing application:
abstract class Shape {
abstract void draw(Canvas c);
}
class Circle extends Shape {
private int x, y, radius;
void draw(Canvas c) { // ...
}
}
class Rectangle extends Shape {
private int x, y, width, height;
void draw(Canvas c) { // ...
}
}
class Canvas {
void draw(Shape s) {
s.draw(this);
}
}
Introduction to Computer Science I: T18
22
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
A Generic Drawing Application
•
•
•
•
Each shape extends class Shape and can draw itself
We will usually have more than one shape to draw
We can keep the shapes in a List<Shapes>
We modify the code of Canvas accordingly:
void drawAll(List<Shape> shapes) {
for (Shape s: shapes) {
s.draw(this);
}
}
• This works fine for any List<Shape>
• What happens if we want to draw a List<Circle>?
– Circle is a subtype of Shape
– But List<Circle> is not a subtype of List<Shape>
– Calling drawAll(List<Circle>) results in a compile error
Introduction to Computer Science I: T18
23
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
A Generic Drawing Application
• Our method drawAll can work on all Shape subtypes
• It should be able to handle List<Circle>, List<Shape>,
List<Rectangle>, …!
• Using “?” will not work
– The unknown type ? does not have a method “draw(Canvas)”
– Casting to Shape is possible but dangerous
• We need to restrict (“bound”) the wildcard
– It should accept Lists of all subtypes of Shape
• Java notation:
void drawAll(List<? extends Shape> shapes) {
for (Shape s: shapes) {
s.draw(this);
}
}
Introduction to Computer Science I: T18
24
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
Bounded Wildcards
• There is small but very important difference
– List<Shape> accepts only exactly List<Shape>
– List<? extends Shape> accepts lists of any subtype of Shape,
including Shape itself
•
•
•
•
List<Shape>
List<Circle>
List<Rectangle>
…
• “? extends X” means:
– We do not know the exact type (“?”)
– But we know it must be a subtype of X
– X is the “upper bound” of the wildcard
Introduction to Computer Science I: T18
25
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
Bounded Wildcards
• What is wrong with the following code?
void addRectangle(List<? extends Shape> shapes) {
shapes.add(0, new Rectangle());
}
• We cannot add a Rectangle to a List<? extends Shape>…
– We do not know the exact type of the elements in shapes
– We know that they will be a subtype of Shape
– But the type may not be a supertype of Rectangle
• E.g., we could call addRectangle(List<Circle>);
• We can not write to the list if the type is unknown
– Bad news on the one hand
– No type problems at run-time on the other hand
– Java opts for the type-safe way
Introduction to Computer Science I: T18
26
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
Writing Generic Methods
• We want to copy all array elements into a Collection
static void copyToCollection(Object[] array, Collection<?> c) {
for (Object o: array) {
c.add(o);
}
}
• We cannot use Collection<Object> as a parameter
• However, Collection<?> will not work, either
– The type is unknown, so any given type may not match 
Introduction to Computer Science I: T18
27
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
Writing Generic Methods
• We use a generic method for this purpose:
static <T> void copyToCollection(T[] array, Collection<T> c) {
for (T o: array) {
c.add(o);
}
}
• The <T> declares this to be a generic method
– T is introduced before the return type
• T is used as the formal parameter type
• The Java compiler can use this for checking accesses
– The types of the array and the collection must conform
– It uses the most specific type argument that matches
• In many cases, wildcards are sufficient
– Wildcards are preferred over generic methods – clearer and
more concise
Introduction to Computer Science I: T18
28
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
Checking the Class Type
• We can query the basic type of a generic type
List<Circle> circles = new ArrayList<Circle>();
List<Rectangle> rects = new ArrayList<Rectangle>();
System.out.println(circles instanceof List); //  true
• But we cannot query the precise generic type
System.out.println(circles instanceof List<Circle>); // error
– Remember that there is only one class List (see slide 15)
– The compile-time information about the formal parameter is
not available at runtime
• We adapt the statement to use getClass():
System.out.println(circles.getClass() == rects.getClass());
• The output is true – getClass() returns java.util.List
Introduction to Computer Science I: T18
29
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
Lower Bound Wildcards
• Assume that we want to implement a sink
– It flushes all collection elements and returns the last element
interface Sink<T> {
void flush(T t);
}
static <T> T flushAll(Collection<T> c, Sink <T> sink) {
T last = null;
for (T t: c) {
last = t;
sink.flush(last);
}
return last;
}
Sink<Object> sink;
Collection<String> collection;
String lastString = flushAll(collection, sink);
• What is the generic type argument <T>?
– There is no legal type <T>, as the types do not match
– The call in the last line is illegal
Introduction to Computer Science I: T18
30
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
Lower Bound Wildcards
• This seems easy to fix…:
static <T> T flushAll(Collection<? extends T> c,
Sink <T> sink) {
• The method call now works fine
• However, T is now matched to Object
– Because this matches the element type of the Sink
– Therefore, the assignment of the return value to String fails
• We need to express “unknown, but super type of T”
• Java notation: <? super T>
static <T> T flushAll(Collection<T> c,
Sink <? super T> sink) {
Introduction to Computer Science I: T18
31
Implementation Example
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
interface Sink<T> {
void flush(T t);
}
class ConcreteSink<T> implements Sink<T> {
public void flush(T t) {
System.err.println("Flushing " + t + ", type: "
+t.getClass().getName());
}
}
static <T> T flushAll(Collection<T> c, Sink <? super T> sink) {
T last = null;
for (T t: c) {
last = t;
sink.flush(last);
}
return last;
}
Sink<Object> sink = new ConcreteSink<Object>();
Collection<String> cs = Arrays.asList("a","bb2","cdf");
System.err.println(flushAll(cs, sink));
We have omitted the necessary class context to save space…
Introduction to Computer Science I: T18
32
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
Static Typing Summary
• Static type systems are still topic of active research
• Due to generics and wildcards, the Java type system is
relatively expressive but also pretty complicated
• Some programmers see static type systems as a
restriction of their freedom ("I know what I am doing")
• Other programmers think that static type systems
enforce a good structure of your code ("think before you
write")
• The debate is not yet settled
• You should have an educated opinion about it!
Introduction to Computer Science I: T18
33
Dr. G. Rößling
Prof. Dr. M. Mühlhäuser
RBG / Telekooperation
©
Related Publications
• See the following materials for more on Generics:
– Java Tutorial on Generics (by Gilad Bracha):
http://java.sun.com/docs/books/tutorial/extra/generics/
– Gilad Bracha, “Generics in the Java Programming Language”
• Used as the main reference for these slides
• http://java.sun.com/j2se/1.5/pdf/generics-tutorial.pdf
– Maurice Naftalin, Philip Wadler: “Java Generics and
Collections”, O’Reilly, 2006
Introduction to Computer Science I: T18
34