GNU bug report logs - #77725
31.0.50; Add support for types accepted by `cl-typep' to cl-generic?

Previous Next

Full log

View this message in rfc822 format

From: Stefan Monnier <monnier <at> iro.umontreal.ca>
To: David Ponce <da_vid <at> orange.fr>
Cc: 77725 <at> debbugs.gnu.org, Eli Zaretskii <eliz <at> gnu.org>
Subject: bug#77725: 31.0.50; Add support for types accepted by `cl-typep' to cl-generic?
Date: Fri, 25 Apr 2025 14:07:04 -0400

>>> (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`.  ]

>> 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`.

>> The need for multiple object would be for cases like:
>>      (cl-deftype car-foo ()
>>        "Car-Foo type.
>>      Check if passed object has a subtype of FOO as car."
>>        `(satisfies ,(lambda (o) (memq 'FOO (gtype-of (car-safe o))))))
>> but I guess this can inf-loop only if we follow a cycle in the object
>> (e.g. say if o == (car (car (car o)))).
>
> Not sure to understand what you mean by "need for multiple object", I am sorry.
>
> I tries this, and, for me it works as expected:
>
> (cl-deftype car-foo ()
>   "Car-Foo type.
> Check if passed object has a subtype of FOO as car."
>   `(satisfies ,(lambda (o) (memq 'FOO (gtype-of (car-safe o))))))
>
> (cl-deftype FOO ()
>   `(or (and symbol (satisfies ,(lambda (o) (eq o 'FOO))))
>        car-foo))
>
> (cl-types-of 'FOO)
> => FOO symbol atom t)
>
> (cl-types-of '(FOO))
> => (FOO car-foo cons list sequence t)
>
> (cl-types-of '(((((FOO))))))
> => (FOO car-foo cons list sequence t)

Don't test it with '(((((FOO))))) because that's not a case where
`o == (car (car (car o)))`  You need something like

    (let ((o (list nil nil)))
      (setq o (list (list (list o))))
      (cl-types-of o))

As I implied, this is probably not too serious.

> 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.

>>> ;; 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.

>>>> There's also some stylistic problems with the tests:
>>>> - We shouldn't test the return value of `cl-deftype`: I don't think it's
>>>>     documented anywhere and I don't think it's good practice to pay
>>>>     attention to the return value of declarations.
>>> You are certainly right.  I just wanted to check that `cl-deftype'
>>> didn't fail, but there is no `should-no-error'.  Would it be better to
>>> test for the presence of the type just defined in `cl--type-list'?
>> I'd just move the `cl-deftype` calls out of the tests and presume that if
>> they signal an error we'll see it.
>
> 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).


        Stefan

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.