Subject: bug#77725: 31.0.50; Add support for types accepted by `cl-typep' to cl-generic?

From: David Ponce <[email-masked]>
Date: Sat, 26 Apr 2025 11:47:52 +0200

On 2025-04-25 20:07, Stefan Monnier wrote:
>>>> (cl-deftype T1 ()
>>>>     "Root type.
>>>> Check if passed object is a subtype of T1. I.e., if T1 is present in
>>>> object type parents."
>>>>     `(satisfies ,(lambda (o) (memq 'T1 (gtype-of o)))))
>>> Hmm... I can see that it could be handy if you don't know how to
>>> characterize type T1 other than as the "sum" of its subtypes.
>>> But this seems rather circular.  Have you seen such things out in
>>> the wild?
>> I am using a such "abstract" type in one of my library for exactly
>> this: "characterize type T1 other than as the "sum" of its subtypes."
> 
> [ FWIW, this definition makes your type-test quite costly since it will
>    test more or less each and every type defined with `cl-deftype`.
>    You'd be better served with a more targeted test which keeps track of
>    the children of T1 so it can then do something like
> 
>        (cl-some (lambda (child) (cl-typep o child)) my-children)
> 
>    This way the performance is not affected by random other unrelated types.
> 
>    But, yes, that begs the question of how to keep track of the
>    children, e.g. how to be told when a child needs to be added/removed
>    to/from `my-children`.  ]

Exactly, I fully agree, the question is "how to keep track of the children"?

I wonder if it would be possible to do something when the type is
(re)defined? For example, pass the type once defined to some kind of
"after-defined-hook" that could adjust the environment accordingly.

>>> More importantly, with your circularity-breaking approach, if `gtype-of`
>>> (aka `cl-types-of`) happens to look at T1 first, that check will
>>> immediately return nil, so `cl-types-of` may decide "Oh, I just
>>> discovered this is not a T1, so I can skip checking all the subtypes of
>>> T1".  So, the cycle is broken, but the output is wrong.
>>
>> Look at T1 first should be possible only if T1 is alone, without any
> [...]
> 
> Agreed.
> 
>> Did I miss something?
> 
> What you missed (because I didn't make it clear) is that I was talking
> about an incorrect behavior of your circularity-breaking approach, when
> coupled with *another* algorithm than the one you currently use to
> collect the set of types to return in `cl-types-of`.

Ah, OK, I better understand your point.  Thanks!

> 
>> This makes me think that errors that might occur when calling
>> `cl-typep' should be handled in `cl-types-of' to prevent an
>> incorrect definition from impacting method dispatching on types
>> correctly defined.
>> WDYT?
> 
> Maybe.  I'd tend to think that `cl-typep` should never error, so if it
> ever does (which would indicate a bug in some `cl-deftype`), we wouldn't
> want to hide that error.

Unfortunately, currently `cl-typep' can error, but currently the
impact is limited to the broken definition.  Here is an example of
broken definition:

(cl-deftype bad-type ()
   '(satisfies unknown-function))

But, when any type defined by 'cl-deftype' can also be a method type
argument, any broken type can also break dispatching of method for
other types.  So, such errors need to be caught and reported by
`cl-types-of'.  For now, I updated `cl-types-of' accordingly.

> 
>>>> ;; T2 will never match, because `cl-types-of' enters in an endless recursion
>>>> (cl-typep (list 'T2) 'T1)
>>>> => nil
>>> This is both right and wrong: we could return t and that would be
>>> equally valid.
>>>
>>>> (cl-types-of (list 'T2))
>>>> => (cons list sequence t)
>>> And here (T2 T1 cons list sequence t) would also be equally valid.
>>
>> Sorry, you lost me here.  As I understand it, a type whose definition
>> enter in an endless recursion is not valid, and should never match?
> 
> It depends on whether you define your types inductively or co-inductively.
> IOW, do you define the type by starting with the "empty set" and then
> adding new elements to it until there's nothing more to add, or do you
> define it by starting with a "total set" that contains everything and
> then remove elements from it until you've removed everything that
> doesn't belong there.
> 
> Another way to look at it: there's nothing in your definition of T2 that
> says that the list `(T2)` should *not* be an element of that type.
> 
> For recursive values, in order to break circularity, it is common to
> check whether a value satisfies a constraint by adding "yes it does" as
> a temporary assumption while performing the check, so as to break the
> cycle when we get to a nested occurrence of that object.
> If we use the same approach here, the T2 test will say that `(T2)` is
> indeed of type T2.
> 

I am afraid, I still don't see how I can implement this "common
approach" to break circularity.

When I consider that a type "match" before to check, it will still match
after a cycle is detected, if I understood correctly your explanation.
So, a circular type will always match for any objet?  I certainly missed
something, sorry.

[...]
>>
>> The problem with this approach is that it is difficult to isolate and cleanup
>> the definitions needed for test-1 from those needed for test-2.  Also the result
>> will depends on the order of the cl-deftype for test-1 and test-2, because these
>> definitions will be effective outside of test-1 and test-2.
>>
>> But maybe it's not so important after all.  I'll try to reformulate the tests this way.
> 
> In the worst case, you can duplicate the definitions (with different names).

Please find attached a new simpler and cleaner version of cl-types-test.el.
All tests pass for me :-)

Also attached my last version of cl-types.el.  For now, I prefer to work on
separate files.  Based on your previous proposal, it should not be difficult to
merge the code in existing libraries when/if we are satisfied of the
implementation ;-)

David