State of Generics and Collections

Hi Rob,

Invariance would make arrays very difficult to adopt, as a library can not start type hinting generic arrays without breaking user code, and users can not pass generic arrays to libraries until they start using generic arrays type declarations.

This seems like a strawman argument, to a degree. In other words, it seems like you could combine static arrays and fluid arrays to accomplish what you are seeking to do. In other words, use static arrays but allow casting to treat it as "fluid."

In other words, simply cast to get your example to compile:

function f(array<int> $a) {}
function g(array $a) {}

$a = (array<int>) [1]; // array unless cast

f($a); // ok
g((array)$a); // ok

And the other way:

function f(array<int> $a) {}
function g(array $a) {}

$a = [1];

f((array<int>)$a); // ok, type check done during cast
g($a); // ok

There is potential for breaking changes in both of your examples:

If f() is a library function that used to be declared as f(array $a), then changing its declaration to f(array<int> $a) is a
breaking change in the Static Arrays flavour, as it would break
library users until they change their code to add casts.

I don't think we should be scared of breaking changes; php 9.0 is coming 🔜 anyway. You could also consider it as "an array might be array<T>, but an array<T> is always an array"

Similarly, the following code would break (when calling g()) if h()
was changed to return an array<int>:

function h(): array {}
function g(array $a);

$a = h();
g($a);

Casting would allow users to pass generic arrays to libraries that
don't support generics yet, but that's expensive as it requires a
copy.

Why does it require a copy? It should only require a copy if the contents are changed (CoW) and at that point, you can know what rules to apply based on the coerced/casted type. I'm doing a similar thing for the Literal Strings RFC, where it is a type that is also indistinguishable from a string until something happens to it and it is no longer a literal string.

So passing a array<int> to a function that only accepts an array shouldn't matter. Once inside that function, all type-checking can be disabled for that array. One approach to that could be to just smack a "type-check strategy" function pointer on zvals, potentially, as that would give the most flexibility for casting, aliases, generics, etc. Don't get me started on the current type checking; it is a mess and inconsistent depending on what is doing the checking (constructor promoted props, properties, method args, function args). Then you can just copy the zval, change a function pointer, but point it to the same array (which will CoW) and change the strategy during casting.

In other words, you could cheaply cast an array<int> to array<string> by (essentially) changing a couple of function pointers, but array<string> to array<int> would be expensive. So I imagine there would strategies for changing strategies... probably. I don't know, I literally just thought of this off the top of my head, so it probably needs more work.

Best Regards,
Arnaud

— Rob

Regarding the Collections PR, I personally really don't like it:

• It implements something which would be trivial if we had reified
generics. If this ever gets merged, and generics happen later, it would
be probably outdated and quirkiness the language has to carry around.
• It's not powerful. But rather a quite limited implementation. No
overrides of the built-in methods possible. No custom operations ("I
want a dict where a specific property on the key is the actual unique
key", "I want a custom callback be executed for each modification").
It's okay as a PoC, but far from a complete enough implementation.
I think we weren't that clear on that section, then. The intent is that dedicated collection classes are, well, classes. They can contain additional methods, and probably can override the parent methods; though the latter may have some trickiness if trying to access the internal data structure, which may or may not look array-ish. (That's why it's just a PoC and we're asking for feedback if it's worth trying to investigate further.)
I assumed so, as said "okay as a PoC" :-)
• It's a very specialized structure/syntax, not extensible for
userland at all. Some functionality like generic traits, where you'd
actually monomorphize the contained methods would be much more
flexible. E.g. class Articles { use Sequence<Article>; }. Much less
specialized syntax, much more extensible. And generic traits would be
doable, regardless of the rest of the generics investigation.
In fact, generic traits (essentially statically replacing the generic
arguments at link-time) would be an useful feature which would remain
useful even if we had fully reified generics.
I recognize that some functionality will need support of internal
zend_object_handlers. But that's not a blocker, we might provide some
default internal traits with PHP, enabling the internal class handlers.
So to summarize, I would not continue on that path, but really invest
into monomorphizable generic traits instead.
Interesting. I have no idea why Arnaud has mainly been investigating reified generics rather than monomorphized, but a monomorphized trait has potential, I suppose. That naturally leads to the question of whether monomorphized interfaces would be possible, and I have no idea there. (I still hold out hope that Levi will take another swing at interface-default-methods.)

Though this still wouldn't be a path to full generics, as you couldn't declare the inner type of an object at creation time, only code time. Still, it sounds like an area worth considering.

--Larry Garfield

