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

Previous Next

Full log

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

Previous Next

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