Showing posts with label Generics. Show all posts
Showing posts with label Generics. Show all posts

Friday, 1 July 2011

Subtyping in Generics

Before starting on subtyping in Generics, let's first understand what is covariance.
See - What is covariance, contravariance and invariance?

In Java, as in other object-oriented typed languages, hierarchies of types can be built:
 
In Java, a subtype of a type T is either a type that extends T or a type that implements T (if T is an interface) directly or indirectly. Since "being subtype of" is a transitive relation, if a type A is a subtype of B and B is a subtype of C, then A will be a subtype of C too. In the figure above:
  • FujiApple is a subtype of Apple.
  • Apple is a subtype of Fruit.
  • FujiApple is a subtype of Fruit.
Every Java type will also be subtype of Object.

Every subtype A of a type B may be assigned to a reference of type B:

Apple a = ...;
Fruit f = a;


Subtyping of Generic Types - Parametrized Type Invariance

If a reference of an Apple instance can be assigned to a reference of a Fruit, as seen above, then what's the relation between, let's say, a List<Apple> and a List<Fruit>? Which one is a subtype of which? More generally, if a type A is a subtype of a type B, how does C<A> and C<B> relate themselves?

Surprisingly, the answer is: in no way. In more formal words, the subtyping relation between generic types is invariant.
Eg.
List<Apple> apples = new ArrayList<>();
List<Apple> foulApples = apples; //fine 
Collection<Apple> greenApples = apples; //fine again


However this is not fine:
List<Apple> apples = new ArrayList<>();
List<Fruit> fruits = apples;//Error

and so does the following:

List<Apple> apples;
List<Fruit> fruits = ...;
apples = fruits;

But why? Is an apple is a fruit, a box of apples (a list) is also a box of fruits.

In some sense, it is, but types (classes) encapsulate state and operations. What would happen if a box of apples was a box of fruits?

List<Apple> apples = ...;
List<Fruit> fruits = apples;
fruits.add(new Strawberry());

If it was, we could add other different subtypes of Fruit into the list and this must be forbidden.

The other way round is more intuitive: a box of fruits is not a box of apples, since it may be a box (List) of other kinds (subtypes) of fruits (Fruit), such as Strawberry.


So what if they were covariant?

Please go through the comments to see what is the problem:
List<Integer> li = new ArrayList<Integer>();
li.add(new Integer(122));
List<Object> lo = li; // Problem starts here
Object num = lo.get(0); // Nothing wrong with this
lo.add("Bang!"); // This would be OK through
// lo but what about li
Integer i = li.get(1); // ClassCastException


Advantage of Generics

Pretty much the same way, methods and constructors can be generic if they declare one or more type variables.

public static <T> T getFirst(List<T> list)

This method will accept a reference to a List<T> and will return an object of type T.


Examples

You can take advantage of generics in both your own classes or the generic Java library classes.

Type Safety When Writing...

In the following code snippet, for example, we create an instance List<String> of populate it with some data:

List<String> str = new ArrayList<String>();
str.add("Hello ");
str.add("World.");

If we tried to put some other kind of object into the List<String>, the compiler would raise an error:

str.add(1); // won't compile

... and When Reading

If we pass the List<String> reference around, we're always guaranteed to retrieve a String object from it:

String myString = str.get(0);

Iterating

Many classes in the library, such as Iterator<T>, have been enhanced and made generic. The iterator() method of the interface List<T> now returns an Iterator<T> that can be readily used without casting the objects it returns via its T next() method.


for (Iterator<String> iter = str.iterator(); iter.hasNext();) {
  String s = iter.next();
  System.out.print(s);
}

Using foreach

The for each syntax takes advantage of generics, too. The previous code snippet could be written as:

for (String s: str) {
  System.out.print(s);
}

that is even easier to read and maintain.

Autoboxing and Autounboxing

The autoboxing/autounboxing features of the Java language are automatically used when dealing with generics, as shown in this code snippet:

List<Integer> ints = new ArrayList<Integer>();
ints.add(0);
ints.add(1);
      
int sum = 0;
for (int i : ints) {
  sum += i;
}

Writing Generic interface

A class or an interface is generic if it has one or more type variable. Type variable are delimited by angle brackets and follow the class (or the interface) name:

public interface List<T> extends Collection<T> {
  ...
}

Roughly speaking, type variables act as parameters and provide the information the compiler needs to make its checks.

Many classes in the Java library, such as the entire Collections Framework, were modified to be generic. The List interface we've used in the first code snippet, for example, is now a generic class. In that snippet, box was a reference to a List<Apple> object, an instance of a class implementing the List interface with one type variable: Apple. The type variable is the parameter that the compiler uses when automatically casting the result of the get method to an Apple reference.

