Monday, October 13, 2014

Java and Scala: Covariance and Contravariance


There is a long-standing bug in the Java type system:

        SubClass[]   subArray   = new SubClass[1];
        SuperClass[] superArray = subArray;
        superArray[0]           = new AnotherSubClass(); // throws java.lang.ArrayStoreException

Scala avoids this quite nicely by using the Array class whose contents are invariant (it's defined as final class Array[T] ...). Note that it has neither + to indicate T is covariant or - to indicate T is contravariant.

Java programmers may understand co- and contravariance in terms of method calls. Here, method parameters are contravariant and return types are covariant. What do I mean? Well take this code:

    public SuperClass getThis(SuperClass x) { ... }

It says it returns a SuperClass but it can actually be overriden with this:

    @Override
    public SubClass getThis(SuperClass x) { ... }

(where not surprisingly SubClass is a subclass of SuperClass). So, the return type is covariant, that is, it can be more specific than its definition.

Contravariance in Java is more rare (example at the bottom) but it means that types can be super classes and still the code will compile.

Generics in Java are invariant (neither co- nor contravariant). That is:

        List<SubClass>    mySubs   = new ArrayList<>();
        List<SuperClass>  mySupers = mySubs; // does not compile

But in Scala, this:

    val subList                                   = List[MySubClass]()
    val superButReallySubList: List[MySuperClass] = subList // allowed

is acceptable because List is defined as:

type List[+A] = scala.collection.immutable.List[A]

That is, the list is covariant (because of the +).

Interestingly, Scala gets around the problems of Java's covariant arrays by changing the type of the list when a covariant type is added.

  val subListWithSuperElem                      = subList :+ new MySuperClass
  subListWithSuperElem :+ new MyOtherSubClass // this is legal because subListWithSuperElem is not the type as subList
  printAllSubs(subListWithSuperElem)          // but this is illegal
.
.

  def printAllSubs(x : List[MySubClass]) = {
    x.foreach(x =< { print(x + " ") } )
  }

Now it gets complicated :) Let's take these four functions that are permutations of functions taking a sub- or super-type and returning a sub- or super-type:

    def superToSub  (x: MySuperClass) : MySubClass    = { new MySubClass()   }
    def subToSub    (x: MySubClass)   : MySubClass    = { new MySubClass()   }
    def superToSuper(x: MySuperClass) : MySuperClass  = { new MySuperClass() }
    def subToSuper  (x: MySubClass)   : MySuperClass  = { new MySuperClass() }

Then we want to pass them to these functions:

  def fnTakesSuperReturnsSub  (x :(MySuperClass)  => MySubClass)   = {...}
  def fnTakesSubReturnsSuper  (x: (MySubClass)    => MySuperClass) = {...}
  def fnTakesSuperReturnsSuper(x: (MySuperClass)  => MySuperClass) = {...}
  def fnTakesSubReturnsSub    (x: (MySubClass)    => MySubClass)   = {...}

Some combinations are allowed, some are not. 

                         Type of called function's parameter
                         (Super)->Sub   (Super)->Super   (Sub)->Sub   (Sub)->Super
Argument  (Super)->Sub         Yes            Yes            Yes          Yes
to        (Super)->Super       No             Yes             No          Yes
Function  (Sub)->Super         No             No              No          Yes
          (Sub)->Sub           No             No             Yes          Yes


The rule is:

When passing function A to function B, function A's argument is covariant to the function defined in B's parameters and the return type is contravariant. In other words, you can be more relaxed about the argument and more precise about the returned type.

Java 8's new Functional Programming style allows us to create similar functions, for example:

        Function<SubClass, SuperClass> subToSuper =
                (SubClass subclass) -> { return new SuperClass(); };

        Function<SubClass, SubClass> subToSub =
                (SubClass subclass) -> { return subclass; };

        Function<SuperClass, SuperClass> superToSuper =
                (SuperClass superClass) -> { return superClass; };

        Function<SuperClass, SubClass> superToSub =
                (SuperClass superClass) -> { return new SubClass(); };

Note, that Java 8 adds the syntactic sugar that makes it look a little like Scala, but it's just creating instances of java.util.function.Function really and the methods we might call may look like this:

    private void doSuperToSub(Function<SuperClass, SubClass> superToSub) { }

    private void doSuperToSuper(Function<SuperClass, SuperClass> superToSuper) { }

    private void doSubToSub(Function<SubClass, SubClass> subToSub) { }

    private void doSubToSuper(Function<SubClass, SuperClass> subToSuper) { }

But this time, since Java generics by default are invariant, there is a one-to-one mapping between the 4 functions and 4 methods above. For instance:

        doSubToSuper(subToSuper); // works!
//        doSubToSuper(subToSub); // doesn't compile

If you want Scala like semantics for argument covariance, you have to start getting clever with generics. For instance, you can do:

    doAnyToSuperToSub(subToSub);
    doAnyToSuperToSub(superToSub);

if we define this method such:

    private <T extends SuperClass> void doAnyToSuperToSub(Function<T, SubClass> anySuperToSub) { }

Similarly, if you want Scala like semantics for the returned type's contravariance, you'll need:

        doSubToAnySuper(subToSuper);
        doSubToAnySuper(subToSuper);

calling something like:

    private void doSubToAnySuper(Function<SubClass, ? super SubClass> fn) {}

But wildcards cause all sorts of confusion and it's starting to look messy.

No comments:

Post a Comment