Give Examples of Functions Which Demonstrate Covariance and Contravariance in the Cases of Both Overloading and Overriding in Java

Give examples of functions which demonstrate covariance and contravariance in the cases of both overloading and overriding in Java?

Covariance:

class Super {
  Object getSomething(){}
}
class Sub extends Super {
  String getSomething() {}
}

Sub#getSomething is covariant because it returns a subclass of the return type of Super#getSomething (but fullfills the contract of Super.getSomething())

Contravariance

class Super{
  void doSomething(String parameter)
}
class Sub extends Super{
  void doSomething(Object parameter)
}

Sub#doSomething is contravariant because it takes a parameter of a superclass of the parameter of Super#doSomething (but, again, fullfills the contract of Super#doSomething)

Notice: this example doesn't work in Java. The Java compiler would overload and not override the doSomething()-Method. Other languages do support this style of contravariance.

Generics

This is also possible for Generics:

List<String> aList...
List<? extends Object> covariantList = aList;
List<? super String> contravariantList = aList;

You can now access all methods of covariantList that doesn't take a generic parameter (as it must be something "extends Object"), but getters will work fine (as the returned object will always be of type "Object")

The opposite is true for contravariantList: You can access all methods with generic parameters (you know it must be a superclass of "String", so you can always pass one), but no getters (The returned type may be of any other supertype of String)

Covariance, Invariance and Contravariance explained in plain English?

Some say it is about relationship between types and subtypes, other say it is about type conversion and others say it is used to decide whether a method is overwritten or overloaded.

All of the above.

At heart, these terms describe how the subtype relation is affected by type transformations. That is, if A and B are types, f is a type transformation, and ≤ the subtype relation (i.e. A ≤ B means that A is a subtype of B), we have

f is covariant if A ≤ B implies that f(A) ≤ f(B)
f is contravariant if A ≤ B implies that f(B) ≤ f(A)
f is invariant if neither of the above holds

Let's consider an example. Let f(A) = List<A> where List is declared by

class List<T> { ... }

Is f covariant, contravariant, or invariant? Covariant would mean that a List<String> is a subtype of List<Object>, contravariant that a List<Object> is a subtype of List<String> and invariant that neither is a subtype of the other, i.e. List<String> and List<Object> are inconvertible types. In Java, the latter is true, we say (somewhat informally) that generics are invariant.

Another example. Let f(A) = A[]. Is f covariant, contravariant, or invariant? That is, is String[] a subtype of Object[], Object[] a subtype of String[], or is neither a subtype of the other? (Answer: In Java, arrays are covariant)

This was still rather abstract. To make it more concrete, let's look at which operations in Java are defined in terms of the subtype relation. The simplest example is assignment. The statement

x = y;

will compile only if typeof(y) ≤ typeof(x). That is, we have just learned that the statements

ArrayList<String> strings = new ArrayList<Object>();
ArrayList<Object> objects = new ArrayList<String>();

will not compile in Java, but

Object[] objects = new String[1];

will.

Another example where the subtype relation matters is a method invocation expression:

result = method(a);

Informally speaking, this statement is evaluated by assigning the value of a to the method's first parameter, then executing the body of the method, and then assigning the methods return value to result. Like the plain assignment in the last example, the "right hand side" must be a subtype of the "left hand side", i.e. this statement can only be valid if typeof(a) ≤ typeof(parameter(method)) and returntype(method) ≤ typeof(result). That is, if method is declared by:

Number[] method(ArrayList<Number> list) { ... }

none of the following expressions will compile:

Integer[] result = method(new ArrayList<Integer>());
Number[] result = method(new ArrayList<Integer>());
Object[] result = method(new ArrayList<Object>());

but

Number[] result = method(new ArrayList<Number>());
Object[] result = method(new ArrayList<Number>());

will.

Another example where subtyping matters is overriding. Consider:

Super sup = new Sub();
Number n = sup.method(1);

where

class Super {
    Number method(Number n) { ... }
}

class Sub extends Super {
    @Override 
    Number method(Number n);
}

Informally, the runtime will rewrite this to:

class Super {
    Number method(Number n) {
        if (this instanceof Sub) {
            return ((Sub) this).method(n);  // *
        } else {
            ... 
        }
    }
}

For the marked line to compile, the method parameter of the overriding method must be a supertype of the method parameter of the overridden method, and the return type a subtype of the overridden method's one. Formally speaking, f(A) = parametertype(method asdeclaredin(A)) must at least be contravariant, and if f(A) = returntype(method asdeclaredin(A)) must at least be covariant.