In fact, the new generic signature or the get method of the interface List is:

T get(int index);

The method get returns indeed an object of type T, where T is the type variable specified in the List<T> declaration.

The Generics Facility

The generics facility introduced the concept of type variable. A type variable, according to the Java Language Specification, is an unqualified identifier introduced by:


Tuesday, 19 April 2011

Bounding the Parameterized Types

Generics won't be complete if this section is not covered. It is all about bounding parametric types. Till now, we have seen parametric types operate on a single java type like Object or String. Now, let us see how the parametric types can be restricted by applying some constraints over them. For this to be illustrated, let us take a sample application called Animal Actions.
Animal Actions class performs various operations on a given Animal like: making them eat, sleep and run. The first constraint that we see here is that only an Animal object can be passed to the Animal Actions class. Let us represent the Animal class as follows.
Animal.java
package generics.bounds;

public abstract class Animal
{
// Some common functionalities here.
}
Note that the Animal class is declared as abstract, meaning that some other concrete class is going to extend this Animal class. Another restriction that we see in Animal Actions class is that they will make the Animals to sleep, eat and run. Since these are behaviors and we may give different representations for the same, let them be modeled as interfaces. Following code shows the interface design for the behaviors,

package generics.bounds;

interface Sleepable
{
public void sleep();
}

interface Runnable
{
public void run();
}

interface Eatable
{
public void eat();
}
Let us give implementation of the above behaviors for some animal, say Dog. The following code snippet is for the implementation of Dog which conforms to eating, sleeping and running behavior.
Dog.java
package generics.bounds;

public class Dog extends Animal implements Sleepable, Runnable, Eatable
{
public void sleep()
{
System.out.println("Dog is sleeping");
}

public void run()
{
System.out.println("Dog is running");
}

public void eat()
{
System.out.println("Dog is eating");
}
}
Now, let us design the Animal Actions class. The restriction we have on Animal Actions class is that, we should operation on any type of object that is an Animal which can eat, sleep and run. Look into the following Animal Actions class,
AnimalActions.java
package generics.bounds;

public class AnimalActions<A extends Animal & Sleepable & Runnable & Eatable>
{
private A animal;

public AnimalActions(A animal)
{
this.animal = animal;
}

public A getAnimal()
{
return animal;
}

public void setAnimal(A animal)
{
this.animal = animal;
}

public void doActions()
{
animal.sleep();
animal.run();
animal.eat();
}
}
The declaration of the parameterized class looks like the following,

public class AnimalActions<A extends Animal & Sleepable & Runnable & Eatable
Let us break down the pieces in the above declaration. The first trivial stuff that has to be noted is the declaration of the typed parameter A (which is for Animal). The next set of expressions are imposing restrictions on the typed parameter A. The phrase 'A extends Animal' tells that whatever type we pass for the substitution parameter must extend/implement the Animal class/interface. The type that comes after extends can either be an interface or a class. It is illegal to mention something like the following,

public class AnimalActions<A implements SomeInterface>
Only extends keyword is used for both class as well the interface and not the implements keyword. If we want the parametric type to confirm by more than one classes or interfaces, then every types should be separated by the symbol &. For example, in our case, we want some Animal to eat, sleep and run by implementing the Eatable, Sleepable and Runnable interface. So, we have declared something like AnimalActions<A extends Animal & Sleepable & Runnable & Eatable. To sum up things, the generic class declaration can be interpreted like this; it can be passed with any type that implements/extends Animal, Sleepable, Runnable and Eatable types.
Following code snippet makes use of the above Animal Actions class. In the below code, a new instance of Dog object is created and passed on to the constructor of the Animal Actions class. This is perfectly valid as the Dog class extends the Animal class and it also implements Sleepable, Eatable and Runnable interfaces. It then makes a call to AnimalActions.doActions(), thereby the execution gets directed towards Dog.sleep(), Dog.eat() and Dot.run().
AnimalActionsTest.java
package generics.bounds;

public class AnimalActionsTest
{
public static void main(String[] args)
{
AnimalActions<Dog> animal = new AnimalActions<Dog>(new Dog());
animal.doActions();
}
}

Generics : Index or TOC

Generics in java 

Motivation behind Generics-Dealing with casting of objects
The Generics Facility  
Creating a Generic class
Writing a Generic Method

Naming convention in generics
Generics are syntactic sugar - Type Erasure with Generics
Advantage of Generics



Subtyping a generic type

Wildcards in Generics
Generics classes in java vs templates in c++


