To: gwydion-group@cs.cmu.edu Subject: [Keith Playford: Re: Subclass Type Function ] Date: Fri, 16 Feb 1996 10:52:53 -0800 From: Bill Chiles I sent some mail to William, Rob, and Hqn people to check on subclass types. Keith's response was interesting. I'm sending the Gwydion group the whole exchange (which is short, modulo Keith's proposal) so that you can know the current scoop on subclass. I didn't want to bother everyone wiht my initial query, which I know is not my typical (or Gwydion's) approach to such mail. Bill ------- Forwarded Message From: Keith Playford Date: Fri, 16 Feb 1996 18:26:57 GMT To: William Lott Cc: chiles, andys, keith, norvig, ram@CS.cmu.edu Subject: Re: Subclass Type Function William Lott writes: > On Mon, 12 Feb 1996 16:20:15 EST, Bill Chiles wrote: > > Could Keith and William comment on the current state of commitment to > > implementing (for their respective implementatons) the subclass function or > > something like it using the limited function? > > Mindy currently has subclass types, and while our new compiler doesn't > yet support them we plan on it as they are quite useful. > > If I remember correctly, Harlequin later proposed a subtype type that > covered all types that were subtypes of the argument type, not just > classes that were subclasses of the argument type. I'm a little leery > of committing to the fuller functionally of subtype types because I > haven't fully though through how to implement them yet. We bailed on subtype because of complexity reasons. We thought we would get our subclass proposal OK'd by Apple in the last round of changes, but they ran out of time to check it. The sticking point seemed to be its interaction with sealing. However, Kim Barrett recently took on the task of verifying that subclass types make sense in the presence of sealing and should hopefully have some word on the subject soon. Meanwhile, our last subclass proposal is enclosed. - -- Keith ISSUE: Subclass specializers CATEGORY: Addition REVISION HISTORY: Version 1, 13th July 95, Keith Playford (Harlequin) Version 2, 8th August 95, Keith Playford (Harlequin) RELATED ISSUES: "Subclass Specialization" (historical) "Method Sealing" "Method Sealing Bug" Version 6 PROBLEM DESCRIPTION: Methods on generic functions such as Dylan's standard "make" and "as" which take types as arguments are impossible to reuse in Dylan without resorting to ad hoc techniques. As things stand, the only available mechanism for specializing such methods is through the use of singleton types. A singleton type specializer used in this way, by definition, gives a method applicable to exactly one type. In particular, such methods are not applicable to subtypes of the type in question. In order to define reusable methods on generic functions like this, we need a type which allows us to express applicability to a type and all its subtypes. PROPOSAL: Define the following: subclass class => subclass [Function] A call to this function returns a type which describes all the objects representing subclasses of the given class. We term such a type a "subclass type". The subclass function is allowed to return an existing type if that type is type equivalent to the subclass type requested. For an object O and class Y, the following instance? relationship applies: INSTANCE-1. instance?(O, subclass(Y)) This will be true if and only if O is a class and O is a subclass of Y. For classes X and Y the following subtype? relationships hold (note that a rule applies only when no preceding rule matches): SUBTYPE-1. subtype?(subclass(X), subclass(Y)) This will be true if and only if X is a subclass of Y. SUBTYPE-2. subtype?(singleton(X), subclass(Y)) This will be true if and only if X is a class and X is a subclass of Y. SUBTYPE-3. subtype?(subclass(X), singleton(Y)) This is always false. SUBTYPE-4. subtype?(subclass(X), Y), where Y is not a subclass type This will be true if Y is or any proper superclass of (including , any implementation-defined supertypes, and unions involving any of these). There may be other implementation-defined combinations of types X and Y for which this is also true. SUBTYPE-5. subtype?(X, subclass(Y)), where X is not a subclass type This will be true if Y is or any proper supertype of and X is a subclass of . Note that by subclass relationships SUBYPE-4 and SUBTYPE-5, we get this correspondance: and subclass() are type equivalent. Where the subtype? test has not been sufficient to determine an ordering for a method's argument position, the following further method ordering rules apply to cases involving subclass types (note that a rule applies only when no preceding rule matches): SPECIFICITY+1. subclass(X) precedes subclass(Y) when the argument is a class C and X precedes Y in the class precedence list of C. SPECIFICITY+2. subclass(X) always precedes Y, Y not a subclass type. That is, applicable subclass types precede any other applicable class-describing specializer. The constraints implied by sealing come by direct application of sealing rules 1 - 3 and the following disjointness criteria for subclass types (note that a rule applies only when no preceding rule matches): DISJOINTNESS+1. A subclass type subclass(X) and a type Y are disjoint if Y is disjoint from . DISJOINTNESS+2. Two subclass types subclass(X) and subclass(Y) are disjoint if the classes X and Y are disjoint. DISJOINTNESS+3. A subclass type subclass(X) and a singleton type singleton(O) are disjoint unless O is a class and O is a subclass of X. Method sealing's rule 3 must be changed to include the following: A method M (with specializers S1...Sn) in G also potentially blocks C at argument position i if there exist j and k such that subclass(Dj) is a pseudosubtype of Si, subclass(Dk) is a pseudosubtype of Ti, and subclass(Dk) is not a pseudosubtype of Si. This relies on the acceptance of Version 6 of "Method Sealing Bug". AMENDMENT: Specify that a subclass of is considered disjoint from a subclass type until a class is created that is a common instance of both. Do this by changing the disjointness rule: * A subclass type subclass(X) and a type Y are disjoint if Y is disjoint from . to read: * A subclass type subclass(X) and a type Y are disjoint if Y is disjoint from , or if Y is a subclass of without instance classes that are also subclasses of X. RATIONALE: Subclass types don't address everything in the problem description, particularly limited collection types, but are simpler to understand than subtype types and still very useful, particularly within user- defined frameworks where limited types are not an issue. The guiding principle behind the semantics is that, as far as possible, methods on classes called with an instance should behave isomorphically to corresponding methods on corresponding subclass types called with the class of that instance. So, for example, given the heterachy: \ / \ \ / and methods: method foo () method foo () method foo () method foo () method foo-using-type (subclass()) method foo-using-type (subclass()) method foo-using-type (subclass()) method foo-using-type (subclass()) that for a direct instance D1 of : foo-using-type() should behave analogously to: foo(D1) with respect to method selection. The clause added to sealing's "Rule 3" forces class creation to respect sealing constraints on this parallel heterarchy. Thus, sealing methods over subclass(C1), ..., subclass(CN) results in the same constraints on class creation as sealing methods with the same structure over C1, ..., CN if metaclasses are ignored. The rule that has subclass specializers precede other specializers applicable to types seems arbitrary but looks to be most useful and leads to the simplest "rule of thumb", being that for a set of applicable types the general order in decreasing order of applicability is: singleton specializer subclass specializers class specializers No attempt is made to be "clever" with subtype? relationships. In particular, the simplifying assumption is made that any class might have subclasses we know nothing about, regardless of any sealing declarations that might appear in the code. This seems a reasonable course to take. The rationale for the amendment is to prevent sealing a generic function over a subclass type of a class from blocking the creation of new metaclasses unnecessarily. The amendment may or may not be considered necessary at this point given that Dylan does not currently address the issue of introducing new metaclasses. Note that even without the amendment an implementation is free to have a number of initial, explicitly-defined metaclasses without any problems, in which case the situation is analogous to that of limited . EXAMPLES: // Common usage: define class () end; define class () end; define class () end; define class (, ) end; define method make (class :: subclass(), #key) print("Making an "); next-method(); end method; define method make (class :: subclass(), #key) print("Making a "); next-method(); end method; define method make (class :: subclass(), #key) print("Making a "); next-method(); end method; define method make (class :: subclass(), #key) print("Making a "); next-method(); end method; ? make(); Making a Making a Making a Making an {instance of } // Less common usage: // Metatype methods define method classify (type :: ) print("A type"); end method; define method classify (type :: ) print("A class"); next-method(); end method; define method classify (type :: ) print("A singleton"); next-method(); end method; // "User" level subclass methods define method classify (type :: subclass()) print("A subclass of "); next-method(); end method; ? classify(); A subclass of A class A type ? classify(singleton()) A subclass of A singleton A type ? classify(subclass()) A subclass of A type COST TO IMPLEMENTORS: Another type to implement. Given the number of types Dylan has and allows you to specialize on already, any implementation is going to require a well thought out type framework. Given this, it should be reasonable to add in the new rules for as specified. COST TO USERS: Another type to understand, although they shouldn't have to face it unless they have need of it, and even then only the "obvious" aspects of its behaviour are likely to be necessary in user programs. PERFORMANCE IMPACT: Singleton types, and possibly limited integer types, are likely to be implemented through some kind of secondary dispatch scheme already. Subclass types could be dealt with using the same technique. In the common case where a generic function defines a restriction on an argument that constrains it to be a type object (make, as), there is potential to do somewhat better by hijacking the primary dispatch mechanism in the corresponding argument position. BENEFITS: Methods that take classes as arguments become reusable! AESTHETICS: Good on balance because it fills a tangible hole in the language in a consistent, intuitive way rather than leaving the hole there to be fallen into or filled by ad hoc techniques. DISCUSSION: The subclass relationship definitions don't spell everything out explicitly when it comes to union types - for the definition of new types to be tractable we have to be able to fall back on existing definitions of composite types like union, and we do here. ------- End of Forwarded Message