Nikita did the investigation into monomorphized generics a long time ago
(https://github.com/PHPGenerics/php-generics-rfc/issues/44). So it was
mostly concluded that reified generics would be the way to go. The
primary issue Arnauld is currently investigating, is propagation of
generic information via runtime behaviour, inference etc.

It would be solving large amounts of problems if you'd have to fully
specify the specific instance of a generic every time you instantiate
one. But PHP is at heart a dynamic language where typing is generally
opt-in (also when constructing new objects of generic classes for
example). And we want to avoid "new List<Entry<Foo<Something>,
WeakReference<GodObject>>>()"-style nesting where not necessary.

"Monomorphization of interfaces" does not really make a lot of sense as
a concept. Ultimately in an interface, all you do is providing
information for classes to type check against, which happens at link
time, once. (Unless you mean interface-default-methods, but that would
just be an implicitly implemented trait implementation wise, really.)

But sure, generic interfaces and monomorphized generic traits are
perfectly implementable today. In fact, I'd definitely suggest we'd
start out by implementing these, orthogonally from actual class generics.

Bob

Hi Larry,

In fact, generic traits (essentially statically replacing the generic
arguments at link-time) would be an useful feature which would remain
useful even if we had fully reified generics.
I recognize that some functionality will need support of internal
zend_object_handlers. But that's not a blocker, we might provide some
default internal traits with PHP, enabling the internal class handlers.
So to summarize, I would not continue on that path, but really invest
into monomorphizable generic traits instead.

Interesting. I have no idea why Arnaud has mainly been investigating reified generics rather than monomorphized, but a monomorphized trait has potential, I suppose. That naturally leads to the question of whether monomorphized interfaces would be possible, and I have no idea there. (I still hold out hope that Levi will take another swing at interface-default-methods.)

Though this still wouldn't be a path to full generics, as you couldn't declare the inner type of an object at creation time, only code time. Still, it sounds like an area worth considering.

Monomorphization as a solution to generic classes has a memory usage
issue (it requires duplicating the class entry, methods, props, and
also opcodes if method bodies can reference type parameters), and does
not solve all the complexity:
https://github.com/PHPGenerics/php-generics-rfc/issues/44.

This would be less a problem for traits, as there is already some
amount of duplication.

Best Regards,
Arnaud

Hey Arnauld,

Hi Bob,

The fluid Arrays section says "A PoC has been implemented, but the performance impact is still uncertain". Where may I find that PoC for my curiosity? I'm imagining the implementation of the array types as a counted collection of types of the entries. But without the PoC I may only guess.
I may publish the PoC at some point, but in the meantime here is a
short description of how it's implemented:

• The zend_array has a zend_type member representing the type of its elements
• Everytime we add or update a member, we union its type with the
  array type. For simple types it's just a |= operation. For arrays with
  a single class it's also simple. For complex types it's more expensive
  currently, but it may be possible to cache transitions to make this
  cheaper.
• Updating the array type on deletes requires to either maintain a
  counter of every type, or to re-compute the type entirely everytime.
  Both are probably too expensive. Instead, we don't update the type on
  deletes, but we re-compute the type entirely when a type check fails.
  This is based on two hypotheses: 1. A delete rarely changes an array's
  type in practice, and 2. Type checks rarely fail

That sounds like a clever way to do it. I like this approach.

• References are treated as mixed, so adding a reference to an array
  or taking a reference to an element changes its type to mixed. Passing
  an array<mixed> to a more specific array<something> will cause a
  re-compute, which also de-refs every reference.

Classifying a reference as mixed certainly makes this work and I guess
it's probably an acceptable overhead. References into (big) arrays are
not that common. Short of doing a foreach by-ref, but that's anyway an
O(n) operation generally.

• Updating a nested element requires updating the type of every parent

Does it actually? It just requires updating the type of the parent, if
the own type is actually changed. But types of arrays don't change all
the time, so that's likely an amortized constant time operation with
respect to inserts/updates.

It also says "Another issue is that [...] typed properties may not be possible.". Why would that be the case? Essentially a typed property would just be a static array, which you describe in the section right below.
It becomes complicated when arrays contain references or nested
arrays. Type constraints must be propagated to nested arrays, but also
removed when an array is not reachable via a typed property anymore.

E.g.

class C {
public array<array<int>> $prop;
}

$a = &$c->prop[0];
$a[] = 'string'; // must be an error
unset($c->prop[0]);
$a[] = 'string'; // must be accepted
In this case $a will decay from a RC=1 reference to a normal value.
During the unreferencing operation the type restrictions can be dropped.
That operation is only O(n) if it actually contains other references.

$b = &$c->prop[1];
$b[] = 'string'; // must be an error
$c->prop = [];
$a[] = 'string'; // must be accepted

I don't remember all the possible cases, but I didn't find a way to
support this that didn't involve recursively scanning an array at some
point. IIRC, without references it's less of an issue, so a possible
way forward would be to forbid references to members of typed
properties. Unfortunately this breaks pass-by-reference, e.g.
sort($c->prop). out/inout parameters may be part of a solution, but
with more array separations than pass-by-ref.

Yes, you'll have to scan the array recursively, but only if it contains
references (which you know thanks to array<mixed> or
array<array<mixed>>). And you also only need to descend into arrays
which contain references.

If something contains a reference, you just slap a property type onto it

• like "foreach entry in array { if entry is reference {
  add_type_source(inner type of entry) } }" - thus, in case of
  array<array<int>>, you slap array<int> onto it. This operation is only
  O(n) if the array type actually contains references (i.e. it will
  mismatch due to array<mixed>, and you have to iterate anyway).