Some mistakes to be avoided with generics:
Beginner's mistake of using Object as type parameter to make method generic
Generic methods: How generic are generic method?
Wildcards in Generics 
Bounded parametric types 
Covariance, contravariance, invariance
Upper bound boundedness in generics
Lower bound boundedness in generics
Multiple bounds in generics
Get and Set principle in generics
Restrictions on wildcards in generics
Expressing dependencies in type parameters : Wildcards vs type parameters

Class objects as type literals
Generic types are not covariant
Type erasure in generics
Making return type of method as generic
Covariant parameter types

Monday, 18 April 2011

Writing generic methods

A Generic class containing a type parameter affects the entire class, but a generic method containing one or more type parameters affects that particular method only. So it means that a non-generic class can contain a mixture of generic and non-generic methods.


Example:

public class GenericMethods
{
static <T> void printType(T anyType)
{
System.out.println(anyType.getClass().getName());
} 
 
//using generic method
public static void main(String[] args) 
{
GenericMethods.printType(String.class);
GenericMethods.printType(new String(""));
}
}

If we look at the way in which a Generic method is declared, we find that the static method printType() has a return type void and it takes a single parameter called T. Here T stands for any parametric type which can be substituted with any of the Java types by the Clients. Since we have introduced a parameter T, it should be defined. But where? It should be defined in the method definition itself just before the return type of the method ().

The moral is whenever we have different type parameters in a method, it should be defined in the method definition. For example, consider the following method that has two type parameters A and B and they are defined before the return type of the method separated by commas.


<A, B> void genericMethod2Parameters(A aType, B bType)
{
// Something here.
}


Writing generic class in java

Consider the following class:

package com.vaani.generics.classes;

public class MyGenericClass<T>
{
private T anyObject;

public T getObject()
{
return anyObject;
}

public void setObject(T anyObject)
{
this.anyObject = anyObject;
}

public String toString()
{
return anyObject.toString();
}
}

Note the following syntax :
public class MyGenericClass<T>
The above statement essentially says that we wish to make the MyGenericClass class as a Generic Class. Technically, it is now a parametric class and T is called a type parameter.

T serves as a place-holder for holding any type of Object. Note the usage of the type parameter within the class declaration. Now, the clients can use the above class by substituting any kind of object for the place-holder T.

public class MyGenericClassRunner
{
public static void main(String[] args) throws Exception
{
MyGenericClass<String> stringHolder =
new MyGenericClass<String>();
stringHolder.setObject(new String("String"));
System.out.println(stringHolder.toString());

MyGenericClass<URL> urlHolder = new MyGenericClass<URL>();
urlHolder.setObject(new URL("http://www.k2java.blogspot.com"));
System.out.println(urlHolder.toString());
}
}

Though parameter is placeholder, its much different from templates in c++.

Note how the clients or users of this class instantiates an instance for the MyGenericClass class. 
MyGenericClass<String> stringHolder = 
new MyGenericClass<String>();

This is called type substitution. For the type parameter O, the type String is substituted.

Generic classes having two or more parametric types

You can simply write:
public class My2ParameterClass<A, B>

So instead of 1 parameter have 2 parameters and initialize etc. like original.

Naming convention on generics

A note on naming conventions. We recommend that you use pithy (single character if possible) yet evocative names for formal type parameters. It’s best to avoid lowercase characters in those names, making it easy to distinguish formal type parameters from ordinary classes and interfaces. Many container types use E, for element, as in the examples above.

Sunday, 17 April 2011

Making the return type of method as generic

Sometimes we may expect different return type for same function.
Consider the following method:

public static final <X> X myGenericMethod(String property)


The method returns a type of whatever you expect it to be (<X> is defined in the method and is absolutely unbounded).

Calling the method :

In this case, the compiler can guess:


Set<String> s = MyClass.myGenericMethod("Some property");

But if it can't, you must type:
MyClass.<String>myGenericMethod("Some Property");


However note that this is very, very dangerous as no provision is made that the return type actually matches the returned value.
The only advantage this has is that you don't have to cast the return value of such generic lookup methods that can return any type.
Use such constructs with care, because you loose pretty much all type-safety and gain only that you don't have to write an explicit cast at each call to get().
And yes: this pretty much is black magic that blows up at runtime and breaks the entire idea of what generics should achieve.

Also if we don't use generic parameter of method, but rather than class the above method becomes:
class MyClass<T>
{

    public static final X myGenericMethod(String property)

}

And now use parametric style only on class object, rather than function.
MyClass<T>.myGenericMethod("Some property");

This facility allows you to create methods in a subclass that return an object whose type is a subtype of that returned by the method it overrides.

