[ clisp-Bugs-1591671 ] typep and subtypep fail on forward-referenced-class

[SourceForge.net <no...@so...>]

Bugs item #1591671, was opened at 2006-11-06 22:59
Message generated for change (Comment added) made by pcostanza
You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=101355&aid=1591671&group_id=1355

Please note that this message will contain a full copy of the comment thread,
including the initial issue submission, for this request,
not just the latest update.
Category: clisp
Group: ANSI compliance issue
Status: Closed
Resolution: Rejected
Priority: 5
Private: No
Submitted By: Pascal Costanza (pcostanza)
Assigned to: Bruno Haible (haible)
Summary: typep and subtypep fail on forward-referenced-class

Initial Comment:
Assume the following definition:

(defclass test (forward) ())

Assume further that 'forward is not defined as a class yet, so it is a 
forward referenced class.

In this case, the following forms fail in clisp:

(typep 5 'forward)

(subtypep 'forward 'standard-object)

This doesn't comply with Section 4.3.7 Integrating Types and Classes in 
the HyperSpec which specifies the semantics of typep and subtypep 
without restricting them to any metaclasses. The CLOS MOP specifies 
forward referenced classes to be instances of the metaclass 'forward-
referenced-class, so typep and subtypep should support such forward 
referenced classes.


----------------------------------------------------------------------

>Comment By: Pascal Costanza (pcostanza)
Date: 2006-11-10 20:40

Message:
Logged In: YES 
user_id=1381112

Comment By: Sam Steingold (sds)
Date: 2006-11-10 00:17

There is no "basic axiom of type theory", and ANSI CL
doesn't mention
anything about a set-theoretic definition of types as well.

http://www.lisp.org/HyperSpec/Body/glo_s.html#subtype
subtype n. a type whose membership is the same as or a
proper subset of the membership of another type, called a
supertype. (Every type is a subtype of itself.)

OK, I missed that definition.

http://www.lisp.org/HyperSpec/Body/glo_s.html#subtype
subclass n. a class that inherits from another class, called
a superclass. (No class is a subclass of itself.)

note two differencies:
SUBTYPE is set-theoretic on types and nominal on classes
SUBTYPE is reflexive while SUBCLASS is not.

I still think there is an interpretation of these definitions that makes forward referenced classes compatible with both. A 
forward referenced class can be instantiated exactly after it has been been given a proper definition - according to the 
CLOS MOP specification, this is achieved via change-class which doesn't change the identity of that class. So when a 
forward referenced class is turned into an "actual" class, it is still the same class. (This is even true under a strict reading 
of this statement: It remains the same under eql / eq. This all is, of course, based on the assumption that forward 
referenced classes are indeed classes - see below.)

Comment By: Bruno Haible (haible)
Date: 2006-11-10 17:23

Oops, I spoke too soon. I was confused by your use of the term
"when forward referenced classes are involved".

To make things clear now, we must distinguish forward-referenced and
incomplete classes:
  (defclass incomplete (forward) ())

1) Regarding 'forward', the clisp position is clear. 'forward' does not
name a class in the sense of ANSI-CL. HyperSpec/Body/mac_defclass.html
says that "defclass defines a new named class". _A_ new class, not several
ones.

This can be read as a mere necessary condition.

'forward' does name a class in the sense of MOP. But the functions
FIND-CLASS, TYPEP, and SUBTYPEP are specified by ANSI-CL, and for clisp,
ANSI-CL has higher priority than MOP, therefore

