Sunday 2 July 2017

Consequences of invariance

First step is curiosity. If you are lucky enough to use at least java8 and you have java.util.function.Function to your disposal then maybe you saw methods (yes "methods on function") like compose or andThen. If you follow implementation you will see that in declaration you have quite broad generics

default <V> Function<V, R> compose(Function<? super V, ? extends T> before)

default <V> Function<T, V> andThen(Function<? super R, ? extends V> after) 

And the point is that we will see such declarations more and more in our daily programming. In this article I will try to prove that technically only such declarations with "? super" and "? extends" has pragmatic sense and you will have to type those signatures each time you are passing function as a parameter. We will see what is the origin of this and that there was and there is maybe more convenient alternative.

When types have a type

Long, long time ego everything in Java was literally an Object. If you had a list then you had a list of Objects - always Objects.It was a time when CRT monitors would burn your eyes and an application started 15 minutes just to throw CastClassException just after start. Because you had to predict or just guess what type you were operating on. It was time when Java did not have generics.

When Generics came to Java5 those problems become marginal. However a new class of problems appeared because now assumption "everything is an Object" started generating some strange problems

Because if String is and Object and we have a "List of Strings" so technically list of objects because everything is an object - then is this list also an Object and finally can it bee also seen as a list of objects? Unfortunately - for java list - the last one is not true.

If this would be possible you could write code like this:

List<String> strings=new LinkedList<>();
List<Object> objects = strings; 
objects.add(1); //disaster!!

This would be disaster. But we case made a pact with compiler that we will not put anything "bad" there and write declaration like following one :

List<? extends Object> pactWithCompiler=strings;

Could have Java choose different approach? There is a convenient alternative which we are going to see soon. Still, looking at this piece of code the list declaration seems to be ok and prevents ClassCastException. This was year 2004. Ten years pass. Java8 is born with java.util.Function in it. And it is this new mechanism where we will see flaws of Java generics design.

Use Site Variance

So again let's take a look at java.util.Function to understand consequences of how generics are implemented in Java.

default <V> Function<V, R> compose(Function<? super V, ? extends T> before) {
        Objects.requireNonNull(before);
        return (V v) -> apply(before.apply(v));
}

Do extends and super have to there? Now focus :) - they had to be there because ... there is no point to not put them there! If you will not put them there you will limit function signature without any justified reason.

extends

What is the difference between two following functions?
public static <A,B> Collection<B> libraryMethod(Collection<A> c, Function<A,B> f){
        List<B> l =new ArrayList<>();
        for(A a: c){
            l.add(f.apply(a));
        }

        return l;
    }


public static <A,B> Collection<B> libraryMethod2(Collection<A> c, Function<? super A,? extends B> f){
        List<B> l =new ArrayList<>();
        for(A a: c){
            l.add(f.apply(a));
        }

        return l;
}

A difference occurs during invocation. Because having following class

class User{
    private String name;
    private Integer age;

    public User(String name, Integer age) {
        this.name = name;
        this.age = age;
    }

    public String getName() {
        return name;
    }

    public Integer getAge() {
        return age;
    }
}

We would like to execute following computation :

Collection<User>  users=new LinkedList<>();
Function<User,String> display=o->o.toString();
Collection<Object> res1=libraryMethod(users,display); // error
Collection<Object> res2=libraryMethod2(users,display);

Unfortunately we can not do it :( Without "super" and "extends" we introduced artificial limitation to our function so that we now can not return supertype of String. To remove this limitation additional effort from our side is needed. There is no justification for this limitation. And this will be popular "pattern" whenever you want to respect subtype polimorpohism

super

I hope need for "extends" is now explained. Situation with "super" is less intuitive. Let's try with following : "a User has subclass which is his specialization".

class SpecialUser extends User{

    private String somethingSpecial;

    public SpecialUser(String name, Integer age, String somethingSpecial) {
        super(name, age);
        this.somethingSpecial = somethingSpecial;
    }
}

And now we have another library function, this time for filtering our objects

public static <A> Collection<A> filter1(Collection<A> c, Function<A,Boolean> f){
        List<A> l =new ArrayList<>();
        for(A a: c){
            if(f.apply(a)) l.add(a);
        }

        return l;
}


public static <A> Collection<A> filter2(Collection<A> c, Function<? super A,Boolean> f){
        List<A> l =new ArrayList<>();
        for(A a: c){
            if(f.apply(a)) l.add(a);
        }

        return l;
}

And again there is no reason to prohibit functions which works on subtypes because after all SpecialUser IS-A type of User.

Function<User,Boolean> isAdult=user->user.getAge()>= 18;

Collection<SpecialUser>  specialUsers=new LinkedList<>();
// filter1(specialUsers,isAdult); //error because of no "super"
filter2(specialUsers,isAdult);

Now if you check how for example map is implemented on java.util.Stream you will see the same pattern again :

<R> Stream<R> map(Function<? super T, ? extends R> mapper);

because really other declarations doesn't have much sense. But in such case would it be possible to implement generics in a different way so that programmers could type less - and what's more important introduce less bugs (what if you forget about "extends") ? Yes, it is possible and it is actually working quite well. Java approach is called declaration site variance and the alternative is...

Definition Site variance

In other languages - instead of writing "extends" in 1000 declaration places we can actually write it one - on declaration . This way we can set "nature" of given construct once and for all. Let see how it is implemented then :

C#

interface IProducer<out T> // Covariant - "extends"
{
    T produce();
}
 
interface IConsumer<in T> // Contravariant - "super"
{
    void consume(T t);
}

Kotlin

abstract class Source<out T> {
    abstract fun nextT(): T
}

Scala

trait Function1[-T1,+R] extends AnyRef 

//now it is default behaviour of every function that it works as 
//'<super,extends>' with input and output types

But why?

Why java has use site variance. I don't know and I'm unable to find on google. Most likely this mechanism has a lot o sense in 2004 when it was created for mutable collections, IE had 90% market, people used tons of xml to share messages and no one thought about functions. In Scala mutable collections like Array are invariant and theoretically in this one place java gives more freedom because you can change construct nature when it is used. But it can actually raise more problems than benefits because now library users - not designers - are responsible for proper declaration. And when it was implemented this way in 2004 then it was also used this way in 2014 for functions - maybe this is an example of technical debt.

About few advantages and many flaws of "Use-Site Variance" you can read here -> https://en.wikipedia.org/wiki/Covariance_and_contravariance_(computer_science)#Comparing_declaration-site_and_use-site_annotations. . In general I hope this article shows clearly that declaration site variance is a lot better choice for Functions.

Links

  1. https://en.wikipedia.org/wiki/Covariance_and_contravariance_(computer_science)
  2. https://kotlinlang.org/docs/reference/generics.html#declaration-site-variance
  3. https://schneide.wordpress.com/2015/05/11/declaration-site-and-use-site-variance-explained/
  4. https://medium.com/byte-code/variance-in-java-and-scala-63af925d21dc#.lleehih3p

No comments:

Post a Comment