Covariance, contravariance and invariance


In programming language conversion from narrower to broader type is of these types:
  • covariant: converting from wider (double) to narrower (float).
  • contravariant: converting from narrower (float) to wider (double).
  • invariant: Not able to convert.



Thursday, 31 March 2011

Covariant Parameter Types

Read - What is covariance?
Covariant Return type

Now we have a look at covariant method parameters, which are considered unsound.


Consider the following code:
public interface TestInterface { }

public class TestClass implements TestInterface { }

import java.util.ArrayList;
import java.util.List;

public class Test {
private List<testclass> list;

public TestInterface test() {
list = new ArrayList<testclass>();
list.add(new TestClass());

return covariant(list);
}

public TestInterface covariant(List<testinterface> ilist) {
return ilist.remove(0);
}
}

Now there is absolutely no reason why this should not work. It is trivially inferable that the above code treats ilist as covariant in the list-type - and that therefore this code is statically correct.

Of course Java's typing has never been particularly smart. List.add(T1) is contra-variant in t1, and T2 List.get(int) is co-variant in t2; so the Java compiler is correct to infer that in the general case List and List are substitutable iff t1 == t2.

If we can't declare a generic parameter to be covariant in its type parameter we have a serious problem - it means that any non-trivial algorithm involving collections is going to run afoul of this. You might consider trying to cast your way around it:


public TestInterface test() {
list = new ArrayList<testclass>();
list.add(new TestClass());

return covariant((List<testinterface>)list);
}

but not surprisingly that didn't work.

Test.java:11: inconvertible types
found : java.util.List<testclass>
required: java.util.List<testinterface>
return convariant((List<testinterface>)list);
^
1 error

If you continue to hack at it you might try a double cast via a non-generic List.

public TestInterface test() {
list = new ArrayList<testclass>();
list.add(new TestClass());

return covariant((List<testinterface>)((List)list));
}

This works but leaves us with the unchecked/unsafe operation warning:
Note: Test.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.



Now this is a perfectly reasonable warning - it is unchecked; it is unsafe; and more importantly it does violate encapsulation. The problem here is that the caller should not be defining the type invariants of the callee - that's the job of the method signature!

The correct solution is to allow us to declare covariant() to be covariant in its argument; and fortunately Java does support this.

To declare an argument to be covariant in its type parameter you can use the extends keyword:
public TestInterface covariant(List<? extends TestInterface> ilist) {
return ilist.remove(0);
}

To declare an argument to be contravariant in its type parameter you use the super keyword:
public void contravariant(List<? super TestClass> clist, TestClass c) {
clist.add(c);
}



Friday, 28 January 2011

Type erasure with generics

Type-safety checking of generic types is only performed at compile time. Type information is then removed and will not appear in the byte code. Consequently, a generic type like ArrayList<String> is translated to its ArrayList equivalent...

List<String> strings = new ArrayList<String>();
List<Integer> nums = new ArrayList<Integer>();
System.out.println(strings.getClass());
System.out.println(nums.getClass());

Both will print java.util.ArrayList. Type erasure means generic type information will not be available at runtime, and the following attempt to create an array of a generic type will not compile...
TreeSet<String>[] families = new TreeSet<String>[5];

The wildcard type is an exception to this :
List<?>[] info = new List<?>[5];

The ? stands for an unknown type that matches anything.

There is however, an upside to type erasure – there will be interoperability between generic type and raw types...

TreeSet<String> names = new TreeSet<String>();
TreeSet rawTree = names; //names is widened to raw type

Type-safety checking can be defeated, typically for backward compatibility. The following will compile, but with an “unchecked cast” warning...



This also works...

import java.lang.reflect.*;
...
TreeSet<String>[] people = (TreeSet<String>[])Array.newInstance(TreeSet.class,5);


But the way is now open for ClassCastException at runtime...
TreeSet rawTree = people[0];
oldTree.add(new Integer(1)); //compiles, but runtime error
Compile-time type-safety check warnings can be suppressed if needed...
@SuppressWarnings("unchecked")
public static void main (String[] args) {
...

}

Runtime operations such as instanceof are not permitted again, because of type erasure.

Similarly, a cast such as...
TreeSet<String> handles = (TreeSet<String>)name;
would produce an unchecked compiler warning because it is not something the run-time system can safely perform.

