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

Previous Next

To reply to this bug, email your comments to 77725 AT debbugs.gnu.org.

Toggle the display of automated, internal messages from the tracker.

Message #5 received at submit <at> debbugs.gnu.org (full text, mbox):

From: David Ponce <da_vid <at> orange.fr>
To: bug-gnu-emacs <at> gnu.org
Subject: 31.0.50; Add support for types accepted by `cl-typep' to cl-generic?
Date: Fri, 11 Apr 2025 09:14:41 +0200

[Message part 1 (text/plain, inline)]

Hello

In the cl-generic library, the implementation of the
`cl-generic-generalizers' "typeof" method, used to dispatch
"normal types", mentions in a FIXME on line 1367: "Add support for
other "types" accepted by `cl-typep' such as `character', `face',
`keyword', ...?".

As part of some other works, I created the attached "gtype" library,
which complements `cl-deftype' so that such defined types are also
recognized as argument types for dispatching generic function methods.
Here is a quick example of use:

(defgtype face nil ()
  "A face type."
  '(satisfies facep))

(gtype-of 'default)
=> face
(cl-type-of 'default)
=> symbol

(cl-defmethod my-add-face ((text string) (face face))
  (propertize text 'face face))
=> my-add-face

(my-add-face "text" 'bold)
=> #("text" 0 4 (face bold))

(my-add-face "text" 'bad-face)
=> No applicable method: add-face, "text", bad-face

I've been using this library successfully in some of my code, and was
wondering if it could help add this functionality to Emacs.  My goal
is not to include this library, but to use it as a starting point for
further reflection on this subject.

My library is relatively concise and adopts a design similar to that
used for built-in types. The new types (which I call "gtypes") are
instances of the structure `gtype-class', derived from `cl--class',
just as built-in types are instances of the structure `built-in-class'
also derived from `cl--class'.  gtypes thus benefits from the existing
infrastructure used for other types.  I also chose to have a separate
"generalizer" for gtypes.  I'm not sure if it would be desirable to
extend the existing generalizer "typof" to support such types.

I would therefore be interested in hearing more expert opinions on
my implementation and whether it could help add this functionality to
cl-generic, if it makes sense.

Thank you for your time.

[gtype.el (text/x-emacs-lisp, attachment)]

Message #8 received at 77725 <at> debbugs.gnu.org (full text, mbox):

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

> Date: Fri, 11 Apr 2025 09:14:41 +0200
> From:  David Ponce via "Bug reports for GNU Emacs,
>  the Swiss army knife of text editors" <bug-gnu-emacs <at> gnu.org>
> In the cl-generic library, the implementation of the
> `cl-generic-generalizers' "typeof" method, used to dispatch
> "normal types", mentions in a FIXME on line 1367: "Add support for
> other "types" accepted by `cl-typep' such as `character', `face',
> `keyword', ...?".
> 
> As part of some other works, I created the attached "gtype" library,
> which complements `cl-deftype' so that such defined types are also
> recognized as argument types for dispatching generic function methods.
> Here is a quick example of use:
> 
> (defgtype face nil ()
>    "A face type."
>    '(satisfies facep))
> 
> (gtype-of 'default)
> => face
> (cl-type-of 'default)
> => symbol
> 
> (cl-defmethod my-add-face ((text string) (face face))
>    (propertize text 'face face))
> => my-add-face
> 
> (my-add-face "text" 'bold)
> => #("text" 0 4 (face bold))
> 
> (my-add-face "text" 'bad-face)
> => No applicable method: add-face, "text", bad-face
> 
> I've been using this library successfully in some of my code, and was
> wondering if it could help add this functionality to Emacs.  My goal
> is not to include this library, but to use it as a starting point for
> further reflection on this subject.
> 
> My library is relatively concise and adopts a design similar to that
> used for built-in types. The new types (which I call "gtypes") are
> instances of the structure `gtype-class', derived from `cl--class',
> just as built-in types are instances of the structure `built-in-class'
> also derived from `cl--class'.  gtypes thus benefits from the existing
> infrastructure used for other types.  I also chose to have a separate
> "generalizer" for gtypes.  I'm not sure if it would be desirable to
> extend the existing generalizer "typof" to support such types.
> 
> I would therefore be interested in hearing more expert opinions on
> my implementation and whether it could help add this functionality to
> cl-generic, if it makes sense.

Thanks, adding Stefan to the discussion.

Message #11 received at 77725 <at> debbugs.gnu.org (full text, mbox):

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

Hi David,

>> As part of some other works, I created the attached "gtype" library,
>> which complements `cl-deftype' so that such defined types are also
>> recognized as argument types for dispatching generic function methods.
>> Here is a quick example of use:
>> 
>> (defgtype face nil ()
>>    "A face type."
>>    '(satisfies facep))
>> 
>> (gtype-of 'default)
>> => face
>> (cl-type-of 'default)
>> => symbol
>> 
>> (cl-defmethod my-add-face ((text string) (face face))
>>    (propertize text 'face face))
>> => my-add-face

Nice.

>> I've been using this library successfully in some of my code, and was
>> wondering if it could help add this functionality to Emacs.  My goal
>> is not to include this library, but to use it as a starting point for
>> further reflection on this subject.

The problem with adding new generalizers is to make sure they interact
correctly with others.  If you allow `satisfies` kind of definitions,
then it's easy to end up with situations where one of your new types is
neither a subtype (aka sub-specializer) nor a supertype
(super-specializer) of an existing type (specializer).

Let's take `function` defined as `(satisfies functionp)` is an example.

    (functionp '(lambda () 1))
    => t
    (type-of '(lambda a))
    => cons

this suggests (satisfies functionp) should be a subtype of `cons`, but
that is clearly wrong because

    (functionp (lambda () 1))
    => t
    (consp (lambda () 1))
    => nil

The type-dispatch code wants *one* value (generalizer) to lookup the
hash-table where it will find the corresponding effective method.
That one value should be "the most specific" generalizer among the
generalizers currently used for that generic function.

Now a `gtype-of` called `g-function` built from `(satisfies functionp)`
will be sometimes more specific and sometimes less specific than
`type-of`, so there is no correct PRIORITY to indicate to
`cl-generic-define-generalizer`: we'll end up with dispatch errors if
a generic function has a method for both `g-function` and for `cons`.


        Stefan

Message #14 received at 77725 <at> debbugs.gnu.org (full text, mbox):

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

On 2025-04-11 15:41, Stefan Monnier wrote:
> Hi David,
> 
>>> As part of some other works, I created the attached "gtype" library,
>>> which complements `cl-deftype' so that such defined types are also
>>> recognized as argument types for dispatching generic function methods.
>>> Here is a quick example of use:
>>>
>>> (defgtype face nil ()
>>>     "A face type."
>>>     '(satisfies facep))
>>>
>>> (gtype-of 'default)
>>> => face
>>> (cl-type-of 'default)
>>> => symbol
>>>
>>> (cl-defmethod my-add-face ((text string) (face face))
>>>     (propertize text 'face face))
>>> => my-add-face
> 
> Nice.
> 
>>> I've been using this library successfully in some of my code, and was
>>> wondering if it could help add this functionality to Emacs.  My goal
>>> is not to include this library, but to use it as a starting point for
>>> further reflection on this subject.
> 
> The problem with adding new generalizers is to make sure they interact
> correctly with others.  If you allow `satisfies` kind of definitions,
> then it's easy to end up with situations where one of your new types is
> neither a subtype (aka sub-specializer) nor a supertype
> (super-specializer) of an existing type (specializer).
> 
> Let's take `function` defined as `(satisfies functionp)` is an example.
> 
>      (functionp '(lambda () 1))
>      => t
>      (type-of '(lambda a))
>      => cons
> 
> this suggests (satisfies functionp) should be a subtype of `cons`, but
> that is clearly wrong because
> 
>      (functionp (lambda () 1))
>      => t
>      (consp (lambda () 1))
>      => nil
> 
> The type-dispatch code wants *one* value (generalizer) to lookup the
> hash-table where it will find the corresponding effective method.
> That one value should be "the most specific" generalizer among the
> generalizers currently used for that generic function.
> 
> Now a `gtype-of` called `g-function` built from `(satisfies functionp)`
> will be sometimes more specific and sometimes less specific than
> `type-of`, so there is no correct PRIORITY to indicate to
> `cl-generic-define-generalizer`: we'll end up with dispatch errors if
> a generic function has a method for both `g-function` and for `cons`.
> 
> 
>          Stefan
> 

Hi Stefan,

Thank you very much for your feedback!

Your remarks make sense, for sure.

Does this mean that for a `cl-deftype'-like generalizer to work
correctly, it must be part of the "typof" generalizer?

In other words, that a function like `gtype-of' should fall back to
`cl-type-of' when there is no corresponding gtype for an object?

Or am I missing something? --- Sorry, I only started studying
cl-generic relatively recently, and I probably don't understand
all its intricacies ;-)

Message #17 received at 77725 <at> debbugs.gnu.org (full text, mbox):

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: Re: bug#77725: 31.0.50; Add support for types accepted by
 `cl-typep' to cl-generic?
Date: Fri, 11 Apr 2025 12:26:05 -0400

> Does this mean that for a `cl-deftype'-like generalizer to work
> correctly, it must be part of the "typof" generalizer?

No, but it needs to be either always more precise or always less precise
than `type-of`.

IOW, either:

    (eql (gtypeof-generalizer A) (gtypeof-generalizer B))
    IMPLIES ((eql (gtypeof-generalizer A) nil)
             OR (eql (cl-type-of A) (cl-type-of B)))

or the reverse.  That's a current limitation in the cl-generic system.

One way to solve this is to use a generalizer that returns either nil or
a pair containing both the `gtype-of` and the `cl-type-of`, so it's
trivially always more precise than `cl-type-of`.  But beware: these
things are compared with `eql` so you need to "uniquify" them with
a sort of hashconsing scheme.

BTW if you do

    (defgtype cons-car-foo nil ()
      "A cons with a `foo' car."
      `(satisfies ,(lambda (x) (eq (car-safe x) 'foo))))

    (defgtype cons-cdr-foo nil ()
      "A cons with a `foo' cdr."
      `(satisfies ,(lambda (x) (eq (cdr-safe x) 'foo))))

what's the `(gtype-of '(foo . foo))` ?

> Or am I missing something? --- Sorry, I only started studying
> cl-generic relatively recently, and I probably don't understand
> all its intricacies ;-)

Yeah, it's unsatisfactorily intricate, indeed.  It's designed first and
foremost to keep the dispatch "simple and reasonable fast", at the cost
of making `cl-generic-define-generalizer` a very sharp tool.  🙂

I have recently been thinking about how to make it more reliable (which
would also make it more flexible/powerful, allowing the definition of
both `and` and `or` specializers).  I have some vague idea, but there's
no code at all yet, and it might come with some non-trivial tradeoffs
(e.g. preloading the byte-compiler).


        Stefan

Message #20 received at 77725 <at> debbugs.gnu.org (full text, mbox):

From: David Ponce <da_vid <at> orange.fr>
To: Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: 77725 <at> debbugs.gnu.org, Eli Zaretskii <eliz <at> gnu.org>
Subject: Re: bug#77725: 31.0.50; Add support for types accepted by `cl-typep'
 to cl-generic?
Date: Sun, 13 Apr 2025 16:45:06 +0200

[Message part 1 (text/plain, inline)]

Hi Stefan,

Sorry for this late answer. It took me a while to take it all in ;-)

On 2025-04-11 18:26, Stefan Monnier wrote:
>> Does this mean that for a `cl-deftype'-like generalizer to work
>> correctly, it must be part of the "typof" generalizer?
> 
> No, but it needs to be either always more precise or always less precise
> than `type-of`.
> 
> IOW, either:
> 
>      (eql (gtypeof-generalizer A) (gtypeof-generalizer B))
>      IMPLIES ((eql (gtypeof-generalizer A) nil)
>               OR (eql (cl-type-of A) (cl-type-of B)))
> 
> or the reverse.  That's a current limitation in the cl-generic system.
>
> One way to solve this is to use a generalizer that returns either nil or
> a pair containing both the `gtype-of` and the `cl-type-of`, so it's
> trivially always more precise than `cl-type-of`. But beware: these
> things are compared with `eql` so you need to "uniquify" them with
> a sort of hashconsing scheme.

I am not sure to understand this point.

AFAICS, gtypes always take precedence over other types.  So, provided
I correctly understand your point, the gtype generalizer is more precise
than `type-of`.

For instance, if you define an icon type like this:

(defgtype icon nil ()
  "Builtin icon type."
  '(and symbol (satisfies iconp)))

(gtype-of 'button)
=> icon
(cl-type-of 'button)
=> symbol

So you cannot have two methods with the same name, one to handle the
symbol type, and one to handle the icon type.  I agree, it is a
limitation.  Is this your point?

I wonder if in practice it is really inconvenient, and worth the
trouble of complicate more the implementation?  Isn't it clearer to
use different methods for icons and symbols? Aren't these types
fundamentally different, and isn't the fact that an icon is a symbol
just an implementation choice?

> 
> BTW if you do
> 
>      (defgtype cons-car-foo nil ()
>        "A cons with a `foo' car."
>        `(satisfies ,(lambda (x) (eq (car-safe x) 'foo))))
> 
>      (defgtype cons-cdr-foo nil ()
>        "A cons with a `foo' cdr."
>        `(satisfies ,(lambda (x) (eq (cdr-safe x) 'foo))))
> 
> what's the `(gtype-of '(foo . foo))` ?

Regarding this point, perhaps it would be possible to use an heuristic
like: "in case of conflict, the last defined type is chosen as the
most specific"?

I implemented this idea in gtype (attached) to compute the gtype
precedence list, by using a topologic sort with a tie-breaker to
decide which gtype will be the most specific between two candidates
that cannot be separated otherwise.  It should be easy to implement
different heuristics by providing different tie-breakers.

With your example, if you define `cons-cdr-foo' after `cons-car-foo':

(gtype-of '(foo . foo))
=> cons-cdr-foo

And, if you define `cons-car-foo' after `cons-cdr-foo':

(gtype-of '(foo . foo))
=> cons-car-foo

To avoid inconsistent method dispatching, the order of gtypes does not
change if you eval again the definition of an existing gtype.  But the
order will change if you first remove the gtype, then define it again.
 
>> Or am I missing something? --- Sorry, I only started studying
>> cl-generic relatively recently, and I probably don't understand
>> all its intricacies ;-)
> 
> Yeah, it's unsatisfactorily intricate, indeed.  It's designed first and
> foremost to keep the dispatch "simple and reasonable fast", at the cost
> of making `cl-generic-define-generalizer` a very sharp tool.  🙂
> 
> I have recently been thinking about how to make it more reliable (which
> would also make it more flexible/powerful, allowing the definition of
> both `and` and `or` specializers).  I have some vague idea, but there's
> no code at all yet, and it might come with some non-trivial tradeoffs
> (e.g. preloading the byte-compiler).

I can't wait to see this :-)

Thanks for your patience!

[gtype.el (text/x-emacs-lisp, attachment)]

Message #23 received at 77725 <at> debbugs.gnu.org (full text, mbox):

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: Re: bug#77725: 31.0.50; Add support for types accepted by
 `cl-typep' to cl-generic?
Date: Sun, 13 Apr 2025 11:53:40 -0400

> For instance, if you define an icon type like this:
>
> (defgtype icon nil ()
>   "Builtin icon type."
>   '(and symbol (satisfies iconp)))
>
> (gtype-of 'button)
> => icon
> (cl-type-of 'button)
> => symbol
>
> So you cannot have two methods with the same name, one to handle the
> symbol type, and one to handle the icon type.  I agree, it is a
> limitation.  Is this your point?

Kind of.  Note: you can.  It's just that with your current code I expect
it will misbehave (rather than signal an error).

BTW, for the above case, your code could recognize that `icon` is
a subtype of `symbol` and tell that to cl-generic.

> I wonder if in practice it is really inconvenient, and worth the
> trouble of complicate more the implementation?

I don't think I understand what compilations you're talking about, nor
what kind of inconvenience you're referring to.

> Isn't it clearer to use different methods for icons and symbols?
> Aren't these types fundamentally different, and isn't the fact that an
> icon is a symbol just an implementation choice?

The question is not whether it's desirable, but whether we can provide
an implementation that works without too many quirks.  🙂

>> BTW if you do
>>      (defgtype cons-car-foo nil ()
>>        "A cons with a `foo' car."
>>        `(satisfies ,(lambda (x) (eq (car-safe x) 'foo))))
>>      (defgtype cons-cdr-foo nil ()
>>        "A cons with a `foo' cdr."
>>        `(satisfies ,(lambda (x) (eq (cdr-safe x) 'foo))))
>> what's the `(gtype-of '(foo . foo))` ?
>
> Regarding this point, perhaps it would be possible to use an heuristic
> like: "in case of conflict, the last defined type is chosen as the
> most specific"?

I'm pretty sure some of your users will still be confused when their
methods are not used, just because some other part of their `cons` cells
happens to have a value recognized by an unrelated type.

And of course, they'd probably also be confused if the method that
handles `cons` is not used for those cons-cells.

>> Yeah, it's unsatisfactorily intricate, indeed.  It's designed first and
>> foremost to keep the dispatch "simple and reasonable fast", at the cost
>> of making `cl-generic-define-generalizer` a very sharp tool.  🙂
>> I have recently been thinking about how to make it more reliable (which
>> would also make it more flexible/powerful, allowing the definition of
>> both `and` and `or` specializers).  I have some vague idea, but there's
>> no code at all yet, and it might come with some non-trivial tradeoffs
>> (e.g. preloading the byte-compiler).
> I can't wait to see this :-)

I know I wrote "yet", but I have a very long list of "ideas I've had":
most of those will never become concrete.


        Stefan

Message #26 received at 77725 <at> debbugs.gnu.org (full text, mbox):

From: David Ponce <da_vid <at> orange.fr>
To: Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: 77725 <at> debbugs.gnu.org, Eli Zaretskii <eliz <at> gnu.org>
Subject: Re: bug#77725: 31.0.50; Add support for types accepted by `cl-typep'
 to cl-generic?
Date: Sun, 13 Apr 2025 18:28:44 +0200

On 2025-04-13 17:53, Stefan Monnier wrote:
>> For instance, if you define an icon type like this:
>>
>> (defgtype icon nil ()
>>    "Builtin icon type."
>>    '(and symbol (satisfies iconp)))
>>
>> (gtype-of 'button)
>> => icon
>> (cl-type-of 'button)
>> => symbol
>>
>> So you cannot have two methods with the same name, one to handle the
>> symbol type, and one to handle the icon type.  I agree, it is a
>> limitation.  Is this your point?
> 
> Kind of.  Note: you can.  It's just that with your current code I expect
> it will misbehave (rather than signal an error).
> 
> BTW, for the above case, your code could recognize that `icon` is
> a subtype of `symbol` and tell that to cl-generic.
> 
>> I wonder if in practice it is really inconvenient, and worth the
>> trouble of complicate more the implementation?
> 
> I don't think I understand what compilations you're talking about, nor
> what kind of inconvenience you're referring to.
> 
>> Isn't it clearer to use different methods for icons and symbols?
>> Aren't these types fundamentally different, and isn't the fact that an
>> icon is a symbol just an implementation choice?
> 
> The question is not whether it's desirable, but whether we can provide
> an implementation that works without too many quirks.  🙂
> 
>>> BTW if you do
>>>       (defgtype cons-car-foo nil ()
>>>         "A cons with a `foo' car."
>>>         `(satisfies ,(lambda (x) (eq (car-safe x) 'foo))))
>>>       (defgtype cons-cdr-foo nil ()
>>>         "A cons with a `foo' cdr."
>>>         `(satisfies ,(lambda (x) (eq (cdr-safe x) 'foo))))
>>> what's the `(gtype-of '(foo . foo))` ?
>>
>> Regarding this point, perhaps it would be possible to use an heuristic
>> like: "in case of conflict, the last defined type is chosen as the
>> most specific"?
> 
> I'm pretty sure some of your users will still be confused when their
> methods are not used, just because some other part of their `cons` cells
> happens to have a value recognized by an unrelated type.
> 
> And of course, they'd probably also be confused if the method that
> handles `cons` is not used for those cons-cells.
> 
>>> Yeah, it's unsatisfactorily intricate, indeed.  It's designed first and
>>> foremost to keep the dispatch "simple and reasonable fast", at the cost
>>> of making `cl-generic-define-generalizer` a very sharp tool.  🙂
>>> I have recently been thinking about how to make it more reliable (which
>>> would also make it more flexible/powerful, allowing the definition of
>>> both `and` and `or` specializers).  I have some vague idea, but there's
>>> no code at all yet, and it might come with some non-trivial tradeoffs
>>> (e.g. preloading the byte-compiler).
>> I can't wait to see this :-)
> 
> I know I wrote "yet", but I have a very long list of "ideas I've had":
> most of those will never become concrete.
> 
> 
>          Stefan
> 

Hi Stefan

Thank you again for your very valuable input.
I am afraid, this discussion just confirms that I don't understand well
enough how cl-generic works, and how it can be improved the correct way :-(

Have a nice Sunday.

David

Message #29 received at 77725 <at> debbugs.gnu.org (full text, mbox):

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: Re: bug#77725: 31.0.50; Add support for types accepted by
 `cl-typep' to cl-generic?
Date: Sun, 13 Apr 2025 13:10:38 -0400

> Thank you again for your very valuable input.
> I am afraid, this discussion just confirms that I don't understand well
> enough how cl-generic works, and how it can be improved the correct way :-(

In case it can help, here's some example:

    (cl-defmethod my-foo ((x symbol))
      (message "%S is a symbol" x))

If I call `(my-foo nil)` it will report that nil is a symbol, even
though `(cl-type-of nil)` returns `null` rather than `symbol`.

If I add a new method for `null`:

    (cl-defmethod my-foo ((x null))
      (message "%S is null" x)
      (cl-call-next-method))

Now a call to `(my-foo nil)` will report both that nil is null and that
it's a symbol (in that order).

For your `button` example, we'd similarly want that

    (cl-defmethod my-foo ((x icon))
      (message "%S is an icon" x)
      (cl-call-next-method))

`(my-foo 'button)` reports button as both an icon and a symbol (in that
order).  Now let's say we add:

    (defgtype face nil ()
      "Builtin face type."
      '(and symbol (satisfies facep)))

    (cl-defmethod my-foo ((x face))
      (message "%S is an face" x)
      (cl-call-next-method))

We'd want `(my-foo 'button)` now to report that button is an icon,
a face, and a symbol (and here I think it's OK if the ordering between
icon and face is arbitrary, tho they should both come before symbol).

One way you could do that is for your `(gtype-of 'button)` to return
some new `face&icon` type and to have your SPECIALIZERS-FUNCTION return
the list `(face icon symbol)` or `(icon face symbol)` for that type.

Does that help?


        Stefan

Message #32 received at 77725 <at> debbugs.gnu.org (full text, mbox):

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

[Message part 1 (text/plain, inline)]

On 2025-04-13 19:10, Stefan Monnier wrote:
> 
> In case it can help, here's some example:
> 
>      (cl-defmethod my-foo ((x symbol))
>        (message "%S is a symbol" x))
> 
> If I call `(my-foo nil)` it will report that nil is a symbol, even
> though `(cl-type-of nil)` returns `null` rather than `symbol`.
> 
> If I add a new method for `null`:
> 
>      (cl-defmethod my-foo ((x null))
>        (message "%S is null" x)
>        (cl-call-next-method))
> 
> Now a call to `(my-foo nil)` will report both that nil is null and that
> it's a symbol (in that order).
> 
> For your `button` example, we'd similarly want that
> 
>      (cl-defmethod my-foo ((x icon))
>        (message "%S is an icon" x)
>        (cl-call-next-method))
> 
> `(my-foo 'button)` reports button as both an icon and a symbol (in that
> order).  Now let's say we add:
> 
>      (defgtype face nil ()
>        "Builtin face type."
>        '(and symbol (satisfies facep)))
> 
>      (cl-defmethod my-foo ((x face))
>        (message "%S is an face" x)
>        (cl-call-next-method))
> 
> We'd want `(my-foo 'button)` now to report that button is an icon,
> a face, and a symbol (and here I think it's OK if the ordering between
> icon and face is arbitrary, tho they should both come before symbol).
> 
> One way you could do that is for your `(gtype-of 'button)` to return
> some new `face&icon` type and to have your SPECIALIZERS-FUNCTION return
> the list `(face icon symbol)` or `(icon face symbol)` for that type.
> 
> Does that help?

Thank you very much Stefan, it helped much!
J'aperçois enfin la lumière au bout du tunnel :-)

I understand more how cl-generic works, and I reworked gtype.el
(attached) according to your inputs and my better understanding.

Now your examples above give the expected results :-)

And:

(gtype-of '(foo . foo))
=> (cons-car-foo cons-cdr-foo cons)

(gtype--specializers (gtype-of '(foo . foo)))
=> (cons-car-foo cons-cdr-foo cons list sequence t)

[gtype.el (text/x-emacs-lisp, attachment)]

Message #35 received at 77725 <at> debbugs.gnu.org (full text, mbox):

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: Re: bug#77725: 31.0.50; Add support for types accepted by
 `cl-typep' to cl-generic?
Date: Mon, 14 Apr 2025 14:27:00 -0400

> I understand more how cl-generic works, and I reworked gtype.el
> (attached) according to your inputs and my better understanding.

Looks good, thanks.

Some comments below.

> (eval-when-compile (require 'cl-macs))  ;For cl--find-class.

You can also use `cl-find-class` which doesn't require this gymnastics.

> (define-inline gtype-p (object)
>   "Return non-nil if the type of OBJECT is a gtype."
>   (inline-letevals (object)
>     (inline-quote
>      (and (symbolp ,object)
>           (eq (type-of (cl--find-class ,object)) 'gtype-class)))))

I hope this function is not speed-critical (and so can be a plain `defun`).

> (define-inline gtype-parents (name)
>   "Get parents of type with NAME.
> NAME is a symbol representing a type.
> Return a possibly empty list of types."
>   (inline-quote
>    (cl--class-allparents (cl--find-class ,name))))

Same here.

> (defun gtype--topologic-sort (graph &optional tie-breaker)

How is this different from `merge-ordered-lists`?

> ;;;###autoload
> (defmacro defgtype (name &optional parents &rest args)
>   "Define NAME as a gtype that inherits from PARENTS.

Inheritance != subtyping.  Better stick to the term "subtype" here since
there doesn't seem to be any inheritance going on here.

> If a gtype with NAME already exists, replace it.
>
> NAME is an unquoted symbol representing a gtype.
>
> Optional argument PARENTS is either an unquoted symbol or list of
> symbols other than NAME representing types parents of NAME.
> PARENTS nil or omitted means that NAME is a root type.
>
> Also pass NAME and ARGS to `cl-deftype' to define NAME as a new data
> type."

I get the impression that the role/impact of PARENTS is not explained
clearly enough.  The explanation should be clear enough that the reader
can infer more or less what could happen if a parent is missing or if
a non-parent is incorrectly listed as a parent.

>   (declare (debug cl-defmacro) (doc-string 4) (indent 3))
>   (cl-with-gensyms (err)
>     `(condition-case ,err
>          (progn
>            (cl-deftype ,name ,@args)
>            (gtype--register ',name ',parents ',args))
>        (error
>         (gtype--unregister ',name)
>         (error (error-message-string ,err))))))

Could we merge this into `cl-deftype`?

> (defmacro remgtype (name)

Try and stay within the namespace prefix.

> (defun gtype-of (object)
>   "Return the most specific possible gtype OBJECT belongs to.
> Return an unique list of types OBJECT belongs to, ordered from the
> most specific type to the most general."
>   ;; Ignore recursive call on the same OBJECT, which can legitimately
>   ;; occur when, for example, a parent type is investigating whether
>   ;; an object's type is that of one of its children.
>   (unless (eq object gtype--object)
>     (let ((gtype--object object)
>           (found (list (cl-type-of object))))
>       ;; Collect all gtypes OBJECT belongs to.
>       (dolist (gtype gtype--list)
>         (if (cl-typep object gtype)
>             (push gtype found)))
>       ;; Return an unique value of type.
>       (with-memoization (gethash found gtype--unique)
>         found))))

Since `gtype-of` is the function used to get the "tagcode" used for
method-dispatch, it is speed-critical.
But the above looks rather costly.  🙁

I think we could reduce this problem significantly with reasonably
simple changes to `cl-generic`: we could provide to the TAGCODE-FUNCTION
the list of specializers used by methods of the current
generic-function, so we'd only need to check those types which are
actually useful for the current dispatch.
[ Hmm... well, maybe not completely "simple" since it might have
  some problematic impact on the `cl--generic-prefill-dispatchers`
  mechanism, but that should be solvable.  ]

> (defun gtype--specializers (tag &rest _)
>   "If TAG is a gtype, return its specializers."
>   (and (consp tag) (gtype-p (car tag))
>        (with-memoization (gethash tag gtype--specializers)
>          (merge-ordered-lists (mapcar #'gtype-parents tag)))))

AFAIK this function is only ever called with "tagcodes" returned by your
own TAGCODE-FUNCTION, so I think the `gtype-p` test is redundant.


        Stefan

Message #38 received at 77725 <at> debbugs.gnu.org (full text, mbox):

From: David Ponce <da_vid <at> orange.fr>
To: Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: 77725 <at> debbugs.gnu.org, Eli Zaretskii <eliz <at> gnu.org>
Subject: Re: bug#77725: 31.0.50; Add support for types accepted by `cl-typep'
 to cl-generic?
Date: Tue, 15 Apr 2025 11:30:58 +0200

[Message part 1 (text/plain, inline)]

On 2025-04-14 20:27, Stefan Monnier wrote:
>> I understand more how cl-generic works, and I reworked gtype.el
>> (attached) according to your inputs and my better understanding.
> 
> Looks good, thanks.

Thank you for your review!  My answers below.

>> (eval-when-compile (require 'cl-macs))  ;For cl--find-class.
> 
> You can also use `cl-find-class` which doesn't require this gymnastics.

Done.  I didn't know about this public version of `cl--find-class'.
However, as it seems not possible to write:

`(setf (cl-find-class object) value)'

I had to use `put' instead in one place in `gtype--register'.

>> (define-inline gtype-p (object)
>>    "Return non-nil if the type of OBJECT is a gtype."
>>    (inline-letevals (object)
>>      (inline-quote
>>       (and (symbolp ,object)
>>            (eq (type-of (cl--find-class ,object)) 'gtype-class)))))
> 
> I hope this function is not speed-critical (and so can be a plain `defun`).
> 
>> (define-inline gtype-parents (name)
>>    "Get parents of type with NAME.
>> NAME is a symbol representing a type.
>> Return a possibly empty list of types."
>>    (inline-quote
>>     (cl--class-allparents (cl--find-class ,name))))
> 
> Same here.

Done.  I didn't notice any significant impact on performance :-)

>> (defun gtype--topologic-sort (graph &optional tie-breaker)
> 
> How is this different from `merge-ordered-lists`?

The result of the two functions are slightly different but seems
consistent, so I switched to `merge-ordered-lists'.

>> ;;;###autoload
>> (defmacro defgtype (name &optional parents &rest args)
>>    "Define NAME as a gtype that inherits from PARENTS.
> 
> Inheritance != subtyping.  Better stick to the term "subtype" here since
> there doesn't seem to be any inheritance going on here.

Done.

> I get the impression that the role/impact of PARENTS is not explained
> clearly enough.  The explanation should be clear enough that the reader
> can infer more or less what could happen if a parent is missing or if
> a non-parent is incorrectly listed as a parent.

This is a very good point.  Currently, the role of PARENTS is limited
to specify in which order gtype `gtype-of' will check gtypes.

This order is not automatically transposed to the type specifier of
`cl-deftype'.  And there is a risk of inconsistency here.

For instance, you can do something like this:

(defgtype a-fixnum nil ()
  'fixnum)

(gtype-of 10)
(a-fixnum fixnum)

(defgtype a-fixnum-between-1-10 a-fixnum ()
  `(satisfies ,(lambda (x) (and (numberp x) (> x 0) (< x 11)))))

(gtype-of 10.1)
(a-fixnum-between-1-10 float)
gtype--list
(a-fixnum-between-1-10 a-fixnum)

Clearly 10.1 is not "a-fixnum-between-1-10", because the type
specifier is incorrect; even if `a-fixnum-between-1-10' is a subtype
of `a-fixnum'.

The correct subtype could be:

(defgtype a-fixnum-between-1-10 a-fixnum ()
  `(and a-fixnum (satisfies ,(lambda (x) (> x 0) (< x 11)))))

But the type specifier is not produced automatically.

Not so easy to put all this in a docstring.  Any idea?

>>    (declare (debug cl-defmacro) (doc-string 4) (indent 3))
>>    (cl-with-gensyms (err)
>>      `(condition-case ,err
>>           (progn
>>             (cl-deftype ,name ,@args)
>>             (gtype--register ',name ',parents ',args))
>>         (error
>>          (gtype--unregister ',name)
>>          (error (error-message-string ,err))))))
> 
> Could we merge this into `cl-deftype`?

That would be great.  But I need some help here to correctly dispatch
all functions in gtype to Emacs libraries: cl-macs, cl-generic ?  May
be in this case, gtype should be moved to the cl namespace too.

Or do you envision something different?

>> (defmacro remgtype (name)
> 
> Try and stay within the namespace prefix.

Renamed to `gtype-remove'.

>> (defun gtype-of (object)
>>    "Return the most specific possible gtype OBJECT belongs to.
>> Return an unique list of types OBJECT belongs to, ordered from the
>> most specific type to the most general."
>>    ;; Ignore recursive call on the same OBJECT, which can legitimately
>>    ;; occur when, for example, a parent type is investigating whether
>>    ;; an object's type is that of one of its children.
>>    (unless (eq object gtype--object)
>>      (let ((gtype--object object)
>>            (found (list (cl-type-of object))))
>>        ;; Collect all gtypes OBJECT belongs to.
>>        (dolist (gtype gtype--list)
>>          (if (cl-typep object gtype)
>>              (push gtype found)))
>>        ;; Return an unique value of type.
>>        (with-memoization (gethash found gtype--unique)
>>          found))))
> 
> Since `gtype-of` is the function used to get the "tagcode" used for
> method-dispatch, it is speed-critical.

I agree.

> But the above looks rather costly.  🙁

emacs -Q on my laptop:

  Processors: 8 × Intel® Core™ i7-7700HQ CPU @ 2.80GHz
  Memory: 15,5 GiB of RAM

consistently takes around 1 millisecond to check 2000 gtypes, which
seems not so bad.

Here is the benchmark I use:

(defgtype cons-car-foo nil ()
  "A cons with a `foo' car."
  `(satisfies ,(lambda (x) (eq (car-safe x) 'foo))))

(defgtype cons-cdr-foo nil ()
  "A cons with a `foo' cdr."
  `(satisfies ,(lambda (x) (eq (cdr-safe x) 'foo))))

(gtype-of '(foo . foo))
=> (cons-car-foo cons-cdr-foo cons)

;; Create a very long list of gtypes that gtype-of will check
;; sequentially.
(let* ((count 2000)
       (gtype--list (let ((list '(cons-cdr-foo)))
                     (dotimes (_ count)
                       (push 'cons-car-foo list))
                     list))
       (object '(foo . foo))
       (runs 1))
  (garbage-collect)
  (benchmark-run
   (gtype-of object)
   runs))

=>(0.00107773 0 0.0)

> I think we could reduce this problem significantly with reasonably
> simple changes to `cl-generic`: we could provide to the TAGCODE-FUNCTION
> the list of specializers used by methods of the current
> generic-function, so we'd only need to check those types which are
> actually useful for the current dispatch.
> [ Hmm... well, maybe not completely "simple" since it might have
>    some problematic impact on the `cl--generic-prefill-dispatchers`
>    mechanism, but that should be solvable.  ]

I am afraid, this looks beyond my knowledge of cl-generic.

>> (defun gtype--specializers (tag &rest _)
>>    "If TAG is a gtype, return its specializers."
>>    (and (consp tag) (gtype-p (car tag))
>>         (with-memoization (gethash tag gtype--specializers)
>>           (merge-ordered-lists (mapcar #'gtype-parents tag)))))
> 
> AFAIK this function is only ever called with "tagcodes" returned by your
> own TAGCODE-FUNCTION, so I think the `gtype-p` test is redundant.

Good find. Done.

Please find attached the last version.

David

[gtype.el (text/x-emacs-lisp, attachment)]

Message #41 received at 77725 <at> debbugs.gnu.org (full text, mbox):

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: Re: bug#77725: 31.0.50; Add support for types accepted by
 `cl-typep' to cl-generic?
Date: Tue, 15 Apr 2025 11:13:16 -0400

>>> (eval-when-compile (require 'cl-macs))  ;For cl--find-class.
>> You can also use `cl-find-class` which doesn't require this gymnastics.
>
> Done.  I didn't know about this public version of `cl--find-class'.
> However, as it seems not possible to write:
>
> `(setf (cl-find-class object) value)'

Ah, right, we still don't have a pubic version of defining a class,
indeed, sorry.  I guess `cl--find-class` it is, huh.

>> I get the impression that the role/impact of PARENTS is not explained
>> clearly enough.  The explanation should be clear enough that the reader
>> can infer more or less what could happen if a parent is missing or if
>> a non-parent is incorrectly listed as a parent.
> This is a very good point.  Currently, the role of PARENTS is limited
> to specify in which order gtype `gtype-of' will check gtypes.

Why does this order matter?  I thought the PARENTS was used just in
`gtype--specializers` to sort the various types.

> For instance, you can do something like this:
>
> (defgtype a-fixnum nil ()
>   'fixnum)
>
> (gtype-of 10)
> (a-fixnum fixnum)
>
> (defgtype a-fixnum-between-1-10 a-fixnum ()
>   `(satisfies ,(lambda (x) (and (numberp x) (> x 0) (< x 11)))))
>
> (gtype-of 10.1)
> (a-fixnum-between-1-10 float)
> gtype--list
> (a-fixnum-between-1-10 a-fixnum)
>
> Clearly 10.1 is not "a-fixnum-between-1-10", because the type
> specifier is incorrect; even if `a-fixnum-between-1-10' is a subtype
> of `a-fixnum'.
>
> The correct subtype could be:
>
> (defgtype a-fixnum-between-1-10 a-fixnum ()
>   `(and a-fixnum (satisfies ,(lambda (x) (> x 0) (< x 11)))))
>
> But the type specifier is not produced automatically.

AFAICT the error will manifest itself in the fact that
`gtype--specializers` will return

    (a-fixnum-between-1-10 a-fixnum float fixnum integer ...)

so a method defined `a-fixnum` may end up incorrectly invoked in this case.

In contrast if `a-fixnum` is missing:

    (defgtype a-fixnum-between-1-10 nil ()
      `(and a-fixnum (satisfies ,(lambda (x) (> x 0) (< x 11)))))

then `gtype--specializers` may end up returning

    (a-fixnum a-fixnum-between-1-10 float fixnum integer ...)

so a method defined for `a-fixnum` may take precedence over one defined
for `a-fixnum-between-1-10`.

> Not so easy to put all this in a docstring.  Any idea?

AFAICT, missing PARENTS may cause incorrect ordering of methods,
while extraneous PARENTS may cause use of extraneous methods.

>>>    (declare (debug cl-defmacro) (doc-string 4) (indent 3))
>>>    (cl-with-gensyms (err)
>>>      `(condition-case ,err
>>>           (progn
>>>             (cl-deftype ,name ,@args)
>>>             (gtype--register ',name ',parents ',args))
>>>         (error
>>>          (gtype--unregister ',name)
>>>          (error (error-message-string ,err))))))
>> Could we merge this into `cl-deftype`?
>
> That would be great.  But I need some help here to correctly dispatch
> all functions in gtype to Emacs libraries: cl-macs, cl-generic ?

Not `cl-generic`, but yes `cl-macs.el` with maybe some parts in
`cl-preloaded.el` and/or `cl-lib.el` and/or `cl-extra.el`.

> May be in this case, gtype should be moved to the cl namespace too.

Yup.  I guess they'd become "cl-types" instead of "gtypes".

> Or do you envision something different?

I was thinking that the main(only?) difference between `cl-deftype` and
`gdeftype` is:

- the PARENTS argument, where the question is how to add a PARENTS
  argument.  Maybe we could use a (declare (parents ...))?
- The ARGS: Clearly your `gtype-of` can invent which args to pass
  for a given value to match the resulting type, so `gtype-of` (and
  everything which relies on it, i.e. method dispatch) wouldn't be
  usable for types with a non-empty arglist.

>> But the above looks rather costly.  🙁
>
> emacs -Q on my laptop:
>
>   Processors: 8 × Intel® Core™ i7-7700HQ CPU @ 2.80GHz
>   Memory: 15,5 GiB of RAM
>
> consistently takes around 1 millisecond to check 2000 gtypes, which
> seems not so bad.

AFAICT its CPU cost is proportional to the number of types defined with
`defgtype`, so the more popular it gets, the slower it becomes.
And of course, the cost of each type check is unbounded, so a single
"expensive" type can slow everything down further.

The usual dispatch is

    (lambda (arg &rest args)
      (let ((f (gethash (cl-typeof arg) precomputed-methods-table)))
        (if f
            (apply f arg args)
          ;; Slow case when encountering a new type
          ...)))

where often the most expensive part is `&rest` (which has to allocate
a list for those remaining arguments),

So we're talking about replacing

    &rest + cl-type-of + gethash + if + apply

with a function that loops over N types, calling `cl-typep` on each one
of them (`cl-typep` itself being a recursive function that basically
interprets the type language).  This is going to slow down dispatch
*very* significantly for those generic functions that have a method that
dispatches on a gtype, compared to those that don't.

It's not the end of the world, especially because there's a lot of
opportunities for optimizations in there, but it's something to keep
in mind.


        Stefan

Message #44 received at 77725 <at> debbugs.gnu.org (full text, mbox):

From: David Ponce <da_vid <at> orange.fr>
To: Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: 77725 <at> debbugs.gnu.org, Eli Zaretskii <eliz <at> gnu.org>
Subject: Re: bug#77725: 31.0.50; Add support for types accepted by `cl-typep'
 to cl-generic?
Date: Tue, 15 Apr 2025 18:40:45 +0200

On 2025-04-15 17:13, Stefan Monnier wrote:

>>> I get the impression that the role/impact of PARENTS is not explained
>>> clearly enough.  The explanation should be clear enough that the reader
>>> can infer more or less what could happen if a parent is missing or if
>>> a non-parent is incorrectly listed as a parent.
>> This is a very good point.  Currently, the role of PARENTS is limited
>> to specify in which order gtype `gtype-of' will check gtypes.
> 
> Why does this order matter?  I thought the PARENTS was used just in
> `gtype--specializers` to sort the various types.

Sorry for the confusion, you are right, of course.

>> For instance, you can do something like this:
>>
>> (defgtype a-fixnum nil ()
>>    'fixnum)
>>
>> (gtype-of 10)
>> (a-fixnum fixnum)
>>
>> (defgtype a-fixnum-between-1-10 a-fixnum ()
>>    `(satisfies ,(lambda (x) (and (numberp x) (> x 0) (< x 11)))))
>>
>> (gtype-of 10.1)
>> (a-fixnum-between-1-10 float)
>> gtype--list
>> (a-fixnum-between-1-10 a-fixnum)
>>
>> Clearly 10.1 is not "a-fixnum-between-1-10", because the type
>> specifier is incorrect; even if `a-fixnum-between-1-10' is a subtype
>> of `a-fixnum'.
>>
>> The correct subtype could be:
>>
>> (defgtype a-fixnum-between-1-10 a-fixnum ()
>>    `(and a-fixnum (satisfies ,(lambda (x) (> x 0) (< x 11)))))
>>
>> But the type specifier is not produced automatically.
> 
> AFAICT the error will manifest itself in the fact that
> `gtype--specializers` will return
> 
>      (a-fixnum-between-1-10 a-fixnum float fixnum integer ...)
> 
> so a method defined `a-fixnum` may end up incorrectly invoked in this case.
> 
> In contrast if `a-fixnum` is missing:
> 
>      (defgtype a-fixnum-between-1-10 nil ()
>        `(and a-fixnum (satisfies ,(lambda (x) (> x 0) (< x 11)))))
> 
> then `gtype--specializers` may end up returning
> 
>      (a-fixnum a-fixnum-between-1-10 float fixnum integer ...)
> 
> so a method defined for `a-fixnum` may take precedence over one defined
> for `a-fixnum-between-1-10`.
> 
>> Not so easy to put all this in a docstring.  Any idea?
> 
> AFAICT, missing PARENTS may cause incorrect ordering of methods,
> while extraneous PARENTS may cause use of extraneous methods.

I will add this to the docstring.

> 
>>>>     (declare (debug cl-defmacro) (doc-string 4) (indent 3))
>>>>     (cl-with-gensyms (err)
>>>>       `(condition-case ,err
>>>>            (progn
>>>>              (cl-deftype ,name ,@args)
>>>>              (gtype--register ',name ',parents ',args))
>>>>          (error
>>>>           (gtype--unregister ',name)
>>>>           (error (error-message-string ,err))))))
>>> Could we merge this into `cl-deftype`?
>>
>> That would be great.  But I need some help here to correctly dispatch
>> all functions in gtype to Emacs libraries: cl-macs, cl-generic ?
> 
> Not `cl-generic`, but yes `cl-macs.el` with maybe some parts in
> `cl-preloaded.el` and/or `cl-lib.el` and/or `cl-extra.el`.

Shouldn't the code related to method dispatching, at the end of gtype.el,
go to cl-generic?

>> May be in this case, gtype should be moved to the cl namespace too.
> 
> Yup.  I guess they'd become "cl-types" instead of "gtypes".
> 
>> Or do you envision something different?
> 
> I was thinking that the main(only?) difference between `cl-deftype` and
> `gdeftype` is:
> 
> - the PARENTS argument, where the question is how to add a PARENTS
>    argument.  Maybe we could use a (declare (parents ...))?

Another possibility could be to have 2 separate definitions:

- cl-deftype to define a data type, as currently.

- cl-types-generalize (or something better) to declare a type previously
  defined by cl-deftype usable to dispatch methods, with specified parents?

  (cl-deftype my-type ()
    "A user defined type."
    ...)
  
  (cl-types-generalize my-type) ;; No parents

  (cl-deftype my-type1 ()
    "Another user defined type."
    ...)
  
  (cl-types-generalize my-type1 my-type) ;; With parents

  It should be possible also to "un-generalize" a type.

> - The ARGS: Clearly your `gtype-of` can invent which args to pass
>    for a given value to match the resulting type, so `gtype-of` (and
>    everything which relies on it, i.e. method dispatch) wouldn't be
>    usable for types with a non-empty arglist.

I am not sure I understand this point regarding ARGS.
Is this related to the `cl-deftype' arguments which cannot be used to
declare argument type of methods:

(defgtype unsigned-byte nil (&optional bits)
  (list 'integer 0 (if (eq bits '*) bits (1- (ash 1 bits)))))

(cl-defmethod my-foo ((n (unsigned-byte 8))) ;; fails
  (format "unsigned, %s" n))

But, below is possible instead:

(defgtype u8 unsigned-byte ()
  '(unsigned-byte 8))

(cl-defmethod my-foo ((n u8))
  (format "unsigned 8bits, %s - also %s"
          n (cl-call-next-method)))

(my-foo 100)
=> "unsigned 8bits, 100 - also unsigned, 100"
(my-foo 256)
=> "unsigned, 256"

> 
>>> But the above looks rather costly.  🙁
>>
>> emacs -Q on my laptop:
>>
>>    Processors: 8 × Intel® Core™ i7-7700HQ CPU @ 2.80GHz
>>    Memory: 15,5 GiB of RAM
>>
>> consistently takes around 1 millisecond to check 2000 gtypes, which
>> seems not so bad.
> 
> AFAICT its CPU cost is proportional to the number of types defined with
> `defgtype`, so the more popular it gets, the slower it becomes.
> And of course, the cost of each type check is unbounded, so a single
> "expensive" type can slow everything down further.
> 
> The usual dispatch is
> 
>      (lambda (arg &rest args)
>        (let ((f (gethash (cl-typeof arg) precomputed-methods-table)))
>          (if f
>              (apply f arg args)
>            ;; Slow case when encountering a new type
>            ...)))
> 
> where often the most expensive part is `&rest` (which has to allocate
> a list for those remaining arguments),
> 
> So we're talking about replacing
> 
>      &rest + cl-type-of + gethash + if + apply
> 
> with a function that loops over N types, calling `cl-typep` on each one
> of them (`cl-typep` itself being a recursive function that basically
> interprets the type language).  This is going to slow down dispatch
> *very* significantly for those generic functions that have a method that
> dispatches on a gtype, compared to those that don't.
> 
> It's not the end of the world, especially because there's a lot of
> opportunities for optimizations in there, but it's something to keep
> in mind.

Sure.

Thanks you again.
David

Message #47 received at 77725 <at> debbugs.gnu.org (full text, mbox):

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: Re: bug#77725: 31.0.50; Add support for types accepted by
 `cl-typep' to cl-generic?
Date: Tue, 15 Apr 2025 15:17:13 -0400

>>> That would be great.  But I need some help here to correctly dispatch
>>> all functions in gtype to Emacs libraries: cl-macs, cl-generic ?
>> Not `cl-generic`, but yes `cl-macs.el` with maybe some parts in
>> `cl-preloaded.el` and/or `cl-lib.el` and/or `cl-extra.el`.
> Shouldn't the code related to method dispatching, at the end of gtype.el,
> go to cl-generic?

Technically it can go to various places, but ideally `cl-generic` just
provides the machinery whereas the actual generalizers would be
defined next to where we define the corresponding types.  In practice,
we have most of the `cl-generic-define-generalizer` in there,
admittedly, but that's because of overriding bootstrapping issues.

Since we're talking about generalizers defined for `cl-deftype` which is
not a core primitive but one defined in `cl-lib`, it makes sense to
define it elsewhere (i.e. in the `cl-lib` files), like we do for
EIEIO types.

>> I was thinking that the main(only?) difference between `cl-deftype` and
>> `gdeftype` is:
>> - the PARENTS argument, where the question is how to add a PARENTS
>>    argument.  Maybe we could use a (declare (parents ...))?
>
> Another possibility could be to have 2 separate definitions:
>
> - cl-deftype to define a data type, as currently.
>
> - cl-types-generalize (or something better) to declare a type previously
>   defined by cl-deftype usable to dispatch methods, with specified parents?
>
>   (cl-deftype my-type ()
>     "A user defined type."
>     ...)
>      (cl-types-generalize my-type) ;; No parents
>
>   (cl-deftype my-type1 ()
>     "Another user defined type."
>     ...)
>      (cl-types-generalize my-type1 my-type) ;; With parents

We could, but having them separate begs the question of how to match one
with the other: e.g. if we re-evaluate (cl-deftype my-type ...) should the
corresponding previous (cl-types-generalize ...) be "undone"?

It's somewhat philosophical, admittedly, but bringing them together
makes it much more clear what is the "right" behavior (regardless if we
end up implementing the right behavior: at least when we get
a bug-report, we know which change is an improvement).

>> - The ARGS: Clearly your `gtype-of` can invent which args to pass
>>    for a given value to match the resulting type, so `gtype-of` (and
>>    everything which relies on it, i.e. method dispatch) wouldn't be
>>    usable for types with a non-empty arglist.
>
> I am not sure I understand this point regarding ARGS.
> Is this related to the `cl-deftype' arguments which cannot be used to
> declare argument type of methods:

Exactly.  `cl-deftype` lets you define types such as `(list-of
integer)`, but your code is not able to figure out that a value is of
type `(list-of integer)` so you can't handle those kinds of types.
And that's OK: it's still better than what we currently have.

> But, below is possible instead:
>
> (defgtype u8 unsigned-byte ()
>   '(unsigned-byte 8))
>
> (cl-defmethod my-foo ((n u8))
>   (format "unsigned 8bits, %s - also %s"
>           n (cl-call-next-method)))

That's right.

We could try to later add support for

    (cl-defmethod my-foo ((n (unsigned-byte 8)))
      (format "unsigned, %s" n))

but ... one step at a time.


        Stefan

Message #50 received at 77725 <at> debbugs.gnu.org (full text, mbox):

From: David Ponce <da_vid <at> orange.fr>
To: Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: 77725 <at> debbugs.gnu.org, Eli Zaretskii <eliz <at> gnu.org>
Subject: Re: bug#77725: 31.0.50; Add support for types accepted by `cl-typep'
 to cl-generic?
Date: Wed, 16 Apr 2025 17:17:36 +0200

[Message part 1 (text/plain, inline)]

On 2025-04-15 21:17, Stefan Monnier wrote:
>>>> That would be great.  But I need some help here to correctly dispatch
>>>> all functions in gtype to Emacs libraries: cl-macs, cl-generic ?
>>> Not `cl-generic`, but yes `cl-macs.el` with maybe some parts in
>>> `cl-preloaded.el` and/or `cl-lib.el` and/or `cl-extra.el`.
>> Shouldn't the code related to method dispatching, at the end of gtype.el,
>> go to cl-generic?
> 
> Technically it can go to various places, but ideally `cl-generic` just
> provides the machinery whereas the actual generalizers would be
> defined next to where we define the corresponding types.  In practice,
> we have most of the `cl-generic-define-generalizer` in there,
> admittedly, but that's because of overriding bootstrapping issues.
> 
> Since we're talking about generalizers defined for `cl-deftype` which is
> not a core primitive but one defined in `cl-lib`, it makes sense to
> define it elsewhere (i.e. in the `cl-lib` files), like we do for
> EIEIO types.

OK.

> 
>>> I was thinking that the main(only?) difference between `cl-deftype` and
>>> `gdeftype` is:
>>> - the PARENTS argument, where the question is how to add a PARENTS
>>>     argument.  Maybe we could use a (declare (parents ...))?
>>
>> Another possibility could be to have 2 separate definitions:
>>
>> - cl-deftype to define a data type, as currently.
>>
>> - cl-types-generalize (or something better) to declare a type previously
>>    defined by cl-deftype usable to dispatch methods, with specified parents?
>>
>>    (cl-deftype my-type ()
>>      "A user defined type."
>>      ...)
>>       (cl-types-generalize my-type) ;; No parents
>>
>>    (cl-deftype my-type1 ()
>>      "Another user defined type."
>>      ...)
>>       (cl-types-generalize my-type1 my-type) ;; With parents
> 
> We could, but having them separate begs the question of how to match one
> with the other: e.g. if we re-evaluate (cl-deftype my-type ...) should the
> corresponding previous (cl-types-generalize ...) be "undone"?
> 
> It's somewhat philosophical, admittedly, but bringing them together
> makes it much more clear what is the "right" behavior (regardless if we
> end up implementing the right behavior: at least when we get
> a bug-report, we know which change is an improvement).

I agree.

> 
>>> - The ARGS: Clearly your `gtype-of` can invent which args to pass
>>>     for a given value to match the resulting type, so `gtype-of` (and
>>>     everything which relies on it, i.e. method dispatch) wouldn't be
>>>     usable for types with a non-empty arglist.
>>
>> I am not sure I understand this point regarding ARGS.
>> Is this related to the `cl-deftype' arguments which cannot be used to
>> declare argument type of methods:
> 
> Exactly.  `cl-deftype` lets you define types such as `(list-of
> integer)`, but your code is not able to figure out that a value is of
> type `(list-of integer)` so you can't handle those kinds of types.
> And that's OK: it's still better than what we currently have.
> 
>> But, below is possible instead:
>>
>> (defgtype u8 unsigned-byte ()
>>    '(unsigned-byte 8))
>>
>> (cl-defmethod my-foo ((n u8))
>>    (format "unsigned 8bits, %s - also %s"
>>            n (cl-call-next-method)))
> 
> That's right.

OK.

> 
> We could try to later add support for
> 
>      (cl-defmethod my-foo ((n (unsigned-byte 8)))
>        (format "unsigned, %s" n))
> 
> but ... one step at a time.

Sure.  Even better could be to support the full type-specifier syntax
;-)


Please find attached a first attempt at a cl-types.el to be merged in
cl-lib.  Please feel free to propose new names if mine are not good.

For now, the new `cl-deftype' is named `cl-deftype2' for testing
without impacting the existing environment.

I tried to consistent at using the `cl-type-' prefix (or `cl--type-'
for internals).  But some names are very close to already existing
ones, like 'cl-type-p' vs. `cl-typep'.  There is also a collision with
the name `cl-type-of', already used for a builtin function, so I used
the name `cl-types-of' which also better represent that this function
returns a list of types.

The new code is also better at handling errors.  It should detect most
of the possible errors, and will restore the current environnement on
error.  I also tried to improve cl-types-of.  Please read my comments
in the code.

WDYT?

Thanks!
David


 

[cl-types.el (text/x-emacs-lisp, attachment)]

Message #53 received at 77725 <at> debbugs.gnu.org (full text, mbox):

From: David Ponce <da_vid <at> orange.fr>
To: Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: 77725 <at> debbugs.gnu.org, Eli Zaretskii <eliz <at> gnu.org>
Subject: Re: bug#77725: 31.0.50; Add support for types accepted by `cl-typep'
 to cl-generic?
Date: Wed, 16 Apr 2025 17:42:15 +0200

[...]
> Please find attached a first attempt at a cl-types.el to be merged in
> cl-lib.  Please feel free to propose new names if mine are not good.
> 
> For now, the new `cl-deftype' is named `cl-deftype2' for testing
> without impacting the existing environment.
> 
> I tried to consistent at using the `cl-type-' prefix (or `cl--type-'
> for internals).  But some names are very close to already existing
> ones, like 'cl-type-p' vs. `cl-typep'.  There is also a collision with
> the name `cl-type-of', already used for a builtin function, so I used
> the name `cl-types-of' which also better represent that this function
> returns a list of types.
> 
> The new code is also better at handling errors.  It should detect most
> of the possible errors, and will restore the current environnement on
> error.  I also tried to improve cl-types-of.  Please read my comments
> in the code.
> 
> WDYT?

I also have a question regarding the "typeof" generalizer which is defined
like this in cl-generic:

(cl-generic-define-generalizer cl--generic-typeof-generalizer
  10 (lambda (name &rest _) `(cl-type-of ,name))
  #'cl--generic-type-specializers)

(cl-defmethod cl-generic-generalizers :extra "typeof" (type)
  "Support for dispatch on types.
This currently works for built-in types and types built on top of records."
  ;; FIXME: Add support for other "types" accepted by `cl-typep' such
  ;; as `character', `face', `keyword', ...?
  (or
   (and (symbolp type)
        (not (eq type t)) ;; Handled by the `t-generalizer'.
        (let ((class (cl--find-class type)))
          (memq (type-of class)
                '(built-in-class cl-structure-class eieio--class)))
        (list cl--generic-typeof-generalizer))
   (cl-call-next-method)))

The proposed "cl-types-of" generalizer must have a higher priority than
"typof" to correctly takes precedence over built-in types.

But, what about the defstruct and defclass types? Shouldn't such types
have higher priority than cl-deftype and builtin types?

I wouldn't want "cl-types-of" to have too much of a performance impact on
method dispatch for defstruct and defclass types, unless it's really
necessary.

Message #56 received at 77725 <at> debbugs.gnu.org (full text, mbox):

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: Re: bug#77725: 31.0.50; Add support for types accepted by
 `cl-typep' to cl-generic?
Date: Wed, 16 Apr 2025 15:56:30 -0400

> Please find attached a first attempt at a cl-types.el to be merged in
> cl-lib.  Please feel free to propose new names if mine are not good.
>
> For now, the new `cl-deftype' is named `cl-deftype2' for testing
> without impacting the existing environment.

👍🏾

> so I used the name `cl-types-of' which also better represent that this
> function returns a list of types.

+1

> WDYT?

See comments below.

> The proposed "cl-types-of" generalizer must have a higher priority than
> "typof" to correctly takes precedence over built-in types.

That's right.

> But, what about the defstruct and defclass types? Shouldn't such types
> have higher priority than cl-deftype and builtin types?

Actually, since Emacs-26 `(cl-)type-of` returns the proper struct type
for both defstruct and defclass types, so they both use the
`cl--generic-typeof-generalizer`.
[ That's still not the case for OClosures, sadly.  ]

> I wouldn't want "cl-types-of" to have too much of a performance impact on
> method dispatch for defstruct and defclass types, unless it's really
> necessary.

The cost is doesn't depend on priority, it depends only on which
generalizers are used for which generic-functions: a generic function
whose methods don't use cl-types will not be affected at all.  A generic
function which does have at least one method dispatching on a cl-type
will be affected, even if you never call it with an object of such cl-type.

> (defun cl-type-p (object)
>   "Return non-nil if OBJECT is a used defined type.
> That is, a type of class `cl-type-class'."
>   (and (symbolp object)
>        (eq (type-of (cl-find-class object)) 'cl-type-class)))

Hmm... yeah... names...

Then again, I don't think we have an equivalent function to test if
a type is a bultin type or a struct type or a defclass type or an
OClosure type, so let's push this to the "cl--" namespace.

> (cl-defstruct
>     (cl-type-class
>      (:include cl--class)
>      (:noinline t)
>      (:constructor nil)
>      (:constructor cl--type-class-make
>                    (name
>                     docstring
>                     parent-types
>                     &aux (parents
>                           (mapcar
>                            (lambda (type)
>                              (cl-check-type type (satisfies cl-type-p))
>                              (cl-find-class type))
>                            parent-types))))
>      (:copier nil))
>   "Type descriptors for user defined types.")

I'm thinking it might be useful to accept builtin types as parents.
E.g. we could make `cl-types-p` skip testing those cl-types whose parents
are incompatible with the output of `cl-type-p`.

I'd add a FIXME in there noting that the `cl-deftype-handler` property
should arguably be turned into a field of this struct (but it has
performance and compatibility implications, so let's not make that
change for now).

> (defun cl-type-parents (name)
>   "Get parents of type with NAME.
> NAME is a symbol representing a type."
>   (cl--class-allparents (cl-find-class name)))

Let's push this to "cl--" as well.

> (defun cl-type-children (name)
>   "Get children of the type with NAME.
> NAME is a symbol representing a type.
> Return a possibly empty list of types."
>   (cl-check-type name (satisfies cl-type-p))
>   (let (children)
>     (dolist (elt cl--type-list)
>       (or (eq name elt)
>           (if (memq name (cl-type-parents elt))
>               (push elt children))))
>     children))

Same.

> (defun cl--type-generalize (name arglist body)
>   "Generalize type with NAME for method dispatching.
> ARGLIST and BODY are passed to `cl-deftype'."
>   (let ((oldtlist (copy-sequence cl--type-list))
>         (oldplist (copy-sequence (symbol-plist name))))
>     (condition-case err
>         (pcase-let* ((`(,decls . ,body) (macroexp-parse-body body))
>                      (docstring (if (stringp (car decls))
>                                     (pop decls)
>                                   (cdr (assq :documentation decls))))
>                      (decls   (cdr (assq 'declare decls)))
>                      (parents (cdr (assq 'subtype-of decls)))

Since we use the word "parents" everywhere, maybe we should look for
`parents` rather than `subtype-of`?

>                      (class   (cl-find-class name))
>                      (reged   (memq name cl--type-list)))
>           (if (null class)
>               (or (null reged)
>                   (error "Type generalized, but doesn't exist"))
>             (or reged "Type exists, but not generalized")

I think there's an `error` missing here or something.

>             (or (eq (type-of class) 'cl-type-class)
>                 (error "Type in another class: %S" (type-of class))))
>           (or (listp parents) (setq parents (list parents)))
>           (if (memq name parents)
>               (error "Type in parents: %S" parents))

Not sure how useful is this test.

>           ;; Setup a type descriptor for NAME.  Can't use `setf' with
>           ;; `cl-find-class', so fallback to plain `put' to set the
>           ;; `cl--class' symbol property.
>           (put name 'cl--class
>                (cl--type-class-make name docstring parents))

Better use `setf` (with `cl--find-class`).

>           ;; Clear cached value of specializers with NAME.
>           (if class
> 	      (cl--type-reset-specializers name)
> 	    ;; Record new type.
> 	    (push name cl--type-list))

Shouldn't we test `reged` before `push`ing?
Also, I think we should skip those types whose arglist is not empty
(and probably signal an error if `subtype-of` is specified at the same
time as a non-empty arglist).

>           ;; Keep most specific types before more general types.
>           (setq cl--type-list (merge-ordered-lists
> 			       (cl--type-dag)
> 			       (lambda (g)
>                                  (error "Invalid DAG, %S" g))))

Why do we need sorting?  Ah, it's so as to avoid sorting in
`cl-types-of`?  Maybe clarify it in the comment, then.

>           ;; Return the form to declare the type.
>           `(cl-eval-when (compile load eval)
>              (define-symbol-prop ',name 'cl-deftype-handler
>                                  (cl-function
>                                   (lambda (&cl-defs ('*) ,@arglist)
>                                     ,docstring
>                                     ,@body)))))

Hmm... wait, so all the code before is executed only during
macro-expansion and not at run-time?  That doesn't sound right.

> (defmacro cl-type-undefine (name)
>   "Remove the definitions of type with NAME.
> NAME is an unquoted symbol representing a type.
> Signal an error if other types inherit from NAME."
>   `(progn
>      (cl-check-type ',name (satisfies cl-type-p))
>      (cl--type-undefine ',name)))

We don't have that for other types.  I understand it's somewhat
dangerous for the other types and not for this one, but I still wonder
if we need it.

> ;; Assuming that `cl--type-list' is properly sorted from most specific
> ;; types to least specific ones, which should be guaranteed by
> ;; `merge-ordered-list' in `cl--type-generalize' this verions of
> ;; `cl-types-of' tries sequentially each type in `cl--type-list', but
> ;; stops on the first type that matches and returns the parents of the
> ;; type plus the builtin type of OBJECT.  If no type is found, return
> ;; nil to fallback to the "typeof" generalizer.

That doesn't sound right: it works only if there are no types which are
overlapping and "incomparable" (like `cons-car-foo` and `cons-cdr-foo`).
We may be able to use the `subtype-of` info to skip some types (e.g. we
don't need to test the parents, or if we traverse the list in the other
direction, we don't need to test FOO if we already saw that the object
failed the test for one of FOO's parents), but in general we'll have to
check them all: we definitely can't stop at the first successful check.


        Stefan


> (defvar cl--type-specializers (make-hash-table :test 'eq)
>   "Memoize type specializers.
> Values are refreshed following the definition or removal of types.")
>
> (defun cl--type-reset-specializers (name)
>   "Remove all cached value of specializers related to type with NAME."
>   (maphash (lambda (key _)
>              (if (memq name key)
>                  (remhash key cl--type-specializers)))
>            cl--type-specializers))

BTW, you can also make `cl-types-of` return directly the complete list
of types+allparents, i.e. the ordered list of specializers.  And then
your `cl--type-specializers` function could turn into the identity.

> ;;; Some tests
> ;;
> '(progn
>    (cl-deftype2 unsigned-byte (&optional bits)
>      "Unsigned integer."
>      `(integer 0 ,(if (eq bits '*) bits (1- (ash 1 bits)))))
>
>    (cl-deftype2 unsigned-16bits ()
>      "Unsigned 16-bits integer."
>      (declare (subtype-of unsigned-byte))
>      '(unsigned-byte 16))
>
>    (cl-deftype2 unsigned-8bits ()
>      "Unsigned 8-bits integer."
>      (declare (subtype-of unsigned-16bits))
>      '(unsigned-byte 8))

I suggest to define something like `multiples-of-2`, `multiples-of-3`,
and `multiples-of-4`, so as to test more complex relationships between
types (with overlap but not inclusion).


        Stefan

Message #59 received at 77725 <at> debbugs.gnu.org (full text, mbox):

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

[Message part 1 (text/plain, inline)]

[...]
> The cost is doesn't depend on priority, it depends only on which
> generalizers are used for which generic-functions: a generic function
> whose methods don't use cl-types will not be affected at all.  A generic
> function which does have at least one method dispatching on a cl-type
> will be affected, even if you never call it with an object of such cl-type.

Good to know :-)

>> (defun cl-type-p (object)
>>    "Return non-nil if OBJECT is a used defined type.
>> That is, a type of class `cl-type-class'."
>>    (and (symbolp object)
>>         (eq (type-of (cl-find-class object)) 'cl-type-class)))
> 
> Hmm... yeah... names...
> 
> Then again, I don't think we have an equivalent function to test if
> a type is a bultin type or a struct type or a defclass type or an
> OClosure type, so let's push this to the "cl--" namespace.

Done.

>> (cl-defstruct
>>      (cl-type-class
>>       (:include cl--class)
>>       (:noinline t)
>>       (:constructor nil)
>>       (:constructor cl--type-class-make
>>                     (name
>>                      docstring
>>                      parent-types
>>                      &aux (parents
>>                            (mapcar
>>                             (lambda (type)
>>                               (cl-check-type type (satisfies cl-type-p))
>>                               (cl-find-class type))
>>                             parent-types))))
>>       (:copier nil))
>>    "Type descriptors for user defined types.")
> 
> I'm thinking it might be useful to accept builtin types as parents.
> E.g. we could make `cl-types-p` skip testing those cl-types whose parents
> are incompatible with the output of `cl-type-p`.

I tried to do that, but I am not sure I well understood your point.
Please let me know if the code is what you expect.

> I'd add a FIXME in there noting that the `cl-deftype-handler` property
> should arguably be turned into a field of this struct (but it has
> performance and compatibility implications, so let's not make that
> change for now).

Done.

>> (defun cl-type-parents (name)
>>    "Get parents of type with NAME.
>> NAME is a symbol representing a type."
>>    (cl--class-allparents (cl-find-class name)))
> 
> Let's push this to "cl--" as well.

Done.  As it is now internal, I used a macro to reduce function calls
in cl-types-of (see your point below about making `cl-types-of`
returns directly the complete list of types+allparents).

> 
>> (defun cl-type-children (name)
>>    "Get children of the type with NAME.
>> NAME is a symbol representing a type.
>> Return a possibly empty list of types."
>>    (cl-check-type name (satisfies cl-type-p))
>>    (let (children)
>>      (dolist (elt cl--type-list)
>>        (or (eq name elt)
>>            (if (memq name (cl-type-parents elt))
>>                (push elt children))))
>>      children))
> 
> Same.

Done.

>> (defun cl--type-generalize (name arglist body)
>>    "Generalize type with NAME for method dispatching.
>> ARGLIST and BODY are passed to `cl-deftype'."
>>    (let ((oldtlist (copy-sequence cl--type-list))
>>          (oldplist (copy-sequence (symbol-plist name))))
>>      (condition-case err
>>          (pcase-let* ((`(,decls . ,body) (macroexp-parse-body body))
>>                       (docstring (if (stringp (car decls))
>>                                      (pop decls)
>>                                    (cdr (assq :documentation decls))))
>>                       (decls   (cdr (assq 'declare decls)))
>>                       (parents (cdr (assq 'subtype-of decls)))
> 
> Since we use the word "parents" everywhere, maybe we should look for
> `parents` rather than `subtype-of`?

Make sense.  I used parents.

> 
>>                       (class   (cl-find-class name))
>>                       (reged   (memq name cl--type-list)))
>>            (if (null class)
>>                (or (null reged)
>>                    (error "Type generalized, but doesn't exist"))
>>              (or reged "Type exists, but not generalized")
> 
> I think there's an `error` missing here or something.

Good catch. Fixed.

>>              (or (eq (type-of class) 'cl-type-class)
>>                  (error "Type in another class: %S" (type-of class))))
>>            (or (listp parents) (setq parents (list parents)))
>>            (if (memq name parents)
>>                (error "Type in parents: %S" parents))
> 
> Not sure how useful is this test.

I removed testing if parents is a list, this is always true.
The other test prevents to define a type whose parent is itself.

>>            ;; Setup a type descriptor for NAME.  Can't use `setf' with
>>            ;; `cl-find-class', so fallback to plain `put' to set the
>>            ;; `cl--class' symbol property.
>>            (put name 'cl--class
>>                 (cl--type-class-make name docstring parents))
> 
> Better use `setf` (with `cl--find-class`).

I switched to `cl--find-class' everywhere for consistency.

>>            ;; Clear cached value of specializers with NAME.
>>            (if class
>> 	      (cl--type-reset-specializers name)
>> 	    ;; Record new type.
>> 	    (push name cl--type-list))
> 
> Shouldn't we test `reged` before `push`ing?

Not sure to understand this point.  name needs to be in cl--type-list
before to call merge-ordered-lists on the DAG.

> Also, I think we should skip those types whose arglist is not empty
> (and probably signal an error if `subtype-of` is specified at the same
> time as a non-empty arglist).

Signal an error if arglist and parents are both non-nil.

>>            ;; Keep most specific types before more general types.
>>            (setq cl--type-list (merge-ordered-lists
>> 			       (cl--type-dag)
>> 			       (lambda (g)
>>                                   (error "Invalid DAG, %S" g))))
> 
> Why do we need sorting?  Ah, it's so as to avoid sorting in
> `cl-types-of`?  Maybe clarify it in the comment, then.

Done.

>>            ;; Return the form to declare the type.
>>            `(cl-eval-when (compile load eval)
>>               (define-symbol-prop ',name 'cl-deftype-handler
>>                                   (cl-function
>>                                    (lambda (&cl-defs ('*) ,@arglist)
>>                                      ,docstring
>>                                      ,@body)))))
> 
> Hmm... wait, so all the code before is executed only during
> macro-expansion and not at run-time?  That doesn't sound right.

OMG! You are right. I fixed that.

>> (defmacro cl-type-undefine (name)
>>    "Remove the definitions of type with NAME.
>> NAME is an unquoted symbol representing a type.
>> Signal an error if other types inherit from NAME."
>>    `(progn
>>       (cl-check-type ',name (satisfies cl-type-p))
>>       (cl--type-undefine ',name)))
> 
> We don't have that for other types.  I understand it's somewhat
> dangerous for the other types and not for this one, but I still wonder
> if we need it.

I thought it could be useful, for example to cleanup the environment
when you kind of uninstall a library which defined types.  Maybe it
could help during tests?

>> ;; Assuming that `cl--type-list' is properly sorted from most specific
>> ;; types to least specific ones, which should be guaranteed by
>> ;; `merge-ordered-list' in `cl--type-generalize' this verions of
>> ;; `cl-types-of' tries sequentially each type in `cl--type-list', but
>> ;; stops on the first type that matches and returns the parents of the
>> ;; type plus the builtin type of OBJECT.  If no type is found, return
>> ;; nil to fallback to the "typeof" generalizer.
> 
> That doesn't sound right: it works only if there are no types which are
> overlapping and "incomparable" (like `cons-car-foo` and `cons-cdr-foo`).
> We may be able to use the `subtype-of` info to skip some types (e.g. we
> don't need to test the parents, or if we traverse the list in the other
> direction, we don't need to test FOO if we already saw that the object
> failed the test for one of FOO's parents), but in general we'll have to
> check them all: we definitely can't stop at the first successful check.

Good point.  But you lost me regarding possible optimizations :-(
I returned to the previous version that check all types.

>> (defvar cl--type-specializers (make-hash-table :test 'eq)
>>    "Memoize type specializers.
>> Values are refreshed following the definition or removal of types.")
>>
>> (defun cl--type-reset-specializers (name)
>>    "Remove all cached value of specializers related to type with NAME."
>>    (maphash (lambda (key _)
>>               (if (memq name key)
>>                   (remhash key cl--type-specializers)))
>>             cl--type-specializers))
> 
> BTW, you can also make `cl-types-of` return directly the complete list
> of types+allparents, i.e. the ordered list of specializers.  And then
> your `cl--type-specializers` function could turn into the identity.

Good idea.  I did that, which seems to work well :-)

>> ;;; Some tests
[...]
> 
> I suggest to define something like `multiples-of-2`, `multiples-of-3`,
> and `multiples-of-4`, so as to test more complex relationships between
> types (with overlap but not inclusion).

Do you have any examples in mind?

Thank you for your help.

David

[cl-types.el (text/x-emacs-lisp, attachment)]

Message #62 received at 77725 <at> debbugs.gnu.org (full text, mbox):

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: Re: bug#77725: 31.0.50; Add support for types accepted by
 `cl-typep' to cl-generic?
Date: Thu, 17 Apr 2025 11:27:01 -0400

>>>              (or (eq (type-of class) 'cl-type-class)
>>>                  (error "Type in another class: %S" (type-of class))))
>>>            (or (listp parents) (setq parents (list parents)))
>>>            (if (memq name parents)
>>>                (error "Type in parents: %S" parents))
>> Not sure how useful is this test.
>
> I removed testing if parents is a list, this is always true.
> The other test prevents to define a type whose parent is itself.

My comment was specifically about the last 2 lines testing if `name` is
in `parents`.  How likely is this error?  Wouldn't it be caught by the
DAG test later anyway?

>>>            ;; Clear cached value of specializers with NAME.
>>>            (if class
>>> 	      (cl--type-reset-specializers name)
>>> 	    ;; Record new type.
>>> 	    (push name cl--type-list))
>> Shouldn't we test `reged` before `push`ing?
> Not sure to understand this point.  name needs to be in cl--type-list
> before to call merge-ordered-lists on the DAG.

IIRC if `reged` is non-nil, `name` is already included in
`cl--type-list` so we shouldn't push it again there.

>>> (defmacro cl-type-undefine (name)
>>>    "Remove the definitions of type with NAME.
>>> NAME is an unquoted symbol representing a type.
>>> Signal an error if other types inherit from NAME."
>>>    `(progn
>>>       (cl-check-type ',name (satisfies cl-type-p))
>>>       (cl--type-undefine ',name)))
>> We don't have that for other types.  I understand it's somewhat
>> dangerous for the other types and not for this one, but I still wonder
>> if we need it.
> I thought it could be useful, for example to cleanup the environment
> when you kind of uninstall a library which defined types.  Maybe it
> could help during tests?

I'm not saying it can't be useful, just wondering if it will be.
In either case it doesn't seem like there's a good reason it should be
a `defmacro` rather than a `defun`.

BTW, part of this is handled by `define-symbol-prop` which makes sure
that the `cl-deftype-handler` is automatically removed when you
`unload-feature`.  Maybe we should use `define-symbol-prop` instead of
`setf` for the `cl--class` property as well.

>> That doesn't sound right: it works only if there are no types which are
>> overlapping and "incomparable" (like `cons-car-foo` and `cons-cdr-foo`).
>> We may be able to use the `subtype-of` info to skip some types (e.g. we
>> don't need to test the parents, or if we traverse the list in the other
>> direction, we don't need to test FOO if we already saw that the object
>> failed the test for one of FOO's parents), but in general we'll have to
>> check them all: we definitely can't stop at the first successful check.
> Good point.  But you lost me regarding possible optimizations :-(

If BAR is declared as a parent of FOO and `cl-types-of` has already
decided that the value *is* of type FOO, then we already know BAR will
be in the output anyway and there's no point testing BAR.

The converse is that if we have already decided that the value is *not*
for type BAR, then it can't be of type FOO either, so there's no point
testing FOO.

This presumes that the declaration that BAR is parent of FOO is
actually correct, of course.

> I returned to the previous version that check all types.

Good.

>>> ;;; Some tests
> [...]
>> I suggest to define something like `multiples-of-2`, `multiples-of-3`,
>> and `multiples-of-4`, so as to test more complex relationships between
>> types (with overlap but not inclusion).
>
> Do you have any examples in mind?

Test that (c-types-of 4) is (multiples-of-4 multiples-of-2 ...)
Test that (c-types-of 6) is (multiples-of-3 multiples-of-2 ...)
Test that (c-types-of 12) is (multiples-of-4 multiples-of-3 multiples-of-2 ...)

This would have failed with your previous code which didn't check
all types.


        Stefan

Message #65 received at 77725 <at> debbugs.gnu.org (full text, mbox):

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

On 2025-04-17 17:27, Stefan Monnier wrote:
>>>>             (if (memq name parents)
>>>>                 (error "Type in parents: %S" parents))
>>> Not sure how useful is this test.
>>
>> I removed testing if parents is a list, this is always true.
>> The other test prevents to define a type whose parent is itself.
> 
> My comment was specifically about the last 2 lines testing if `name` is
> in `parents`.  How likely is this error?  Wouldn't it be caught by the
> DAG test later anyway?

In principle your are correct, the cycle should be caught at DAG test.
But it seems it's not the case.  I removed the test for `name' in `parents'
and tried these definitions:

(cl-deftype test ()
  'number)

(cl-deftype test ()
  (declare (parents test))
  'number)

Normally, the second definition should be caught by the DAG test, but is
not, and produced wrong definition, with `cl--type-list' equals to
(test test).

It seems the problem is that `merge-ordered-lists' doesn't caught this
case:

(merge-ordered-lists '((test test)))
=> (test test)

I tried the same test with the topologic sort, and it failed as expected:

(gtype--topologic-sort '((test test)))
=> "Invalid graph" error

> 
>>>>             ;; Clear cached value of specializers with NAME.
>>>>             (if class
>>>> 	      (cl--type-reset-specializers name)
>>>> 	    ;; Record new type.
>>>> 	    (push name cl--type-list))
>>> Shouldn't we test `reged` before `push`ing?
>> Not sure to understand this point.  name needs to be in cl--type-list
>> before to call merge-ordered-lists on the DAG.
> 
> IIRC if `reged` is non-nil, `name` is already included in
> `cl--type-list` so we shouldn't push it again there.

In fact, push is done only if `class' is nil, which is the equivalent
to `reged' non-nil.  For clarity, I changed to test with `reged'
(renamed `recorded' new versions).

>>>> (defmacro cl-type-undefine (name)
>>>>     "Remove the definitions of type with NAME.
>>>> NAME is an unquoted symbol representing a type.
>>>> Signal an error if other types inherit from NAME."
>>>>     `(progn
>>>>        (cl-check-type ',name (satisfies cl-type-p))
>>>>        (cl--type-undefine ',name)))
>>> We don't have that for other types.  I understand it's somewhat
>>> dangerous for the other types and not for this one, but I still wonder
>>> if we need it.
>> I thought it could be useful, for example to cleanup the environment
>> when you kind of uninstall a library which defined types.  Maybe it
>> could help during tests?
> 
> I'm not saying it can't be useful, just wondering if it will be.
> In either case it doesn't seem like there's a good reason it should be
> a `defmacro` rather than a `defun`.
> 
> BTW, part of this is handled by `define-symbol-prop` which makes sure
> that the `cl-deftype-handler` is automatically removed when you
> `unload-feature`.  Maybe we should use `define-symbol-prop` instead of
> `setf` for the `cl--class` property as well.

This is good to know.  For now, I only kept the function `cl--type-undefine',
in case we need it to cleanup things while testing.  We can remove it later
if not useful.

>>> That doesn't sound right: it works only if there are no types which are
>>> overlapping and "incomparable" (like `cons-car-foo` and `cons-cdr-foo`).
>>> We may be able to use the `subtype-of` info to skip some types (e.g. we
>>> don't need to test the parents, or if we traverse the list in the other
>>> direction, we don't need to test FOO if we already saw that the object
>>> failed the test for one of FOO's parents), but in general we'll have to
>>> check them all: we definitely can't stop at the first successful check.
>> Good point.  But you lost me regarding possible optimizations :-(
> 
> If BAR is declared as a parent of FOO and `cl-types-of` has already
> decided that the value *is* of type FOO, then we already know BAR will
> be in the output anyway and there's no point testing BAR.

This looks like what I did in my previous version.  When FOO matched,
I put FOO and its parents in the result.  My mistake was stopping there
instead of continuing to the end of the list!

> The converse is that if we have already decided that the value is *not*
> for type BAR, then it can't be of type FOO either, so there's no point
> testing FOO.

Wouldn't this involve calculating the parents of all the types traversed,
instead of just the matching ones? If so, wouldn't we risk losing on one
side what we gain on the other?

>>>> ;;; Some tests
>> [...]
>>> I suggest to define something like `multiples-of-2`, `multiples-of-3`,
>>> and `multiples-of-4`, so as to test more complex relationships between
>>> types (with overlap but not inclusion).
>>
>> Do you have any examples in mind?
> 
> Test that (c-types-of 4) is (multiples-of-4 multiples-of-2 ...)
> Test that (c-types-of 6) is (multiples-of-3 multiples-of-2 ...)
> Test that (c-types-of 12) is (multiples-of-4 multiples-of-3 multiples-of-2 ...)
> 
> This would have failed with your previous code which didn't check
> all types.

Thank you, I'll give it a try.

Message #68 received at 77725 <at> debbugs.gnu.org (full text, mbox):

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: Re: bug#77725: 31.0.50; Add support for types accepted by
 `cl-typep' to cl-generic?
Date: Thu, 17 Apr 2025 23:42:48 -0400

> (merge-ordered-lists '((test test)))
> => (test test)

Ah, right, `merge-ordered-lists` presumes the arg lists are already sane.

>> The converse is that if we have already decided that the value is *not*
>> for type BAR, then it can't be of type FOO either, so there's no point
>> testing FOO.
> Wouldn't this involve calculating the parents of all the types traversed,
> instead of just the matching ones?

I wasn't describing an algorithm, just a principle that can be used
within an algorithm.  Depending on the algorithm you use it can be used
in different ways.  With your current loop, I don't think you can make
much use of it.

But I think what we could do fairly easily is the following:

- based on the PARENTS declaration, create a map from builtin-type to
  the set of cl-types that have that builtin-type among their parents.
  That presumes some PARENTS include some builtin-types, obviously
  otherwise the map will be trivial with all cl-types associated with
  the `t` "dummy parent".
  [ We could even go crazy and try and guess PARENTS when not provided,
    by analyzing the type's definition.  ]
- in `cl-types-of` start by calling `cl-type-of`, then use the map to
  find which cl-types may need to be checked.

But let's keep this for later.


        Stefan

Message #71 received at 77725 <at> debbugs.gnu.org (full text, mbox):

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

[Message part 1 (text/plain, inline)]

Hi Stefan,

>> (merge-ordered-lists '((test test)))
>> => (test test)
> 
> Ah, right, `merge-ordered-lists` presumes the arg lists are already sane.
>

So, I kept the test to ensure `name' is not in `parents'.

>>> The converse is that if we have already decided that the value is *not*
>>> for type BAR, then it can't be of type FOO either, so there's no point
>>> testing FOO.
>> Wouldn't this involve calculating the parents of all the types traversed,
>> instead of just the matching ones?
> 
> I wasn't describing an algorithm, just a principle that can be used
> within an algorithm.  Depending on the algorithm you use it can be used
> in different ways.  With your current loop, I don't think you can make
> much use of it.
> 
> But I think what we could do fairly easily is the following:
> 
> - based on the PARENTS declaration, create a map from builtin-type to
>    the set of cl-types that have that builtin-type among their parents.
>    That presumes some PARENTS include some builtin-types, obviously
>    otherwise the map will be trivial with all cl-types associated with
>    the `t` "dummy parent".
>    [ We could even go crazy and try and guess PARENTS when not provided,
>      by analyzing the type's definition.  ]
> - in `cl-types-of` start by calling `cl-type-of`, then use the map to
>    find which cl-types may need to be checked.
> 
> But let's keep this for later.

I was thinking about the exact same idea not long ago :-) I totally
agree with your analysis.  I noted this point in a FIXME.

Please, find attached a new version of cl-types.el:

- I've divided the code more logically between the `cl-deftype2' macro
  and the `cl--type-generalize' function.

- In `cl-types-of', I implemented the idea of ​​not testing a type
  already selected as a parent of a type already selected :-)

- I tried to add some comments to the not so obvious code.

I also wrote a first try at a test file, cl-types-tests.el, also
attached:

- It includes your proposed tests with multiples-of...
  All tests pass for me :-)

Please let me know if something is not correct, need more work, etc.

Regarding a possible merge in cl-lib, should cl-types.el be copied at
the end of cl-lib, after cl-macs is loaded?  If I correctly understand
the logic of loading these libs ;-)

Thank you!
David

[cl-types-tests.el (text/x-emacs-lisp, attachment)]

[cl-types.el (text/x-emacs-lisp, attachment)]

Message #74 received at 77725 <at> debbugs.gnu.org (full text, mbox):

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

[Message part 1 (text/plain, inline)]

> Regarding a possible merge in cl-lib, should cl-types.el be copied at
> the end of cl-lib, after cl-macs is loaded?  If I correctly understand
> the logic of loading these libs ;-)

I looked into this a bit more, and it turns out that cl-generic
depends on cl-lib, so the code in cl-types.el that depends on
cl-generic can't go in cl-lib. This concern the two definitions
at the end of cl-types.el:

(cl-generic-define-generalizer cl--type-generalizer
  ...
  )

(cl-defmethod cl-generic-generalizers :extra "cl-types-of" (type)
 ...
  )

which could logically go in cl-generic?

I attached a slightly updated version of cl-types.el, mainly to check
first if a type is of class `cl-type-class' in `cl-types-of', and to
use the predicate `cl-type-class-p' simpler than `cl-typep'.

Happy Easter weekend :-)

[cl-types.el (text/x-emacs-lisp, attachment)]

Message #77 received at 77725 <at> debbugs.gnu.org (full text, mbox):

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: Re: bug#77725: 31.0.50; Add support for types accepted by
 `cl-typep' to cl-generic?
Date: Sat, 19 Apr 2025 10:20:00 -0400

>> Regarding a possible merge in cl-lib, should cl-types.el be copied at
>> the end of cl-lib, after cl-macs is loaded?  If I correctly understand
>> the logic of loading these libs ;-)
>
> I looked into this a bit more, and it turns out that cl-generic
> depends on cl-lib, so the code in cl-types.el that depends on
> cl-generic can't go in cl-lib. This concern the two definitions
> at the end of cl-types.el:

Yes, as you've seen, the placement can be tricky.  There are bootstrap
constraints as well as "general design" desires, and they all kind
of pull in different directions.
I'll take a closer look and come back with a proposal.


        Stefan

Message #80 received at 77725 <at> debbugs.gnu.org (full text, mbox):

From: David Ponce <da_vid <at> orange.fr>
To: Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: 77725 <at> debbugs.gnu.org, Eli Zaretskii <eliz <at> gnu.org>
Subject: Re: bug#77725: 31.0.50; Add support for types accepted by `cl-typep'
 to cl-generic?
Date: Sat, 19 Apr 2025 17:37:55 +0200

On 2025-04-19 16:20, Stefan Monnier wrote:
>>> Regarding a possible merge in cl-lib, should cl-types.el be copied at
>>> the end of cl-lib, after cl-macs is loaded?  If I correctly understand
>>> the logic of loading these libs ;-)
>>
>> I looked into this a bit more, and it turns out that cl-generic
>> depends on cl-lib, so the code in cl-types.el that depends on
>> cl-generic can't go in cl-lib. This concern the two definitions
>> at the end of cl-types.el:
> 
> Yes, as you've seen, the placement can be tricky.  There are bootstrap
> constraints as well as "general design" desires, and they all kind
> of pull in different directions.
> I'll take a closer look and come back with a proposal.

Great. Thank you!

David

Message #83 received at 77725 <at> debbugs.gnu.org (full text, mbox):

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: Re: bug#77725: 31.0.50; Add support for types accepted by
 `cl-typep' to cl-generic?
Date: Tue, 22 Apr 2025 17:34:17 -0400

[Message part 1 (text/plain, inline)]

>> Yes, as you've seen, the placement can be tricky.  There are bootstrap
>> constraints as well as "general design" desires, and they all kind
>> of pull in different directions.
>> I'll take a closer look and come back with a proposal.
> Great. Thank you!

Sorry for the delay, here's what I came up with.

I added a FIXME about the recursion-breaker which I have a feeling might
not work.

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.
- They use `eval` too much.


        Stefan

[cl-types.patch (text/x-diff, inline)]

diff --git a/lisp/emacs-lisp/cl-extra.el b/lisp/emacs-lisp/cl-extra.el
index 6390d17a5b7..eb2ad605c8e 100644
--- a/lisp/emacs-lisp/cl-extra.el
+++ b/lisp/emacs-lisp/cl-extra.el
@@ -577,8 +577,8 @@ cl-subseq
 			,new)))))
   (seq-subseq seq start end))
 
-;;; This isn't a defalias because autoloading defaliases doesn't work
-;;; very well.
+;; This isn't a defalias because autoloading defaliases doesn't work
+;; very well.
 
 ;;;###autoload
 (defun cl-concatenate (type &rest sequences)
@@ -731,6 +731,213 @@ cl-prettyexpand
       (cl-prettyprint form)
     (message "")))
 
+;;; CL type defined via `deftype'.
+
+(defvar cl--type-list nil
+  "List of defined types to lookup for method dispatching.")
+
+;; FIXME: The `cl-deftype-handler' property should arguably be turned
+;; into a field of this struct (but it has performance and
+;; compatibility implications, so let's not make that change for now).
+(cl-defstruct
+    (cl-type-class
+     (:include cl--class)
+     (:noinline t)
+     (:constructor nil)
+     (:constructor cl--type-class-make
+                   (name
+                    docstring
+                    parent-types
+                    &aux (parents
+                          (mapcar
+                           (lambda (type)
+                             (or (cl--find-class type)
+                                 (error "Unknown type: %S" type)))
+                           parent-types))))
+     (:copier nil))
+  "Type descriptors for types defined by `cl-deftype'.")
+
+(defun cl--type-p (object)
+  "Return non-nil if OBJECT is a used defined type.
+That is, a type of class `cl-type-class'."
+  (and (symbolp object) (cl-type-class-p (cl--find-class object))))
+
+(defmacro cl--type-parents (name)
+  "Get parents of type with NAME.
+NAME is a symbol representing a type."
+  `(cl--class-allparents (cl--find-class ,name)))
+
+(defun cl--type-children (name)
+  "Get children of the type with NAME.
+NAME is a symbol representing a type.
+Return a possibly empty list of types."
+  (cl-check-type name (satisfies cl--type-p))
+  (let (children)
+    (dolist (elt cl--type-list)
+      (or (eq name elt)
+          (if (memq name (cl--type-parents elt))
+              (push elt children))))
+    children))
+
+;; Keep it for now, for testing.
+(defun cl--type-undefine (name)
+  "Remove the definitions of type with NAME.
+NAME is an unquoted symbol representing a type.
+Signal an error if other types inherit from NAME."
+  (declare-function cl-remprop "cl-extra" (symbol propname))
+  (cl-check-type name (satisfies cl--type-p))
+  (when-let* ((children (and (cl--type-p name)
+                             (cl--type-children name))))
+    (error "Type has children: %S" children))
+  (cl-remprop name 'cl--class)
+  (cl-remprop name 'cl-deftype-handler)
+  (setq cl--type-list (delq name cl--type-list)))
+
+;;;###autoload
+(defun cl--type-deftype (name parents &optional docstring)
+  "Generalize type with NAME for method dispatching.
+PARENTS is a list of types NAME is a subtype of, or nil.
+DOCSTRING is an optional documentation string."
+  (let ((oldplist (copy-sequence (symbol-plist name))))
+    (condition-case err
+        (let* ((class (cl--find-class name))
+               (recorded (memq name cl--type-list)))
+          (if (null class)
+              (or (null recorded)
+                  (error "Type generalized, but doesn't exist"))
+            (or recorded (error "Type exists, but not generalized"))
+            (or (cl-type-class-p class)
+                (error "Type in another class: %S" (type-of class))))
+          (if (memq name parents)
+              (error "Type in parents: %S" parents))
+          ;; Setup a type descriptor for NAME.
+          (setf (cl--find-class name)
+                (cl--type-class-make name docstring parents))
+          ;; `cl-types-of' iterates through all known types to collect
+          ;; all those an object belongs to, sorted from the most
+          ;; specific type to the more general type.  So, keep the
+          ;; global list in this order.
+          (setq cl--type-list
+                (merge-ordered-lists
+                 (mapcar (lambda (type)
+                           (cl--class-allparents (cl--find-class type)))
+                         (if recorded
+                             cl--type-list
+                           (cons name cl--type-list)))
+                 (lambda (_) (error "Invalid dependency graph")))))
+      (error
+       ;; On error restore previous data.
+       (setf (symbol-plist name) oldplist)
+       (error (format "Define %S failed: %s"
+                      name (error-message-string err)))))))
+
+(defvar cl--type-object (make-symbol "void"))
+;; Ensure each type satisfies `eql'.
+(defvar cl--type-unique (make-hash-table :test 'equal)
+  "Record an unique value of each type.")
+
+;; FIXME: `cl-types-of' CPU cost is proportional to the number of types
+;; defined with `cl-deftype', so the more popular it gets, the slower
+;; it becomes.  And of course, the cost of each type check is
+;; unbounded, so a single "expensive" type can slow everything down
+;; further.
+;;
+;; The usual dispatch is
+;;
+;;   (lambda (arg &rest args)
+;;     (let ((f (gethash (cl-typeof arg) precomputed-methods-table)))
+;;       (if f
+;;           (apply f arg args)
+;;         ;; Slow case when encountering a new type
+;;         ...)))
+;;
+;; where often the most expensive part is `&rest' (which has to
+;; allocate a list for those remaining arguments),
+;;
+;; So we're talking about replacing
+;;
+;;   &rest + cl-type-of + gethash + if + apply
+;;
+;; with a function that loops over N types, calling `cl-typep' on each
+;; one of them (`cl-typep' itself being a recursive function that
+;; basically interprets the type language).  This is going to slow
+;; down dispatch very significantly for those generic functions that
+;; have a method that dispatches on a user defined type, compared to
+;; those that don't.
+;;
+;; A possible further improvement:
+;;
+;; - based on the PARENTS declaration, create a map from builtin-type
+;;   to the set of cl-types that have that builtin-type among their
+;;   parents.  That presumes some PARENTS include some builtin-types,
+;;   obviously otherwise the map will be trivial with all cl-types
+;;   associated with the `t' "dummy parent".  [ We could even go crazy
+;;   and try and guess PARENTS when not provided, by analyzing the
+;;   type's definition. ]
+;;
+;; - in `cl-types-of' start by calling `cl-type-of', then use the map
+;;   to find which cl-types may need to be checked.
+;;
+;;;###autoload
+(defun cl-types-of (object)
+  "Return the types OBJECT belongs to.
+Return an unique list of types OBJECT belongs to, ordered from the
+most specific type to the most general."
+  ;; Ignore recursive call on the same OBJECT, which can legitimately
+  ;; occur when a parent type is checking whether an object's type is
+  ;; that of one of its children.
+  ;; FIXME: Does this even work?  Won't `cl--type-object' be rebound to
+  ;; the other object before we get here?  IOW wouldn't we need a list
+  ;; of objects that are in the process of being checked?  And while
+  ;; returning nil breaks the recursion, won't it return a bogus result?
+  (unless (eq object cl--type-object)
+    (let ((cl--type-object object)
+          (found (list (cl--type-parents (cl-type-of object)))))
+      ;; Build a DAG of all types OBJECT belongs to.
+      (dolist (type cl--type-list)
+        (and
+         ;; Skip type not defined by `cl-deftype'.
+         (cl-type-class-p (cl--find-class type))
+         ;; If BAR is declared as a parent of FOO and `cl-types-of'
+         ;; has already decided that the value is of type FOO, then we
+         ;; already know BAR will be in the output anyway and there's
+         ;; no point testing BAR.  So, skip type already selected as
+         ;; parent of another type, assuming that, most of the time,
+         ;; `assq' will be faster than `cl-typep'.
+         (null (assq type found))
+         ;; If OBJECT is of type, add type and parents to the DAG.
+         (cl-typep object type)
+         ;; (dolist (p (cl--type-parents type))
+         ;;   (push (cl--type-parents p) found))
+         ;; Equivalent to the `dolist' above, but faster: avoid to
+         ;; recompute several lists of parents we already know.
+         (let ((pl (cl--type-parents type)))
+           (while pl
+             (push pl found)
+             (setq pl (cdr pl))))
+         ))
+      ;; Compute an ordered list of types from the collected DAG.
+      (setq found (merge-ordered-lists found))
+      ;; Return an unique value of this list of types, which is also
+      ;; the list of specifiers for this type.
+      (with-memoization (gethash found cl--type-unique)
+        found))))
+
+(cl-deftype extended-char () '(and character (not base-char)))
+
+;;;; Method dispatching
+
+(cl-generic-define-generalizer cl--type-generalizer
+  20 ;; "typeof" < "cl-types-of" < "head" priority
+  (lambda (obj &rest _) `(cl-types-of ,obj))
+  (lambda (tag &rest _) (if (consp tag) tag)))
+
+(cl-defmethod cl-generic-generalizers :extra "cl-types-of" (type)
+  "Support for dispatch on types."
+  (if (cl--type-p type)
+      (list cl--type-generalizer)
+    (cl-call-next-method)))
+
 ;;; Integration into the online help system.
 
 (eval-when-compile (require 'cl-macs))  ;Explicitly, for cl--find-class.
diff --git a/lisp/emacs-lisp/cl-generic.el b/lisp/emacs-lisp/cl-generic.el
index 8de45626bf0..af38f432e84 100644
--- a/lisp/emacs-lisp/cl-generic.el
+++ b/lisp/emacs-lisp/cl-generic.el
@@ -582,6 +582,7 @@ cl-defmethod
          (,'declare-function ,name "")
          ;; We use #' to quote `name' so as to trigger an
          ;; obsolescence warning when applicable.
+         ;; FIXME: Eval `eql'and `head' thingies!
          (cl-generic-define-method #',name ',(nreverse qualifiers) ',args
                                    ',call-con ,fun)))))
 
diff --git a/lisp/emacs-lisp/cl-macs.el b/lisp/emacs-lisp/cl-macs.el
index a966ec5eaf6..1bd3ab55519 100644
--- a/lisp/emacs-lisp/cl-macs.el
+++ b/lisp/emacs-lisp/cl-macs.el
@@ -3786,15 +3786,46 @@ cl--compiler-macro-get
 ;;;###autoload
 (defmacro cl-deftype (name arglist &rest body)
   "Define NAME as a new data type.
-The type name can then be used in `cl-typecase', `cl-check-type', etc."
+The type NAME can then be used in `cl-typecase', `cl-check-type', etc,
+and as argument type for dispatching generic function methods.
+
+ARGLIST is a Common Lisp argument list of the sort accepted by
+`cl-defmacro'.  BODY forms are evaluated and should return a type
+specifier that is equivalent to the type (see the Info node `(cl) Type
+Predicates' in the GNU Emacs Common Lisp Emulation manual).
+
+If there is a `declare' form in BODY, the spec (parents PARENTS) is
+recognized to specify a list of types NAME is a subtype of.  For
+instance:
+
+  (cl-deftype unsigned-byte (&optional bits)
+    \"Unsigned integer.\"
+    (list \\='integer 0 (if (eq bits \\='*) bits (1- (ash 1 bits)))))
+
+  (cl-deftype unsigned-8bits ()
+    \"Unsigned 8-bits integer.\"
+    (declare (parents unsigned-byte))
+    \\='(unsigned-byte 8))
+
+The list of PARENTS types determines the order of methods invocation,
+and missing PARENTS may cause incorrect ordering of methods, while
+extraneous PARENTS may cause use of extraneous methods."
   (declare (debug cl-defmacro) (doc-string 3) (indent 2))
-  `(cl-eval-when (compile load eval)
-     (define-symbol-prop ',name 'cl-deftype-handler
-                         (cl-function (lambda (&cl-defs ('*) ,@arglist) ,@body)))))
-
-(cl-deftype extended-char () '(and character (not base-char)))
-;; Define fixnum so `cl-typep' recognize it and the type check emitted
-;; by `cl-the' is effective.
+  (pcase-let*
+      ((`(,decls . ,forms) (macroexp-parse-body body))
+       (docstring (if (stringp (car decls))
+                      (car decls)
+                    (cadr (assq :documentation decls))))
+       (parents (cdr (assq 'parents (cdr (assq 'declare decls))))))
+    (and parents arglist
+         (error "Parents specified, but arglist not empty"))
+    (if docstring (setq forms (cons docstring forms)))
+    `(cl-eval-when (compile load eval)
+       (cl--type-deftype ',name ',parents ,docstring)
+       (define-symbol-prop ',name 'cl-deftype-handler
+                           (cl-function
+                            (lambda (&cl-defs ('*) ,@arglist)
+                              ,@forms))))))
 
 ;;; Additional functions that we can now define because we've defined
 ;;; `cl-defsubst' and `cl-typep'.
diff --git a/test/lisp/emacs-lisp/cl-extra-tests.el b/test/lisp/emacs-lisp/cl-extra-tests.el
index 20d1e532a6f..08198faf28c 100644
--- a/test/lisp/emacs-lisp/cl-extra-tests.el
+++ b/test/lisp/emacs-lisp/cl-extra-tests.el
@@ -348,4 +348,156 @@ cl-extra-test-tailp
     (should (cl-tailp l l))
     (should (not (cl-tailp '(4 5) l)))))
 
+(ert-deftest cl-types-test-1 ()
+  "Test types definition and cl-types-of."
+
+  (should
+   (functionp
+    (eval
+     '(cl-deftype multiples-of (&optional m)
+        (let ((multiplep (if (eq m '*)
+                             #'ignore
+                           (lambda (n) (= 0 (% n m))))))
+          `(and integer (satisfies ,multiplep))))
+     t)))
+
+  (should
+   (functionp
+    (eval
+     '(cl-deftype multiples-of-2 ()
+        '(multiples-of 2))
+     t)))
+
+  (should
+   (functionp
+    (eval
+     '(cl-deftype multiples-of-3 ()
+        '(multiples-of 3))
+     t)))
+
+  (should
+   (functionp
+    (eval
+     '(cl-deftype multiples-of-4 ()
+        (declare (parents multiples-of-2))
+        '(and multiples-of-2 (multiples-of 4)))
+     t)))
+
+  ;; Test that (cl-types-of 4) is (multiples-of-4 multiples-of-2 ...)
+  ;; Test that (cl-types-of 6) is (multiples-of-3 multiples-of-2 ...)
+  ;; Test that (cl-types-of 12) is (multiples-of-4 multiples-of-3 multiples-of-2 ...)
+  (should
+   (equal
+    (cl-types-of 2)
+    '( multiples-of-2 fixnum integer number integer-or-marker
+       number-or-marker atom t)))
+
+  (should
+   (equal
+    (cl-types-of 4)
+    '( multiples-of-4 multiples-of-2 fixnum integer number
+       integer-or-marker number-or-marker atom t)
+    ))
+
+  (should
+   (equal
+    (cl-types-of 6)
+    '( multiples-of-3 multiples-of-2 fixnum integer number
+       integer-or-marker number-or-marker atom t)
+    ))
+
+  (should
+   (equal
+    (cl-types-of 12)
+    '( multiples-of-3 multiples-of-4 multiples-of-2 fixnum integer
+       number integer-or-marker number-or-marker atom t)
+    ))
+
+  (should
+   (equal
+    (cl-types-of 5)
+    '(fixnum integer number integer-or-marker number-or-marker atom t)
+    ))
+
+  ;; Cleanup
+  (mapc #'cl--type-undefine cl--type-list)
+
+  )
+
+(ert-deftest cl-types-test-2 ()
+  "Test types definition and dispatch."
+
+  (should
+   (functionp
+    (eval
+     '(cl-deftype unsigned-byte (&optional bits)
+        "Unsigned integer."
+        `(integer 0 ,(if (eq bits '*) bits (1- (ash 1 bits)))))
+     t)))
+
+  (should
+   (functionp
+    (eval
+     '(cl-deftype unsigned-16bits ()
+        "Unsigned 16-bits integer."
+        (declare (parents unsigned-byte))
+        '(unsigned-byte 16))
+     t)))
+
+  (should
+   (functionp
+    (eval
+     '(cl-deftype unsigned-8bits ()
+        "Unsigned 8-bits integer."
+        (declare (parents unsigned-16bits))
+        '(unsigned-byte 8))
+     t)))
+
+  ;; Invalid DAG error
+  (should-error
+   (eval
+    '(cl-deftype unsigned-16bits ()
+       "Unsigned 16-bits integer."
+       (declare (parents unsigned-8bits))
+       '(unsigned-byte 16))
+    t))
+
+  (eval
+   '(cl-defmethod my-foo ((_n unsigned-byte))
+      (format "unsigned"))
+   t)
+
+  (eval
+   '(cl-defmethod my-foo ((_n unsigned-16bits))
+      (format "unsigned 16bits - also %s"
+              (cl-call-next-method)))
+   t)
+
+  (eval
+   '(cl-defmethod my-foo ((_n unsigned-8bits))
+      (format "unsigned 8bits - also %s"
+              (cl-call-next-method)))
+   t)
+
+  (should
+   (equal
+    (my-foo 100)
+    "unsigned 8bits - also unsigned 16bits - also unsigned"
+    ))
+
+  (should
+   (equal
+    (my-foo 256)
+    "unsigned 16bits - also unsigned"
+    ))
+
+  (should
+   (equal
+    (my-foo most-positive-fixnum)
+    "unsigned"
+    ))
+  ;; Cleanup
+  (mapc #'cl--type-undefine cl--type-list)
+  )
+
 ;;; cl-extra-tests.el ends here

Message #86 received at 77725 <at> debbugs.gnu.org (full text, mbox):

From: David Ponce <da_vid <at> orange.fr>
To: Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: 77725 <at> debbugs.gnu.org, Eli Zaretskii <eliz <at> gnu.org>
Subject: Re: bug#77725: 31.0.50; Add support for types accepted by `cl-typep'
 to cl-generic?
Date: Wed, 23 Apr 2025 11:34:52 +0200

On 2025-04-22 23:34, Stefan Monnier wrote:
>>> Yes, as you've seen, the placement can be tricky.  There are bootstrap
>>> constraints as well as "general design" desires, and they all kind
>>> of pull in different directions.
>>> I'll take a closer look and come back with a proposal.
>> Great. Thank you!
> 
> Sorry for the delay, here's what I came up with.

No problem, we're in no rush and certainly have plenty of other things
to do in our life.  Thank you very much for taking time to work on
this!

> I added a FIXME about the recursion-breaker which I have a feeling might
> not work.

I read your FIXME:

+  ;; FIXME: Does this even work?  Won't `cl--type-object' be rebound to
+  ;; the other object before we get here?  IOW wouldn't we need a list
+  ;; of objects that are in the process of being checked?  And while
+  ;; returning nil breaks the recursion, won't it return a bogus result?

However, I don't understand why you think this might not work.  I don't
see how `cl--type-object' can be rebound while `cl-types-of' is
running?  Recursion can only occur when calling `cl-typep' to check the
type of `cl--type-object', and `cl-types-of' will immediately return
nil in that case.  Did I miss something?

Regarding the bogus result, I chose to ignore types that will never
match, resulting in infinite recursion of `cl-types-of'.  It's not
possible to signal an error here, as that would block subsequent types
that have no problem.  Perhaps a warning message is missing when
recursion is detected on a type?  It would probably be much better to
detect recursions during type definition and report an error at that
point.  But I suspect that would be a lot of work.

Here is a test case with a recursion:

(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)))))

(cl-deftype T2 ()
  "Recursive on checking for T1, never match."
  (declare (parents T1))
  `(and T1 (satisfies ,(lambda (o) (equal o '(T2))))))

(defgtype T3 ()
  "Not recursive on T1."
  (declare (parents T1))
  `(satisfies ,(lambda (o) (equal o '(T3)))))

;; T2 will never match, because `cl-types-of' enters in an endless recursion
(cl-typep (list 'T2) 'T1)
=> nil

(cl-types-of (list 'T2))
=> (cons list sequence t)

;; T3 will match.
(cl-typep (list 'T3) 'T1)
=> (T1 cons list sequence t)

(cl-types-of (list 'T3))
=> (T3 T1 cons list sequence t)

> 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'?

> - They use `eval` too much.

This is because `cl-deftype' is a macro and the doc string of
`ert-deftest' suggests to wrap macros in `(eval (quote ...))' to test
them.

But I must admit that my knowledge of ERT is very limited.  Any
suggestions for improving the tests would be welcome.

David

Message #89 received at 77725 <at> debbugs.gnu.org (full text, mbox):

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

[Message part 1 (text/plain, inline)]

While working with cl-types.el I discovered a nasty side effect
of byte compilation on the cl--type-list.

I can't explain what is going on :-(

Here is a recipe:

- run emacs -Q

- load cl-type.el (the last version previously attached)

- load cl-type-recipe.el (attached)

- In the scratch buffer eval cl--type-list.  Result is expected:

  (cons-cdr-foo cons-car-foo)

- Then open cl-type-recipe.el and byte-compile it with
  M-x emacs-lisp-byte-compile

- Then eval again cl--type-list in the scratch buffer, and now the
  result is something like this:

  (#<symbol cons-cdr-foo at 158> #<symbol cons-car-foo at 46>)

  Which completely breaks cl-types !

I hope you can shed some light on what is going on here.

Thanks!

[cl-type-recipe.el (text/x-emacs-lisp, attachment)]

Message #92 received at 77725 <at> debbugs.gnu.org (full text, mbox):

From: David Ponce <da_vid <at> orange.fr>
To: Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: 77725 <at> debbugs.gnu.org, Eli Zaretskii <eliz <at> gnu.org>
Subject: Re: bug#77725: 31.0.50; Add support for types accepted by `cl-typep'
 to cl-generic?
Date: Thu, 24 Apr 2025 13:44:09 +0200

[Message part 1 (text/plain, inline)]

On 2025-04-23 14:59, David Ponce wrote:
> 
> While working with cl-types.el I discovered a nasty side effect
> of byte compilation on the cl--type-list.
> 
> I can't explain what is going on :-(
> 
> Here is a recipe:
> 
> - run emacs -Q
> 
> - load cl-type.el (the last version previously attached)
> 
> - load cl-type-recipe.el (attached)
> 
> - In the scratch buffer eval cl--type-list.  Result is expected:
> 
>    (cons-cdr-foo cons-car-foo)
> 
> - Then open cl-type-recipe.el and byte-compile it with
>    M-x emacs-lisp-byte-compile
> 
> - Then eval again cl--type-list in the scratch buffer, and now the
>    result is something like this:
> 
>    (#<symbol cons-cdr-foo at 158> #<symbol cons-car-foo at 46>)
> 
>    Which completely breaks cl-types !
> 
> I hope you can shed some light on what is going on here.
> 
> Thanks!
> 

It seems the side effect is more general than just with cl-type.el.

I attached cl-type-recipe2.el, another simple recipe to illustrate with
current `cl-deftype'.

- Run emacs -Q and load cl-type-recipe2.el.
- Then in the scratch buffer eval:

(symbol-plist 'cons-car-foo)
=> (cl-deftype-handler #[nil ((list 'satisfies #'(lambda (x) (eq (car-safe x) 'foo)))) (t) nil "A cons with a `foo' car."])

- Then open cl-type-recipe2.el and M-x emacs-lisp-byte-compile

- Then in the scratch buffer eval again:

(symbol-plist 'cons-car-foo)
=> (cl-deftype-handler #[nil (`(#<symbol satisfies at 113> ,(#<symbol lambda at 125> (x) (#<symbol eq at 137> (#<symbol car-safe at 141> #<symbol x at 150>) '#<symbol foo at 154>)))) (t) nil "A cons with a `foo' car."])

And, of course:

(cl-typep '(foo) 'cons-car-foo)
=> (invalid-function #<symbol lambda at 125>)

Without compile in the `cl-eval-when' in `cl-deftype', there is no side effect.

Hope it will help.

David

[cl-type-recipe2.el (text/x-emacs-lisp, attachment)]

Message #95 received at 77725 <at> debbugs.gnu.org (full text, mbox):

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

On 2025-04-24 13:44, David Ponce wrote:
> On 2025-04-23 14:59, David Ponce wrote:
>>
>> While working with cl-types.el I discovered a nasty side effect
>> of byte compilation on the cl--type-list.
>>
>> I can't explain what is going on :-(
>>
>> Here is a recipe:
>>
>> - run emacs -Q
>>
>> - load cl-type.el (the last version previously attached)
>>
>> - load cl-type-recipe.el (attached)
>>
>> - In the scratch buffer eval cl--type-list.  Result is expected:
>>
>>    (cons-cdr-foo cons-car-foo)
>>
>> - Then open cl-type-recipe.el and byte-compile it with
>>    M-x emacs-lisp-byte-compile
>>
>> - Then eval again cl--type-list in the scratch buffer, and now the
>>    result is something like this:
>>
>>    (#<symbol cons-cdr-foo at 158> #<symbol cons-car-foo at 46>)
>>
>>    Which completely breaks cl-types !
>>
>> I hope you can shed some light on what is going on here.
>>
>> Thanks!
>>
> 
> It seems the side effect is more general than just with cl-type.el.
> 
> I attached cl-type-recipe2.el, another simple recipe to illustrate with
> current `cl-deftype'.
> 
> - Run emacs -Q and load cl-type-recipe2.el.
> - Then in the scratch buffer eval:
> 
> (symbol-plist 'cons-car-foo)
> => (cl-deftype-handler #[nil ((list 'satisfies #'(lambda (x) (eq (car-safe x) 'foo)))) (t) nil "A cons with a `foo' car."])
> 
> - Then open cl-type-recipe2.el and M-x emacs-lisp-byte-compile
> 
> - Then in the scratch buffer eval again:
> 
> (symbol-plist 'cons-car-foo)
> => (cl-deftype-handler #[nil (`(#<symbol satisfies at 113> ,(#<symbol lambda at 125> (x) (#<symbol eq at 137> (#<symbol car-safe at 141> #<symbol x at 150>) '#<symbol foo at 154>)))) (t) nil "A cons with a `foo' car."])
> 
> And, of course:
> 
> (cl-typep '(foo) 'cons-car-foo)
> => (invalid-function #<symbol lambda at 125>)
> 
> Without compile in the `cl-eval-when' in `cl-deftype', there is no side effect.
> 
> Hope it will help.
> 
> David

Another information which could be useful: if I replace (cl-eval-when (compile load eval) ...)
by (eval-and-compile ...) in the definition of `cl-deftype', there is no side effect
of the byte-compilation on the current definition.

What I don't know is if the two forms are equivalent.

Message #98 received at 77725 <at> debbugs.gnu.org (full text, mbox):

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: Re: bug#77725: 31.0.50; Add support for types accepted by
 `cl-typep' to cl-generic?
Date: Thu, 24 Apr 2025 15:38:40 -0400

> Here is a test case with a recursion:
>
> (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?

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.

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

> (cl-deftype T2 ()
>   "Recursive on checking for T1, never match."
>   (declare (parents T1))
>   `(and T1 (satisfies ,(lambda (o) (equal o '(T2))))))

Is this definition meaningful with the above definition of T1?
I don't think it's well-founded.

> (defgtype T3 ()
>   "Not recursive on T1."
>   (declare (parents T1))
>   `(satisfies ,(lambda (o) (equal o '(T3)))))
>
> ;; 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.

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

>> - They use `eval` too much.
> This is because `cl-deftype' is a macro and the doc string of
> `ert-deftest' suggests to wrap macros in `(eval (quote ...))' to test
> them.

That's only when you specifically need to test the effect of the
macro-expansion itself, rather than test the result of running the
macro-expanded code.  It's rarely needed IME.  An example would be to
detect when a macro-expansion emits a warning.

Also, by using this `eval+quote` you can't test the macro in the way
it's usually used (where it's macro-expanded once during compilation and
then its result is run in another Emacs session) so you may miss bugs
such as when the macro's expansion performs a side-effect (like add
something to a list) which the expanded code expects to have happened
(but this will have happened during compilation, so the element may not
be in the list any more when the code is finally executed).

IOW, I disagree with the docstring.  🙁


        Stefan

Message #101 received at 77725 <at> debbugs.gnu.org (full text, mbox):

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: Re: bug#77725: 31.0.50; Add support for types accepted by
 `cl-typep' to cl-generic?
Date: Thu, 24 Apr 2025 15:44:38 -0400

> Another information which could be useful: if I replace (cl-eval-when
> (compile load eval) ...)  by (eval-and-compile ...) in the definition
> of `cl-deftype', there is no side effect of the byte-compilation on
> the current definition.

It looks like this is a bug in `cl-eval-when` introduced when Alan added
"symbol with positions" for better error reporting.

Could you make it a separate bug-report?

> What I don't know is if the two forms are equivalent.

Obviously they don't do quite the same thing, but AFAIK they *should*
behave the same, so I'd use `eval-and-compile`.


        Stefan

Message #104 received at 77725 <at> debbugs.gnu.org (full text, mbox):

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

On 2025-04-24 21:38, Stefan Monnier wrote:
>> Here is a test case with a recursion:
>>
>> (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."

> 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
subtype defined.  This is why I call T1 an "abstract" type.  And as such
it is normal that no object will belong to it directly.  For an object to
belong to T1 it must first belong to one of its "concrete" subtype (with a
builtin Emacs type in parents).  And in this case it is guaranteed that
subtypes will appear before T1 in the list of defined types to check.
So, no recursion on T1 when subtypes exist.

Did I miss something?

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

However, in the last case, cl-types-of is entered 95 times!

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?

> 
>> (cl-deftype T2 ()
>>    "Recursive on checking for T1, never match."
>>    (declare (parents T1))
>>    `(and T1 (satisfies ,(lambda (o) (equal o '(T2))))))
> 
> Is this definition meaningful with the above definition of T1?
> I don't think it's well-founded.

Correct.  It was just a "bad" example.  The correct definition is T3.

>> (defgtype T3 ()
>>    "Not recursive on T1."
>>    (declare (parents T1))
>>    `(satisfies ,(lambda (o) (equal o '(T3)))))
>>
>> ;; 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?

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

> 
>>> - They use `eval` too much.
>> This is because `cl-deftype' is a macro and the doc string of
>> `ert-deftest' suggests to wrap macros in `(eval (quote ...))' to test
>> them.
> 
> That's only when you specifically need to test the effect of the
> macro-expansion itself, rather than test the result of running the
> macro-expanded code.  It's rarely needed IME.  An example would be to
> detect when a macro-expansion emits a warning.
> 
> Also, by using this `eval+quote` you can't test the macro in the way
> it's usually used (where it's macro-expanded once during compilation and
> then its result is run in another Emacs session) so you may miss bugs
> such as when the macro's expansion performs a side-effect (like add
> something to a list) which the expanded code expects to have happened
> (but this will have happened during compilation, so the element may not
> be in the list any more when the code is finally executed).
> 
> IOW, I disagree with the docstring.  🙁

I understand.

Thanks

Message #107 received at 77725 <at> debbugs.gnu.org (full text, mbox):

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

On 2025-04-24 21:44, Stefan Monnier wrote:
>> Another information which could be useful: if I replace (cl-eval-when
>> (compile load eval) ...)  by (eval-and-compile ...) in the definition
>> of `cl-deftype', there is no side effect of the byte-compilation on
>> the current definition.
> 
> It looks like this is a bug in `cl-eval-when` introduced when Alan added
> "symbol with positions" for better error reporting.
> 
> Could you make it a separate bug-report?

Done. Bug#78056

> 
>> What I don't know is if the two forms are equivalent.
> 
> Obviously they don't do quite the same thing, but AFAIK they *should*
> behave the same, so I'd use `eval-and-compile`.
>

Ok, done.

Thank you!

Message #110 received at 77725 <at> debbugs.gnu.org (full text, mbox):

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: Re: 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

Message #113 received at 77725 <at> debbugs.gnu.org (full text, mbox):

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: Re: bug#77725: 31.0.50; Add support for types accepted by
 `cl-typep' to cl-generic?
Date: Fri, 25 Apr 2025 15:37:38 -0400

[ Just tooting my horn, nothing to see.  ]

>> Here is a test case with a recursion:
>>
>> (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?

BTW, this form of circularity is called an *impredicative* definition:
the above definition does not directly refer to T1 (as in the case of
a recursive definition), instead it refers (via the definition of
`gtypes-of`) to the set of all types, to which T1 happens to belong.

As it happens, the notion of *type* was invented/introduced by Bertrand
Russel (early 20th century) specifically in order to try and disallow
the kind of paradoxes (like Russel's paradox or the paradox of the
barber) that impredicativity makes possible.

OK, you can go back to your regularly scheduled ELisp hacking now,


        Stefan

Message #116 received at 77725 <at> debbugs.gnu.org (full text, mbox):

From: David Ponce <da_vid <at> orange.fr>
To: Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: 77725 <at> debbugs.gnu.org, Eli Zaretskii <eliz <at> gnu.org>
Subject: Re: bug#77725: 31.0.50; Add support for types accepted by `cl-typep'
 to cl-generic?
Date: Sat, 26 Apr 2025 11:47:52 +0200

[Message part 1 (text/plain, inline)]

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

[cl-types-tests.el (text/x-emacs-lisp, attachment)]

[cl-types.el (text/x-emacs-lisp, attachment)]

Message #119 received at 77725 <at> debbugs.gnu.org (full text, mbox):

From: David Ponce <da_vid <at> orange.fr>
To: Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: 77725 <at> debbugs.gnu.org, Eli Zaretskii <eliz <at> gnu.org>
Subject: Re: bug#77725: 31.0.50; Add support for types accepted by `cl-typep'
 to cl-generic?
Date: Sat, 26 Apr 2025 11:50:31 +0200

On 2025-04-25 21:37, Stefan Monnier wrote:
> [ Just tooting my horn, nothing to see.  ]
> 
>>> Here is a test case with a recursion:
>>>
>>> (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?
> 
> BTW, this form of circularity is called an *impredicative* definition:
> the above definition does not directly refer to T1 (as in the case of
> a recursive definition), instead it refers (via the definition of
> `gtypes-of`) to the set of all types, to which T1 happens to belong.
> 
> As it happens, the notion of *type* was invented/introduced by Bertrand
> Russel (early 20th century) specifically in order to try and disallow
> the kind of paradoxes (like Russel's paradox or the paradox of the
> barber) that impredicativity makes possible.
> 
> OK, you can go back to your regularly scheduled ELisp hacking now,

Thank you!  I always appreciate enriching my knowledge :-)

Message #122 received at 77725 <at> debbugs.gnu.org (full text, mbox):

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: Re: bug#77725: 31.0.50; Add support for types accepted by
 `cl-typep' to cl-generic?
Date: Sun, 27 Apr 2025 01:54:55 -0400

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

You could approximate it with `after-load-functions`.  Or, with the
proposed patch, you could use an advice on `cl--type-deftype`.  Once you
do that, you won't need to break circularity in `cl-types-of`.

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

Maybe more generally we could/should provide "fast" (i.e. cached)
versions of `cl--class-allparents` and `cl--class-children`.
[ And remove those `--`.  ]

>>> 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 this is bug in the definition of the type.

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

You could also take the position that we shouldn't catch those errors
and instead put pressure to fix those broken `cl-deftype` definitions.

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

I think it would look something like:

    (defvar cl--type-pending nil)

    (defun cl--typep (o type)
      ;; Like `cl-typep` but with recursion-check.
      (let ((entry (cons o type)))
        ;; Note: `member` is not quite right.
        (if (member entry cl--type-pending)
            ;; We're called recursively while in the process of testing
            ;; if `o` is of type `type`, so presume it's true for now,
            ;; rather than inf-loop.
            t
          (let ((cl--type-pending (cons  cl--type-pending)))
            (cl-typep o type)))))

    (defun cl-types-of (o)
      (let ((types ()))
        (dolist (type ...alltypes...)
          (when (cl--typep o type)
            (push type types))))))
        ...types...))

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

If the type is "trivially circular", yes.  Otherwise, not necessarily.

E.g.

    (cl-deftype is-cons (t1 t2)
      `(and cons (satisfies
                  ,(lambda (x)
                     (and (cl--typep (car x) t1) (cl--typep (car x) t2))))))

    (cl-deftype list-of-int ()
      `(is-cons integer (or null list-of-int)))

and then

    (let ((x (list 1 2 3 4 5)))
      (setcdr (last x) x)
      (cl--typep x 'list-of-int))

would terminate and return t but

    (let ((x (list "1" "2" "3" "4" "5")))
      (setcdr (last x) x)
      (cl--typep x 'list-of-int))

would return nil.

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

Looks good, thanks.

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

It would be good to check that the split I proposed works correctly, tho.
The main issues are likely to be around whether things are autoloaded
when they to.


        Stefan

Message #125 received at 77725 <at> debbugs.gnu.org (full text, mbox):

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: Re: bug#77725: 31.0.50; Add support for types accepted by
 `cl-typep' to cl-generic?
Date: Sun, 27 Apr 2025 08:59:24 -0400

>> Exactly, I fully agree, the question is "how to keep track of the
>> children"?
>
> You could approximate it with `after-load-functions`.  Or, with the
> proposed patch, you could use an advice on `cl--type-deftype`.  Once you
> do that, you won't need to break circularity in `cl-types-of`.

I think what I was trying to say all along is:
the circularity you're trying to break doesn't come from `cl-deftype` or
`cl-types-of` but from your impredicative definition of `T1`.
So it'd be best to fix it there:

    (cl-deftype T1 ()
      `(satisfies ,(lambda (o) (memq 'T1 (cl-types-of o)))))

=>

    (defvar my-pending-T1-check (make-symbol "void"))

    (cl-deftype T1 ()
      `(satisfies
        ,(lambda (o)
           (and (not (eq o my-pending-T1-check))
                (let ((my-pending-T1-check o))
                  (memq 'T1 (cl-types-of o)))))))


- Stefan

Message #128 received at 77725 <at> debbugs.gnu.org (full text, mbox):

From: David Ponce <da_vid <at> orange.fr>
To: Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: 77725 <at> debbugs.gnu.org, Eli Zaretskii <eliz <at> gnu.org>
Subject: Re: bug#77725: 31.0.50; Add support for types accepted by `cl-typep'
 to cl-generic?
Date: Sun, 27 Apr 2025 17:31:39 +0200

On 2025-04-27 14:59, Stefan Monnier wrote:
>>> Exactly, I fully agree, the question is "how to keep track of the
>>> children"?
>>
>> You could approximate it with `after-load-functions`.  Or, with the
>> proposed patch, you could use an advice on `cl--type-deftype`.  Once you
>> do that, you won't need to break circularity in `cl-types-of`.
> 
> I think what I was trying to say all along is:
> the circularity you're trying to break doesn't come from `cl-deftype` or
> `cl-types-of` but from your impredicative definition of `T1`.
> So it'd be best to fix it there:
> 
>      (cl-deftype T1 ()
>        `(satisfies ,(lambda (o) (memq 'T1 (cl-types-of o)))))
> 
> =>
> 
>      (defvar my-pending-T1-check (make-symbol "void"))
> 
>      (cl-deftype T1 ()
>        `(satisfies
>          ,(lambda (o)
>             (and (not (eq o my-pending-T1-check))
>                  (let ((my-pending-T1-check o))
>                    (memq 'T1 (cl-types-of o)))))))
> 

Hi Stefan,

I quite like this approach, where it's not `cl-types-of', but each type
that bears responsibility for its implementation.

So, if I understand correctly, your recommendation is to not try to solve
recursion (or other) problems in `cl-types-of' at all, but rather at the
level of each type's definition, and to let ill-defined types possibly
cause errors?

The only point that still bothers me is not protecting `cl-types-of' from
errors due to ill-defined types.  This is particularly true because this
can impact the entire Emacs session if certain methods are prevented from
working, such as those involved in the display process (I use such methods
based on `cl-deftype' for example, in my own alternative implementation of
icons and tab-line).

If you agree I will update cl-types.el accordingly and dispatch it in
the existing libraries according to your previous proposal... to see what
happens ;-)

Thanks again for being so helpful!

David

Message #131 received at 77725 <at> debbugs.gnu.org (full text, mbox):

From: David Ponce <da_vid <at> orange.fr>
To: Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: 77725 <at> debbugs.gnu.org, Eli Zaretskii <eliz <at> gnu.org>
Subject: Re: bug#77725: 31.0.50; Add support for types accepted by `cl-typep'
 to cl-generic?
Date: Mon, 28 Apr 2025 12:56:35 +0200

[Message part 1 (text/plain, inline)]

On 2025-04-27 17:31, David Ponce wrote:
> On 2025-04-27 14:59, Stefan Monnier wrote:
>>>> Exactly, I fully agree, the question is "how to keep track of the
>>>> children"?
>>>
>>> You could approximate it with `after-load-functions`.  Or, with the
>>> proposed patch, you could use an advice on `cl--type-deftype`.  Once you
>>> do that, you won't need to break circularity in `cl-types-of`.
>>
>> I think what I was trying to say all along is:
>> the circularity you're trying to break doesn't come from `cl-deftype` or
>> `cl-types-of` but from your impredicative definition of `T1`.
>> So it'd be best to fix it there:
>>
>>      (cl-deftype T1 ()
>>        `(satisfies ,(lambda (o) (memq 'T1 (cl-types-of o)))))
>>
>> =>
>>
>>      (defvar my-pending-T1-check (make-symbol "void"))
>>
>>      (cl-deftype T1 ()
>>        `(satisfies
>>          ,(lambda (o)
>>             (and (not (eq o my-pending-T1-check))
>>                  (let ((my-pending-T1-check o))
>>                    (memq 'T1 (cl-types-of o)))))))
>>
> 
> Hi Stefan,
> 
> I quite like this approach, where it's not `cl-types-of', but each type
> that bears responsibility for its implementation.
> 
> So, if I understand correctly, your recommendation is to not try to solve
> recursion (or other) problems in `cl-types-of' at all, but rather at the
> level of each type's definition, and to let ill-defined types possibly
> cause errors?
> 
> The only point that still bothers me is not protecting `cl-types-of' from
> errors due to ill-defined types.  This is particularly true because this
> can impact the entire Emacs session if certain methods are prevented from
> working, such as those involved in the display process (I use such methods
> based on `cl-deftype' for example, in my own alternative implementation of
> icons and tab-line).
> 
> If you agree I will update cl-types.el accordingly and dispatch it in
> the existing libraries according to your previous proposal... to see what
> happens ;-)
> 
> Thanks again for being so helpful!
> 
> David

Please find attached a new version of cl-types.el, where any attempt to work
around type definition errors with `cl-types-of' has been removed.  If such
an error occurs, it is now clearly signaled by `warn', and the affected type
is marked as "in error" and ignored until its next redefinition or deletion.

WDYT?

[cl-types.el (text/x-emacs-lisp, attachment)]

Message #134 received at 77725 <at> debbugs.gnu.org (full text, mbox):

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: Re: bug#77725: 31.0.50; Add support for types accepted by
 `cl-typep' to cl-generic?
Date: Mon, 28 Apr 2025 17:44:49 -0400

[Message part 1 (text/plain, inline)]

> I quite like this approach, where it's not `cl-types-of', but each type
> that bears responsibility for its implementation.

Usually, I like to solve a problem centrally so it's done once and for
all, but here the problem is that breaking recursion is tricky business
which may need to be done in different ways in different cases, and on
top of that it's a fairly rare need, so I think in this case dumping the
responsibility onto those rare users of circularity in types is the
right tradeoff.

> So, if I understand correctly, your recommendation is to not try to solve
> recursion (or other) problems in `cl-types-of' at all, but rather at the
> level of each type's definition, and to let ill-defined types possibly
> cause errors?

Basically, yes.

> The only point that still bothers me is not protecting `cl-types-of' from
> errors due to ill-defined types.  This is particularly true because this
> can impact the entire Emacs session if certain methods are prevented from
> working, such as those involved in the display process (I use such methods
> based on `cl-deftype' for example, in my own alternative implementation of
> icons and tab-line).

Fair enough.

I pushed your new code to the `scratch/cl-types` branch in `emacs.git`.
I haven't integrated it into the other CL-Lib files yet.
See patch below for comments on your code.


        Stefan

[cl-types.patch (text/x-diff, inline)]

diff --git a/lisp/emacs-lisp/cl-types.el b/lisp/emacs-lisp/cl-types.el
index 0a384e09d79..830acb1ff0c 100644
--- a/lisp/emacs-lisp/cl-types.el
+++ b/lisp/emacs-lisp/cl-types.el
@@ -46,12 +46,13 @@ cl--type-p
 That is, a type of class `cl-type-class'."
   (and (symbolp object) (cl-type-class-p (cl--find-class object))))
 
-(defmacro cl--type-parents (name)
+(defmacro cl--type-parents (name) ;FIXME: Make it a `defun' or `defsubst'!
   "Get parents of type with NAME.
 NAME is a symbol representing a type."
   `(cl--class-allparents (cl--find-class ,name)))
 
 (defun cl--type-children (name)
+  ;; FIXME: Isn't that he same as `cl--class-children'?
   "Get children of the type with NAME.
 NAME is a symbol representing a type.
 Return a possibly empty list of types."
@@ -82,6 +83,7 @@ cl--type-undefine
   (setq cl--type-list (delq name cl--type-list)))
 
 (defun cl--type-deftype (name parents &optional docstring)
+  ;; FIXME: Should we also receive the arglist?
   "Generalize type with NAME for method dispatching.
 PARENTS is a list of types NAME is a subtype of, or nil.
 DOCSTRING is an optional documentation string."
@@ -95,8 +97,13 @@ cl--type-deftype
                   (error "Type generalized, but doesn't exist"))
             (or recorded (error "Type exists, but not generalized"))
             (or (cl-type-class-p class)
+                ;; FIXME: We have some uses `cl-deftype' in Emacs that
+                ;; "complement" another declaration of the same type, so
+                ;; maybe we should turn this into a warning (and not overwrite
+                ;; the `cl--find-class' in that case)?
                 (error "Type in another class: %S" (type-of class))))
           (if (memq name parents)
+              ;; FIXME: This test should be performed in the macro not here.
               (error "Type in parents: %S" parents))
           ;; Setup a type descriptor for NAME.
           (setf (cl--find-class name)
@@ -110,12 +117,21 @@ cl--type-deftype
           ;; all those an object belongs to, sorted from the most
           ;; specific type to the more general type.  So, keep the
           ;; global list in this order.
+          ;; FIXME: This global operation is a bit worrisome, because it
+          ;; scales poorly with the number of types.  I guess it's OK
+          ;; for now because `cl-deftype' is not very popular, but it'll
+          ;; probably need to be replaced at some point.  Maybe we
+          ;; should simply require that the parents be defined already,
+          ;; then we can just `push' the new type, knowing it's in
+          ;; topological order by construction.
           (setq cl--type-list
                 (merge-ordered-lists
                  (cl--type-dag)
                  (lambda (_) (error "Invalid dependency graph")))))
       (error
        ;; On error restore previous data.
+       ;; FIXME: `cl--type-list' has not been changed yet at this point, AFAIK,
+       ;; so restoring with `oldtlist' is always redundant.
        (setq cl--type-list oldtlist)
        (setf (symbol-plist name) oldplist)
        (error (format "Define %S failed: %s"
@@ -155,16 +171,27 @@ cl-deftype2
       ((`(,decls . ,forms) (macroexp-parse-body body))
        (docstring (if (stringp (car decls))
                       (car decls)
-                    (cadr (assq :documentation decls))))
-       (parents (cdr (assq 'parents (cdr (assq 'declare decls))))))
+                      (cadr (assq :documentation decls))))
+       (declares (assq 'declare decls))
+       (parent-decl (assq 'parents (cdr declares)))
+       (parents (cdr parent-decl)))
+    (when parent-decl
+      ;; "Consume" the `parents' declaration.
+      (cl-callf (lambda (x) (delq parent-decl x)) (cdr declares))
+      (when (equal declares '(declare))
+        (cl-callf (lambda (x) (delq declares x)) decls)))
     (and parents arglist
          (error "Parents specified, but arglist not empty"))
-    (if docstring (setq forms (cons docstring forms)))
     `(eval-and-compile ;;cl-eval-when (compile load eval)
+       ;; FIXME: Where should `cl--type-deftype' go?  Currently, code
+       ;; using `cl-deftype' can use (eval-when-compile (require 'cl-lib)),
+       ;; so `cl--type-deftype' needs to go either to `cl-preloaded.el'
+       ;; or it should be autoloaded even when `cl-lib' is not loaded.
        (cl--type-deftype ',name ',parents ,docstring)
        (define-symbol-prop ',name 'cl-deftype-handler
                            (cl-function
                             (lambda (&cl-defs ('*) ,@arglist)
+                              ,@decls
                               ,@forms))))))
 
 ;; Ensure each type satisfies `eql'.
@@ -226,6 +253,9 @@ cl-types-of
   "Return the types OBJECT belongs to.
 Return an unique list of types OBJECT belongs to, ordered from the
 most specific type to the most general."
+  ;; FIXME: The current implementation of `cl--type-parents' is
+  ;; moderately expensive, so we should probably avoid calling it
+  ;; before we do the `gethash'.
   (let ((found (list (cl--type-parents (cl-type-of object)))))
     ;; Build a DAG of all types OBJECT belongs to.
     (dolist (type cl--type-list)
@@ -242,6 +272,9 @@ cl-types-of
        ;; will be faster than `cl-typep'.
        (null (assq type found))
        ;; If OBJECT is of type, add type and its parents to the DAG.
+       ;; FIXME: This `condition-case' will make it harder to get a backtrace
+       ;; to debug the error in the type definition.  So maybe
+       ;; use `condition-case-unless-debug'.
        (condition-case e
            (cl-typep object type)
          (error (cl--type-error type e)))
@@ -254,11 +287,10 @@ cl-types-of
            (push pl found)
            (setq pl (cdr pl))))))
     ;; Compute an ordered list of types from the collected DAG.
-    (setq found (merge-ordered-lists found))
     ;; Return an unique value of this list of types, which is also the
     ;; list of specifiers for this type.
     (with-memoization (gethash found cl--type-unique)
-      found)))
+      (merge-ordered-lists found))))
 
 ;;; Method dispatching
 ;;

Message #137 received at 77725 <at> debbugs.gnu.org (full text, mbox):

From: David Ponce <da_vid <at> orange.fr>
To: Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: 77725 <at> debbugs.gnu.org, Eli Zaretskii <eliz <at> gnu.org>
Subject: Re: bug#77725: 31.0.50; Add support for types accepted by `cl-typep'
 to cl-generic?
Date: Tue, 29 Apr 2025 12:50:27 +0200

[Message part 1 (text/plain, inline)]

On 2025-04-28 23:44, Stefan Monnier wrote:

[...]
> I pushed your new code to the `scratch/cl-types` branch in `emacs.git`.
> I haven't integrated it into the other CL-Lib files yet.
> See patch below for comments on your code.

Merci!

Please find attached a new version of cl-types.el with some updates
following your comments.

Regarding this FIXME, in `cl--type-deftype', about the global setting
of `cl--type-list':

;; FIXME: This global operation is a bit worrisome, because it
;; scales poorly with the number of types.  I guess it's OK
;; for now because `cl-deftype' is not very popular, but it'll
;; probably need to be replaced at some point.  Maybe we
;; should simply require that the parents be defined already,
;; then we can just `push' the new type, knowing it's in
;; topological order by construction.

It's not clear to me how "simply require that the parents be defined
already", makes the new type "in topological order by construction".
Also, as all this is done only at type (re)definition, which should
not happen so often, I am curious to know why you think "this global
operation is a bit worrisome"?

In `cl-types-of', I liked your idea to avoid calls to
`cl--type-parents' and `merge-ordered-list' before we do the
`gethash'.  I've gone a bit further in this direction (hopefully not
too far!) by doing all the type list computation just before creating
a new entry in the hash table. There's a slight overhead to determine
the types of objects not yet processed, but determining the types of
similar objects should be faster, which should be the most common case
(or at least the one to favor) when using types to dispatch methods.

WDYT?

Thanks!
David

[cl-types.el (text/x-emacs-lisp, attachment)]

Message #140 received at 77725 <at> debbugs.gnu.org (full text, mbox):

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: Re: bug#77725: 31.0.50; Add support for types accepted by
 `cl-typep' to cl-generic?
Date: Tue, 29 Apr 2025 10:49:13 -0400

> ;; FIXME: This global operation is a bit worrisome, because it
> ;; scales poorly with the number of types.  I guess it's OK
> ;; for now because `cl-deftype' is not very popular, but it'll
> ;; probably need to be replaced at some point.  Maybe we
> ;; should simply require that the parents be defined already,
> ;; then we can just `push' the new type, knowing it's in
> ;; topological order by construction.
>
> It's not clear to me how "simply require that the parents be defined
> already", makes the new type "in topological order by construction".

If they're already defined, it means they're already in the list, so if
you add the new type at the head of the list you know this "child" comes
before all its parents in the list.  If the list is constructed only by
making such additions where we make sure the parents are already there,
then the property is valid over the whole list.

Note, there's no magic: we should push the responsibility of topological
sorting onto the programmers (who now have to define their types in
topological order).

> Also, as all this is done only at type (re)definition, which should
> not happen so often, I am curious to know why you think "this global
> operation is a bit worrisome"?

The algorithmic complexity of merge-ordered-list is O(N²), in the number
of types IIRC, so while it may seem fine with 10 types, it could take
more than a minute given enough type declarations.

> In `cl-types-of', I liked your idea to avoid calls to
> `cl--type-parents' and `merge-ordered-list' before we do the
> `gethash'.  I've gone a bit further in this direction (hopefully not
> too far!) by doing all the type list computation just before creating
> a new entry in the hash table. There's a slight overhead to determine
> the types of objects not yet processed, but determining the types of
> similar objects should be faster, which should be the most common case
> (or at least the one to favor) when using types to dispatch methods.

+1

I notice that the `(null (assq type found))` is now ineffective, tho.
Maybe it's OK and we should just remove it.

> WDYT

Why all the `defsubst`?  Have you measured a noticeable speed difference
by using them?  I have a hard time seeing how that could happen.
All 3 `defsubst` in your patch are for function which contain
a non-trivial loop, so I'd expect the overhead of a function call to be
negligible.


        Stefan

Message #143 received at 77725 <at> debbugs.gnu.org (full text, mbox):

From: David Ponce <da_vid <at> orange.fr>
To: Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: 77725 <at> debbugs.gnu.org, Eli Zaretskii <eliz <at> gnu.org>
Subject: Re: bug#77725: 31.0.50; Add support for types accepted by `cl-typep'
 to cl-generic?
Date: Tue, 29 Apr 2025 17:49:51 +0200

On 2025-04-29 16:49, Stefan Monnier wrote:
>> ;; FIXME: This global operation is a bit worrisome, because it
>> ;; scales poorly with the number of types.  I guess it's OK
>> ;; for now because `cl-deftype' is not very popular, but it'll
>> ;; probably need to be replaced at some point.  Maybe we
>> ;; should simply require that the parents be defined already,
>> ;; then we can just `push' the new type, knowing it's in
>> ;; topological order by construction.
>>
>> It's not clear to me how "simply require that the parents be defined
>> already", makes the new type "in topological order by construction".
> 
> If they're already defined, it means they're already in the list, so if
> you add the new type at the head of the list you know this "child" comes
> before all its parents in the list.  If the list is constructed only by
> making such additions where we make sure the parents are already there,
> then the property is valid over the whole list.
> 
> Note, there's no magic: we should push the responsibility of topological
> sorting onto the programmers (who now have to define their types in
> topological order).

Of course, it makes much sense.  If I am not wrong, the constructor of the
class `cl-type-class' already ensures that parent types must be defined
before their "child" types (i.e. already added to the `cl--type-list' for
types defined with `cl-deftype").  So it should work to simply push a new
type at the beginning of the list.  And, when a type is redefined, move it
at the beginning of the list?

>> Also, as all this is done only at type (re)definition, which should
>> not happen so often, I am curious to know why you think "this global
>> operation is a bit worrisome"?
> 
> The algorithmic complexity of merge-ordered-list is O(N²), in the number
> of types IIRC, so while it may seem fine with 10 types, it could take
> more than a minute given enough type declarations.

I understand now, thanks!

> 
>> In `cl-types-of', I liked your idea to avoid calls to
>> `cl--type-parents' and `merge-ordered-list' before we do the
>> `gethash'.  I've gone a bit further in this direction (hopefully not
>> too far!) by doing all the type list computation just before creating
>> a new entry in the hash table. There's a slight overhead to determine
>> the types of objects not yet processed, but determining the types of
>> similar objects should be faster, which should be the most common case
>> (or at least the one to favor) when using types to dispatch methods.
> 
> +1
> 
> I notice that the `(null (assq type found))` is now ineffective, tho.
> Maybe it's OK and we should just remove it.

Good catch :-)  I think it's OK to just remove this test.

> Why all the `defsubst`?  Have you measured a noticeable speed difference
> by using them?  I have a hard time seeing how that could happen.
> All 3 `defsubst` in your patch are for function which contain
> a non-trivial loop, so I'd expect the overhead of a function call to be
> negligible.

Sorry, that's a bit paranoid of me, as I've heard many times that function
calls are inefficient in ELisp.  You're certainly right: in this case, the
overhead of a function call should be negligible.  I'll replace those
"defsubst" with "defun".

David

Message #146 received at 77725 <at> debbugs.gnu.org (full text, mbox):

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: Re: bug#77725: 31.0.50; Add support for types accepted by
 `cl-typep' to cl-generic?
Date: Tue, 29 Apr 2025 12:33:06 -0400

> Of course, it makes much sense.  If I am not wrong, the constructor of the
> class `cl-type-class' already ensures that parent types must be defined
> before their "child" types (i.e. already added to the `cl--type-list' for
> types defined with `cl-deftype").

I think so, yes.

> So it should work to simply push a new type at the beginning of the
> list.

Yup.

> And, when a type is redefined, move it at the beginning of
> the list?

Redefinition is more complicated, because child types may be in the
list, so moving the type to the head can be incorrect.  The "cheap"
solution is to leave the list unchanged (and hope the redefinition
doesn't change the hierarchy too much).

Side note: Redefinitions introduce other problems as well because the
class object's `parents` slot contains references to `cl--class`
objects, so after a redefinition via (setf (cl--find-class FOO) ...),
the children's `parents` slots point to the old class object.
That's a problem that affects all types and that we don't really try to
solve currently.

> Sorry, that's a bit paranoid of me, as I've heard many times that function
> calls are inefficient in ELisp.

FWIW, calls from bytecode to bytecode have been improved noticeable by
Mattias (can't remember if that was for Emacs-29 or Emacs-30), so it's
not as bad as it used to be.

> You're certainly right: in this case, the overhead of a function call
> should be negligible.  I'll replace those "defsubst" with "defun".

It's good to be mindful of costs, but it's also important to remember
that the majority of the code is actually not performance sensitive at
all (by which I mean that small constant factors, like what you get from
inlining, don't matter).


        Stefan

Message #149 received at 77725 <at> debbugs.gnu.org (full text, mbox):

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: Re: bug#77725: 31.0.50; Add support for types accepted by
 `cl-typep' to cl-generic?
Date: Tue, 29 Apr 2025 14:02:17 -0400

[Message part 1 (text/plain, inline)]

Further comments:

- For a declaration like

    (cl-deftype list-of (elem-type)
      `(and list
            (satisfies ,(lambda (list)
                          (cl-every (lambda (elem) (cl-typep elem elem-type))
                                    list)))))
    
  we add the type to `cl--type-list` even though it's unusable there
  (the `cl-typep` call in `cl-types-of` will always signal an error
  because the type can't be used without argument).

- Regarding incorporation into CL-Lib: apparently we don't need to
  `cl-deftype` in preloaded files, so `cl--type-deftype`
  does not have to be in `cl-preloaded`.
  But if `cl-deftype` expands to a call to it, then it needs to be
  (auto)loaded even when CL-Lib is not loaded, which suggests putting it
  into `cl-lib.el`.
  Another option would be to make `cl-deftype` expand to code which does
  not immediately call `cl--type-deftype`.  One way to do that would be to
  wrap the call into a `(with-eval-after-load 'cl-lib ...)` or
  something similar.

- One way to solve the problem with `list-of` (and even open up the
  possibility to dispatch on complex types like `(list-of FOO)`) is to
  populate `cl--type-dispatch-list` (i.e. the list of types that need to
  be checked during dispatch) from `cl-generic-generalizers` so it
  includes only those types for which there's a method, rather than all
  defined types.

- The dispatch of types defined by `cl-deftype` is inherently unreliable
  because the priority to use is not always the same.  For a type
  defined as `(or integer symbol)` the priority should be *lower* than
  the priority of the "typeof" generalizer, whereas for a type defined
  as `(list-of (eql 'a))` the priority should be higher than that of the
  "head" generalizer.
  I don't think we can solve this problem, but it should be clearly
  documented somewhere as a limitation.

See below my current local changes (not really related to the comments
above) as a diff w.r.t. the `scratch/cl-types` branch.


        Stefan

[cl-types.patch (text/x-diff, inline)]

diff --git a/lisp/emacs-lisp/cl-types.el b/lisp/emacs-lisp/cl-types.el
index c10ce4a24fb..02972e0b817 100644
--- a/lisp/emacs-lisp/cl-types.el
+++ b/lisp/emacs-lisp/cl-types.el
@@ -48,22 +48,12 @@ cl--type-p
 That is, a type defined by `cl-deftype', of class `cl-type-class'."
   (and (symbolp object) (cl-type-class-p (cl--find-class object))))
 
-(defsubst cl--type-parents (name)
+(defun cl--type-parents (name)
   "Get parents of type with NAME.
 NAME is a symbol representing a type.
 Return a possibly empty list of types."
   (cl--class-allparents (cl--find-class name)))
 
-(defsubst cl--type-children (name)
-  "Get children of the type with NAME.
-NAME is a symbol representing a type.
-Return a possibly empty list of types."
-  (cl--class-children (cl--find-class name)))
-
-(defsubst cl--type-dag (types)
-  "Return a DAG from the list of TYPES."
-  (mapcar #'cl--type-parents types))
-
 ;; Keep it for now, for testing.
 (defun cl--type-undefine (name)
   "Remove the definition of cl-type with NAME.
@@ -71,7 +61,7 @@ cl--type-undefine
 Signal an error if NAME has subtypes."
   (cl-check-type name (satisfies cl--type-p))
   (when-let* ((children (and (cl--type-p name)
-                             (cl--type-children name))))
+                             (cl--class-children (cl--find-class name)))))
     (error "Type has children: %S" children))
   (cl-remprop name 'cl--type-error)
   (cl-remprop name 'cl--class)
@@ -80,6 +70,8 @@ cl--type-undefine
 
 (defun cl--type-deftype (name parents &optional docstring)
   ;; FIXME: Should we also receive the arglist?
+  ;; FIXME: "Generalize" is not right, and the part related to
+  ;; method-dispatch is just that: a part.
   "Generalize cl-type with NAME for method dispatching.
 PARENTS is a list of types NAME is a subtype of, or nil.
 DOCSTRING is an optional documentation string."
@@ -105,22 +97,7 @@ cl--type-deftype
               ;; Clear any previous error mark.
               (cl-remprop name 'cl--type-error)
             ;; Record new type to include its dependency in the DAG.
-            (push name typelist))
-          ;; `cl-types-of' iterates through all known types to collect
-          ;; all those an object belongs to, sorted from the most
-          ;; specific type to the more general type.  So, keep the
-          ;; global list in this order.
-          ;; FIXME: This global operation is a bit worrisome, because it
-          ;; scales poorly with the number of types.  I guess it's OK
-          ;; for now because `cl-deftype' is not very popular, but it'll
-          ;; probably need to be replaced at some point.  Maybe we
-          ;; should simply require that the parents be defined already,
-          ;; then we can just `push' the new type, knowing it's in
-          ;; topological order by construction.
-          (setq cl--type-list
-                (merge-ordered-lists
-                 (cl--type-dag typelist)
-                 (lambda (_) (error "Invalid dependency graph")))))
+            (push name typelist)))
       (error
        (setf (symbol-plist name) oldplist)
        (error (format "Define %S failed: %s"
@@ -252,14 +229,8 @@ cl-types-of
        ;; Skip type, if it previously produced an error.
        (null (get type 'cl--type-error))
        ;; Skip type not defined by `cl-deftype'.
+       ;; FIXME: Can we make sure this is simply always true?
        (cl-type-class-p (cl--find-class type))
-       ;; If BAR is declared as a parent of FOO and `cl-types-of' has
-       ;; already decided that the value is of type FOO, then we
-       ;; already know BAR will be in the output anyway and there's no
-       ;; point testing BAR.  So, skip type already selected as parent
-       ;; of another type, assuming that, most of the time, `assq'
-       ;; will be faster than `cl-typep'.
-       (null (assq type found))
        ;; If OBJECT is of type, add type to the matching list.
        (condition-case-unless-debug e
            (cl-typep object type)
@@ -268,17 +239,10 @@ cl-types-of
     ;; Return an unique value of the list of types OBJECT belongs to,
     ;; which is also the list of specifiers for OBJECT.
     (with-memoization (gethash found cl--type-unique)
-      ;; Compute a DAG from the collected matching types.
-      (let (dag)
-        (dolist (type found)
-          (let ((pl (cl--type-parents type)))
-            (while pl
-              (push pl dag)
-              (setq pl (cdr pl)))))
-        ;; Compute an ordered list of types from the DAG.
-        (merge-ordered-lists
-         (nreverse (cons (cl--type-parents (cl-type-of object))
-                         dag)))))))
+      ;; Compute an ordered list of types from the DAG.
+      (merge-ordered-lists
+       (nreverse (mapcar #'cl--type-parents
+                         (cons (cl-type-of object) found)))))))
 
 ;;; Method dispatching
 ;;

Message #152 received at 77725 <at> debbugs.gnu.org (full text, mbox):

From: David Ponce <da_vid <at> orange.fr>
To: Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: 77725 <at> debbugs.gnu.org, Eli Zaretskii <eliz <at> gnu.org>
Subject: Re: bug#77725: 31.0.50; Add support for types accepted by `cl-typep'
 to cl-generic?
Date: Wed, 30 Apr 2025 11:28:58 +0200

[Message part 1 (text/plain, inline)]

On 2025-04-29 20:02, Stefan Monnier wrote:
> Further comments:
> 
> - For a declaration like
> 
>      (cl-deftype list-of (elem-type)
>        `(and list
>              (satisfies ,(lambda (list)
>                            (cl-every (lambda (elem) (cl-typep elem elem-type))
>                                      list)))))
>      
>    we add the type to `cl--type-list` even though it's unusable there
>    (the `cl-typep` call in `cl-types-of` will always signal an error
>    because the type can't be used without argument).
> 
> - Regarding incorporation into CL-Lib: apparently we don't need to
>    `cl-deftype` in preloaded files, so `cl--type-deftype`
>    does not have to be in `cl-preloaded`.
>    But if `cl-deftype` expands to a call to it, then it needs to be
>    (auto)loaded even when CL-Lib is not loaded, which suggests putting it
>    into `cl-lib.el`.
>    Another option would be to make `cl-deftype` expand to code which does
>    not immediately call `cl--type-deftype`.  One way to do that would be to
>    wrap the call into a `(with-eval-after-load 'cl-lib ...)` or
>    something similar.
> 
> - One way to solve the problem with `list-of` (and even open up the
>    possibility to dispatch on complex types like `(list-of FOO)`) is to
>    populate `cl--type-dispatch-list` (i.e. the list of types that need to
>    be checked during dispatch) from `cl-generic-generalizers` so it
>    includes only those types for which there's a method, rather than all
>    defined types.
> 
> - The dispatch of types defined by `cl-deftype` is inherently unreliable
>    because the priority to use is not always the same.  For a type
>    defined as `(or integer symbol)` the priority should be *lower* than
>    the priority of the "typeof" generalizer, whereas for a type defined
>    as `(list-of (eql 'a))` the priority should be higher than that of the
>    "head" generalizer.
>    I don't think we can solve this problem, but it should be clearly
>    documented somewhere as a limitation.

I'm afraid this is all a bit beyond my grasp :-(
I'll defer to your expert opinion.

> 
> See below my current local changes (not really related to the comments
> above) as a diff w.r.t. the `scratch/cl-types` branch.

Thanks!

Attached you will find another version of cl-types.el, and
cl-types-test.el updated according to last changes.

I've included your edits in cl-types.el and improved `cl-types-of',
exploring the idea of ​​mapping a set of cl-types to a built-in type.  I
propose a simple solution derived from this idea, based on a "type
flag" (a symbol property for now) whose value lets us know whether the
type is worth checking, i.e. not in error, or match the built-in type
of the checked object.  Maybe, this "type property" could also become
a slot in the `cl-type-class' structure?

I also removed the test `(cl-type-class-p (cl--find-class type))'
which is always true, because in `cl--type-deftype' we only push such
types in `cl--type-list', and this list is only updated here and in
`cl--type-undefine' to remove a type.


David

[cl-types-tests.el (text/x-emacs-lisp, attachment)]

[cl-types.el (text/x-emacs-lisp, attachment)]

Message #155 received at 77725 <at> debbugs.gnu.org (full text, mbox):

From: David Ponce <da_vid <at> orange.fr>
To: Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: 77725 <at> debbugs.gnu.org, Eli Zaretskii <eliz <at> gnu.org>
Subject: Re: bug#77725: 31.0.50; Add support for types accepted by `cl-typep'
 to cl-generic?
Date: Thu, 1 May 2025 17:51:49 +0200

[Message part 1 (text/plain, inline)]

On 2025-04-30 11:28, David Ponce wrote:
> On 2025-04-29 20:02, Stefan Monnier wrote:
>> Further comments:
>>
>> - For a declaration like
>>
>>      (cl-deftype list-of (elem-type)
>>        `(and list
>>              (satisfies ,(lambda (list)
>>                            (cl-every (lambda (elem) (cl-typep elem elem-type))
>>                                      list)))))
>>    we add the type to `cl--type-list` even though it's unusable there
>>    (the `cl-typep` call in `cl-types-of` will always signal an error
>>    because the type can't be used without argument).
>>

>> - One way to solve the problem with `list-of` (and even open up the
>>    possibility to dispatch on complex types like `(list-of FOO)`) is to
>>    populate `cl--type-dispatch-list` (i.e. the list of types that need to
>>    be checked during dispatch) from `cl-generic-generalizers` so it
>>    includes only those types for which there's a method, rather than all
>>    defined types.
>>

Please find attached a version of cl-types.el with my first try at
implementing something related to your idea above to populate a
`cl--type-dispatch-list' from `cl-generic-generalizers'.

Changes are at the end of the file in the last section "Method dispatching".
I hope I started understanding your idea ;-)

Thanks!
David

[cl-types.el (text/x-emacs-lisp, attachment)]

Message #158 received at 77725 <at> debbugs.gnu.org (full text, mbox):

From: David Ponce <da_vid <at> orange.fr>
To: Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: 77725 <at> debbugs.gnu.org, Eli Zaretskii <eliz <at> gnu.org>
Subject: Re: bug#77725: 31.0.50; Add support for types accepted by `cl-typep'
 to cl-generic?
Date: Fri, 2 May 2025 11:24:24 +0200

[Message part 1 (text/plain, inline)]

> 
> Please find attached a version of cl-types.el with my first try at
> implementing something related to your idea above to populate a
> `cl--type-dispatch-list' from `cl-generic-generalizers'.

See attached my current local changes as a diff w.r.t. the `scratch/cl-types` branch.
And a possible change log:

2025-05-02  David Ponce  <da_vid <at> orange.fr>
	    Stefan Monnier <monnier <at> iro.umontreal.ca>

	* lisp/emacs-lisp/cl-types.el (cl--type-list): Doc string.
	(cl--type-dispatch-list): New variable.
	(cl--type-parents): Make it a plain defun.
	(cl--type-children, cl--type-dag): Remove.
	(cl--type-undefine): Remove duplicate test for `cl--type-p'.  Use
	`cl--class-children'.  Clear `cl--type-flag' instead of
	`cl--type-error'.  Also remove type from the dispatch list.
	(cl--type-deftype): Doc string.  Remove useless safeguard of
	data on error.  Fix some error messages.  Clear `cl--type-flag'
	when a type is (re)defined.  Just push new types on
	`cl--type-list'.
	(cl--type-error): Set `cl--type-flag' to the symbol `error'.
	(cl-types-of): Doc string.  Remove useless check for
	`cl-type-class-p'.  Skip types which we are sure will not match.
	Simplify creation of the DAG.
	(cl--type-generalizer): In the tagcode-function, check only types
	that can be dispatched.
	(cl-generic-generalizers): Populate the dispatch list.

Thanks!
David

[cl-types.patch (text/x-patch, attachment)]

Message #161 received at 77725 <at> debbugs.gnu.org (full text, mbox):

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

[Message part 1 (text/plain, inline)]

On 2025-05-02 11:24, David Ponce wrote:
>>
>> Please find attached a version of cl-types.el with my first try at
>> implementing something related to your idea above to populate a
>> `cl--type-dispatch-list' from `cl-generic-generalizers'.
> 

Sorry, here is the correct patch, and updated change log.

2025-05-02  David Ponce  <da_vid <at> orange.fr>
            Stefan Monnier <monnier <at> iro.umontreal.ca>

	* lisp/emacs-lisp/cl-types.el (cl--type-list): Doc string.
	(cl--type-dispatch-list): New variable.
	(cl--type-parents): Make it a plain defun.
	(cl--type-children, cl--type-dag): Remove.
	(cl--type-undefine): Remove duplicate test for `cl--type-p'.  Use
	`cl--class-children'.  Clear `cl--type-flag' instead of
	`cl--type-error'.  Also remove type from the dispatch list.
	(cl--type-deftype): Doc string.  Remove useless safeguard of
	data on error.  Fix some error messages.  Clear `cl--type-flag'
	when a type is (re)defined.  Just push new types on
	`cl--type-list'.
	(cl--type-error): Set `cl--type-flag' to the symbol `error' and
	remove type in error from the dispatch list.
	(cl-types-of): Doc string.  Remove useless check for
	`cl-type-class-p'.  Skip types which we are sure will not match.
	Simplify creation of the DAG.
	(cl--type-generalizer): In the tagcode-function, check only types
	that can be dispatched.
	(cl-generic-generalizers): Populate the dispatch list.

[cl-types.patch (text/x-patch, attachment)]

Message #164 received at 77725 <at> debbugs.gnu.org (full text, mbox):

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: Re: bug#77725: 31.0.50; Add support for types accepted by
 `cl-typep' to cl-generic?
Date: Mon, 05 May 2025 11:15:54 -0400

> Sorry, here is the correct patch, and updated change log.

Thanks, pushed to the branch.  I think the code is looking pretty good now.
I just have to decide how to integrate it into CL-Lib so it's loaded
when we need it, and then we can push it to `master`.

The optimization on the dispatch is nice.  We could do even better and
test only those types which have methods for the current generic
function rather than for any generic function.  I thought I had a patch
which provides that info to the `tagcode-function`, but sadly I was
confused: the patch I have provides that info only to the
`specializer-function`.  It can (and arguably should) be done, of
course, but it requires a fair bit of changes to `cl-generic.el`.  🙁


        Stefan

Message #167 received at 77725 <at> debbugs.gnu.org (full text, mbox):

From: David Ponce <da_vid <at> orange.fr>
To: Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: 77725 <at> debbugs.gnu.org, Eli Zaretskii <eliz <at> gnu.org>
Subject: Re: bug#77725: 31.0.50; Add support for types accepted by `cl-typep'
 to cl-generic?
Date: Mon, 5 May 2025 20:05:35 +0200

> Thanks, pushed to the branch.  I think the code is looking pretty good now.

Thank you, that's great!  And it's certainly largely thanks to you :-)

> I just have to decide how to integrate it into CL-Lib so it's loaded
> when we need it, and then we can push it to `master`.

That would be great.  Please let me know if I can help to test.

> The optimization on the dispatch is nice.  We could do even better and
> test only those types which have methods for the current generic
> function rather than for any generic function.  I thought I had a patch
> which provides that info to the `tagcode-function`, but sadly I was
> confused: the patch I have provides that info only to the
> `specializer-function`.  It can (and arguably should) be done, of
> course, but it requires a fair bit of changes to `cl-generic.el`.  🙁

I hope you find the time and motivation to improve cl-generic.el,
which certainly deserves to be used more.  I'm not sure I can help you
much in this area, but if you think I can help you, even if it's just
for testing, please don't hesitate to ask me; I'll be happy to
contribute, within my means.

Many thanks!
David

Message #170 received at 77725 <at> debbugs.gnu.org (full text, mbox):

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: Re: bug#77725: 31.0.50; Add support for types accepted by
 `cl-typep' to cl-generic?
Date: Mon, 05 May 2025 14:59:28 -0400

[Message part 1 (text/plain, inline)]

>> Thanks, pushed to the branch.  I think the code is looking pretty good now.
> Thank you, that's great!

I just pushed to the branch a further patch (see attached) which tries
to simplify the code a bit more.


        Stefan

[cl-types.patch (text/x-diff, inline)]

commit 68a50324a70bd794d7f3228290310093f1515f7b
Author: Stefan Monnier <monnier <at> iro.umontreal.ca>
Date:   Mon May 5 14:57:05 2025 -0400

    cl-types: Simplify a bit further
    
    Mostly, get rid of `cl--type-flag` and rely only on the presence/absence
    of the type on `cl--types-list` to "flag" erroring-types.
    Also, don't try and catch errors during dispatch.
    
    * lisp/emacs-lisp/cl-types.el (cl--type-dispatch-list): Move to the
    relevant section.
    (cl--type-parents): Inline into sole caller.
    (cl--type-deftype): Add `arglist` argument.
    Don't signal an error if the type already existed but wasn't in
    `cl--type-list` since that's normal and we can fix it.
    Don't touch `cl--type-flag` any more.
    Don't add to `cl--type-list` if it can't be used without arguments.
    (cl-deftype2): Adjust call accordingly.
    (cl--type-error): Inline into sole caller.
    (cl-types-of): Be more careful to preserve ordering of types
    before passing them to `merge-ordered-lists`.
    Add `types` argument for use by dispatch.
    Don't bother skipping the `root-type` since that's a built-in type,
    so it should never happen anyway.
    Don't catch errors if called from dispatch.
    Don't bother with `cl--type-flag`.
    (cl--type-generalizer): Use new arg of `cl-types-of` instead of
    let-binding `cl--type-list`, in case `cl-types-of` ends up (auto)loading
    a file or some such thing which needs to use/modify `cl--type-list`.
    (cl--type-undefine): Move to end of file.
    
    * test/lisp/emacs-lisp/cl-types-tests.el (cl-types-test): Remove DAG
    test since we don't detect such errors any more.
    Relax ordering test when the order is not guaranteed
    by parent-relationships.

diff --git a/lisp/emacs-lisp/cl-types.el b/lisp/emacs-lisp/cl-types.el
index b7816ca3a84..a466c309a33 100644
--- a/lisp/emacs-lisp/cl-types.el
+++ b/lisp/emacs-lisp/cl-types.el
@@ -22,9 +22,6 @@
 (defvar cl--type-list nil
   "Precedence list of the defined cl-types.")
 
-(defvar cl--type-dispatch-list nil
-  "List of types that need to be checked during dispatch.")
-
 ;; FIXME: The `cl-deftype-handler' property should arguably be turned
 ;; into a field of this struct (but it has performance and
 ;; compatibility implications, so let's not make that change for now).
@@ -51,71 +48,44 @@ cl--type-p
 That is, a type defined by `cl-deftype', of class `cl-type-class'."
   (and (symbolp object) (cl-type-class-p (cl--find-class object))))
 
-(defun cl--type-parents (name)
-  "Get parents of type with NAME.
-NAME is a symbol representing a type.
-Return a possibly empty list of types."
-  (cl--class-allparents (cl--find-class name)))
-
-;; Keep it for now, for testing.
-(defun cl--type-undefine (name)
-  "Remove the definition of cl-type with NAME.
-NAME is an unquoted symbol representing a cl-type.
-Signal an error if NAME has subtypes."
-  (cl-check-type name (satisfies cl--type-p))
-  (when-let* ((children (cl--class-children (cl--find-class name))))
-    (error "Type has children: %S" children))
-  (cl-remprop name 'cl--type-flag)
-  (cl-remprop name 'cl--class)
-  (cl-remprop name 'cl-deftype-handler)
-  (setq cl--type-dispatch-list (delq name cl--type-dispatch-list))
-  (setq cl--type-list (delq name cl--type-list)))
-
-(defun cl--type-deftype (name parents &optional docstring)
-  ;; FIXME: Should we also receive the arglist?
+(defun cl--type-deftype (name parents arglist &optional docstring)
   "Register cl-type with NAME for method dispatching.
 PARENTS is a list of types NAME is a subtype of, or nil.
 DOCSTRING is an optional documentation string."
-  (condition-case err
-      (let* ((class (cl--find-class name))
-             (recorded (memq name cl--type-list)))
-        (if (null class)
-            (or (null recorded)
-                (error "Type registered, but doesn't exist"))
-          (or recorded (error "Type exists, but not registered"))
-          (or (cl-type-class-p class)
-              ;; FIXME: We have some uses `cl-deftype' in Emacs that
-              ;; "complement" another declaration of the same type,
-              ;; so maybe we should turn this into a warning (and
-              ;; not overwrite the `cl--find-class' in that case)?
-              (error "Type in another class: %S" (type-of class))))
-        ;; Setup a type descriptor for NAME.
-        (setf (cl--find-class name)
-              (cl--type-class-make name docstring parents))
-        ;; Reset NAME as a newly defined type.
-        (cl-remprop name 'cl--type-flag)
-        ;; Record new type.  The constructor of the class
-        ;; `cl-type-class' already ensures that parent types must be
-        ;; defined before their "child" types (i.e. already added to
-        ;; the `cl--type-list' for types defined with `cl-deftype').
-        ;; So it is enough to simply push a new type at the beginning
-        ;; of the list.
-        ;; Redefinition is more complicated, because child types may
-        ;; be in the list, so moving the type to the head can be
-        ;; incorrect.  The "cheap" solution is to leave the list
-        ;; unchanged (and hope the redefinition doesn't change the
-        ;; hierarchy too much).
-        ;; Side note: Redefinitions introduce other problems as well
-        ;; because the class object's `parents` slot contains
-        ;; references to `cl--class` objects, so after a redefinition
-        ;; via (setf (cl--find-class FOO) ...), the children's
-        ;; `parents` slots point to the old class object.  That's a
-        ;; problem that affects all types and that we don't really try
-        ;; to solve currently.
-        (or recorded (push name cl--type-list)))
-    (error
-     (error (format "Define %S failed: %s"
-                    name (error-message-string err))))))
+  (let* ((class (cl--find-class name)))
+    (when class
+      (or (cl-type-class-p class)
+          ;; FIXME: We have some uses `cl-deftype' in Emacs that
+          ;; "complement" another declaration of the same type,
+          ;; so maybe we should turn this into a warning (and
+          ;; not overwrite the `cl--find-class' in that case)?
+          (error "Type in another class: %S" (type-of class))))
+    ;; Setup a type descriptor for NAME.
+    (setf (cl--find-class name)
+          (cl--type-class-make name docstring parents))
+    ;; Record new type.  The constructor of the class
+    ;; `cl-type-class' already ensures that parent types must be
+    ;; defined before their "child" types (i.e. already added to
+    ;; the `cl--type-list' for types defined with `cl-deftype').
+    ;; So it is enough to simply push a new type at the beginning
+    ;; of the list.
+    ;; Redefinition is more complicated, because child types may
+    ;; be in the list, so moving the type to the head can be
+    ;; incorrect.  The "cheap" solution is to leave the list
+    ;; unchanged (and hope the redefinition doesn't change the
+    ;; hierarchy too much).
+    ;; Side note: Redefinitions introduce other problems as well
+    ;; because the class object's `parents` slot contains
+    ;; references to `cl--class` objects, so after a redefinition
+    ;; via (setf (cl--find-class FOO) ...), the children's
+    ;; `parents` slots point to the old class object.  That's a
+    ;; problem that affects all types and that we don't really try
+    ;; to solve currently.
+    (or (memq name cl--type-list)
+        ;; Exclude types that can't be used without arguments.
+        ;; They'd signal errors in `cl-types-of'!
+        (not (memq (car arglist) '(nil &rest &optional &keys)))
+        (push name cl--type-list))))
 
 ;;;###autoload
 (defmacro cl-deftype2 (name arglist &rest body)
@@ -170,7 +140,7 @@ cl-deftype2
        ;; 'cl-lib)), so `cl--type-deftype' needs to go either to
        ;; `cl-preloaded.el' or it should be autoloaded even when
        ;; `cl-lib' is not loaded.
-       (cl--type-deftype ',name ',parents ,docstring)
+       (cl--type-deftype ',name ',parents ',arglist ,docstring)
        (define-symbol-prop ',name 'cl-deftype-handler
                            (cl-function
                             (lambda (&cl-defs ('*) ,@arglist)
@@ -181,17 +151,6 @@ cl-deftype2
 (defvar cl--type-unique (make-hash-table :test 'equal)
   "Record an unique value of each type.")
 
-(defun cl--type-error (type error)
-  "Mark TYPE as in-error, and report the produced ERROR value."
-  ;; Temporarily raise the recursion limit to avoid another recursion
-  ;; error while reporting ERROR.
-  (let ((max-lisp-eval-depth (+ 800 max-lisp-eval-depth)))
-    ;; Mark TYPE as in-error and remove it from the dispatch list.
-    (put type 'cl--type-flag 'error)
-    (setq cl--type-dispatch-list (delq type cl--type-dispatch-list))
-    (warn  "cl-types-of %s, %s" type (error-message-string error)))
-  nil)
-
 ;; FIXME: `cl-types-of' CPU cost is proportional to the number of types
 ;; defined with `cl-deftype', so the more popular it gets, the slower
 ;; it becomes.  And of course, the cost of each type check is
@@ -234,59 +193,54 @@ cl--type-error
 ;; - in `cl-types-of' start by calling `cl-type-of', then use the map
 ;;   to find which cl-types may need to be checked.
 ;;
-(defun cl-types-of (object)
-"Return the types OBJECT belongs to.
+(defun cl-types-of (object &optional types)
+  "Return the types OBJECT belongs to.
 Return an unique list of types OBJECT belongs to, ordered from the
-most specific type to the most general."
-(let* ((root-type (cl-type-of object))
-       (found (list root-type)))
-  ;; Build a list of all types OBJECT belongs to.
-  (dolist (type cl--type-list)
-    (let ((flag (get type 'cl--type-flag)))
+most specific type to the most general.
+TYPES is an internal argument."
+  (let* ((found nil))
+    ;; Build a list of all types OBJECT belongs to.
+    (dolist (type (or types cl--type-list))
       (and
-       ;; Skip type, if it previously produced an error.
-       (not (eq flag 'error))
-       ;; Skip type which we are sure will not match.
-       (or (null flag) (eq flag root-type))
        ;; If OBJECT is of type, add type to the matching list.
-       (condition-case-unless-debug e
+       (if types
+           ;; For method dispatch, we don't need to filter out errors, since
+           ;; we can presume that method dispatch is used only on
+           ;; sanely-defined types.
            (cl-typep object type)
-         (error (cl--type-error type e)))
-       (or flag (put type 'cl--type-flag root-type))
-       (push type found))))
-  ;; Return an unique value of the list of types OBJECT belongs to,
-  ;; which is also the list of specifiers for OBJECT.
-  (with-memoization (gethash found cl--type-unique)
-    ;; Compute an ordered list of types from the DAG.
-    (merge-ordered-lists (mapcar #'cl--type-parents found)))))
+         (condition-case-unless-debug e
+             (cl-typep object type)
+           (error (setq cl--type-list (delq type cl--type-list))
+                  (warn  "cl-types-of %S: %s"
+                         type (error-message-string e)))))
+       (push type found)))
+    (push (cl-type-of object) found)
+    ;; Return an unique value of the list of types OBJECT belongs to,
+    ;; which is also the list of specifiers for OBJECT.
+    (with-memoization (gethash found cl--type-unique)
+      ;; Compute an ordered list of types from the DAG.
+      (merge-ordered-lists
+       (mapcar (lambda (type) (cl--class-allparents (cl--find-class type)))
+               (nreverse found))))))
 
 ;;; Method dispatching
 ;;
 
-;; For a declaration like
-;;
-;;   (cl-deftype list-of (elem-type)
-;;     `(and list
-;;           (satisfies ,(lambda (list)
-;;                         (cl-every (lambda (elem)
-;;                                     (cl-typep elem elem-type))
-;;                                   list)))))
-;;
-;; we add the type to `cl--type-list' even though it's unusable there
-;; (the `cl-typep` call in `cl-types-of' will always signal an error
-;; because the type can't be used without argument).
-;;
-;; One way to solve this (and even open up the possibility to
-;; dispatch on complex types like `(list-of FOO)') is to populate
-;; `cl--type-dispatch-list' (i.e. the list of types that need to
-;; be checked during dispatch) from `cl-generic-generalizers' so it
-;; includes only those types for which there's a method, rather than
-;; all defined types.
+(defvar cl--type-dispatch-list nil
+  "List of types that need to be checked during dispatch.")
 
 (cl-generic-define-generalizer cl--type-generalizer
+  ;; FIXME: This priority can't be always right.  :-(
+  ;; E.g. a method dispatching on a type like (or number function),
+  ;; should take precedence over a method on `t' but not over a method
+  ;; on `number'.  Similarly a method dispatching on a type like
+  ;; (satisfies (lambda (x) (equal x '(A . B)))) should take precedence
+  ;; over a method on (head 'A).
+  ;; Fixing this 100% is impossible so this generalizer is condemned to
+  ;; suffer from "undefined method ordering" problems, unless/until we
+  ;; restrict it somehow to a subset that we can handle reliably.
   20 ;; "typeof" < "cl-types-of" < "head" priority
-  (lambda (obj &rest _) `(let ((cl--type-list cl--type-dispatch-list))
-                           (cl-types-of ,obj)))
+  (lambda (obj &rest _) `(cl-types-of ,obj cl--type-dispatch-list))
   (lambda (tag &rest _) (if (consp tag) tag)))
 
 (cl-defmethod cl-generic-generalizers :extra "cl-types-of" (type)
@@ -296,6 +250,9 @@ cl-generic-generalizers
         ;; Add a new dispatch type to the dispatch list, then
         ;; synchronize with `cl--type-list' so that both lists follow
         ;; the same type precedence order.
+        ;; The `merge-ordered-lists' is `cl-types-of' should we make this
+        ;; ordering unnecessary, but it's still handy for all those types
+        ;; that don't declare their parents.
         (unless (memq type cl--type-dispatch-list)
           (setq cl--type-dispatch-list
                 (seq-intersection cl--type-list
@@ -303,6 +260,21 @@ cl-generic-generalizers
         (list cl--type-generalizer))
     (cl-call-next-method)))
 
+;;; Support for unloading.
+
+;; Keep it for now, for testing.
+(defun cl--type-undefine (name)
+  "Remove the definition of cl-type with NAME.
+NAME is an unquoted symbol representing a cl-type.
+Signal an error if NAME has subtypes."
+  (cl-check-type name (satisfies cl--type-p))
+  (when-let* ((children (cl--class-children (cl--find-class name))))
+    (error "Type has children: %S" children))
+  (cl-remprop name 'cl--class)
+  (cl-remprop name 'cl-deftype-handler)
+  (setq cl--type-dispatch-list (delq name cl--type-dispatch-list))
+  (setq cl--type-list (delq name cl--type-list)))
+
 (provide 'cl-types)
 
 ;;; cl-types.el ends here
diff --git a/test/lisp/emacs-lisp/cl-types-tests.el b/test/lisp/emacs-lisp/cl-types-tests.el
index f247ddd89d9..746270578e7 100644
--- a/test/lisp/emacs-lisp/cl-types-tests.el
+++ b/test/lisp/emacs-lisp/cl-types-tests.el
@@ -48,14 +48,15 @@ cl-types-test
   "Test types definition, cl-types-of and method dispatching."
 
   ;; Invalid DAG error
-  (should-error
-   (eval
-    '(cl-deftype2 unsigned-16bits ()
-       "Unsigned 16-bits integer."
-       (declare (parents unsigned-8bits))
-       '(unsigned-byte 16))
-    lexical-binding
-    ))
+  ;; FIXME: We don't test that any more.
+  ;; (should-error
+  ;;  (eval
+  ;;   '(cl-deftype2 unsigned-16bits ()
+  ;;      "Unsigned 16-bits integer."
+  ;;      (declare (parents unsigned-8bits))
+  ;;      '(unsigned-byte 16))
+  ;;   lexical-binding
+  ;;   ))
 
   ;; Test that (cl-types-of 4) is (multiples-of-4 multiples-of-2 ...)
   ;; Test that (cl-types-of 6) is (multiples-of-3 multiples-of-2 ...)
@@ -70,8 +71,10 @@ cl-types-test
     (should (equal '(multiples-of-3 multiples-of-2)
 		   (seq-intersection (cl-types-of 6) types)))
 
-    (should (equal '(multiples-of-3 multiples-of-4 multiples-of-2)
-		   (seq-intersection (cl-types-of 12) types)))
+    (should (member (seq-intersection (cl-types-of 12) types)
+		    ;; Order between 3 and 4/2 is undefined.
+		    '((multiples-of-3 multiples-of-4 multiples-of-2)
+		      (multiples-of-4 multiples-of-2 multiples-of-3))))
 
     (should (equal '()
 		   (seq-intersection (cl-types-of 5) types)))

Message #173 received at 77725 <at> debbugs.gnu.org (full text, mbox):

From: David Ponce <da_vid <at> orange.fr>
To: Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: 77725 <at> debbugs.gnu.org, Eli Zaretskii <eliz <at> gnu.org>
Subject: Re: bug#77725: 31.0.50; Add support for types accepted by `cl-typep'
 to cl-generic?
Date: Tue, 6 May 2025 00:37:07 +0200

On 2025-05-05 20:59, Stefan Monnier wrote:
>>> Thanks, pushed to the branch.  I think the code is looking pretty good now.
>> Thank you, that's great!
> 
> I just pushed to the branch a further patch (see attached) which tries
> to simplify the code a bit more.

Thank you!

The only change I cannot understand is this one in `cl-types-of':

"Don't bother skipping the `root-type` since that's a built-in type,
so it should never happen anyway."

The `root-type' was not skipped, but, on the contrary, was used to test
only types which have the same `root-type', i.e. skip types with a
different `root-type', which we are sure cannot match.  Your change just
removed this improvement and now all types are tested even if we can know
they cannot match.

As mentioned in a previous message, `cl--type-flag' explored the idea of
​​mapping a set of cl-types to a built-in type (root-type), and its value
allowed us to know whether the type is worth checking, i.e. either not
yet passed a `cl-typep' in `cl-types-of', or its root-type match the
`root-type' of the checked object:

(or (null cl--type-flag) (eq cl--type-flag root-type))


For example:

(cl-deftype2 icon ()
  "Builtin icon type."
  '(and symbol (satisfies iconp)))

(cl-types-of 'button) => button match `icon' type, so the `cl--type-flag'
of `icon' is set to `symbol' (cl-type-of or root-type of `button')

(cl-types-of 12) => `root-type' of 12 is `fixnum', so cl-types-of doesn't
waste time checking if 12 if of type `icon', because we are sure it cannot
match (their root-types are different).  An so on with other types whose
root-type is known.

Hope I am clear enough.

David

Message #176 received at 77725 <at> debbugs.gnu.org (full text, mbox):

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: Re: bug#77725: 31.0.50; Add support for types accepted by
 `cl-typep' to cl-generic?
Date: Mon, 05 May 2025 23:45:47 -0400

> As mentioned in a previous message, `cl--type-flag' explored the idea of
> ​​mapping a set of cl-types to a built-in type (root-type), and its value
> allowed us to know whether the type is worth checking, i.e. either not
> yet passed a `cl-typep' in `cl-types-of', or its root-type match the
> `root-type' of the checked object:

Oh, duh!  I completely misunderstood this and confused it with a flag
that indicated the type was signaling errors.
Thanks for the heads up.

I the mean time, I pushed the branch another change which smears the
code over the various `cl-*.el` files.  It's ugly as sin, but that's the
best I could come up with.

> (cl-types-of 'button) => button match `icon' type, so the `cl--type-flag'
> of `icon' is set to `symbol' (cl-type-of or root-type of `button')
>
> (cl-types-of 12) => `root-type' of 12 is `fixnum', so cl-types-of doesn't
> waste time checking if 12 if of type `icon', because we are sure it cannot
> match (their root-types are different).  An so on with other types whose
> root-type is known.

That makes a lot of sense, indeed.
But ... does it work for:

   (cl-deftype my-pair ()
     `(and number (satisfies ,(lambda (x) (zerop (logand x 1))))))

(cl-types-of (expt 2 128)) => (expt 2 128) matches `my-pair` type, so
the `cl--type-flag` of `my-pair` is set to `bignum`.  Now when I try
(cl-types-of 4) won't it skip `my-pair` because (cl-type-of 4) is not
`bignum`?  What am I missing?


        Stefan

Message #179 received at 77725 <at> debbugs.gnu.org (full text, mbox):

From: David Ponce <da_vid <at> orange.fr>
To: Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: 77725 <at> debbugs.gnu.org, Eli Zaretskii <eliz <at> gnu.org>
Subject: Re: bug#77725: 31.0.50; Add support for types accepted by `cl-typep'
 to cl-generic?
Date: Tue, 6 May 2025 16:57:51 +0200

On 2025-05-06 05:45, Stefan Monnier wrote:
>> As mentioned in a previous message, `cl--type-flag' explored the idea of
>> ​​mapping a set of cl-types to a built-in type (root-type), and its value
>> allowed us to know whether the type is worth checking, i.e. either not
>> yet passed a `cl-typep' in `cl-types-of', or its root-type match the
>> `root-type' of the checked object:
> 
> Oh, duh!  I completely misunderstood this and confused it with a flag
> that indicated the type was signaling errors.
> Thanks for the heads up.
> 
> I the mean time, I pushed the branch another change which smears the
> code over the various `cl-*.el` files.  It's ugly as sin, but that's the
> best I could come up with.

Great! Thank you!
I successfully "make bootstrap" the branch :-)
I run the cl-types-test with success, but one type has been signaled
in error on first run:

 Debugger entered--Lisp error: (void-function kmacro-register-p)
  kmacro-register-p(2)
  cl-typep(2 (satisfies kmacro-register-p))
  cl-typep(2 kmacro-register)
  cl-types-of(2)
  (seq-intersection (cl-types-of 2) types)
  [...]

>> (cl-types-of 'button) => button match `icon' type, so the `cl--type-flag'
>> of `icon' is set to `symbol' (cl-type-of or root-type of `button')
>>
>> (cl-types-of 12) => `root-type' of 12 is `fixnum', so cl-types-of doesn't
>> waste time checking if 12 if of type `icon', because we are sure it cannot
>> match (their root-types are different).  An so on with other types whose
>> root-type is known.
> 
> That makes a lot of sense, indeed.
> But ... does it work for:
> 
>     (cl-deftype my-pair ()
>       `(and number (satisfies ,(lambda (x) (zerop (logand x 1))))))
> 
> (cl-types-of (expt 2 128)) => (expt 2 128) matches `my-pair` type, so
> the `cl--type-flag` of `my-pair` is set to `bignum`.  Now when I try
> (cl-types-of 4) won't it skip `my-pair` because (cl-type-of 4) is not
> `bignum`?  What am I missing?

Good point! The problem is that the type returned by `cl-type-of' is too
specific. If I instead use `type-of' to map a set of cl-types to a
built-in type, your example above works as expected, as do other
categories I've tested, like symbol, cons, string, etc.
Using `type-of' to determine a set of cl-types seems like a good
compromise to me. WDYT?

I am still reviewing your (big) change, and will let you know any remarks
shortly, along with any proposals as a patch.

David

Message #182 received at 77725 <at> debbugs.gnu.org (full text, mbox):

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: Re: bug#77725: 31.0.50; Add support for types accepted by
 `cl-typep' to cl-generic?
Date: Tue, 06 May 2025 11:55:09 -0400

>  Debugger entered--Lisp error: (void-function kmacro-register-p)
>   kmacro-register-p(2)
>   cl-typep(2 (satisfies kmacro-register-p))
>   cl-typep(2 kmacro-register)
>   cl-types-of(2)
>   (seq-intersection (cl-types-of 2) types)
>   [...]

That's an incorrect `cl-deftype` call.  AFAIK this was in `register.el`
but I actually removed it from there with:

    commit b1407b41a16c4a3ec15c88be91ba0ae1e65c212e
    Author: Stefan Monnier <monnier <at> iro.umontreal.ca>
    Date:   Tue Apr 29 16:04:54 2025 -0400
    
        register.el: Remove bogus deftypes and fix associated methods
        
        * lisp/register.el (frame-register, kmacro-register): Remove bogus deftypes.
        (register--type) <oclosure>: Fix kmacro method and generalize it to
        any OClosure.
        (register--type) <frameset-register>: Fix method and move it to ...
        * lisp/frameset.el (register--type) <frameset-register>: ... here,
        where `frameset-register` is defined.

I guess I need to rebase the `cl-types` branch.  🙂

>>> (cl-types-of 'button) => button match `icon' type, so the `cl--type-flag'
>>> of `icon' is set to `symbol' (cl-type-of or root-type of `button')
>>>
>>> (cl-types-of 12) => `root-type' of 12 is `fixnum', so cl-types-of doesn't
>>> waste time checking if 12 if of type `icon', because we are sure it cannot
>>> match (their root-types are different).  An so on with other types whose
>>> root-type is known.
>> That makes a lot of sense, indeed.
>> But ... does it work for:
>>     (cl-deftype my-pair ()
>>       `(and number (satisfies ,(lambda (x) (zerop (logand x 1))))))
>> (cl-types-of (expt 2 128)) => (expt 2 128) matches `my-pair` type, so
>> the `cl--type-flag` of `my-pair` is set to `bignum`.  Now when I try
>> (cl-types-of 4) won't it skip `my-pair` because (cl-type-of 4) is not
>> `bignum`?  What am I missing?
>
> Good point! The problem is that the type returned by `cl-type-of' is too
> specific. If I instead use `type-of' to map a set of cl-types to a
> built-in type, your example above works as expected, as do other
> categories I've tested, like symbol, cons, string, etc.
> Using `type-of' to determine a set of cl-types seems like a good
> compromise to me. WDYT?

That just solves some occurrences, but not all:

     (cl-deftype my-pair-length ()
       `(and sequence (satisfies ,(lambda (x) (zerop (logand (length x) 1))))))

and now (cl-types-of [1 2]) will set `cl--type-flag` to
`vector` so (cl-types-of "ab") will miss `my-pair-length`!

If you want more cases, think of

    (cl-deftype my-foo ()
      '(or TYPE1 TYPE2))


- Stefan

Message #185 received at 77725 <at> debbugs.gnu.org (full text, mbox):

From: David Ponce <da_vid <at> orange.fr>
To: Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: 77725 <at> debbugs.gnu.org, Eli Zaretskii <eliz <at> gnu.org>
Subject: Re: bug#77725: 31.0.50; Add support for types accepted by `cl-typep'
 to cl-generic?
Date: Tue, 6 May 2025 18:54:01 +0200

[Message part 1 (text/plain, inline)]

On 2025-05-06 17:55, Stefan Monnier wrote:
>>   Debugger entered--Lisp error: (void-function kmacro-register-p)
>>    kmacro-register-p(2)
>>    cl-typep(2 (satisfies kmacro-register-p))
>>    cl-typep(2 kmacro-register)
>>    cl-types-of(2)
>>    (seq-intersection (cl-types-of 2) types)
>>    [...]
> 
> That's an incorrect `cl-deftype` call.  AFAIK this was in `register.el`
> but I actually removed it from there with:
> 
>      commit b1407b41a16c4a3ec15c88be91ba0ae1e65c212e
>      Author: Stefan Monnier <monnier <at> iro.umontreal.ca>
>      Date:   Tue Apr 29 16:04:54 2025 -0400
>      
>          register.el: Remove bogus deftypes and fix associated methods
>          
>          * lisp/register.el (frame-register, kmacro-register): Remove bogus deftypes.
>          (register--type) <oclosure>: Fix kmacro method and generalize it to
>          any OClosure.
>          (register--type) <frameset-register>: Fix method and move it to ...
>          * lisp/frameset.el (register--type) <frameset-register>: ... here,
>          where `frameset-register` is defined.
> 
> I guess I need to rebase the `cl-types` branch.  🙂

I also see a similar error with type `frame-register':

"cl-types-of frame-register: Symbol’s function definition is void: frameset-register-p"

> 
>>>> (cl-types-of 'button) => button match `icon' type, so the `cl--type-flag'
>>>> of `icon' is set to `symbol' (cl-type-of or root-type of `button')
>>>>
>>>> (cl-types-of 12) => `root-type' of 12 is `fixnum', so cl-types-of doesn't
>>>> waste time checking if 12 if of type `icon', because we are sure it cannot
>>>> match (their root-types are different).  An so on with other types whose
>>>> root-type is known.
>>> That makes a lot of sense, indeed.
>>> But ... does it work for:
>>>      (cl-deftype my-pair ()
>>>        `(and number (satisfies ,(lambda (x) (zerop (logand x 1))))))
>>> (cl-types-of (expt 2 128)) => (expt 2 128) matches `my-pair` type, so
>>> the `cl--type-flag` of `my-pair` is set to `bignum`.  Now when I try
>>> (cl-types-of 4) won't it skip `my-pair` because (cl-type-of 4) is not
>>> `bignum`?  What am I missing?
>>
>> Good point! The problem is that the type returned by `cl-type-of' is too
>> specific. If I instead use `type-of' to map a set of cl-types to a
>> built-in type, your example above works as expected, as do other
>> categories I've tested, like symbol, cons, string, etc.
>> Using `type-of' to determine a set of cl-types seems like a good
>> compromise to me. WDYT?
> 
> That just solves some occurrences, but not all:
> 
>       (cl-deftype my-pair-length ()
>         `(and sequence (satisfies ,(lambda (x) (zerop (logand (length x) 1))))))
> 
> and now (cl-types-of [1 2]) will set `cl--type-flag` to
> `vector` so (cl-types-of "ab") will miss `my-pair-length`!
> 
> If you want more cases, think of
> 
>      (cl-deftype my-foo ()
>        '(or TYPE1 TYPE2))

Of course, you are right ;-)

I guess a general solution is much more complex than what I thought.  And maybe
risk to be more costly than the current implementation without set of cl-types.


Please find attached a patch proposal for the branch.  Mainly to
ensure that types not suitable for cl-defmethod (erroneous type or
type with arguments) will signal an "Unknown specializer" error when
trying to use them as argument type in cl-defmethod.  Also to improve
handling of errors with recursive types that can lead to error in the
error handler in `cl-types-of', because the maximum recursion limit is
reached.

2025-05-06  David Ponce  <da_vid <at> orange.fr>

	* lisp/emacs-lisp/cl-lib.el (cl-generic-generalizers :extra
	"cl-types-of"): Fix indentation.

	* lisp/emacs-lisp/cl-macs.el (cl-deftype): Don't register types
	that can't be used without arguments, so they are not valid types
	for method arguments.

	* lisp/emacs-lisp/cl-extra.el (cl--type-dispatch-list): Move
	definition before first use.
	(cl-types-of): Temporarily raise the recursion limit in error
	handler.  Remove the type in error from valid specializers.

	* lisp/emacs-lisp/cl-preloaded.el (cl--type-deftype): Remove the
	ARGLIST argument, no more used.  Don't exclude here types that
	can't be used without arguments.

Thanks!

[cl-types-V1.patch (text/x-patch, attachment)]

Message #188 received at 77725 <at> debbugs.gnu.org (full text, mbox):

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: Re: bug#77725: 31.0.50; Add support for types accepted by
 `cl-typep' to cl-generic?
Date: Tue, 06 May 2025 22:51:00 -0400

>>>   Debugger entered--Lisp error: (void-function kmacro-register-p)
>>>    kmacro-register-p(2)
>>>    cl-typep(2 (satisfies kmacro-register-p))
>>>    cl-typep(2 kmacro-register)
>>>    cl-types-of(2)
>>>    (seq-intersection (cl-types-of 2) types)
>>>    [...]
>> That's an incorrect `cl-deftype` call.  AFAIK this was in `register.el`
>> but I actually removed it from there with:
>>      commit b1407b41a16c4a3ec15c88be91ba0ae1e65c212e
>>      Author: Stefan Monnier <monnier <at> iro.umontreal.ca>
>>      Date:   Tue Apr 29 16:04:54 2025 -0400
>>               register.el: Remove bogus deftypes and fix associated
>> methods
>>                   * lisp/register.el (frame-register, kmacro-register):
>> Remove bogus deftypes.
>>          (register--type) <oclosure>: Fix kmacro method and generalize it to
>>          any OClosure.
>>          (register--type) <frameset-register>: Fix method and move it to ...
>>          * lisp/frameset.el (register--type) <frameset-register>: ... here,
>>          where `frameset-register` is defined.
>> I guess I need to rebase the `cl-types` branch.  🙂
>
> I also see a similar error with type `frame-register':
>
> "cl-types-of frame-register: Symbol’s function definition is void: frameset-register-p"

IIUC: Same error, at the same place, fixed by the same commit, yes.  🙂

> I guess a general solution is much more complex than what I thought.
> And maybe risk to be more costly than the current implementation
> without set of cl-types.

There's probably some way to do better than the naïve loop we have now,
but ... we can keep that for later.

> Please find attached a patch proposal for the branch.  Mainly to
> ensure that types not suitable for cl-defmethod (erroneous type or
> type with arguments) will signal an "Unknown specializer" error when
> trying to use them as argument type in cl-defmethod.

Good point.  But see below.

>           (condition-case-unless-debug e
>               (cl-typep object type)
> -           (error (setq cl--type-list (delq type cl--type-list))
> -                  (warn  "cl-types-of %S: %s"
> -                         type (error-message-string e)))))
> +           (error
> +            ;; Temporarily raise the recursion limit to avoid
> +            ;; another recursion error while processing error.
> +            (let ((max-lisp-eval-depth (+ 800 max-lisp-eval-depth)))

We almost never do that in ELisp except in very specific circumstances
where we decide it's really worth the trouble (even in though in theory
it could be necessary in pretty much all error handlers).
Is there a reason why it's more necessary here than usual?
Maybe a simpler fix is to replace `warn` with `message`?

> +              ;; Remove the type in error from valid specializers.
> +              (cl-remprop type 'cl--class)

I think that's rather drastic.  Just because it signals errors in
`cl-types-of` doesn't mean it can't be useful in other places.

> +              (setq cl--type-dispatch-list (delq type cl--type-dispatch-list))

Why do we need this?  The `(if types` test above presumes that we're OK
with the assumption that we don't need to catch/silence errors for types
in `cl--type-dispatch-list`.

> --- a/lisp/emacs-lisp/cl-macs.el
> +++ b/lisp/emacs-lisp/cl-macs.el
> @@ -3816,18 +3816,22 @@ cl-deftype
>          (cl-callf (lambda (x) (delq declares x)) decls)))
>      (and parents arglist
>           (error "Parents specified, but arglist not empty"))
> -    `(eval-and-compile ;;cl-eval-when (compile load eval)
> -       ;; FIXME: Where should `cl--type-deftype' go?  Currently, code
> -       ;; using `cl-deftype' can use (eval-when-compile (require
> -       ;; 'cl-lib)), so `cl--type-deftype' needs to go either to
> -       ;; `cl-preloaded.el' or it should be autoloaded even when
> -       ;; `cl-lib' is not loaded.
> -       (cl--type-deftype ',name ',parents ',arglist ,docstring)
> -       (define-symbol-prop ',name 'cl-deftype-handler
> -                           (cl-function
> -                            (lambda (&cl-defs ('*) ,@arglist)
> -                              ,@decls
> -                              ,@forms))))))
> +    ;; Don't register types that can't be used without arguments for
> +    ;; dispatch.  They'd signal errors in `cl-types-of'!
> +    (let ((noarg (memq (car arglist) '(nil &rest &optional &keys))))
> +      ;;(or noarg (message "Can't dispatch type with argument, `%S'" name))
> +      `(eval-and-compile ;;cl-eval-when (compile load eval)
> +         ;; FIXME: Where should `cl--type-deftype' go?  Currently, code
> +         ;; using `cl-deftype' can use (eval-when-compile (require
> +         ;; 'cl-lib)), so `cl--type-deftype' needs to go either to
> +         ;; `cl-preloaded.el' or it should be autoloaded even when
> +         ;; `cl-lib' is not loaded.
> +         ,@(if noarg `((cl--type-deftype ',name ',parents ,docstring)))
> +         (define-symbol-prop ',name 'cl-deftype-handler
> +                             (cl-function
> +                              (lambda (&cl-defs ('*) ,@arglist)
> +                                ,@decls
> +                                ,@forms)))))))

I intend to use the `cl--type-class` struct in `cl--class` for purposes
like browsing types (via `C-h o`) like we can do already for structs and
built-in types, so we should register the types with `cl--type-deftype`
regardless if they can be used for dispatch.

So I installed an alternative solution to this problem in
`cl-generic-generalizers`, we call the `cl-type-handler` to make sure
it's valid to use the type without arguments.


        Stefan

Message #191 received at 77725 <at> debbugs.gnu.org (full text, mbox):

From: David Ponce <da_vid <at> orange.fr>
To: Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: 77725 <at> debbugs.gnu.org, Eli Zaretskii <eliz <at> gnu.org>
Subject: Re: bug#77725: 31.0.50; Add support for types accepted by `cl-typep'
 to cl-generic?
Date: Wed, 7 May 2025 12:35:59 +0200

[Message part 1 (text/plain, inline)]

On 2025-05-07 04:51, Stefan Monnier wrote:
[...]
>> I guess a general solution is much more complex than what I thought.
>> And maybe risk to be more costly than the current implementation
>> without set of cl-types.
> 
> There's probably some way to do better than the naïve loop we have now,
> but ... we can keep that for later.

OK.  I wonder if a intermediate acceptable solution could be to manually
map builtin types returned by `type-of' to a symbol that identifies an
unique set of cl-types?  But, as you say we can keep that for later ;-)

>> Please find attached a patch proposal for the branch.  Mainly to
>> ensure that types not suitable for cl-defmethod (erroneous type or
>> type with arguments) will signal an "Unknown specializer" error when
>> trying to use them as argument type in cl-defmethod.
> 
> Good point.  But see below.
> 
>>            (condition-case-unless-debug e
>>                (cl-typep object type)
>> -           (error (setq cl--type-list (delq type cl--type-list))
>> -                  (warn  "cl-types-of %S: %s"
>> -                         type (error-message-string e)))))
>> +           (error
>> +            ;; Temporarily raise the recursion limit to avoid
>> +            ;; another recursion error while processing error.
>> +            (let ((max-lisp-eval-depth (+ 800 max-lisp-eval-depth)))
> 
> We almost never do that in ELisp except in very specific circumstances
> where we decide it's really worth the trouble (even in though in theory
> it could be necessary in pretty much all error handlers).
> Is there a reason why it's more necessary here than usual?
> Maybe a simpler fix is to replace `warn` with `message`?

Yes, `message' will definitely work better, but errors will be less
highlighted.  But a message is always better than nothing ;-)

I wouldn't want ill-defined types entering infinite recursion to
break error handling, just because the depth limit is reached,
thus preventing `warn' to be called.  And no error handling in
`cl-types-of' is not an option IMHO, because Emacs risks to become
unusable if methods based on cl-types, used for example in a display
context, crash.  In fact, I don't like the idea of ​​well-defined
things being disrupted by ill-defined ones ;-)

> 
>> +              ;; Remove the type in error from valid specializers.
>> +              (cl-remprop type 'cl--class)
> 
> I think that's rather drastic.  Just because it signals errors in
> `cl-types-of` doesn't mean it can't be useful in other places.
> 
>> +              (setq cl--type-dispatch-list (delq type cl--type-dispatch-list))
> 
> Why do we need this?  The `(if types` test above presumes that we're OK
> with the assumption that we don't need to catch/silence errors for types
> in `cl--type-dispatch-list`.

I just wanted to keep both lists consistent. If a type is no longer in
the main list, it shouldn't be in the dispatch list either.  But maybe
your last change to `cl-generic-generalizers` is enough?

> 
>> --- a/lisp/emacs-lisp/cl-macs.el
>> +++ b/lisp/emacs-lisp/cl-macs.el
>> @@ -3816,18 +3816,22 @@ cl-deftype
>>           (cl-callf (lambda (x) (delq declares x)) decls)))
>>       (and parents arglist
>>            (error "Parents specified, but arglist not empty"))
>> -    `(eval-and-compile ;;cl-eval-when (compile load eval)
>> -       ;; FIXME: Where should `cl--type-deftype' go?  Currently, code
>> -       ;; using `cl-deftype' can use (eval-when-compile (require
>> -       ;; 'cl-lib)), so `cl--type-deftype' needs to go either to
>> -       ;; `cl-preloaded.el' or it should be autoloaded even when
>> -       ;; `cl-lib' is not loaded.
>> -       (cl--type-deftype ',name ',parents ',arglist ,docstring)
>> -       (define-symbol-prop ',name 'cl-deftype-handler
>> -                           (cl-function
>> -                            (lambda (&cl-defs ('*) ,@arglist)
>> -                              ,@decls
>> -                              ,@forms))))))
>> +    ;; Don't register types that can't be used without arguments for
>> +    ;; dispatch.  They'd signal errors in `cl-types-of'!
>> +    (let ((noarg (memq (car arglist) '(nil &rest &optional &keys))))
>> +      ;;(or noarg (message "Can't dispatch type with argument, `%S'" name))
>> +      `(eval-and-compile ;;cl-eval-when (compile load eval)
>> +         ;; FIXME: Where should `cl--type-deftype' go?  Currently, code
>> +         ;; using `cl-deftype' can use (eval-when-compile (require
>> +         ;; 'cl-lib)), so `cl--type-deftype' needs to go either to
>> +         ;; `cl-preloaded.el' or it should be autoloaded even when
>> +         ;; `cl-lib' is not loaded.
>> +         ,@(if noarg `((cl--type-deftype ',name ',parents ,docstring)))
>> +         (define-symbol-prop ',name 'cl-deftype-handler
>> +                             (cl-function
>> +                              (lambda (&cl-defs ('*) ,@arglist)
>> +                                ,@decls
>> +                                ,@forms)))))))
> 
> I intend to use the `cl--type-class` struct in `cl--class` for purposes
> like browsing types (via `C-h o`) like we can do already for structs and
> built-in types, so we should register the types with `cl--type-deftype`
> regardless if they can be used for dispatch.
> 
> So I installed an alternative solution to this problem in
> `cl-generic-generalizers`, we call the `cl-type-handler` to make sure
> it's valid to use the type without arguments.

I didn't know that.  Fine for me.

While testing, I discovered two nasty bugs in `cl-types-of' illustrated
by the following recipe:

(cl-deftype T1 ()
  "Ill-defined type."
  '(satisfies unknown-predicate))

(cl-types-of 12)
Raise this warning as expected:
Warning (emacs): cl-types-of T1: Symbol’s function definition is void: unknown-predicate

But returns this incorrect list of types:
=> (T1 kmacro-register frame-register fixnum integer number integer-or-marker number-or-marker atom t)

(cl-defmethod test-T1 ((obj T1))
  (format "test-T1 %S" obj))
Should signal an "unknown specializer" for T1, but do not.

Even worse:
(test-T1 nil) => No applicable method, as expected
(test-T1 12)  => "test-T1 12" which is plain wrong

This because always return a wrong cached value from `cl--type-unique':
(cl-types-of 12)
=> (T1 kmacro-register frame-register fixnum integer number integer-or-marker number-or-marker atom t)


The first problem is that the error handler didn't return nil, so
the type in error is pushed in `found'.

The second problem is a nasty side effect of `nreverse' which
causes a wrong key pushed in the `gtype--unique' hash table.

The attached patch solved both issues for me.  To compute the DAG,
I preferred to use a `dolist' loop rather than a `mapcar'+`reverse'
combination, to avoid going through the list twice.


David

[cl-types-of.patch (text/x-patch, attachment)]

Message #194 received at 77725 <at> debbugs.gnu.org (full text, mbox):

From: David Ponce <da_vid <at> orange.fr>
To: Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: 77725 <at> debbugs.gnu.org, Eli Zaretskii <eliz <at> gnu.org>
Subject: Re: bug#77725: 31.0.50; Add support for types accepted by `cl-typep'
 to cl-generic?
Date: Wed, 7 May 2025 15:40:31 +0200

[Message part 1 (text/plain, inline)]

Please find attached another small patch for the method
`cl-generic-generalizers' in cl-lib.el.

It ensures that the derived type is still present in the
`cl--type-list', in order to signal an "unkonw specializer"
error, if the type was removed from the list because it
was in error.

David

[cl-lib.patch (text/x-patch, attachment)]

Message #197 received at 77725 <at> debbugs.gnu.org (full text, mbox):

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: Re: bug#77725: 31.0.50; Add support for types accepted by
 `cl-typep' to cl-generic?
Date: Wed, 07 May 2025 12:19:22 -0400

>>>            (condition-case-unless-debug e
>>>                (cl-typep object type)
>>> -           (error (setq cl--type-list (delq type cl--type-list))
>>> -                  (warn  "cl-types-of %S: %s"
>>> -                         type (error-message-string e)))))
>>> +           (error
>>> +            ;; Temporarily raise the recursion limit to avoid
>>> +            ;; another recursion error while processing error.
>>> +            (let ((max-lisp-eval-depth (+ 800 max-lisp-eval-depth)))
>> We almost never do that in ELisp except in very specific circumstances
>> where we decide it's really worth the trouble (even in though in theory
>> it could be necessary in pretty much all error handlers).
>> Is there a reason why it's more necessary here than usual?
>> Maybe a simpler fix is to replace `warn` with `message`?
>
> Yes, `message' will definitely work better, but errors will be less
> highlighted.  But a message is always better than nothing ;-)
>
> I wouldn't want ill-defined types entering infinite recursion to
> break error handling, just because the depth limit is reached,

As I said, this is a general problem.  Do you have reasons to believe it
is much more prevalent here than elsewhere?

Also, to some extent it could be fixed in a general way (and indeed we
do have code in `Fsignal` to bump up the depth limit when running some
of the error handling code, so it may just need to be adjusted to cover
more cases).
Maybe it should be a separate bug-report/feature-request.

> thus preventing `warn' to be called.  And no error handling in
> `cl-types-of' is not an option IMHO, because Emacs risks to become
> unusable if methods based on cl-types, used for example in a display
> context, crash.

To the extend the method dispatch only looks at types used in existing
methods, this shouldn't be a big issue: hopefully a method wouldn't use
a type whose definition is broken, and if it does we'd hopefully
discover it quickly so it would be fixed quickly as well.

> In fact, I don't like the idea of ​​well-defined
> things being disrupted by ill-defined ones ;-)

But there's a trade-off.  Also it's easier to add error checking after
the fact than to remove it after the fact, so I'd strongly prefer to let
errors be signaled for now.

> While testing, I discovered two nasty bugs in `cl-types-of' illustrated
> by the following recipe:
>
> (cl-deftype T1 ()
>   "Ill-defined type."
>   '(satisfies unknown-predicate))
>
> (cl-types-of 12)
> Raise this warning as expected:
> Warning (emacs): cl-types-of T1: Symbol’s function definition is void: unknown-predicate
>
> But returns this incorrect list of types:
> => (T1 kmacro-register frame-register fixnum integer number
> integer-or-marker number-or-marker atom t)

Oops, good catch, thanks.

> (cl-defmethod test-T1 ((obj T1))
>   (format "test-T1 %S" obj))
> Should signal an "unknown specializer" for T1, but do not.

I don't think it should: T1 *is* a known specializer.  It's just one
whose definition is broken, but we'll only discover that when we
actually try to use it.

> The second problem is a nasty side effect of `nreverse' which
> causes a wrong key pushed in the `gtype--unique' hash table.

Duh, indeed!

> The attached patch solved both issues for me.  To compute the DAG,
> I preferred to use a `dolist' loop rather than a `mapcar'+`reverse'
> combination, to avoid going through the list twice.

I like `mapcar`, but indeed here we do want the reversal that
dolist+push gives us "for free".  I haven't pushed your patch yet
because git.sv.gnu.org is not responding, but I'll do it "soonish".

> Please find attached another small patch for the method
> `cl-generic-generalizers' in cl-lib.el.
>
> It ensures that the derived type is still present in the
> `cl--type-list', in order to signal an "unkonw specializer"
> error, if the type was removed from the list because it
> was in error.

But this can lead to the weird "unknown specializer" error for a type
which *is* known (just defined poorly enough that it signaled an error
at some point).


        Stefan

Message #200 received at 77725 <at> debbugs.gnu.org (full text, mbox):

From: David Ponce <da_vid <at> orange.fr>
To: Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: 77725 <at> debbugs.gnu.org, Eli Zaretskii <eliz <at> gnu.org>
Subject: Re: bug#77725: 31.0.50; Add support for types accepted by `cl-typep'
 to cl-generic?
Date: Wed, 7 May 2025 19:06:19 +0200

On 2025-05-07 18:19, Stefan Monnier wrote:
>> Yes, `message' will definitely work better, but errors will be less
>> highlighted.  But a message is always better than nothing ;-)
>>
>> I wouldn't want ill-defined types entering infinite recursion to
>> break error handling, just because the depth limit is reached,
> 
> As I said, this is a general problem.  Do you have reasons to believe it
> is much more prevalent here than elsewhere?

Without error handling, types that follow a type in error will not be
considered, so the corresponding methods will not be dispatched, so
other errors, etc.

I tried to issue a plain `message' instead of calling `warn', and it
works nicely without the need to increase recursion depth in
relevant cases.  Valid types are still usable, and the message clearly
mention the type that encountered a problem, and what the problem is.
So, for me, it is a clear benefit ;-)

[...]
> I like `mapcar`, but indeed here we do want the reversal that
> dolist+push gives us "for free".  I haven't pushed your patch yet
> because git.sv.gnu.org is not responding, but I'll do it "soonish".

Thank you!
 
>> Please find attached another small patch for the method
>> `cl-generic-generalizers' in cl-lib.el.
>>
>> It ensures that the derived type is still present in the
>> `cl--type-list', in order to signal an "unkonw specializer"
>> error, if the type was removed from the list because it
>> was in error.
> 
> But this can lead to the weird "unknown specializer" error for a type
> which *is* known (just defined poorly enough that it signaled an error
> at some point).

On the other hand, I don't see what advantage there is in allowing the
definition of new methods based on a type that cannot be dispatched
because it is in error.  Unless perhaps these methods become functional
again without doing anything when the type definition has been
fixed.  In this case, I agree it is better not to block
anything.  So I will rely on your experience in this area ;-)

David

Message #203 received at 77725 <at> debbugs.gnu.org (full text, mbox):

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: Re: bug#77725: 31.0.50; Add support for types accepted by
 `cl-typep' to cl-generic?
Date: Wed, 07 May 2025 14:59:40 -0400

> On the other hand, I don't see what advantage there is in allowing the
> definition of new methods based on a type that cannot be dispatched
> because it is in error.  Unless perhaps these methods become functional
> again without doing anything when the type definition has been
> fixed.  In this case, I agree it is better not to block
> anything.  So I will rely on your experience in this area ;-)

I'm just being optimistic.
It may turn out you were right, in which case we'll revisit
this decision.

In the mean time I did some renaming to use the term "derived type",
added some docs, and pushed the result to `master`.


        Stefan

Message #206 received at 77725 <at> debbugs.gnu.org (full text, mbox):

From: David Ponce <da_vid <at> orange.fr>
To: Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: 77725 <at> debbugs.gnu.org, Eli Zaretskii <eliz <at> gnu.org>
Subject: Re: bug#77725: 31.0.50; Add support for types accepted by `cl-typep'
 to cl-generic?
Date: Wed, 7 May 2025 21:33:05 +0200

On 2025-05-07 20:59, Stefan Monnier wrote:
>> On the other hand, I don't see what advantage there is in allowing the
>> definition of new methods based on a type that cannot be dispatched
>> because it is in error.  Unless perhaps these methods become functional
>> again without doing anything when the type definition has been
>> fixed.  In this case, I agree it is better not to block
>> anything.  So I will rely on your experience in this area ;-)
> 
> I'm just being optimistic.
> It may turn out you were right, in which case we'll revisit
> this decision.

Make sense :-)

> 
> In the mean time I did some renaming to use the term "derived type",
> added some docs, and pushed the result to `master`.

You did an impressive work!
Thank you so much for making this breakthrough for Emacs possible!

David

Message #209 received at 77725 <at> debbugs.gnu.org (full text, mbox):

From: David Ponce <da_vid <at> orange.fr>
To: Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: 77725 <at> debbugs.gnu.org, Eli Zaretskii <eliz <at> gnu.org>
Subject: Re: bug#77725: 31.0.50; Add support for types accepted by `cl-typep'
 to cl-generic?
Date: Thu, 8 May 2025 13:55:13 +0200

Just to let you know that I now switched my own libraries to use the
builtin derived types, and they work nicely :-)

I am following your last (great) changes on master, and I wonder if
the method `cl-generic-generalizers' in cl-lib:

  (cl-defmethod cl-generic-generalizers :extra "derived-types" (type)
    "Support for dispatch on derived types, i.e. defined with `cl-deftype'."
    (if (and (symbolp type) (cl-derived-type-class-p (cl--find-class type))
             ;; Make sure this derived type can be used without arguments.
             (let ((expander (get type 'cl-deftype-handler)))
               (and expander (with-demoted-errors "%S" (funcall expander)))))
        (cl--derived-type-generalizers type)
      (cl-call-next-method)))

Could now be simplified like this:

  (cl-defmethod cl-generic-generalizers :extra "derived-types" (type)
    "Support for dispatch on derived types, i.e. defined with `cl-deftype'."
    (if (and (symbolp type) (cl-derived-type-class-p (cl--find-class type))
             ;; Make sure this derived type can be used without arguments.
             (memq type cl--derived-type-list)) ;; <<<<<<<<<<<<<<<<<<<
        (cl--derived-type-generalizers type)
      (cl-call-next-method)))

Because `cl--define-derived-type' ensures that only type without
arguments are in `cl--derived-type-list'.  This will also ensure
that the type had no error (otherwise it would have been removed
from `cl--derived-type-list'), for free ;-)

Thanks!
David

Message #212 received at 77725 <at> debbugs.gnu.org (full text, mbox):

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: Re: bug#77725: 31.0.50; Add support for types accepted by
 `cl-typep' to cl-generic?
Date: Thu, 08 May 2025 10:56:16 -0400

>   (cl-defmethod cl-generic-generalizers :extra "derived-types" (type)
>     "Support for dispatch on derived types, i.e. defined with `cl-deftype'."
>     (if (and (symbolp type) (cl-derived-type-class-p (cl--find-class type))
>              ;; Make sure this derived type can be used without arguments.
>              (let ((expander (get type 'cl-deftype-handler)))
>                (and expander (with-demoted-errors "%S" (funcall expander)))))
>         (cl--derived-type-generalizers type)
>       (cl-call-next-method)))
>
> Could now be simplified like this:
>
>   (cl-defmethod cl-generic-generalizers :extra "derived-types" (type)
>     "Support for dispatch on derived types, i.e. defined with `cl-deftype'."
>     (if (and (symbolp type) (cl-derived-type-class-p (cl--find-class type))
>              ;; Make sure this derived type can be used without arguments.
>              (memq type cl--derived-type-list)) ;; <<<<<<<<<<<<<<<<<<<
>         (cl--derived-type-generalizers type)
>       (cl-call-next-method)))

Yes, or we could check (get type 'cl-deftype-satisfies), but I think
here if (funcall expander) signals an error we want the user to know,
because when (cl-derived-type-class-p (cl--find-class type)) is true, it
means *we* are the generalizer that should be in charge and an expander
error means there's an error elsewhere, most likely in TYPE itself.
That's also why I changed the `ignore-errors` to `with-demoted-errors`.

Actually, I think this expander test should be moved to
`cl--derived-type-generalizers` so we don't keep trying with
other generalizers.


        Stefan

Message #215 received at 77725 <at> debbugs.gnu.org (full text, mbox):

From: David Ponce <da_vid <at> orange.fr>
To: Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: 77725 <at> debbugs.gnu.org, Eli Zaretskii <eliz <at> gnu.org>
Subject: Re: bug#77725: 31.0.50; Add support for types accepted by `cl-typep'
 to cl-generic?
Date: Thu, 8 May 2025 17:27:14 +0200

On 2025-05-08 16:56, Stefan Monnier wrote:
>>    (cl-defmethod cl-generic-generalizers :extra "derived-types" (type)
>>      "Support for dispatch on derived types, i.e. defined with `cl-deftype'."
>>      (if (and (symbolp type) (cl-derived-type-class-p (cl--find-class type))
>>               ;; Make sure this derived type can be used without arguments.
>>               (let ((expander (get type 'cl-deftype-handler)))
>>                 (and expander (with-demoted-errors "%S" (funcall expander)))))
>>          (cl--derived-type-generalizers type)
>>        (cl-call-next-method)))
>>
>> Could now be simplified like this:
>>
>>    (cl-defmethod cl-generic-generalizers :extra "derived-types" (type)
>>      "Support for dispatch on derived types, i.e. defined with `cl-deftype'."
>>      (if (and (symbolp type) (cl-derived-type-class-p (cl--find-class type))
>>               ;; Make sure this derived type can be used without arguments.
>>               (memq type cl--derived-type-list)) ;; <<<<<<<<<<<<<<<<<<<
>>          (cl--derived-type-generalizers type)
>>        (cl-call-next-method)))
> 
> Yes, or we could check (get type 'cl-deftype-satisfies), but I think
> here if (funcall expander) signals an error we want the user to know,
> because when (cl-derived-type-class-p (cl--find-class type)) is true, it
> means *we* are the generalizer that should be in charge and an expander
> error means there's an error elsewhere, most likely in TYPE itself.
> That's also why I changed the `ignore-errors` to `with-demoted-errors`.
> 

Ah, OK, it makes sense. Thank you!

> Actually, I think this expander test should be moved to
> `cl--derived-type-generalizers` so we don't keep trying with
> other generalizers.

It would be better, yes.

Have a nice day.
David

Message #218 received at 77725 <at> debbugs.gnu.org (full text, mbox):

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: Re: bug#77725: 31.0.50; Add support for types accepted by
 `cl-typep' to cl-generic?
Date: Thu, 08 May 2025 17:31:57 -0400

Now that it's in `master`, you can think of the next steps:

- Make it more efficient.  By following the `parents` you can collect
  the set of built-in type in its ancestry and from that compute the set
  of types that `cl-type-of` might return for which there's a change
  that the current type applies.  Basically: walk up the `parents` chain
  until the first built-in type.  And from there, walk *down* from that
  "parent built-in type" to collect all its descendants: if `cl-type-of`
  returns a type which is not among those collected types, then we know
  the value is not in our type.
  E.g. `natnum` would have `integer` as parent, so we'd collect
  `integer`, `fixnum`, and `bignum` as the possible types.
  We could then have a hash-table indexed by built-in type giving the
  set of possible derived types, and we'd add `natnum` to all
  three entries (we may be able to skip `integer`, tho currently we
  don't keep track of which built-in types are abstract like `integer`
  and which ones are concrete (meaning that `cl-type-of` may return
  it)).
  So `cl-types-of` could start by indexing in the hash-table and then
  only test the possibly relevant derived types.

- Make it more automatic: we should be able to guess the `parents`
  automatically in many cases.  Just look for `(and TYPE1 TYPE2 ...)`
  and you immediately know that TYPE1 and TYPE2 are parents.

- Make it better behaved: E.g. if after defining `natnum` I define
  `my-foo` as `(or natnum symbol)`, then `my-foo` is less specific
  than `natnum` but it will appear first in the list, because I defined
  it afterwards.
  To resolve this, I think we need to support a `children` declaration,
  in addition to the `parents` declaration.  Then again maybe we don't
  need a declaration for that and we can extract that info by looking
  for types of the form `(or TYPE1 TYPE2 ...)`.  But we still then need
  to make use of that information to properly order the types.
  Another way to look at this is to try and implement `cl-subtypep`.


        Stefan

Message #221 received at 77725 <at> debbugs.gnu.org (full text, mbox):

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

Hi Stefan,

It seems that since your commit below:

commit	dfafe1830f06634ec779fd62f7081d4cc4f6d3e7
lisp/emacs-lisp/cl-macs.el (cl--define-derived-type): Fix partial bootstrap

None of the derived types mentioned in cl-macs.el are created anymore.
Even after "make bootstrap".

The patch below fixed the problem for me, so I'm wondering if, when you
wrote "unless," you actually meant "when" ;-)

Thanks!

diff --git a/lisp/emacs-lisp/cl-macs.el b/lisp/emacs-lisp/cl-macs.el
index d086afc49e4..d594b3cb233 100644
--- a/lisp/emacs-lisp/cl-macs.el
+++ b/lisp/emacs-lisp/cl-macs.el
@@ -3820,7 +3820,7 @@ cl-deftype
 ;; Thanks to `eval-and-compile', `cl--define-derived-type' is needed
 ;; both at compile-time and at runtime, so we need to double-check.
 (static-if (not (fboundp 'cl--define-derived-type)) nil
-  (unless (fboundp 'cl--define-derived-type)
+  (when (fboundp 'cl--define-derived-type)
     (cl-deftype natnum () (declare (parents integer)) '(satisfies natnump))
     (cl-deftype character () (declare (parents fixnum natnum))
                 '(and fixnum natnum))
 

Message #224 received at 77725 <at> debbugs.gnu.org (full text, mbox):

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: Re: bug#77725: 31.0.50; Add support for types accepted by
 `cl-typep' to cl-generic?
Date: Tue, 13 May 2025 22:39:12 -0400

> -  (unless (fboundp 'cl--define-derived-type)
> +  (when (fboundp 'cl--define-derived-type)

Duh!


        Stefan

Message #227 received at 77725 <at> debbugs.gnu.org (full text, mbox):

From: David Ponce <da_vid <at> orange.fr>
To: Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: 77725 <at> debbugs.gnu.org, Eli Zaretskii <eliz <at> gnu.org>
Subject: Re: bug#77725: 31.0.50; Add support for types accepted by `cl-typep'
 to cl-generic?
Date: Wed, 14 May 2025 10:47:57 +0200

On 2025-05-14 04:39, Stefan Monnier wrote:
>> -  (unless (fboundp 'cl--define-derived-type)
>> +  (when (fboundp 'cl--define-derived-type)
> 
> Duh!
> 
> 
>          Stefan
> 

It's better now, thanks for committing the fix. But I'm still not sure
about the current behavior.

After "make bootstrap", run "emacs -Q" and evaluate the below recipe
in the *scratch* buffer:

cl--derived-type-list
=> nil

(require 'cl-lib)
=> cl-lib

cl--derived-type-list
=> nil

(require 'cl-macs)
=> cl-macs

cl--derived-type-list
=> (real command keyword extended-char base-char character natnum)

So, to create the predefined derived types, it seems that cl-macs
needs to be explicitly loaded. I wonder if this is the expected
behavior?

David

Message #230 received at 77725 <at> debbugs.gnu.org (full text, mbox):

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: Re: bug#77725: 31.0.50; Add support for types accepted by
 `cl-typep' to cl-generic?
Date: Wed, 14 May 2025 12:28:57 -0400

> So, to create the predefined derived types, it seems that cl-macs
> needs to be explicitly loaded. I wonder if this is the expected
> behavior?

Agreed.  But this is the way it's been defined since times immemorial,
so I'm not sure we want to change it.  I'm not saying we don't, because
the new features mean that the circumstances have changed, but I think
I'd rather see first how things play out.

Some of those types are virtually never used, so maybe we'll want to
move some but not all?


        Stefan

Message #233 received at 77725 <at> debbugs.gnu.org (full text, mbox):

From: David Ponce <da_vid <at> orange.fr>
To: Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: 77725 <at> debbugs.gnu.org, Eli Zaretskii <eliz <at> gnu.org>
Subject: Re: bug#77725: 31.0.50; Add support for types accepted by `cl-typep'
 to cl-generic?
Date: Thu, 15 May 2025 07:02:23 +0200

On 2025-05-14 18:28, Stefan Monnier wrote:
>> So, to create the predefined derived types, it seems that cl-macs
>> needs to be explicitly loaded. I wonder if this is the expected
>> behavior?
> 
> Agreed.  But this is the way it's been defined since times immemorial,
> so I'm not sure we want to change it.  I'm not saying we don't, because
> the new features mean that the circumstances have changed, but I think
> I'd rather see first how things play out.

That's fine with me.  I asked because it seemed to me that it wasn't
recommended to load cl-macs but rather cl-lib.

> Some of those types are virtually never used, so maybe we'll want to
> move some but not all?

To be honest, I don't know if/when these types are used.

Thanks
David

Message #236 received at 77725 <at> debbugs.gnu.org (full text, mbox):

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: Re: bug#77725: 31.0.50; Add support for types accepted by
 `cl-typep' to cl-generic?
Date: Fri, 16 May 2025 10:30:00 -0400

>>> So, to create the predefined derived types, it seems that cl-macs
>>> needs to be explicitly loaded. I wonder if this is the expected
>>> behavior?
>> Agreed.  But this is the way it's been defined since times immemorial,
>> so I'm not sure we want to change it.  I'm not saying we don't, because
>> the new features mean that the circumstances have changed, but I think
>> I'd rather see first how things play out.
> That's fine with me.  I asked because it seemed to me that it wasn't
> recommended to load cl-macs but rather cl-lib.

Yes, but that worked OK because in order to *use* those types you needed
to use `cl-deftype` or `cl-typep`, both of which are autoloaded from
`cl-macs.el`.

>> Some of those types are virtually never used, so maybe we'll want to
>> move some but not all?
> To be honest, I don't know if/when these types are used.

`grep` can provide some answers to that question.  🙂


        Stefan

Message #239 received at 77725 <at> debbugs.gnu.org (full text, mbox):

From: David Ponce <da_vid <at> orange.fr>
To: Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: 77725 <at> debbugs.gnu.org, Eli Zaretskii <eliz <at> gnu.org>
Subject: Re: bug#77725: 31.0.50; Add support for types accepted by `cl-typep'
 to cl-generic?
Date: Sat, 17 May 2025 16:41:24 +0200

[Message part 1 (text/plain, inline)]

[...]
>> That's fine with me.  I asked because it seemed to me that it wasn't
>> recommended to load cl-macs but rather cl-lib.
> 
> Yes, but that worked OK because in order to *use* those types you needed
> to use `cl-deftype` or `cl-typep`, both of which are autoloaded from
> `cl-macs.el`.

You are right, I forgot that, sorry.

>>> Some of those types are virtually never used, so maybe we'll want to
>>> move some but not all?
>> To be honest, I don't know if/when these types are used.
> 
> `grep` can provide some answers to that question.  🙂

Sure ;-)



Please find attached a proposal to improve error handling in
`cl-types-of'.  Ultimately, I think you were right and it is better to
simply report derived type errors to the caller and abort processing,
but while also preventing their recurrence as much as possible :-)

So my proposal is to still handle any error on a derived type, in
order to disable the type as is currently done by removing it from the
list of types; but, instead of warn, raise a new `cl-type-error'
mentioning the type in error and the underlying error.  Here are some
simple examples for you to observe the result.

(cl-deftype T1 ()
  '(satisfies plusp))

(cl-types-of -0.5)
=> (real float number number-or-marker atom t)

(cl-types-of 12)
=> (T1 real base-char character fixnum natnum integer number integer-or-marker number-or-marker atom t)

(cl-types-of "12")
=> Error on derived type: T1, (wrong-type-argument number-or-marker-p "12")

(cl-deftype T2 ()
  `(satisfies ,(lambda (o) (memq 'T1 (cl-types-of o)))))

(cl-types-of "12")
=> Error on derived type: T2, (excessive-lisp-nesting 1601)

Does it make sense?

Thanks!
David

[cl-extra.patch (text/x-patch, attachment)]

Message #242 received at 77725 <at> debbugs.gnu.org (full text, mbox):

From: David Ponce <da_vid <at> orange.fr>
To: Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: 77725 <at> debbugs.gnu.org, Eli Zaretskii <eliz <at> gnu.org>
Subject: Re: bug#77725: 31.0.50; Add support for types accepted by `cl-typep'
 to cl-generic?
Date: Mon, 19 May 2025 10:08:17 +0200

[Message part 1 (text/plain, inline)]

> Please find attached a proposal to improve error handling in
> `cl-types-of'.  Ultimately, I think you were right and it is better to
> simply report derived type errors to the caller and abort processing,
> but while also preventing their recurrence as much as possible :-)
> 
> So my proposal is to still handle any error on a derived type, in
> order to disable the type as is currently done by removing it from the
> list of types; but, instead of warn, raise a new `cl-type-error'
> mentioning the type in error and the underlying error.  Here are some
> simple examples for you to observe the result.
> 
> (cl-deftype T1 ()
>    '(satisfies plusp))
> 
> (cl-types-of -0.5)
> => (real float number number-or-marker atom t)
> 
> (cl-types-of 12)
> => (T1 real base-char character fixnum natnum integer number integer-or-marker number-or-marker atom t)
> 
> (cl-types-of "12")
> => Error on derived type: T1, (wrong-type-argument number-or-marker-p "12")
> 
> (cl-deftype T2 ()
>    `(satisfies ,(lambda (o) (memq 'T1 (cl-types-of o)))))
> 
> (cl-types-of "12")
> => Error on derived type: T2, (excessive-lisp-nesting 1601)
> 
> Does it make sense?

Please find attached a better patch, and a possible change log below.
Thanks
David

2025-05-19  David Ponce  <da_vid <at> orange.fr>

	Signal a `cl-type-error' instead of warning when a derived type
	encounters an error.

	* lisp/emacs-lisp/cl-extra.el (cl-type-error): New error symbol.
	(cl-types-of): Use it.

[cl-extra-V1.patch (text/x-patch, attachment)]

Message #245 received at 77725 <at> debbugs.gnu.org (full text, mbox):

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: Re: bug#77725: 31.0.50; Add support for types accepted by
 `cl-typep' to cl-generic?
Date: Mon, 19 May 2025 18:05:03 -0400

>  ;;;###autoload
>  (defun cl-types-of (object &optional types)
>    "Return the atomic types OBJECT belongs to.
> @@ -1044,11 +1046,18 @@ cl-types-of
>               (funcall pred object)
>             (condition-case-unless-debug e
>                 (funcall pred object)
> -             (error (setq cl--derived-type-list
> -                          (delq type cl--derived-type-list))
> -                    (warn  "cl-types-of %S: %s"
> -                           type (error-message-string e))
> -                    nil)))
> +             ;; Catching `cl-type-error' means it comes from recursive
> +             ;; calls to `cl-types-of', so propagate the error until
> +             ;; escaping the outermost call to `cl-types-of'.
> +             (cl-type-error
> +              (signal (car e) (cdr e)))
> +             (error
> +              ;; If checking TYPE signals an error, disable TYPE and
> +              ;; signal a `cl-type-error' error mentioning TYPE and
> +              ;; the underlying error.
> +              (setq cl--derived-type-list
> +                    (delq type cl--derived-type-list))
> +              (signal 'cl-type-error (list type e)))))
>           (push type found))))
>      (push (cl-type-of object) found)
>      ;; Return the list of types OBJECT belongs to, which is also the list

Hmm... usually we have two preoccupations:

- Notify the existence of a problem.
- Try and provide "graceful degradation", i.e. still do something
  useful, despite the problem.
- Make it easy to debug.

Both the "before" and "after" versions of the code above seem to satisfy
those needs in more or less the same way, but your new code is more
complex, so I'm wondering what do you see as the advantage?

BTW, a related option is to do something like:

    (let ((error t))
      (unwind-protect
          (prog1 (funcall pred object)
                 (setq error nil))
        (when error
          (setq cl--derived-type-list
                (delq type cl--derived-type-list)))))


- Stefan

Message #248 received at 77725 <at> debbugs.gnu.org (full text, mbox):

From: David Ponce <da_vid <at> orange.fr>
To: Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: 77725 <at> debbugs.gnu.org, Eli Zaretskii <eliz <at> gnu.org>
Subject: Re: bug#77725: 31.0.50; Add support for types accepted by `cl-typep'
 to cl-generic?
Date: Wed, 21 May 2025 11:00:10 +0200

[Message part 1 (text/plain, inline)]

On 2025-05-20 00:05, Stefan Monnier wrote:
>>   ;;;###autoload
>>   (defun cl-types-of (object &optional types)
>>     "Return the atomic types OBJECT belongs to.
>> @@ -1044,11 +1046,18 @@ cl-types-of
>>                (funcall pred object)
>>              (condition-case-unless-debug e
>>                  (funcall pred object)
>> -             (error (setq cl--derived-type-list
>> -                          (delq type cl--derived-type-list))
>> -                    (warn  "cl-types-of %S: %s"
>> -                           type (error-message-string e))
>> -                    nil)))
>> +             ;; Catching `cl-type-error' means it comes from recursive
>> +             ;; calls to `cl-types-of', so propagate the error until
>> +             ;; escaping the outermost call to `cl-types-of'.
>> +             (cl-type-error
>> +              (signal (car e) (cdr e)))
>> +             (error
>> +              ;; If checking TYPE signals an error, disable TYPE and
>> +              ;; signal a `cl-type-error' error mentioning TYPE and
>> +              ;; the underlying error.
>> +              (setq cl--derived-type-list
>> +                    (delq type cl--derived-type-list))
>> +              (signal 'cl-type-error (list type e)))))
>>            (push type found))))
>>       (push (cl-type-of object) found)
>>       ;; Return the list of types OBJECT belongs to, which is also the list
> 
> Hmm... usually we have two preoccupations:
> 
> - Notify the existence of a problem.
> - Try and provide "graceful degradation", i.e. still do something
>    useful, despite the problem.
> - Make it easy to debug.
> 
> Both the "before" and "after" versions of the code above seem to satisfy
> those needs in more or less the same way, but your new code is more
> complex, so I'm wondering what do you see as the advantage?
> 
> BTW, a related option is to do something like:
> 
>      (let ((error t))
>        (unwind-protect
>            (prog1 (funcall pred object)
>                   (setq error nil))
>          (when error
>            (setq cl--derived-type-list
>                  (delq type cl--derived-type-list)))))
> 
> 

My code is slightly more complex to correctly handle recursive errors:

1. Avoid disabling again and again the type in error following nested
   `condition-case'.  Currently cleanup is just a `delq', but maybe in
   the future it could be more, or delegated to a user function, for
   example.  So, IMO, the behavior should be consistent, and
   regardless of the error, 1 error => 1 cleanup ;-)

2. Clearly mention the type in error to help fixing the issue.

For instance eval this derived type definition, badly recursive:

 (cl-deftype T1 ()
  `(satisfies ,(lambda (o) (memq 'T1 (cl-types-of o)))))

Then: (cl-types-of "any-object")

My proposal shows this message in the echo area:

  Error on derived type: T1, (excessive-lisp-nesting 1601)

And this line in the *Message* buffer:

  forward-sexp-default-function: Error on derived type: T1, (excessive-lisp-nesting 1601)

Your `unwind' proposal shows this message in the echo area:

  Args out of range: 79, 83

And these lines in the *Message* buffer:

  cl-prin1: (error "Lisp nesting exceeds ‘max-lisp-eval-depth’") [10 times]
  make-text-button: Args out of range: 79, 83

If my proposal is too complex, at least, the current behavior using
`warn' is better.

Thanks
David

I reattached my patch where an autoload cookie was missing.

[cl-extra-V2.patch (text/x-patch, attachment)]

Message #251 received at 77725 <at> debbugs.gnu.org (full text, mbox):

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: Re: bug#77725: 31.0.50; Add support for types accepted by
 `cl-typep' to cl-generic?
Date: Wed, 21 May 2025 11:30:47 -0400

> My code is slightly more complex to correctly handle recursive errors:
>
> 1. Avoid disabling again and again the type in error following nested
>    `condition-case'.  Currently cleanup is just a `delq', but maybe in
>    the future it could be more, or delegated to a user function, for
>    example.  So, IMO, the behavior should be consistent, and
>    regardless of the error, 1 error => 1 cleanup ;-)

To me, this smells of over-engineering.

> 2. Clearly mention the type in error to help fixing the issue.
>
> For instance eval this derived type definition, badly recursive:
>
>  (cl-deftype T1 ()
>   `(satisfies ,(lambda (o) (memq 'T1 (cl-types-of o)))))
>
> Then: (cl-types-of "any-object")
>
> My proposal shows this message in the echo area:
>
>   Error on derived type: T1, (excessive-lisp-nesting 1601)

Errors here should be rare (and get ever more rare the more this
functionality is used), so I don't think we should focus on making error
messages pretty.  We should just focus on making them not debilitating
while still allowing the usual debugging tools to do their job.

[ Also, I don't think the above error is representative of the kind of
  errors we should expect to see.  ]


        Stefan

Message #254 received at 77725 <at> debbugs.gnu.org (full text, mbox):

From: David Ponce <da_vid <at> orange.fr>
To: Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: 77725 <at> debbugs.gnu.org, Eli Zaretskii <eliz <at> gnu.org>
Subject: Re: bug#77725: 31.0.50; Add support for types accepted by `cl-typep'
 to cl-generic?
Date: Wed, 21 May 2025 20:59:48 +0200

On 2025-05-21 17:30, Stefan Monnier wrote:
>> My code is slightly more complex to correctly handle recursive errors:
>>
>> 1. Avoid disabling again and again the type in error following nested
>>     `condition-case'.  Currently cleanup is just a `delq', but maybe in
>>     the future it could be more, or delegated to a user function, for
>>     example.  So, IMO, the behavior should be consistent, and
>>     regardless of the error, 1 error => 1 cleanup ;-)
> 
> To me, this smells of over-engineering.

Replacing 4 lines of code with 5 is not what I would call over-engineering ;-)

> 
>> 2. Clearly mention the type in error to help fixing the issue.
>>
>> For instance eval this derived type definition, badly recursive:
>>
>>   (cl-deftype T1 ()
>>    `(satisfies ,(lambda (o) (memq 'T1 (cl-types-of o)))))
>>
>> Then: (cl-types-of "any-object")
>>
>> My proposal shows this message in the echo area:
>>
>>    Error on derived type: T1, (excessive-lisp-nesting 1601)
> 
> Errors here should be rare (and get ever more rare the more this
> functionality is used), so I don't think we should focus on making error
> messages pretty.  We should just focus on making them not debilitating
> while still allowing the usual debugging tools to do their job.

I was not focusing on making error messages pretty but error data useful ;-)

> 
> [ Also, I don't think the above error is representative of the kind of
>    errors we should expect to see.  ]

That's fine with me. After all, it was just a suggestion ;-)

David

Message #257 received at 77725 <at> debbugs.gnu.org (full text, mbox):

From: David Ponce <da_vid <at> orange.fr>
To: Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: 77725 <at> debbugs.gnu.org, Eli Zaretskii <eliz <at> gnu.org>
Subject: Re: bug#77725: 31.0.50; Add support for types accepted by `cl-typep'
 to cl-generic?
Date: Sat, 24 May 2025 12:52:08 +0200

[Message part 1 (text/plain, inline)]

Hello Stefan,

Please find below the proposal for a new approach to speed up dispatch
of methods with derived type specializers.

Currently, to dispatch a method with derived type specializers, all
the derived types of all such methods are checked.  This is not very
efficient when the number of methods using derived types becomes high.

My reasoning is that to achieve the same only the method specializers
of the called generic function need to be checked.  For instance to
dispatch the below generic function `foo:

(cl-defmethod foo ((arg1 A) (arg2 B))
  ...
  )
(cl-defmethod foo ((arg1 A) (arg2 C))
  ...
  )

It is enough to test that the type of the objects passed to `foo'
belongs to the list of derived types (A B C).
              
Thus, the number of types to check will depend on the number of
different derived types "specializers" used in methods defined for one
generic function.  IMO, this number should remain very reasonable for
a given generic function.

The other advantage of this approach is that it limits the impact of
an ill-defined type to only the methods that use it, making error
handling in `cl-types-of' unnecessary.

It turns out that the dispatcher produced by the function
`cl--generic-get-dispatcher' already captures the list of methods of
the called generic function in its lexical environment.  So I modified
`cl--generic-get-dispatcher' to be able to pass this method list to
the tagcode function via an optional additional argument.  Then, I
modified the tagcode function of `cl--derived-type-generalizer' to
compute a "dispatch" list from the list of methods defined for the
called generic function.  This calculation is memoized to save time,
since the methods of a generic function shouldn't change much, except
perhaps during development.  Finally, I simplified the `cl-types-of'
function by removing error handling, no longer really useful here.

The tests in `cl-types-test' pass with the new implementation, which
also works well in some of my libraries I use daily :-)

I hope I didn't miss anything important!
Your opinion will obviously be more than welcome ;-)

Patch attached and a possible change log below.

Thanks!
David

2025-05-24  David Ponce  <da_vid <at> orange.fr>

	To speed up dispatch of methods with derived types specializers,
	limit the list of types that need to be checked to those used in
	methods specializers of the called generic function.

	* lisp/emacs-lisp/cl-generic.el (cl--generic-get-dispatcher): Add
	an optional second argument to the tagcode function to receive the
	methods of the called generic function.
        (cl--generic-derived-generalizer): Fix arglist of the tagcode
	function.

	* lisp/emacs-lisp/cl-extra.el (cl-types-of): There is no need to
	filter out errors: we can assume that the dispatch method is used
	only on sanely-defined types; when "cl-types-of" is called
	directly, whe can use the usual debugging tools to analyze and fix
	ill-defined types.
	(cl--derived-type-dispatch-memo): New variable.
	(cl--derived-type-dispatch-list): Replace variable by a function.
	(cl--derived-type-generalizer): Call it in the tagcode function.
	(cl--derived-type-generalizers): Simplify.

[cl-types-V0.patch (text/x-patch, attachment)]

Message #260 received at 77725 <at> debbugs.gnu.org (full text, mbox):

From: David Ponce <da_vid <at> orange.fr>
To: Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: 77725 <at> debbugs.gnu.org, Eli Zaretskii <eliz <at> gnu.org>
Subject: Re: bug#77725: 31.0.50; Add support for types accepted by `cl-typep'
 to cl-generic?
Date: Thu, 5 Jun 2025 11:14:59 +0200

[Message part 1 (text/plain, inline)]

On 2025-05-24 12:52, David Ponce wrote:
> Hello Stefan,
> 
> Please find below the proposal for a new approach to speed up dispatch
> of methods with derived type specializers.

Hello Stefan,

Following our last exchange in French, to feed our discussion more
concretely, please find attached a new patch that explore further the
idea of removing the global variable `cl--derived-type-list', and make
`cl-types-of' a private function named `cl--derived-type-specializers'
with a mandatory argument to receive the list of dispatch types to
check.

The patch also improve a little the `cl-deftype' macro to allow
dispatching of atomic derived type with both optional
arguments and parents, like in this example:

(cl-deftype my-integer ()
  'integer)

;; Currently the below declaration is not valid because ARGLIST and
;; PARENTS are both non-nil.
(cl-deftype unsigned-byte (&optional bits)
  "Unsigned integer."
  (declare (parents my-integer))
  `(integer 0 ,(if (memq bits '(nil *)) bits (1- (ash 1 bits)))))

(cl-defmethod test-byte ((this my-integer))
  (format "%S is an integer" this))

(cl-defmethod test-byte ((this unsigned-byte))
  (format "%S is an unsigned byte - %s" this
          (cl-call-next-method)))

David

[cl-types-V2.patch (text/x-patch, attachment)]

Previous Next

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