Note the "at least" above. Those are minimum requirements any reasonable statically type safe object oriented programming language will enforce, but a programming language may elect to be more strict. In the case of Java 1.4, parameter types and method return types must be identical (except for type erasure) when overriding methods, i.e. parametertype(method asdeclaredin(A)) = parametertype(method asdeclaredin(B)) when overriding. Since Java 1.5, covariant return types are permitted when overriding, i.e. the following will compile in Java 1.5, but not in Java 1.4:

class Collection {
    Iterator iterator() { ... }
}

class List extends Collection {
    @Override 
    ListIterator iterator() { ... }
}

I hope I covered everything - or rather, scratched the surface. Still I hope it will help to understand the abstract, but important concept of type variance.

How to grok bounded wildcards in Java?

Possible answer to the first question:

public interface Consumer<T> {
    void accept(T t);
    default Consumer<T> andThen(Consumer<? super T> after) {

The bounded wildcard ? super T conveys the information that andThen takes Consumers of T or supertypes of T, aka. contravariant Consumers, as arguments.

Possible answer to the secondary question: https://stackoverflow.com/a/2501513

Basically - completely independent of generics (!) - method return return types are inherently "covariant" (assumed to be "producers") in the Java language. If overriding a method in a child class, you can always declare a more specific return type.

Method arguments are of course also "covariant" - you can only pass more specific objects than the method signature specifies. But on subclasses, although the method is technically not overriden for non-parametric arguments - adhering to the Liskov_substitution_principle - it often makes sense to declare "contravariant" argument types in child classes, which - if the name and other arguments are equal - "overloads" the methods in the parent class. "Static" (reference-type-governed) method dispatch will then ensure that the (less specific) child method is called wins. Method arguments are assumed to be "consumed" and then PECS applies. Anyhow, for generic parameters, bridge methods are generated and it is all a bit more hairy. But we will get there.

Generic substitution principle - how application of principle is governed

If I understood the question correctly, in Java and in the situation you described, the Liskov substition principle does not apply because List<Integer> is not a subtype of List<Number>, which however is a requirement for the Likov substition principle.

That being said, the relation between List<Integer> and List<Number> can be described by covaraince and contravariance, which models the expactation which could be formulated as follows.

As Integer is a subtype of Number, which means that every implementation for Number can be used for Integer, the same must apply for types which instantiate the same generic template, but use Integer and Number as type arguments.

However, to my understanding, this is a different mechanism, which is also discussed in this question for generics.

Generics cast issue

In the first example, the inferred type of the Arrays.asList() call is List<Class<? extends A>>, which is obviously assignable to a variable of the same type.

In the second example, the type of the right side is List<Class>. While Class is assignable to Class<? extends A>, List<Class> is not assignable to List<Class<? extends A>>. It would be assignable to List<? extends Class<? extends A>>.

The reason for this is the same one as why a List isn't assignable to List<A>. If it was, it would make the following (not-typesafe) code possible:

List<Class<B>> bb = new ArrayList<B>();
List<Class<? extends A>> aa = bb;
aa.add(A.class);

Invariance, covariance and contravariance in Java

This is not specific to OO, but has to do with the properties of certain types.

For example, with the function type

 A -> B                 // functional notation
 public B meth(A arg)   // how this looks in Java

we have the following:

Let C be a subtype of A, and D be a subtype of B. Then the following is valid:

 B b       = meth(new C());  // B >= B, C < A
 Object o  = meth(new C());  // Object > B, C < A

but the follwoing are invalid:

 D d       = meth(new A());        // because D < B
 B b       = meth(new Object());   // because Object > A

hence, to check whether a call of meth is valid, we must check

The expected return type is a supertype of the declared return type.
The actual argument type is a subtype of the declared argument type.

This is all well known and intuitive. By convention we say that the return type of a function is covariant, and the argument type of a method is contravariant.

With parameterized types, like List, we have it that the argument type is invariant in languages like Java, where we have mutability. We can't say that a list of C's is a list of A's, because, if it were so, we could store an A in a list of Cs, much to the surprise of the caller, who assumes only Cs in the list. However, in languages where values are immutable, like Haskell, this is not a problem. Because the data we pass to functions cannot be mutated, a list of C actually is a list of A if C is a subtype of A. (Note that Haskell has no real subtyping, but has instead the related notion of "more/less polymorphic" types.)

Why is there no parameter contra-variance for overriding?

On the pure issue of contra-variance

Adding contra-variance to a language opens a whole lot of potential problems or unclean solutions and offers very little advantage as it can be easily simulated without language support:

struct A {};
struct B : A {};
struct C {
   virtual void f( B& );
};
struct D : C {
   virtual void f( A& );     // this would be contravariance, but not supported
   virtual void f( B& b ) {  // [0] manually dispatch and simulate contravariance
      D::f( static_cast<A&>(b) );
   }
};

With a simple extra jump you can manually overcome the problem of a language that does not support contra-variance. In the example, f( A& ) does not need to be virtual, and the call is fully qualified to inhibit the virtual dispatch mechanism.

This approach shows one of the first problems that arise when adding contra-variance to a language that does not have full dynamic dispatch:

// assuming that contravariance was supported:
struct P {
   virtual f( B& ); 
};
struct Q : P {
   virtual f( A& );
};
struct R : Q {
   virtual f( ??? & );
};

With contravariance in effect, Q::f would be an override of P::f, and that would be fine as for every object o that can be an argument of P::f, that same object is a valid argument to Q::f. Now, by adding an extra level to the hierarchy we end up with design problem: is R::f(B&) a valid override of P::f or should it be R::f(A&)?

Without contravariance R::f( B& ) is clearly an override of P::f, since the signature is a perfect match. Once you add contravariance to the intermediate level the problem is that there are arguments that are valid at the Q level but are not at either P or R levels. For R to fulfill the Q requirements, the only choice is forcing the signature to be R::f( A& ), so that the following code can compile:

int main() {
   A a; R r;
   Q & q = r;
   q.f(a);
}

At the same time, there is nothing in the language inhibiting the following code:

struct R : Q {
   void f( B& );    // override of Q::f, which is an override of P::f
   virtual f( A& ); // I can add this
};

Now we have a funny effect:

int main() {
  R r;
  P & p = r;
  B b;
  r.f( b ); // [1] calls R::f( B& )
  p.f( b ); // [2] calls R::f( A& )
}

In [1], there is a direct call to a member method of R. Since r is a local object and not a reference or pointer, there is no dynamic dispatch mechanism in place and the best match is R::f( B& ). At the same time, in [2] the call is made through a reference to the base class, and the virtual dispatch mechanism kicks in.

Since R::f( A& ) is the override of Q::f( A& ) which in turn is the override of P::f( B& ), the compiler should call R::f( A& ). While this can be perfectly defined in the language, it might be surprising to find out that the two almost exact calls [1] and [2] actually call different methods, and that in [2] the system would call a not best match of the arguments.

Of course, it can be argued differently: R::f( B& ) should be the correct override, and not R::f( A& ). The problem in this case is:

int main() {
   A a; R r;
   Q & q = r;
   q.f( a );  // should this compile? what should it do?
}

If you check the Q class, the previous code is perfectly correct: Q::f takes an A& as argument. The compiler has no reason to complain about that code. But the problem is that under this last assumption R::f takes a B& and not an A& as argument! The actual override that would be in place would not be able to handle the a argument, even if the signature of the method at the place of call seems perfectly correct. This path leads us to determine that the second path is much worse than the first. R::f( B& ) cannot possibly be an override of Q::f( A& ).

Following the principle of least surprise, it is much simpler both for the compiler implementor and the programmer not to have contra variance in function arguments. Not because it is not feasible, but because there would be quirks and surprises in code, and considering that there are simple work-arounds if the feature is not present in the language.

On Overloading vs Hiding

Both in Java and C++, in the first example (with A, B, C and D) removing the manual dispatch [0], C::f and D::f are different signatures and not overrides. In both cases they are actually overloads of the same function name with the slight difference that because of the C++ lookup rules, the C::f overload will by hidden by D::f. But that only means that the compiler will not find the hidden overload by default, not that it is not present:

int main() {
   D d; B b;
   d.f( b );    // D::f( A& )
   d.C::f( b ); // C::f( B& )
}

And with a slight change in the class definition it can be made to work exactly the same as in Java:

struct D : C {
   using C::f;           // Bring all overloads of `f` in `C` into scope here
   virtual void f( A& );
};
int main() {
   D d; B b;
   d.f( b );  // C::f( B& ) since it is a better match than D::f( A& )
}

Generics cast issue

In the first example, the inferred type of the Arrays.asList() call is List<Class<? extends A>>, which is obviously assignable to a variable of the same type.

The reason for this is the same one as why a List isn't assignable to List<A>. If it was, it would make the following (not-typesafe) code possible:

List<Class<B>> bb = new ArrayList<B>();
List<Class<? extends A>> aa = bb;
aa.add(A.class);

Give Examples of Functions Which Demonstrate Covariance and Contravariance in the Cases of Both Overloading and Overriding in Java