Parameterized Java Types (Generics)

Question

Consider this "legacy" code:

public interface IPersistentCollection {
    IPersistentCollection cons(Object o);
}

Genericized in Java, it could become something like this:

public interface IPersistentCollection<T> {
    IPersistentCollection<T> cons(T o);
}

Clearly adding a new item to a mutable Java collection shouldn't change the type of the existing collection. But unlike the Java collections, cons() returns a completely new, immutable collection, leaving the old collection unchanged, opening the possibility that it could meaningfully take on a different type than the original collection had.

1. Obviously, you should be able to cons an object of type Ford to a collection of Cars and get a collection of Cars back (covariance). I think this is covered by the above generic example.

2. If Car and Train both extended a Vehicle class, it would be handy to be able to cons a Train to a collection of Cars and get a collection of Vehicles back (contravariance). How would I even write that? I thought by declaring new bounded type variables, S and E for "Vehicle" and "Train" in this example:

   // Illegal because of <S super T>
   <S super T, E extends S> IPersistentCollection<S> cons(E o);
   
   // Simpler, but still Illegal because java disallows <S super T>
   <S super T> IPersistentCollection<S> cons(S o);
   

3. If we want to assume that the programmer knows what they are doing, you should be allowed to cons something totally unrelated to a collection and get a collection of Objects back. I think this is the extreme case of contravariance, but I'm not sure there is even a name for it ("Dynamic Language" maybe?).

I think that if #2 were legal, it would cover cases #1 and #3.

My questions are:

A. To what degree is it possible to do #2 in Java?

B. Is #2 possible/easier in other languages? Scala? Haskell? ML?

C. In theory, a type system that preferred the most specific version of S in example 2 could handle a definition like this. What book can I read about type systems without a PHD in math? Is "Types and Programming Languages" by Pierce the best place to start?

Sample code would be appreciated. If I'm using terms like covariance and contravariance incorrectly, I would appreciate being politely corrected.

Answer 1

Scala's Lists work this way for the :: (cons) and ++ (concat) operators, but not for +, :+, and +: (which is okay because that's sometimes what you want). The type signature looks like:

::[B >: T](x: B): List[B]

// Returns a List[Any] (Any is Scala's "Object" type)
5 :: List("example")

This says B is a superclass of T, the type of the List you're consing onto. You're consing a B element and returning a List of Bs.

Let's say T is a Car and B is a Vehicle. The x parameter can be any subclass of Vehicle due to covariance, so you don't need to specify a third type. I don't know Java's type system as well, but I imagine its equivalent (if it's supported) would be:

<B super T> IPersistentCollection<B> cons(B o);

Answer 2

Angelika Langer is my new hero. She has an incredible Java Generics FAQ http://www.angelikalanger.com/GenericsFAQ/FAQSections/TypeParameters.html#FAQ107

1. She had the insight "class Box<T super Number> {...} is not permitted"... and "conjunctions with method declarations, type parameters with a lower bound would occasionally be useful." Wow! A.) I'm not wasting my time trying the impossible and B.) there is a chance that what I'm trying to do might be useful!

2. She suggests the workaround of using a static method as follows:

   static <A, B, X extends A, Y extends B>
           B addToMap(Pair<X,Y> pair, Map<A,B> map) {
       return map.put(pair.first,pair.second);
   }
   

I was able to apply that directly to a static method in my interface, which worked!

@SuppressWarnings("unchecked")
static <S, E extends S, T extends S> Consable<S> cons(Consable<T> cs, E e) {
    return Consable3.of((S) e, (Consable<S>) cs);
}

For a short time I thought that this same technique can be applied to an instance method, but it cannot:

public static interface Consable<T> {
    // T is the type of our existing collection (defined above)
    // E is the new element being cons-ed with our collection
    // S is a super-type of both T and E and therefore the
    //   type of our new collection.
    <S, E extends S, T extends S> Consable<S> cons(E e);
}

...

class Animal {}
class Mammal extends Animal {}

...

// Consable<Vehicle> vehicles = cars.cons(new Train());
Consable<Animal> vehicles = cars.cons(new Mammal()); 

Commenting out cons-ing things to the vehicles, That compiles! Eek! And runs!

$ javac -Xlint JavaConsSignature.java 
$ java JavaConsSignature
JavaConsSignature$Mammal@15db9742
JavaConsSignature$Car@6d06d69c
JavaConsSignature$Chevy@7852e922
JavaConsSignature$Chevy@4e25154f
JavaConsSignature$Chevy@70dea4e

So static method: Good. Instance method: Bad. It doesn't support fluent interface building, but at least you can have this particular kind of type safety on some kind of method in Java.