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

[Stefan Monnier]

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