So it will just work like references to property types do: these can
also never violate the type containing them. At least in my mind.

I'd also be happy to chat more about it off-list, but possibly easier
too once the patch is public.

Best Regards,
Arnaud

Overall I would not focus too much on making the case "reference into
array" too much of a blocker. It should work, but it's fine if it comes
with a couple rough edges regarding performance. I don't think arrays
where you hold a reference into them are commonly passed around or big.

There are a few edge cases like state machines built with array
references, but the solution to these is ... don't type the property
containing it then. And if it really becomes a problem, we may still
invest time into it after landing it.

Thanks,

Bob

Hi Bob,

The fluid Arrays section says "A PoC has been implemented, but the
performance impact is still uncertain". Where may I find that PoC for my
curiosity? I'm imagining the implementation of the array types as a counted
collection of types of the entries. But without the PoC I may only guess.

I may publish the PoC at some point, but in the meantime here is a
short description of how it's implemented:

• The zend_array has a zend_type member representing the type of its
  elements
• Everytime we add or update a member, we union its type with the
  array type. For simple types it's just a |= operation. For arrays with
  a single class it's also simple. For complex types it's more expensive
  currently, but it may be possible to cache transitions to make this
  cheaper.
• Updating the array type on deletes requires to either maintain a
  counter of every type, or to re-compute the type entirely everytime.
  Both are probably too expensive. Instead, we don't update the type on
  deletes, but we re-compute the type entirely when a type check fails.
  This is based on two hypotheses: 1. A delete rarely changes an array's
  type in practice, and 2. Type checks rarely fail
• References are treated as mixed, so adding a reference to an array
  or taking a reference to an element changes its type to mixed. Passing
  an array<mixed> to a more specific array<something> will cause a
  re-compute, which also de-refs every reference.
• Updating a nested element requires updating the type of every parent

It also says "Another issue is that [...] typed properties may not be
possible.". Why would that be the case? Essentially a typed property would
just be a static array, which you describe in the section right below.

It becomes complicated when arrays contain references or nested
arrays. Type constraints must be propagated to nested arrays, but also
removed when an array is not reachable via a typed property anymore.

E.g.

class C {
public array<array<int>> $prop;
}

$a = &$c->prop[0];
$a[] = 'string'; // must be an error
unset($c->prop[0]);
$a[] = 'string'; // must be accepted

$b = &$c->prop[1];
$b[] = 'string'; // must be an error
$c->prop = [];
$a[] = 'string'; // must be accepted

I don't remember all the possible cases, but I didn't find a way to
support this that didn't involve recursively scanning an array at some
point. IIRC, without references it's less of an issue, so a possible
way forward would be to forbid references to members of typed
properties. Unfortunately this breaks pass-by-reference, e.g.
sort($c->prop). out/inout parameters may be part of a solution, but
with more array separations than pass-by-ref.

Best Regards,
Arnaud

Another one that I don't see mentioned that naturally follows from a
conversation I had with you a few weeks ago is operators on arrays. Namely,
the behavior of the + operator when used with arrays. How this would
interact with generics, and with different approaches to generics and
arrays, is probably something that will require attention. Operators in
general present some challenges (though not unsolvable ones, just
complicated ones) to languages that try to use both generics and loose
types, because operators generally don't have a way for the programmer to
help the engine with typing during the evaluation.

Jordan

Hi Mike,

It seems Java-style Generics are viewed as the proper archetype for Generics in PHP? I would challenge the wisdom of taking that road considering how different the compilers and runtimes are between the Java and PHP. PHP should seek out solutions that are a perfect fit for its nature and not pursue parity with Java.

As PHP is primarily a web development language — vs. a systems language like C or Rust, or an enterprise application language like Java or C# — reducing code complexity for reading and understanding is a very important attribute of the language.

PHP is also a unique language and novel solutions benefit a unique language. PHP should pursue solutions that result in less complex code even if not found in other languages. Your collections idea is novel — which is great — but there are probably even more novel solutions to address other needs vs. going full-on with Java-style generics.