But why java uses Type erasures?
Type erasure is not a fault, rather it was clever step taken by java designers.
The reason why Java uses type erasure is to maintain backwards compatibility. Let's assume you wrote some code a few years back which used Java Lists, before generics was introduced in the language. Obviously your code had no mention of generics. Now, when engineers at Sun decided to introduce generics, they did not want to break code which people had already written.
One possible way was to ensure that client code which uses generics in the classes they invoke, never carries any information about generics in the compiled code. So the above class when compiled should not carry any information about generics. Because compiled client code never carries information about generics anyways, library implementers are free to add generics to their code without the worry of breaking anyone's old code.

Generic types are not covariant : Generics allow you to use only one type

All the Object-based collection types (known as raw types) in classic Java are now retrofitted as generic types and accept type parameters. Generic types allow you to express your intent as being restricted to a particular type when creating and using it...

TreeSet<String> names = new TreeSet<String>();
names.add("Fred");
names.add("Wilma");
names.add("Pebbles");

SortedSet<String> is called the parameterized type and String is the actual type argument. Type-safety checking will be performed at compile time...
names.add(new Integer(100)); //compilation error

The compiler will also reject the following...
TreeSet<Object> names = new TreeSet<String>();
TreeSet<Object> alias = (TreeSet<Object>)names;


This is because generic types are not covariant – a TreeSet of String references is not a TreeSet of Object references.
With generic types, retrieved elements do not require explicit conversion...

Wednesday, 27 October 2010

Generic classes in java vs templates in C++

Here is a small excerpt from the definitions of the interfaces List and Iterator in package :
java.util:
public interface List<E> {
void add(E x);
Iterator<E> iterator();
}
public interface Iterator<E> {
E next();
boolean hasNext();
}

This should all be familiar, except for the stuff in angle brackets. Those are the
declarations of the formal type parameters of the interfaces List and Iterator.
Type parameters can be used throughout the generic declaration, pretty much where
you would use ordinary types (though there are some important restrictions.

In the introduction, we saw invocations of the generic type declaration List, such
as List<Integer>. In the invocation (usually called a parameterized type), all occurrences of the formal type parameter (E in this case) are replaced by the actual type argument (in this case, Integer).

You might imagine that List<Integer> stands for a version of List where E has been uniformly replaced by Integer:
public interface IntegerList {
void add(Integer x);
Iterator<Integer> iterator();
}

This intuition can be helpful, but it’s also misleading.
It is helpful, because the parameterized type List<Integer> does indeed have methods that look just like this expansion.
It is misleading, because the declaration of a generic is never actually expanded in this way. There aren’t multiple copies of the code: not in source, not in binary, not on disk and not in memory. If you are a C++ programmer, you’ll understand that this is very different than a C++ template.

A generic type declaration is compiled once and for all, and turned into a single class file, just like an ordinary class or interface declaration. Type parameters are analogous to the ordinary parameters used in methods or constructors. Much like a method has formal value parameters that describe the kinds of values it operates on, a generic declaration has formal type parameters. When a method is invoked, actual arguments are substituted for the formal parameters, and the method body is evaluated.
When a generic declaration is invoked, the actual type arguments are substituted for the formal type parameters.

The Motivation for Generics : dealing with casting of objects

Consider the following code:
List myIntList = new LinkedList(); // line no. 1
myIntList.add(new Integer(0)); // line no. 2
Integer x = (Integer) myIntList.iterator().next(); //line no. 3

The cast on line 3 is slightly annoying. Typically, the programmer knows what kind of data has been placed into a particular list. However, the cast is essential. The compiler can only guarantee that an Object will be returned by the iterator.
To ensure the assignment to a variable of type Integer is type safe, the cast is required.
Of course, the cast not only introduces clutter, it also introduces the possibility of a run time error, since the programmer might be mistaken.


Removing the cast
What if programmers could actually express their intent, and mark a list as being restricted to contain a particular data type?
This is the core idea behind generics.
Here is a version of the program fragment given above using generics:

List<Integer> myIntList = new LinkedList<Integer>(); // 1’
//OR
List<Integer> myIntList = new LinkedList(); // 1’

myIntList.add(new Integer(0)); //2’
Integer x = myIntList.iterator().next(); // 3’

Now, you might think that all we’ve accomplished is to move the clutter around.

Instead of a cast to Integer on line 3, we have Integer as a type parameter on line 1’. However, there is a very big difference here. The compiler can now check the type correctness of the program at compile-time. When we say that myIntList is declared with type List<Integer>, this tells us something about the variable myIntList, which holds true wherever and whenever it is used, and the compiler will guarantee it. In contrast, the cast tells us something the programmer thinks is true at a single point in the code.

The net effect, especially in large programs, is improved readability and robustness.

A big big note on Generics
Generics provides a sort of a syntactic sugar that might spare you some casting operation. But behind the scenes, after compilation the byte code is same. See Type Erasure with Generics to see how.