Introducing new "type" classes

[Marco Antoniotti]

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.

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?

Cheers

--
Marco

[Marco Antoniotti]

PS. I know about ANSI 4.2.2 "Type Relationships".

Marco

Post by Marco Antoniotti
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.
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?
Cheers
--
Marco
_______________________________________________
closer-devel mailing list
http://common-lisp.net/cgi-bin/mailman/listinfo/closer-devel

--
Marco Antoniotti

[Pascal Costanza]

Hey,

Post by Marco Antoniotti
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). ;)

Post by Marco Antoniotti
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.

Christophe Rhodes has worked on the technical issues in the CLOS MOP
to be able to plug in new specializers, and implemented this for SBCL.
However, this covers 'only' the technical aspects of the MOP, not the
semantic issues sketched above. Jim Newton has come up with an idea
how to turn the decision which methods are more specific into a
property of the respective generic function. This doesn't really solve
the issue, you still need ad-hoc solutions, but at least they can look
different for different generic functions, which I think is an
improvement. (Both Christophe and Jim have written papers about their
ideas, presented at last year's European Lisp Workshop.)

For pragmatic purposes, a compromise could be to have a two-step
process: Base the applicability on classes and eql-specializers, and
then use a filter to get rid of methods you actually don't want. A
method definition could then look like this:

(defmethod* foo ((x integer))
(:filter (x (integer 1 10)))
...)

Maybe this could be added as new qualifiers and the filtering could
then be part of a user-defined method combination. This would then be
portable.

However, I don't know how much this would be an improvement over this:

(defmethod foo ((x integer))
(unless (typep x '(integer 1 10))
(return-from foo (call-next-method)))
...)

[These thoughts are a bit random, sorry for that. But they are a rough
summary of my views on this issue I have developed so far...]


Pascal

[Ross Jekel]

Hello,

There has been a good summary of the issues here already. I thought I
would mention an example of a similar system (RuleDispatch by Phillip
J. Eby) in Python (sorry) that takes the approach of allowing
ambiguity in the dispatch rules, only throwing an exception at runtime
if it actually occurs. In Python the throwing of the
dispatch.interfaces.AmbiguousMethod exception pretty much means your
call is over, but with Lisp one might be able to define conditions
that would allow the user to do custom handlers to resolve the
ambiguity.

Just a thought. This Charming Python article
(http://www-128.ibm.com/developerworks/library/l-cppeak2/) and these
slides (http://peak.telecommunity.com/PyCon05Talk/PyCon05Talk.html)
might give you some ideas. Mr. Eby based the dispatching engine on two
papers mentioned in slide 12
(http://peak.telecommunity.com/PyCon05Talk/img12.html).

Ross

[Michael Weber]

Post by Pascal Costanza
For pragmatic purposes, a compromise could be to have a two-step
process: Base the applicability on classes and eql-specializers,
and then use a filter to get rid of methods you actually don't
(defmethod* foo ((x integer))
(:filter (x (integer 1 10)))
...)
Maybe this could be added as new qualifiers and the filtering could
then be part of a user-defined method combination. This would then
be portable.
(defmethod foo ((x integer))
(unless (typep x '(integer 1 10))
(return-from foo (call-next-method)))
...)
[These thoughts are a bit random, sorry for that. But they are a
rough summary of my views on this issue I have developed so far...]

A generalization of the above would be predicate dispatch:
* Ernst et al: "Predicate Dispatching: A Unified Theory of Dispatch"
<http://citeseer.ist.psu.edu/ernst98predicate.html>
* Ucko: "Predicate Dispatching in the Common Lisp Object System"
<http://citeseer.ist.psu.edu/526172.html>

I forgot what Ucko does about the specificity issue.


Cheers,
Michael

[Pascal Costanza]

Post by Michael Weber
* Ernst et al: "Predicate Dispatching: A Unified Theory of
Dispatch" <http://citeseer.ist.psu.edu/ernst98predicate.html>
* Ucko: "Predicate Dispatching in the Common Lisp Object System" <http://citeseer.ist.psu.edu/526172.html
I forgot what Ucko does about the specificity issue.

Those approaches typically restrict the predicate language such that
it becomes statically tractable (so not Turing complete).


Pascal

[Marco Antoniotti]

Hi Pascal

Post by Pascal Costanza
Hey,

Post by Marco Antoniotti
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. :)

Post by Pascal Costanza

Post by Marco Antoniotti
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". 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?

Post by Pascal Costanza
Christophe Rhodes has worked on the technical issues in the CLOS
MOP to be able to plug in new specializers, and implemented this
for SBCL. However, this covers 'only' the technical aspects of the
MOP, not the semantic issues sketched above. Jim Newton has come up
with an idea how to turn the decision which methods are more
specific into a property of the respective generic function. This
doesn't really solve the issue, you still need ad-hoc solutions,
but at least they can look different for different generic
functions, which I think is an improvement. (Both Christophe and
Jim have written papers about their ideas, presented at last year's
European Lisp Workshop.)
For pragmatic purposes, a compromise could be to have a two-step
process: Base the applicability on classes and eql-specializers,
and then use a filter to get rid of methods you actually don't
(defmethod* foo ((x integer))
(:filter (x (integer 1 10)))
...)
Maybe this could be added as new qualifiers and the filtering could
then be part of a user-defined method combination. This would then
be portable.
(defmethod foo ((x integer))
(unless (typep x '(integer 1 10))
(return-from foo (call-next-method)))
...)

I do not like either cases. They break down the modularity of
defmethod and do amount to something like

(defmethod (x y .. (i integer) .. w)
(filter (i integer)
((integer 0 42) 42)
((integer -42 0) -42)
(integer 0)))

where FILTER is a macro (macrolet? automagicallymacroizedmacro? that
works kind of TYPECASE and ensures that all the types in the clauses
heads are SUBTYPEP of INTEGER. This gives you full control, and it
is readily built, but it does break the modularity and the magic of
DEFMETHOD.

Post by Pascal Costanza
[These thoughts are a bit random, sorry for that. But they are a
rough summary of my views on this issue I have developed so far...]

No no. This is all good and helpful.


Cheers

Marco



--
Marco Antoniotti

[Pascal Costanza]

Post by Marco Antoniotti
Hi Pascal

Post by Pascal Costanza
Hey,

Post by Marco Antoniotti
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. :)

:)

Post by Marco Antoniotti

Post by Pascal Costanza

Post by Marco Antoniotti
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.

Post by Marco Antoniotti
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

[Marco Antoniotti]

Post by Pascal Costanza

Post by Marco Antoniotti
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... ;)

Yes, but I would not allow that. First of all I think it is easier
to check for these things at (re)definition time, secondly, I believe
in helping the compiler and letting it help me (as an aside, I am
nonplussed by the comment "don't lie to the compiler" comment you get
sometime).

Post by Pascal Costanza
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
(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.

Yes. That is what I had in mind as well. Note that your example is
a little misleading. If next I do

(setf *a-person* (make-instance 'person))

(foo *a-person*)

I get an error.

This means that the generation on the fly of the singleton classes is
warranted. But for subset relationships you have to jump through a
number of hoops, as you cannot subclass INTEGER etc etc.

Post by Pascal Costanza
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
(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.

I think I lost you here.... AFAIU, why should you not make
SPECIALIZER-OF dependent on the GF as well? That would seem to me to
be the right anchor for this kind of information.

Post by Pascal Costanza
That's a very rough idea, there are probably a couple of devils in
the details...
Just brainstorming...

Of course... but maybe something interesting will come out of it.

Cheers

Marco

PS. Can you point me in the direction of the papers by Chris and Jim?