Consider if adding type aliases; or augmenting, enhancing, or even merging classes, interfaces, and/or traits to address the needs Java-style generics would otherwise provide. I would work on some examples but I think you are more likely to adopt the features you come up with on your own.

Part of the appeal for Java/C#/Kotlin-like generics is that they are
well understood and their usefulness is not to be proven.

Yes, they are well understood by programmers who develop in a significantly more complex language. So while I acknowledge that appeal, I think the complexity provides benefit for most PHP developers.

Also they fit well with the object-oriented aspect of the language,

Even more importantly, PHP is not Java and what works for a compiled and strongly typed language does not necessarily work for a interpreted language with looser typing and where only one file can be seen by the compiler at a time.

and many PHP projects already use them via PHPStan/Psalm.

As an aside, it is an interesting data point that such as small percent of PHP developers actually use those tools.

Could it be because of their complexity? I cannot say for certain that is why, but it surely is a factor to ponder.

More experimental alternatives would be more risky.

Fair point

I would be interested to see suggestions or examples, however.

Two examples were already shown and/or mentioned: the collections class and automatic interface implementation based on structural typing.

I am sure they are more, and if I am able to identify any as the topic is discussed I will bring them up.

As for type-erasure, I am on the fence, but I find the proposed "how" problematic.
I can see wanting some code to be type-checked and other code not, but I think more often developers would want code type-checked during development and testing but not for staging or production. And if the switch for that behavior is in every file that means modifying every file during deployment. IMO that is just a non-starter.

The reason for this "how" is that type checking is also coercing, so
disabling it "from the outside" may break a program that's not
designed for that.

AFAIK if you are using type checking then the code is never correct if the types do not match, the errors just may go unreported. Thus I do not see how the code that uses code with types could not be designed for code with types; disabling if from the outside does not change that.

Disabling type checking is not like changing the syntax that is allowed by strict mode, AFAIK.

type checking is also coercing

However, I do not understand your claim here. Is there some form of typing that would modify code behavior if the types were erased? Would allowing that even make sense? Can you give an example of this?

That's why this is something that should be enabled
on a per-file basis, and can probably not be switched on/off depending
on the environment.

I reserve my opinion on this awaiting your example(s).

P.S. Also consider offering the ability for a function or class method to "type" a parameter or variable based on an interface and then allow values that satisfy that interface structurally[1] but not necessarily require the class to explicitly implement the interface.

Unfortunately, I believe that structural types would be very expensive
to implement at runtime. Static analysers could support this, however
(PHPStan/Psalm support some structural types already).

But would it really be too expensive? Has anyone ever pursued considering it, or just dismissed it summarily? Seems to me it could handled rather inexpensively with bitmaps.

-Mike

On Fri, Aug 23, 2024 at 4:27 PM Larry Garfield larry@garfieldtech.com
wrote:

Moving those definitions to attributes is certainly possible, though AFAIK
both the PHPStan and Psalm devs have expressed zero interest in it.

Part of the challenge is that such an approach will either still involve

string parsing,

That's not really a challenge and would help somewhat with the current
status quo where we have to guess where the type ends and the textual part
of the comment begins. But it gets ugly for any type that has to include
quotes (literal strings, array keys, etc). Technically one can use nowdocs,
but it's not much better: https://3v4l.org/4hpte

or will involve a lot of deeply nested attribute classes.

Yeah, that would look like Lisp's S-exprs, but much worse - which, in my
opinion, would harm adoption.

All in all, in my opinion attribute-based solutions are less ergonomic than
what we already have now in docblocks.

--
Best regards,
Bruce Weirdan mailto:
weirdan@gmail.com

The null option is always an option, yes. The thing to understand is that today, we already have erased generics, via PHPStan/Psalm. That's one reason I am, personally, against erased generics in the language proper. They don't really offer anything we don't have already.

As for making docblock generics "official", one, as I noted I hate the current syntax. :-) Two, that seems unwise as long as PHP still has an option to remove comments/docblocks at compile time. Even if it's not used much anymore, the option is still there, AFAIK.

It seems you answered your own point here. Erased generics do bring
better syntax.

And that's before we even run into the long-standing Internals aversion to even recognizing the existence of 3rd party tools for fear of "endorsing" anything. (With the inexplicable exception of Docuwiki.)

Are you referring to this page: https://wiki.php.net/wiki/dokuwiki? It
doesn’t appear to be an endorsement and could be removed easily.

Additionally, there are several third-party extensions documented on
php.net, such as Swoole, Ds, Yaf, etc., which are, in a way, endorsed
by their inclusion.