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

Previous Next

Full log

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

Previous Next

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