(find-class 'forward)
  => ERROR

(typep 42 'forward)
  => ERROR

(subtypep 'forward 'number)
  => ERROR

(subtypep 'forward 'standard-object)
  => ERROR

This is mandated by ANSI-CL compliance. It will not be changed in clisp.

I think you are reading things into the spec that aren't really there.

----------------------------------------------------------------------------
Now a reply to Pascal's new arguments:
"forward referenced classes can be found by find-class (nothing in
ANSI CL prevents this)"

See HyperSpec/Body/mac_defclass.html
    HyperSpec/Body/glo_c.html#class
    HyperSpec/Body/sec_4-3-1.html
You find so many statements there which don't apply to MOP's
forward-referenced classes.

Maybe I am blind, but I really don't see them. To the contrary: The specification of defclass states that "Each superclass-
name argument specifies a direct superclass of the new class." and "It is not required that the superclasses of a class be 
defined before the defclass form for that class is evaluated."

It doesn't say that the names listed as direct superclasses are not classes but something else. It explicitly still calls them 
classes.

It would be nice if you could mention the statements (or at least some of them) which don't apply to forward referenced 
classes. (I am genuinely interested in better understanding your position!)

Thanks,
Pascal


----------------------------------------------------------------------

Comment By: Bruno Haible (haible)
Date: 2006-11-10 17:23

Message:
Logged In: YES 
user_id=5923

Oops, I spoke too soon. I was confused by your use of the term
"when forward referenced classes are involved".

To make things clear now, we must distinguish forward-referenced and
incomplete classes:
  (defclass incomplete (forward) ())

1) Regarding 'forward', the clisp position is clear. 'forward' does not
name a class in the sense of ANSI-CL. HyperSpec/Body/mac_defclass.html
says that "defclass defines a new named class". _A_ new class, not several
ones.

'forward' does name a class in the sense of MOP. But the functions
FIND-CLASS, TYPEP, and SUBTYPEP are specified by ANSI-CL, and for clisp,
ANSI-CL has higher priority than MOP, therefore

