[closer-devel] Introducing new "type" classes

Sun Feb 17 18:08:54 UTC 2008

On 16 Feb 2008, at 18:40, Marco Antoniotti wrote:

> Hi Pascal
>
> On Feb 16, 2008, at 17:17 , Pascal Costanza wrote:
>
>> Hey,
>>
>> On 15 Feb 2008, at 16:58, Marco Antoniotti wrote:
>>
>>> Hi
>>>
>>> this is a little OT wrt Closer, but this is probably the venue  
>>> where most of the expertise meets.
>>>
>>> In CLOS you have classes for INTEGER, REAL etc etc.  You can then  
>>> write methods like
>>>
>>> 	(defmethod foo ((i integer)) ...)
>>>
>>> Now, we cannot write methods like
>>>
>>> 	(defmethod foo ((i (integer 1 42))) ...)
>>>
>>> and this may be ok.
>>
>> That's actually relatively easy: Just write a macro 'my-defmethod  
>> that expands into a number of methods with eql specializers (42  
>> different methods in this case). ;)
>
> That is another answer.  I was asking for the question. :)

:)

>>> However, i am playing around with things like
>>>
>>> 	(deftype positive-integer () '(integer 1 *))
>>>
>>> is there any magic I can conjure to (semi) portably having a class  
>>> named POSITIVE-INTEGER that actually corresponds to the type  
>>> definition?
>>
>> The specializers are used to determine the applicability of  
>> methods. The result of compute-applicable-methods must be a list of  
>> applicable method, sorted according to their specificity (!). This  
>> is where the problem is: As soon as you try to use more general  
>> types than classes and eql specializers, you get into trouble with  
>> sorting. For example, assume you have two methods specilaized on  
>> the types (satisfies oddp) and (satisfies primep), and both  
>> trigger, which one gets executed first?
>>
>> The general problem here is that you need to analyze the  
>> specificity statically, without running any of the predicates. This  
>> is generally not possible. (Consider (satisfies haltp). ;)
>>
>> If you allow for subsets, you get similar problems, although  
>> superficially speaking, they seem more tractable. But consider you  
>> have two methods specialized on the types (integer 0 *) and  
>> (integer 1 10) - which one is more specific? Hard to tell.
>
> I have not read the papers by Christophe and Jim you mention below  
> (let me look for them), but I guess everything boils down to the  
> definition of "specificity".

Yep.

> For classes and EQL specializers you have a notion, but why should  
> this not be hammered into a subset relationship, ANSI 4.2.2 "Type  
> Relationships" notwithstanding?
>
> Given that SATIFIES is a no-no in any case when wanting to do  
> something useful with types (at least w.r.t. compilation: Python  
> does not deal with SATISFIES and, last I checked, AND types are  
> dealt with in a limited way) and that therefore we can readily hide  
> it under the carpet for the time being, we have that (integer 1 10)  
> is a subset of (integer 0 *), thus I would consider it more  
> specific.  The issues really start when you deal with intersections,  
> e.g.
>
> (defmethod foo ((i (integer 0 100))) ...)
> (defmethod foo ((j (integer 32 1024))) ...)
>
> (foo 42)
>
> But even in this case you could raise an error at (re)definition  
> time because you are defining a method which would require a runtime  
> choice (in the above example at the definition time of the second  
> FOO method).
>
> Am I making sense or is there a hole somewhere?  Are there type  
> subset tests that could not be made at (re)definition time?

Hm. could make sense.

Thinking out aloud again: You could even defer the error to invocation  
time, because maybe the conflict never arises. (Hmm, hmm... ;)

Another issue that may come up: The idea of using classes for dispatch  
is interesting because it gives you pretty good efficiency. Method  
dispatch works by looking at the classes of all the required  
arguments, and looking up applicable methods for those classes. This  
can be implemented very efficiently, both in terms of space and lookup  
time. Eql specializers already make that a bit harder, and subset  
relationships could be even more problematic. (But maybe not...)

In my personal opinion, I think the protocol for eql specializers is  
misdesigned anyway. Whenever defmethod sees an (eql xyz) form, it  
turns it into an instance of eql-specializer, and such instances are  
used for method lookup. Since eql-specializers are so different from  
class specializers, the lookup has to be split into two different  
steps, compute-applicable-methods-using-classes and compute-applicable- 
methods. C-a-m-u-c signals an 'error' in case classes are not  
sufficient to determine method applicability. I think there is a lost  
opportunity for having a more streamlined protocol.

What I would envision is something like this: An eql-specializer could  
actually be an instance of a class generated on the fly which is a  
subclass of the class of the object in question. So, say, you have the  
following definitions:

(defclass person (...) ...)

(defvar *a-person* (make-instance 'person ...))

(defmethod foo ((obj (eql *a-person*))) ...)

The idea is that (intern-eql-specializer *a-person*) should return an  
object whose class is a generated subclass of person.

This would allow for having a single generic function compute- 
applicable-methods-using-specializer, instead of two separate ones. In  
order to perform method dispatch, the discriminating function would  
have to look for the specializers of the objects, not the classes.  
Roughly as follows:

(defmethod compute-discriminating-function ((gf standard-generic- 
function))
   (lambda (&rest args)
     (let* ((specializers (mapcar #'specializer-of args))
            (applicables  (compute-applicable-methods-using- 
specializers gf specializers))
            (effective-method (compute-effective-method gf (generic- 
function-method-combination gf) applicables))
            (effective-metod-function (compute-effective-method- 
function gf effective-method)))
       (apply effective-method-function args))))

The hard part would be to find an efficient implementation for  
specializer-of. One idea would be to add a tag bit to objects that  
indicate whether they are used as eql specializers anywhere in a  
system, and if that tag bit is not set, specializer-of can just be  
implemented with class-of, otherwise it will call intern-eql- 
specializer. If on top of that, specializer-of is a generic function,  
one could then maybe add functionalities like dispatching on set  
types, as you suggest, for one's own generic function classes.

That's a very rough idea, there are probably a couple of devils in the  
details...

Just brainstorming...

Pascal

-- 
1st European Lisp Symposium (ELS'08)
http://prog.vub.ac.be/~pcostanza/els08/

Pascal Costanza, mailto:pc at p-cos.net, http://p-cos.net
Vrije Universiteit Brussel, Programming Technology Lab
Pleinlaan 2, B-1050 Brussel, Belgium