Contravariance and the "empty type" View as Markdown

This discussion made me have another look at the Generics RFC,
https://wiki.php.net/rfc/generics

It seems to me that the proposal violates LSP, because it does not
correctly implement contravariance.
Look at the part where it talks about instanceof.

interface Feline {}
class Cat implements Feline {}
class Tiger implements Feline {}

class Box<T is Feline> {
function entrap(T $feline) {}
}

$feline_box = new Box<Feline>();
$cat_box = new Box<Cat>();
$tiger_box = new Box<Tiger>();

$cat = new Cat();
$tiger = new Tiger();

assert($feline_box instanceof Box<Feline>); // -> ok.
assert($tiger_box instanceof Box<Feline>); // -> ok.
assert($cat_box instanceof Box<Feline>); // -> ok.

assert($cat instanceof Feline); // -> ok.
assert($tiger instanceof Feline); // -> ok.

$feline_box->entrap($cat); // -> ok.
$cat_box->entrap($cat); // -> ok.
$tiger_box->entrap($cat); // -> Fatal error: Uncaught TypeError.

So, even with generics, we still need to think about contravariance.

We need to distinguish 3 types of type parameter on classes:

1. Those which are used in method return types.
2. Those which are used in method parameter types.
3. Those which are used in both.

For these 3 cases, the following rules would need to apply:

1. Contravariance.
2. Covariance
3. Identity.

E.g.

interface Fruit;
interface Banana extends Fruit;

interface Grower<T is Fruit> {
function grow() : T;
}

interface Processor<T is Fruit> {
function process(T $fruit) : T;
}

interface Eater<T is Fruit> {
function eat(T $fruit);
}

// Covariance
var_dump(new Grower<Banana> instanceof Grower<Fruit>); // => (bool) true
var_dump(new Grower<Fruit> instanceof Grower<Banana>); // => (bool) false

// Identity
var_dump(new Processor<Banana> instanceof Processor<Fruit>); // => (bool) false
var_dump(new Processor<Fruit> instanceof Processor<Banana>); // => (bool) false

// Contravariance
var_dump(new Eater<Banana> instanceof Eater<Fruit>); // => (bool) false
var_dump(new Eater<Fruit> instanceof Eater<Banana>); // => (bool) true

The only supertype for all Eater<*> types would be Eater<EMPTY_TYPE>.
This super-eater has the absolute fruit allergy.

On Wed, Aug 23, 2017 at 9:18 AM, Michał Brzuchalski
michal@brzuchalski.com wrote:

Hi Andreas,

2017-08-22 21:11 GMT+02:00 Andreas Hennings andreas@dqxtech.net:

On Tue, Aug 22, 2017 at 10:39 AM, Nikita Popov nikita.ppv@gmail.com
wrote:

On Tue, Aug 22, 2017 at 4:27 AM, Andreas Hennings andreas@dqxtech.net
wrote:

Hello list,
for a while I had this thought about contravariance and an "empty type".
I don't expect too much of it, for now I just want to share the idea.
Maybe this concept even exists somewhere in a different language, and
I am not aware of it.

I think it has some overlap with generics,
https://wiki.php.net/rfc/generics.

---

I think I am not the first one to suggest allowing contravariance for
method parameters.
E.g. here, "PHP RFC: Parameter Type Widening"
https://wiki.php.net/rfc/parameter-no-type-variance

From this RFC:

Unfortunately “true” contravariance for class types isn't part of this
RFC, as implementing that is far more difficult, and would require
additional rules about autoloading and/or class compilation, which
might
only be acceptable at a major release.

For anyone not familiar with the term:

interface I {
function foo(J $arg);
}

interface J extends I {
function foo(I $arg);
}

So: While return types in a child method should be either the same or
more narrow, the parameter types should be either the same or more
permissive.
Without this it would break Liskov substitution.

---

Now for my actual proposal: The "empty type".
We can think of a type (class/interface or primitive) as a set or a
constraint on the kind of values that it allows.
There is a special type, "mixed", which allows all values. We could
also think of it as the union of all types.

A natural extension of this concept, on the other end, would be a type
"nothing" or "empty", which would allow no values at all.
We could think of this as the intersection of all types.
In fact it is already sufficient to intersect just two distinct
primitive types to get this empty type:
"All values that are at the same time string and integer" clearly is
an empty type.

How would this ever be useful?
If we write a base class or interface for a category of interfaces
that have a similar signature.

interface Fruit {..}
interface Apple extends Fruit {..}
interface Banana extends Fruit {..}

interface AbstractFruitEater {
function eat(EMPTY_TYPE $fruit);
}

interface BananaEater extends AbstractFoodEater {
function eat(Banana $banana);
}

interface AppleEater extends AbstractFoodEater {
function eat(Apple $apple);
}

One could imagine a component that has a list of AbstractFruitEater
objects, and chooses one that is suitable for the given fruit, using
instanceof.
I think the correct term is "chain of responsibility".

function eatApple(array $fruitEaters, Apple $apple) {
foreach ($fruitEaters as $eater) {
if ($eater instanceof AppleEater) {
$eater->eat($apple);
break;
}
}
}