(find-class 'forward)
  => ERROR

(typep 42 'forward)
  => ERROR

(subtypep 'forward 'number)
  => ERROR

(subtypep 'forward 'standard-object)
  => ERROR

This is mandated by ANSI-CL compliance. It will not be changed in clisp.

2) Regarding 'incomplete'. Most of the discussion about the empty set of
objects applies to incomplete classes as well. As of yesterday's clisp:

(find-class 'incomplete)
  => #<STANDARD-CLASS INCOMPLETE :INCOMPLETE>

(typep 42 'incomplete)
  => NIL

(subtypep 'incomplete 'number)
  => NIL, T

(subtypep 'incomplete 'standard-object)
  => ERROR, should be NIL, T
     because (clos:class-direct-superclasses (find-class 'incomplete))
             = (#<FORWARD-REFERENCED-CLASS UNDEFINED>)
     and because of the requirement on SUBTYPEP that Sam mentioned.

----------------------------------------------------------------------------
Now a reply to Pascal's new arguments:
> "forward referenced classes can be found by find-class (nothing in
> ANSI CL prevents this)"

See HyperSpec/Body/mac_defclass.html
    HyperSpec/Body/glo_c.html#class
    HyperSpec/Body/sec_4-3-1.html
You find so many statements there which don't apply to MOP's
forward-referenced classes.

> There is no "basic axiom of type theory", and ...
> A class whose 
> definition refers to other classes for the purpose of inheriting from them
> is said to be a subclass of each of those classes.

You can certainly define higher-order theories about classes this way.

It's like the axioms of natural numbers: the definition of a natural number
is as an equivalence class of sets where the equivalence is defined through
the existence of a bijective map. Rules like "a + b = b + a" are not axioms
for natural numbers, they are theorems. But you can create theories
generalizing these (group theory) by taking these rules as axioms.

Similar for types. The basic, original definition is that you have objects
in memory. Classes come later.

> Section 4.3.7 states this: "The proper name of every class is a
> valid type specifier.

Sure. But 'forward' does not name an ANSI-CL class - whereas 'incomplete'
does.


----------------------------------------------------------------------

Comment By: Sam Steingold (sds)
Date: 2006-11-10 00:17

Message:
Logged In: YES 
user_id=5735

> There is no "basic axiom of type theory", and ANSI CL
doesn't mention
> anything about a set-theoretic definition of types as well.

http://www.lisp.org/HyperSpec/Body/glo_s.html#subtype
subtype n. a type whose membership is the same as or a
proper subset of the membership of another type, called a
supertype. (Every type is a subtype of itself.)

http://www.lisp.org/HyperSpec/Body/glo_s.html#subtype
subclass n. a class that inherits from another class, called
a superclass. (No class is a subclass of itself.)

note two differencies:
SUBTYPE is set-theoretic on types and nominal on classes
SUBTYPE is reflexive while SUBCLASS is not.

----------------------------------------------------------------------

Comment By: Pascal Costanza (pcostanza)
Date: 2006-11-10 00:07

Message:
Logged In: YES 
user_id=1381112

+ Indeed, my ABSTRACT-CLASS example is not a counterexample. I forgot about the class prototype.

+ The description at http://clisp.cons.org/impnotes/mop-chap.html#forward-referenced-class-clisp is incorrect 
in that forward referenced classes can be found by find-class (nothing in ANSI CL prevents this). So the first 
argument to ensure-class and ensure-class-using-class can be forward referenced classes. You also don't need 
many forward referenced classes with the same name, and you can change forward referenced classes via 
change-class because object identity is not an issue. All other CLOS MOP implementations that I am aware of do 
these things, and correctly so.

+ There is no "basic axiom of type theory", and ANSI CL doesn't mention anything about a set-theoretic definition 
of types as well. To the contrary, in Section 4.3.1, the HyperSpec states the following things: "A class whose 
definition refers to other classes for the purpose of inheriting from them is said to be a subclass of each of those 
classes. The classes that are designated for purposes of inheritance are said to be superclasses of the inheriting 
class." and "A class C1 is a direct superclass of a class C2 if C2 explicitly designates C1 as a superclass in its 
definition. In this case C2 is a direct subclass of C1. A class Cn is a superclass of a class C1 if there exists a series 
of classes C2,...,Cn-1 such that Ci+1 is a direct superclass of Ci for 1 <=i<n. In this case, C1 is a subclass of Cn. 
A class is considered neither a superclass nor a subclass of itself. That is, if C1 is a superclass of C2, then C1 /
=C2. The set of classes consisting of some given class C along with all of its superclasses is called ``C and its 
superclasses.''" This is actually just a description of a nominal subclass/superclass relationship.

Note that none of these statements contradict the concept of forward referenced classes in any way because 
according to the CLOS MOP spec, forward referenced classes have both lists of direct superclasses and lists of 
direct subclasses, so the subclass and superclass relationships can be unambiguously determined.

Finally, Section 4.3.7 states this: "The proper name of every class is a valid type specifier. In addition, every class 
object is a valid type specifier. Thus the expression (typep object class) evaluates to true if the class of object is 
class itself or a subclass of class. The evaluation of the expression (subtypep class1 class2) returns the values 
true and true if class1 is a subclass of class2 or if they are the same class; otherwise it returns the values false 
and true. If I is an instance of some class C named S and C is an instance of standard-class, the evaluation of the 
expression (type-of I) returns S if S is the proper name of C; otherwise, it returns C."

So it is clearly the case that subtype and supertype relationships between classes are mapped to subclass and 
superclass relationships, as defined in Section 4.3.1. So we indeed have nominal subtype/supertype relationships.

These sections also don't say anything about whether classes are defined by the defclass form or otherwise. 
Section 4.3.7 only refers to classes with "proper names." Proper names are specified in Section 4.3.1 that states 
that "A class can have a name. The function class-name takes a class object and returns its name. The name of an 
anonymous class is nil. A symbol can name a class. The function find-class takes a symbol and returns the class 
that the symbol names. A class has a proper name if the name is a symbol and if the name of the class names 
that class. That is, a class C has the proper name S if S= (class-name C) and C= (find-class S). Notice that it is 
possible for (find-class S1) = (find-class S2) and S1/=S2. If C= (find-class S), we say that C is the class named S."

There are various ways that classes can get proper names, at the lowest level via (setf class-name) and (setf find-
class). That a class is defined via defclass is not a necessary condition, so forward referenced classes clearly 
apply.

Note that the subtype and supertype relationships are also specified in the HyperSpec in Section 4.3.7 for plain 
class objects (such as class objects that represent forward referenced classes) without the need to have proper 
names.

+ (subtypep 'test 'standard-object) isn't necessarily true because (find-class 'test) could ultimately be an instance 
of a metaclass that doesn't define standard-object as one of the default superclasses (and ensure-class-using-
class is not the only function that can possibly create forward referenced classes). At least, I don't see any direct 
or indirect requirement to the contrary. The only reliable information that you have for forward referenced classes 
are the available lists of direct superclasses and direct subclasses, and they allow you to unambiguously 
determine subclass and superclass relationships.


----------------------------------------------------------------------

Comment By: Sam Steingold (sds)
Date: 2006-11-09 19:54

Message:
Logged In: YES 
user_id=5735

SUBTYPE cannot return "unknown" for classes:
http://www.lisp.org/HyperSpec/Body/fun_subtypep.html
subtypep never returns a second value of nil when both
type-1 and type-2 involve only the names ... of types
defined by ... defclass
hmmm --- otoh, forward classes are NOT defined by defclass!
 they are implicitly created!
barring further evidence that forward classes require the
same treatment as classes defined by DEFCLASS, I would stick
with my original suggestion that such classes should
canonicalize to NIL (except that not-yet-finalized classes
are in the same boat as the forward classes...)
at any rate, my tentatice TYPEP patch is attached.

----------------------------------------------------------------------

Comment By: Bruno Haible (haible)
Date: 2006-11-09 19:38

Message:
Logged In: YES 
user_id=5923

I support Pascal's argumentation that TYPEP and SUBTYPEP should not
yield an error here, because after
   (defclass test (forward) ())
(find-class 'test) succeeds, i.e. TEST is a valid type name.
Inside SUBTYPEP, SYS::CANONICALIZE-TYPE accepts TEST, therefore the
rest of SUBTYPEP should proceed without errors.

I am with Sam regarding the consideration of subtype relationship on
a set-theoretic basis, rather than on a nominal basis. The
set-theoretic definition of a type is the basic axiom of type theory.
Your ABSTRACT-TEST class is not a counterexample, because the
implementation could create an instance of the class when you finalize
it (bypassing the ALLOCATE-INSTANCE method, since this instance is
just for bookkeeping purposes of the implementation, not accessible to
the user).

Regarding TYPEP, we all agree that (TYPEP 5 'TEST) must return NIL.

Regarding SUBTYPEP, (subtypep 'TEST 'STANDARD-OBJECT) should not
yield an error (see above). Instead it should return "unknown",
i.e. (values NIL NIL). It can also return T, after processing the
already-known superclasses; but I consider this a "quality of
implementation" issue (i.e. optional).


----------------------------------------------------------------------

Comment By: Sam Steingold (sds)
Date: 2006-11-09 17:41

Message:
Logged In: YES 
user_id=5735

please take a look at
http://clisp.cons.org/impnotes/mop-chap.html#forward-referenced-class-clisp

----------------------------------------------------------------------

Comment By: Pascal Costanza (pcostanza)
Date: 2006-11-07 11:16

Message:
Logged In: YES 
user_id=1381112

In order to avoid losing context, here is a summary of my arguments, together with some more details and a response:

+ Subtyping relationships between CLOS classes are nominal, not set-theoretic.

+ Section 4.3.7 in the HyperSpec requires that typep and subtypep operate on instances of forward-referenced-class.

This poses no problems when nominal subtyping is considered. Forward referenced classes have well-defined direct 
superclasses and subclasses from which the subtyping relationships can be fully inferred. Especially, no class precedence list 
is required for determining subtyping relationships, and the restrictions on compute-class-precedence-list ensure that class 
precedence lists cannot affect subtyping relationships after the fact.

+ Your argument is based on the idea that forward referenced classes cannot have instances, saying that in a set-theoretic 
interpretation this would mean that they are subtypes of any type. The underlying assumption is wrong, though: Here is an 
illustration how a class that is guaranteed not to have any instances is not automatically a subtype of any other type.

(use-package :clos)

(defclass abstract-class (standard-class)
  ())

(defmethod validate-superclass
  ((class abstract-class)
   (superclass standard-class))
  t)

(defmethod allocate-instance :before
  ((class abstract-class) &rest initargs)
  (declare (ignore initargs))
  (error "Abstract class ~S cannot be instantiated." class))

(defclass abstract-test ()
  ()
  (:metaclass abstract-class))

(assert
  (handler-case
    (progn
      (make-instance 'abstract-test)
      nil)
    (error () t)))

(assert (subtypep 'abstract-test 'standard-object))

(assert (not (subtypep 'abstract-test 'number)))


----------------------------------------------------------------------

Comment By: Sam Steingold (sds)
Date: 2006-11-07 00:56

Message:
Logged In: YES 
user_id=5735

I am saying that the only meaningful alternative to failing
is canonicalising typespec forward to nil.
why do you think it is more useful?
I do not like the subtype behavior you describe because it
violates the set theory paradigm.
since the implementation can proved that the set of
instances is empty, there is not reason not to use that.

----------------------------------------------------------------------

Comment By: Pascal Costanza (pcostanza)
Date: 2006-11-07 00:41

Message:
Logged In: YES 
user_id=1381112

Hm, maybe it's unclear what I mean by "fail." Currently, typep and subtypep just signal errors when forward referenced 
classes are involved. They shouldn't do that, but return useful values instead. Subtypep should probably return (values nil 
t) most of the time when forward referenced classes are involved (unless both arguments are the same, or the first is a 
subclass of the second argument, which can already be determined for forward referenced classes).

Signalling errors here is not a good idea because this makes at least one idiom unnecessarily hard when writing CLOS 
metaprograms.


----------------------------------------------------------------------

Comment By: Sam Steingold (sds)
Date: 2006-11-07 00:30

Message:
Logged In: YES 
user_id=5735

how is (subtypep 'forward 'number) different from (subtypep
'(and pathname string) 'number)?
if the implementation can prove that a type is empty (at a
given time), it can treat it as an equivalent to nil.
>Furthermore, the subtyping relationships between classes can
>already vary over time in CLOS due to class redefinition. 
indeed, and when forward is actually defined, the value of
(subtypep 'forward 'number) will change.

----------------------------------------------------------------------

Comment By: Pascal Costanza (pcostanza)
Date: 2006-11-07 00:06

Message:
Logged In: YES 
user_id=1381112

What set theory interpretation? Your reasoning would imply that any class of which there are no instances at some 
point in time would be a subtype of number at that point in time. This makes even less sense.

The subtyping relationships between classes, structures and conditions are nominal - see http://en.wikipedia.org/
wiki/Nominative_type_system

Furthermore, the subtyping relationships between classes can already vary over time in CLOS due to class redefinition. 
So there can indeed be instances of an instance of forward-referenced-class, after it has been changed to a different 
metaclass (which doesn't change its identity).


----------------------------------------------------------------------

Comment By: Sam Steingold (sds)
Date: 2006-11-06 23:52

Message:
Logged In: YES 
user_id=5735

Suppose you think it is useful to interpret
forward-referenced-class as a type specification,
e.g., to enable on to use SUBTYPEP on not-yet defined
classes that still carry subclass info.
Since such a class has no instances, it is functionally
equivalent to type NIL.
One implication is, of course, that (subtype 'forward
'number) will return True (an empty set is a subset of any
set), thus defeating any usefulness of subtypep for such
classes.
Anything else will break the set theory interpretation of
TYPEP/SUBTYPEP predicates.
Since SUBCLASSP is not exported, it is a pity that there is
no alternative route available, but I don't think that
forward-referenced-class is a good reason to kill the set
theory interpretation of the TYPEP/SUBTYPEP predicates.

----------------------------------------------------------------------

Comment By: Sam Steingold (sds)
Date: 2006-11-06 23:28

Message:
Logged In: YES 
user_id=5735

the only sensible interpretation as a type of a
forward-referenced-class is NIL (i.e., the empty type) since
there can be never any objects of this type. 
how useful is that?!

----------------------------------------------------------------------

You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=101355&aid=1591671&group_id=1355