How could argument contravariance in Liskov principle work?

Question

The basic point of Liskov substition principle is that a superclass can be replaced with a subclass which follows the same contract (behaviour). Or as Martin Fowler has put it: "Functions that use pointers or references to base classes must be able to use objects of derived classes without knowing it."

Argument contravariance is mentioned to be a part of LSP but I cannot seem to understand why and how it can work. I.e., in a subclass, the overriding method could accept wider (less derived argument).

something like this:

class Base
{
  int GetLenght(string s)
  {
     return s.lenght;
  }  
}
class Derived: Base
{
 override int GetLenght(object s)
  {
    ??  I cannot return any lenght of an object..
  }
}

How could this ever work? I mean, how could I comply with the contract if the less derived argument does not have the properties I need?

PS: I do know that most OO languages do not support that, I am just curious.

Answer 1

Argument contravariance is mentioned to be a part of LSP but I cannot seem to understand why and how it can work. I.e., in a subclass, the overriding method could accept wider (less derived argument).

First of all let's make sure we have defined our terms.

"Covariance" is a property of relations and transformations. Specifically it is the property that a particular relation is maintained over a particular transformation. "Contravariance" is the same as covariance except that it is that a particular relation is maintained but reversed over a transformation.

Let's give an example. I have a type in hand and I wish to transform it into a different type by the rule T is transformed to Func<T>. I have a relation between types: "an expression of type X can be assigned to a variable of type Y" For example, an expression of type Giraffe can be assigned to a variable of type Animal. The transformation is covariant because the relation is preserved across the transformation: an expression of type Func<Giraffe> can be assigned to a variable of type Func<Animal>.

The transformation T is transformed to Action<T> reverses the relation: Action<Animal> can be assigned to Action<Giraffe>.

But the T in Action<T> is the formal parameter type of the method represented by the delegate. So as you see, we can have contravariance on formal parameter types.

What does this mean for method overriding? When you say

class B 
{
  public virtual void M(Giraffe g) { b body }
}
class D : B 
{
  public override void M(Giraffe g) { d body }
}

That is logically the same as

class B 
{
  protected Action<Giraffe> a = g => { b body }; 
  public void M(Giraffe g) { this.a(g); }
}
class D : B 
{
  public D() {  
    this.a = g => { d body };
  }
}

Right? It would be perfectly legal for us to replace D's constructor with

   this.a = some Action<Animal>

right? However, C# -- and most other OO languages, but not all -- do not allow

class D : B 
{
  public override void M(Animal a) { d body }
}

even though logically it works just as well as generic delegate contravariance works. It's just a feature that could be implemented that never is implemented because there are so many better things to do.

How could this ever work? I mean, how could I comply with the contract if the less derived argument does not have the properties I need?

Well if you couldn't, then you wouldn't, would you?

Suppose I need

int CompareHeights(Giraffe g1, Giraffe g2)

Does it seem so implausible that I could replace this with a method

int CompareHeights(Animal a1, Animal a2)

? I need a method that compares heights of giraffes, I have a method that compares heights of animals, so I'm done, right?

Suppose I need

void Paint(Circle, Color)

Does it seem implausible that I could replace this with a method

void Paint(Shape, Color)

? That seems plausible to me. I need a method that paints circles, I have a method that paints any shape, so I am done.

If I need

int GetLength(string)

and I have

int GetLength(IEnumerable)

then I'm good. I need a method that gets the length of a string, which is a sequence of chars. I have a method that can get the length of any sequence, so I'm good.

Answer 2

lets change the example a bit:

Let us for a moment assume that here is an interface Sequence which implements a GetLength method, and that String implements this interface. Let us also assume that in your example, instead of object Sequence is used, which is a wider type then String (its actual implementation in this case).

Base base;
Derived derived;

String s;
Sequence o;

int i;
i = base.GetLength(s); // valid
i = derived.GetLength(o); // valid
i = base.GetLength(o); // obviously invalid