---

We can go one step further.

The natural parameter type to use for param $fruit in
AbstractFruitEater::foo() would not be the global EMPTY_TYPE, but
something more specific:
The projected intersection of all real and hypothetical children of
interface Fruit.
Obviously this does not and cannot exist as a class or interface.

Practically, for the values it allows, this is the same as the global
EMPTY_TYPE.
But unlike the EMPTY_TYPE, this would poses a restriction on the
parameter type in child interfaces.

What would be the syntax / notation for such a projected hypothetical
subtype?
I don't know. Let's say INTERSECT_CHILDREN<Fruit>

So, would the following work?

interface Food {..}
interface Fruit extends Food {..}
interface Banana extends Fruit {..}

interface AbstractFoodEater {
function eat(INTERSECT_CHILDREN<Food> $food);
}

interface AbstractFruitEater extends AbstractFoodEater {
function eat(INTERSECT_CHILDREN<Fruit> $fruit);
}

interface BananaEater extends AbstractFruitEater {
function eat(Banana $banana);
}

I'm not sure.
Liskov would not care. Both AbstractFoodEater and AbstractFruitEater
are useless on their own.
Maybe there are other logical conflicts which I don't see.

---

Obviously with generics this base interface would no longer be relevant.
https://wiki.php.net/rfc/generics

interface FruitEater<FruitType> {
function eat(FruitType $fruit);
}

// This is not really necessary.
interface BananaEater extends FruitEater<Banana> {
function eat(Banana $banana);
}

So, would the "empty type" become obsolete? Maybe.
I did not arrive at a final conclusion yet. It still seems too
interesting to let it go.

-- Andreas

What's the purpose of this construction? I get the general idea (work
around
LSP variance restrictions without generics), but I don't see how the
practical use would look like.

To be honest I am still not fully convinced myself.
I just couldn't resist because this idea was haunting me for too long.

After all, using the empty type as an
argument implies that the method may not ever be called, so wouldn't an
interface using it be essentially useless?

Nikita

Interfaces like AbstractFruitEater would mainly be used to categorize
its child interfaces, and as a formalized constraint on method
::eat().

Any child interface of AbstractFruitEater must have a method eat(),
which must have exactly one required parameter (and as many optional
parameters as it wants). This parameter must have a type hint
compatible with the constraint mentioned above (in case of EMPTY_TYPE,
there is no constraint on the parameter type, it could as well be
"mixed").

Any component that wants to call $eater->eat($apple) on an $eater of
type AbstractFruitEater, needs to do one of two things first:

• Use reflection to check for the first parameter's type, if it allows
  Apple.
• Use instanceof to check if it implements AppleEater.

If the $eater was only type-hinted as "object" instead of
AbstractFruitEater, the reflection would have to do more work. It
would have to check if a method eat() exists, and then check the first
parameter's type.

A component I might have built with the EMPTY_TYPE or with
INTERSECT_CHILDREN<Food> would be something like this:

// Base interface for eaters that only eat a specific fruit type.
interface AbstractSpecificFruitEater {
function eat(INTERSECT_CHILDREN<Food> $fruit);
}

// Interface for eaters that eat any fruit.
// This could extend AbstractSpecificFruitEater, but doesn't have to.
interface FruitEater /* extends AbstractSpecificFruitEater */ {
function eat(Fruit $fruit);
}

class ChainedFruitEater implements FruitEater {
private $eaters = [];
public function addSpecificEater(AbstractSpecificFruitEater $eater) {
$paramClass = (new
\ReflectionObject($eater))->getMethod('eat')->
getParameters()[0]->getClass();
$this->eaters[$paramClass] = $eater;
}
public function eat(Fruit $fruit) {
if (null !== $specificEater = $this->findSuitableEater($fruit)) {
$specificEater->eat($fruit);
return true;
}
else {
return false;
}
}
private function findSuitableEater(Fruit $fruit) {
foreach ($this->eaters as $paramClass => $eater) {
if ($fruit instanceof $paramClass) {
return $eater;
}
}
}
}

Without the EMPTY_TYPE or INTERSECT_CHILDREN<Food>, the interface
AbstractSpecificFruitEater could not define a method ::eat().

Classes implementing AbstractSpecificFruitEater would not know that a
method ::eat() is required, and what structure it must have.

The reflection line would need to check if the method exists, if the
method is public and non-static, if the parameter exists, if it has a
type hint class.

In the end I implemented this another way.
My specific fruit eaters now always accept any fruit, but do an
instanceof check inside. They have an added method like
"acceptsFruitClass($class)".

I don't know if I would replace my current implementation with the code
above.
I think I rather wait for generics.

NOTE: When I say "type hint", I do not distinguish what is currently
implemented natively, what is in the @param PhpDoc, and what might be
implemented natively in the future. E.g. I don't even know if "mixed"
or "object" is currently implemented or not in latest PHP 7.

"object" type hint and return type is a part of current 7.2 release,
"mixed" not

--

--
regards / pozdrawiam,

Michał Brzuchalski
about.me/brzuchal
brzuchalski.com