If Car is a subtype of Vehicle, why is Vehicle->void considered a subtype of Car->void?

Question

Reading a fundamental paper about inheritance, I am unable to understand the reasoning shown below. Apparently it is correct as contravariance does work, I would just like to understand the reasoning. First, it is shown that:

• If a function returns Car, then it is a subtype of function returning Vehicle. That is because all vehicles are also cars. (Covariance of return types).
• If a function takes Vehicle, then it is a subtype of a function that takes Car because "In general every function on vehicles is also a function on cars."
  I cannot understand the explanation of this inversion, so I am showing this below:

My naive interpretation:

As functions on ALL vehicles will work on ALL cars, then the function taking Vehicle is a subtype of function taking Car because the set of functions of Vehlice is smaller - Car can have more functions.

Answer 1

Your question is about covariance and contravariance of functions, and I think it will help for your understanding if we map some of the language-agnostic symbolic relationships in the paper to actual code. In C++, the function being discussed here would be:

int GetSpeedOf(Vehicle vehicle);

Subtype must be understood in terms of Liskov-substitution; if a function is expecting any type of animal, you can give it a cat and everything should work fine, but the opposite is not the case; a function requiring a cat could not work on any type of animal.

Assuming you understand that it is possible to pass a Car to the GetSpeedOf function, now we will address the more complicated case of functions accepting functions, which brings contravariance into the picture.

The following CarWrapper has a private Car which it will do stuff to, using a function supplied from outside. That function must work for Cars. So if you give a function which works more generally for all Vehicles, that's fine.

#include <functional>

class Vehicle { };
class Car : public Vehicle { };

class CarWrapper
{
    Car car;
    typedef std::function<auto(Car) -> void> CarCallback;
    CarCallback functionPtr;

public:
    void PassCallback(CarCallback cb)
    {
        functionPtr = cb;
    }

    void DoStuff()
    {
        functionPtr(car);
    }
};

void Works(Vehicle v){}

int main() {
    CarWrapper b;
    b.PassCallback(&Works);
}

So, the PassCallback function is expecting type CarCallback ("Car -> void" in your paper), but we give it a subtype, "Vehicle -> void", because the type of "&Works" is actually std::function<auto(Vehicle) -> void>. Hence "If a function takes Vehicle, then it is a subtype of a function that takes Car". This is possible because all of the operations that the "Works" function will do, must also be possible on what is actually passed in - a car.

A use-case of this, is that the Works function could also be passed to a BoatWrapper class, which expects a function operating on boats. We can give a subtype of that functiontype, "Vehicle -> void", knowing that all operations in the actual passed function must also be available on the Boat passed to it, since Boat is a subtype of Vehicle, and our actual function only uses the more general Vehicle'ness of the parameter to operate.

Covariance, on the other hand, operates on the return type; if the CarWrapper class expected a callback that generates a Car for us, we would not be able to pass in a Vehicle-generating function, because then CarWrapper would not be able to use the result in car-specific ways.

If we had a function expecting a Vehicle generator though, we would be able to give it a Car Generator or a Boat Generator; hence (void -> Car) is a subtype of (void -> Vehicle) iff Car is a subtype of Vehicle.

Covariance implies that the subtype relationship stays in the same direction, so we can keep sticking in another function application, and still the "Car side" will be a subtype of the "Vehicle side", i.e.:

Car is a subtype of Vehicle means that:
(void -> Car) is a subtype of (void -> Vehicle) - as in the code sample above
(void -> (void -> Car)) is a subtype of (void -> (void -> Vehicle))
(void -> (void -> (void -> Car))) is a subtype of (void -> (void -> (void -> Vehicle)))

What this means is that if we expected a VehicleFactoryFactoryFactory, we should be satisfied when given a CarFactoryFactoryFactory:

#include <functional>

class Vehicle { };
class Car : public Vehicle { };

typedef std::function<auto() -> Vehicle> VehicleFactory;
typedef std::function<auto() -> VehicleFactory> VehicleFactoryFactory;
typedef std::function<auto() -> VehicleFactoryFactory> VehicleFactoryFactoryFactory;

void GiveMeAFactory(VehicleFactoryFactoryFactory factory)
{
    Vehicle theVehicle = factory()()();
}

typedef std::function<auto() -> Car> CarFactory;
typedef std::function<auto() -> CarFactory> CarFactoryFactory;
typedef std::function<auto() -> CarFactoryFactory> CarFactoryFactoryFactory;

Car ActualCarCreateFunc() { return Car(); }
CarFactory CarFactoryCreateFunc() { return &ActualCarCreateFunc; }
CarFactoryFactory CarFactoryFactoryCreateFunc() { return &CarFactoryCreateFunc; }

int main() {
    GiveMeAFactory(&CarFactoryFactoryCreateFunc);
}

With contravariance of the parameter types, the relationship inverts with each function application.

Car is a subtype of Vehicle means that:
(Vehicle -> void) is a subtype of (Car -> void)
((Car -> void) -> void) is a subtype of ((Vehicle -> void) -> void)
(((Vehicle -> void) -> void) -> void) is a subtype of (((Car -> void) -> void) -> void)

In the case of contravariance, it is very difficult to understand this in intuitive terms. That's why my CarWrapper only attempts to explain it for a single application of the rule, while the CarFactory example contains three applications of covariance.