28

C++ and Java support return-type covariance when overriding methods.

Neither, however, support contra-variance in parameter types - instead, it translates to overloading (Java) or hiding (C++).

Why is that? It seems to me that there is no harm in allowing that. I can find one reason for it in Java - since it has the "choose-the-most-specific-version" mechanism for overloading anyway - but can't think of any reason for C++.

Example (Java):

class A {
    public void f(String s) {…}
}
class B extends A {
    public void f(Object o) {…} // Why doesn't this override A.f?
}
Enlico
  • 23,259
  • 6
  • 48
  • 102
Oak
  • 26,231
  • 8
  • 93
  • 152

6 Answers6

25

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& )
}
David Rodríguez - dribeas
  • 204,818
  • 23
  • 294
  • 489
  • 2
    This is just the first one I can think of. If you read The Design & Evolution of C++ you will find out that all design decisions in the language boil down to: what advantage does it offer, what problems does it create, can it be implemented with the available language facilities? The committee is quite conservative, and if a feature raises any issues, unless it offers a great advantage and cannot be implemented with the current language the feature will be discarded. – David Rodríguez - dribeas Jun 10 '10 at 11:10
  • Hey David, does "The Design & Evolution of C++" actually talk about function argument contravariance? There is a section about overloading relaxation with respect to arguments (13.7.1), but it discusses the common incorrect proposal of function argument *covariance*. – Edward Z. Yang Dec 03 '13 at 02:38
17
class A {
    public void f(String s) {...}
    public void f(Integer i) {...}
}

class B extends A {
    public void f(Object o) {...} // Which A.f should this override?
}
Don Roby
  • 40,677
  • 6
  • 91
  • 113
  • 9
    Good point, though I can see no reason it cannot override both, since every `f` call can legally be redirected to `B.f`. – Oak Jun 08 '10 at 11:45
5

For C++, Stroustrup discusses the reasons for hiding briefly in section 3.5.3 of The Design & Evolution of C++. His reasoning is (I paraphrase) that other solutions raise just as many issues, and it has been this way since C With Classes days.

As an example, he gives two classes - and a derived class B. Both have a virtual copy() function which takes a pointer of their respective types. If we say:

A a;
B b;
b.copy( & a );

that is currently an error, as B's copy() hides A's. If it were not an error, only the A parts of B could be updated by A's copy() function.

Once again, I've paraphrased - if you are interested, read the book, which is excellent.

  • 1
    Do you have an example to an issue this raises? – Oak Jun 08 '10 at 09:26
  • 4
    This doesn't sound like contravariance to me. If we have `void A::copy(A*)` and `void B::copy(B*)`, and if we have that `B <: A`, then contravariance would be if we had `void B::copy(A*)` and `void A::copy(B*)`. You have covariance, which is permitted for return types but is type-unsafe for argument types. (Although I might have gotten it backwards—I have a tendency to flip these around. But I'm fairly sure.) – Antal Spector-Zabusky Jun 08 '10 at 10:29
  • @Antal The OP's question specifically mentioned hiding in C++, and the Java code in his example is covariant. –  Jun 08 '10 at 10:32
  • @Neil: I could be wrong, but I looked it up and the OP's example is contravariant. If it was covariant, then it would be a form of multiple dispatch (see http://en.wikipedia.org/wiki/Covariance_and_contravariance_(computer_science)). That was my mixup, so I deleted my answer. – stefaanv Jun 08 '10 at 10:55
  • @stef I agree with you, it is contra-variant. – fredoverflow Jun 08 '10 at 11:16
  • Neil: in Oak's example, the subclass's method takes an argument of a *more* general type: `B <: A` and `Object :> String`. In your example, the subclass's method takes an argument of a *less* general type: `B <: A` and `B <: A`. – Antal Spector-Zabusky Jun 08 '10 at 16:51
  • This is an argument on why in C++ the method in the derived class hides the method in the base class (as compared to Java pulling the base method into the derived class), but it is unrelated to contra-variance which is the main question. Still, +1 for the contents. – David Rodríguez - dribeas Jun 10 '10 at 10:29
3

Although this is a nice-to-have in any oo language, I still need to encounter it's applicability in my current job.

Maybe there isn't really a need for it.

xtofl
  • 40,723
  • 12
  • 105
  • 192
2

Thanks to Donroby for his answer above - I'm just extending on it.

interface Alpha
interface Beta
interface Gamma extends Alpha, Beta
class A {
    public void f(Alpha a)
    public void f(Beta b)
}
class B extends A {
    public void f(Object o) {
        super.f(o); // What happens when o implements Gamma?
    }
}

You're falling on a problem akin to the reason multiple implementation inheritance is discouraged. (If you try to invoke A.f(g) directly, you'll get a compile error.)

