Newsgroups: php.internals
Path: news.php.net
Xref: news.php.net php.internals:100300
Mailing-List: contact internals-help@lists.php.net; run by ezmlm
Received-SPF: error (pb1.pair.com: domain dqxtech.net from 209.85.218.49 cause and error)
MIME-Version: 1.0
In-Reply-To: <CABdc3WqrKerAt9ONfMOjf2Y1KmUPaz6XMX+NGxxv2VBAhN6GvQ@mail.gmail.com>
References: <CAH0Uv3EW=KQy-DmfZrptd4LTYsudRNj+a+Ut_dcG=VG3+T9N_Q@mail.gmail.com>
 <CAF+90c_M3Pbpo0L066EeHYjgT6E1uWMuMmZiCYSbpbcaWY_EoQ@mail.gmail.com>
 <CAH0Uv3Ez5yKy43pruJ9nsFfyCVDEUMRcz3XFv7p_aAO2_D2h0g@mail.gmail.com> <CABdc3WqrKerAt9ONfMOjf2Y1KmUPaz6XMX+NGxxv2VBAhN6GvQ@mail.gmail.com>
Date: Thu, 24 Aug 2017 23:26:21 +0200
Message-ID: <CAH0Uv3HQpJprgyfH0nfQOD4O6dnZXHnTFyXWEgPFM1oQm1H-7Q@mail.gmail.com>
To: =?UTF-8?Q?Micha=C5=82_Brzuchalski?= <michal@brzuchalski.com>
Cc: Nikita Popov <nikita.ppv@gmail.com>, PHP internals <internals@lists.php.net>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Subject: Re: [PHP-DEV] Contravariance and the "empty type"
From: andreas@dqxtech.net (Andreas Hennings)

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 =3D new Box<Feline>();
$cat_box =3D new Box<Cat>();
$tiger_box =3D new Box<Tiger>();

$cat =3D new Cat();
$tiger =3D 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>); // =3D> (bool) true
var_dump(new Grower<Fruit> instanceof Grower<Banana>); // =3D> (bool) false

// Identity
var_dump(new Processor<Banana> instanceof Processor<Fruit>); // =3D> (bool)=
 false
var_dump(new Processor<Fruit> instanceof Processor<Banana>); // =3D> (bool)=
 false

// Contravariance
var_dump(new Eater<Banana> instanceof Eater<Fruit>); // =3D> (bool) false
var_dump(new Eater<Fruit> instanceof Eater<Banana>); // =3D> (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=C5=82 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 typ=
e".
>> >> 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 =E2=80=9Ctrue=E2=80=9D 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 typ=
e
>> >> "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 releva=
nt.
>> >> 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 a=
n
>> > 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 =3D [];
>>   public function addSpecificEater(AbstractSpecificFruitEater $eater) {
>>     $paramClass =3D (new
>> \ReflectionObject($eater))->getMethod('eat')->
>> getParameters()[0]->getClass();
>>     $this->eaters[$paramClass] =3D $eater;
>>   }
>>   public function eat(Fruit $fruit) {
>>     if (null !=3D=3D $specificEater =3D $this->findSuitableEater($fruit)=
) {
>>       $specificEater->eat($fruit);
>>       return true;
>>     }
>>     else {
>>       return false;
>>     }
>>   }
>>   private function findSuitableEater(Fruit $fruit) {
>>     foreach ($this->eaters as $paramClass =3D> $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
>
>
>> --
>> PHP Internals - PHP Runtime Development Mailing List
>> To unsubscribe, visit: http://www.php.net/unsub.php
>>
>>
>
>
> --
> regards / pozdrawiam,
> --
> Micha=C5=82 Brzuchalski
> about.me/brzuchal
> brzuchalski.com