3

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.

  • #3 is just ordinary contravariance. You up the type parameter of the return type to the most specific common super type; for two "totally unrelated" classes the most specific common super type is Object. – user7043 Aug 30 '14 at 20:34
  • the compiled code would be the same – ratchet freak Aug 30 '14 at 20:46
  • 1
    If both Car and Train both implement interfaces Vehicle and PurchasableItem, which type would a concatenation of cars and trains become? – Pete Kirkham Aug 30 '14 at 21:08
  • 1
    @PeteKirkham <T extends Vehicle & PurchasableItem>, but Java is quite limited in how this can be used. – ggovan Aug 30 '14 at 21:20
  • 1
    @Pete, probably in that situation the compiler would flag an ambiguity and require the programmer to explicitly specify the result type. – Karl Bielefeldt Aug 30 '14 at 21:50
2

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);
1

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.