base = derived;
base.GetLength(s); // valid
base.getLength(o); // still invalid, 
// the contract of "Base" still requires an argument of type string,
// despite actually being of type "Derived"

You actual implementation is irrelevant, whats important is types. As long as you do not break the functionality when getting a string, you can return whatever floats your boat as length of arbitrary objects, for example:

class Derived : Base {
    override int GetLenght(Sequence s) {
      return s.GetLength();
    }
}

As you can see, you can can give derived any type of Sequence, but Base still requires the specific type of String.

Thus, contravariance works without violating the LSP in many cases. As you can see in your own example, you can not use object instead of string without arguably violating the LSP in that regard (You can and Base/Derived still don't violate the LSP, the LSP violation is hidden inside Derived, and not visible to the outside).

There are some really great articles by Eric Lippert about covariance and contravariance in C#, starting with Covariance and Contravariance in C#, Part One (which goes up to Part 11).

More can be found here:
Covariance and Contravariance

As a side note: While not violating he LSP is something to strife for, its not always the most economical choice. Working with 3rd party or legacy APIs, sometimes simply breaking the LSP can be a savior of sanity, time and resources.

Answer 3

This could work because consumers of the base class call it using the interface of the base class (they don't need to know about the derived class), and since the subclass is less restrictive, any argument that could be passed to the base class method can be passed to the subclass method. (In your example, a consumer of Base would pass a string to Base.GetLenght (and it couldn't pass any other type because it's reference is to the method with the string parameter), which is overridden by Derived.GetLenght, and Derived.GetLenght would receive the string argument, which is valid for it).

Consumers of the subclass can have a reference typed as the type of the subclass (i.e. they are aware of its less restrictive interface) and so can pass any argument accepted by the subclass. This argument is passed to the subclass method (which can accept that argument). Of course, if the overriding method was to call the base class method, it would have to convert (or substitute) the argument to something that is valid for the base class.

Of course, the overriding method has to be able to handle its argument. In the example, that means that it has to have a way of getting the 'length' of any object, and must define what that actually means.

Semantics

A well-written base class would define the contract of what the method should do (in a comment, for example). Conforming to the Liskov Substitution Principle in the derived class also requires semantically conforming to that (at least not contradicting it), so that it doesn't return unexpected (but syntactically valid) values for a consumer of the base class.

In the example, this would probably mean (depending on the semantic contract of that method) that if the argument was a string, the overriding method must return the length (requiring checking its type and casting it).

For example, the base class method might have a comment stating: returns the number of characters in the string and returns -1 if 's' is null.

The overriding method might have a comment that says Given any sequence or collection (including a string, which is treated as a sequence of characters for this purpose), this returns the number of elements in the sequence or collection, and returns -1 if the argument is null or not a collection or sequence. Note that by this definition, it does the same thing as the base class when passed a string. If it did not (for example, by returning 0 or throwing an exception when passed null), that would be a Liskov violation, even if its parameter type was the same.

Then it would have to implement that by checking the type of the argument, and casting to the appropriate type to get the size of the collection or length of the string (it could cast and call the base class for the latter).

Possible Implementation

In most object-oriented languages, When the parameter type of both methods is an object (usually implemented by a piece of data that starts with a reference to type information), the entry in the virtual method table for Derived.GetLenght could be the same as if it had the same parameter type (i.e. directly pointing to that method), with the type checking done at compile time.

If one of the methods had a parameter that was not binary compatible with the other (for example if the base class took and int (for which the compiler passed just a 32-bit value) and the derived class took an object), the overriding method (in the source code) would be compiled as a new method (with its own entry in the virtual method table), and the compiler could internally generate a method with the prototype of the base class method, that casts the argument and passes it to the overriding method. (The latter is what the virtual method table entry would point to in the derived class.)

If the method were overridden again in a class derived from the derived class, this mechanism could also be used, but the compiler would have to internally generate these overriding methods for all superclass methods (including the top level one), casting and calling the overridden method in this lowest class.