Jean Hominal
  • 16,518
  • 5
  • 56
  • 90
  • 7
    But `super.f(o)` should raise a compile-time type error: it can be statically known that there is no `super.f` which takes an `Object`. (What would happen if you called `new B().f("bad")`, for instance? It's not merely ambiguous, but type-unsafe!) There are a large class of type-unsafe programs which arise if you allow unrestricted use of `super`, but you can have parameter contravariance without this. – Antal Spector-Zabusky Jun 08 '10 at 17:46
  • Well, I thought that if we want to build parameter contra-variance, there would have to be a specification for `super` (but as it stands, there is no specification that could be consistent and useful). Then, let's disallow `super` completely in B.f(Object). What, then, is the point of the feature, except adding yet one more method linking rule to C++? – Jean Hominal Jun 09 '10 at 09:45
1

Thanks to donroby's and David's answers, I think I understand that the main problem with introducing parameter contra-variance is the integration with the overloading mechanism.

So not only is there a problem with a single override for multiple methods, but also the other way:

class A {
    public void f(String s) {...}
}

class B extends A {
    public void f(String s) {...} // this can override A.f
    public void f(Object o) {...} // with contra-variance, so can this!
}

And now there are two valid overrides for the same method:

A a = new B();
a.f(); // which f is called?

Other than the overloading issues, I couldn't think of anything else.

Edit: I've since found this C++ FQA entry (20.8) which agrees with the above - the presence of overloading creates a serious problem for parameter contra-variance.

Oak
  • 26,231
  • 8
  • 93
  • 152
  • It could go for the most specific one (string, in this case). – devoured elysium Sep 20 '10 at 09:43
  • @devoured I'm guessing it can, but that means introducing a completely new resolution mechanism to the language - since this is not overloading. A has only one f(), so overloading does no come into play when calling f on a variable with type A. – Oak Jan 09 '11 at 22:13
  • It's not really a new resolution mechanism though Oak, is it? It would be resolved in exactly the same way as when calling the method in B with a String as the parameter. It's the same static resolution strategy used for calling overloaded methods, just applied in a different context. – Elias Vasylenko Aug 04 '12 at 11:34
  • @EliasVasylenko I guess it could be resolved following the same algorithm, but notice that unlike overloading, this resolution will have to take place at *runtime* - because the code for `B` may not even be available when `a.f();` is compiled. [The overloading resolution algorithm is one of the most complicated things in the entire Java specifications](http://docs.oracle.com/javase/specs/jls/se7/html/jls-15.html#jls-15.12), and I'm really not sure running it in runtime is a good idea. – Oak Aug 04 '12 at 19:42
  • The code for B may not be available when a.f(); is compiled, but it doesn't need to be! This part of the override/overload resolution only needs to be performed when B is compiled. To illustrate: consider the resolution for contravariant overrides being done as a precompilation step. We know that the example you gave will compile fine and give the expected behaviour as things stand, and that behaviour does not need to change. [TBC...] – Elias Vasylenko Aug 05 '12 at 13:12
  • [Cont...] A could compile as normal, then when we compile: class B extends A { public void f(Object o) {...} } We just need to tell the compiler to recognise that f(Object) is the most specific override available for f(String) and then replace: public void f(Object o) {...} with: public void f(Object o) {...} public void f(String o) {f((Object) o);} Then continue to compile as normal! Maintains binary backwards compatibility and everything. It does cause an issue with generic parameters, though. I wrote a bit more (too much, actually, I'm bad at blogging) here: [TBC...] – Elias Vasylenko Aug 05 '12 at 13:17
  • [Cont...] http://elionline.co.uk/blog/2012/08/02/on-contravariant-method-parameters-in-java/ Sorry for the flood of comments! Silly character limit :). Also, silly removal of formatting! That last comment looks awful :s... – Elias Vasylenko Aug 05 '12 at 13:18
  • @EliasVasylenko I don't see how this can be done in compile-time. An invocation of `a.f()` will jump to the vtable entry for `A.f` - and there is only one, because there's no overloading there - and then what? Where would that entry point to? You need to pick the appropriate method based on the static type of the argument(s), but you have to do it in run-time because the method invocation will be resolved, in the client side, independently from `B`'s implementation. Well maybe you addressed this in your blog, I confess I haven't had a chance to read it yet :) – Oak Aug 05 '12 at 16:37
  • An invocation of a.f(String) will jump to the vtable for A.f(String), then the VM will see that it has been overridden by B.f(String) for this object and run that, in exactly the same was as happens at the moment. The VM doesn't even need to be modified from the way it handles overrides atm. The reason B.f(String) now exists - in this example - is because when B was compiled it was automatically generated by the compiler to satisfy the interface of A, since it knows it can be forwarded to the contravariantly compatible B.f(Object). Simple as that! I think you are overcomplicating things :). – Elias Vasylenko Aug 05 '12 at 20:53
  • @Oak: Having a method which accepts `Object` implicitly override one which accepts something else would be problematic, certainly. On the other hand, in some cases it may be useful to explicitly specify that a one written-out piece of source code should be regarded as both overriding or implementing one or more particular base-class or interface methods with particular parameter types, and also as implementing a new type with more general parameter types. – supercat Oct 19 '12 at 19:31