Issue: ARRAY-TYPE-ELEMENT-TYPE-SEMANTICS (Version 8)

[masinter.pa@Xerox.COM]

I modified this issue to tone down its criticizm of the current
Common Lisp situation (e.g., removed the assertion that it has been
a "disaster"). I think it still reads well. I also tried to squeeze
into the discussion section some of the alternatives that were tried
and not adopted, and the reasons for not adopting them.

I don't think there are two many others that I'll have last
minute revisions to; if you're there and listening today, let
me know. (Or call at (415) 494-4365).

!
Issue:         ARRAY-TYPE-ELEMENT-TYPE-SEMANTICS

References:    Data types and Type specifiers: CLtL p. 11; Sect. 4.5, p.45
                    TYPEP and SUBTYPEP; CLtL Sect. 6.2.1, p.72
                    ARRAY-ELEMENT-TYPE, CLtL p. 291
               The type-specifiers ARRAY, COMPLEX, SIMPLE-ARRAY, and VECTOR

Related Issues: SUBTYPEP-TOO-VAGUE, LIST-TYPE-SPECIFIER

Category:      CHANGE

Edit history:  Version 1, 13-May-88, JonL
               Version 2, 23-May-88, JonL  
                (typo fixes, comments from moon, rearrange some discussion)
               Version 3, 02-Jun-88, JonL  
                (flush alternate proposal ["flush-upgrading"]; consequently,
                 move more of discussion back to discussion section.
               Version 4, 01-Oct-88, Jan Pedersen & JonL
                (reduce discussion, and "cleanup" wordings)
               (Version 5 edit history missing)
               Version 6, 6-Oct-88, Moon
                (fix typos, cover subtypep explicitly, add complex,
                 change name of UPGRADE-ARRAY-ELEMENT-TYPE)
               Version 7, 7-Oct-88, JonL (more name and wording changes)
               Version 8,  8-Oct-88, Masinter (wording, discussion)


Problem description:

 CLtL occasionally draws a distinction between type-specifiers "for
 declaration" and "for discrimination".  Many people are confused by
 this situation.  A consequence of this distinction is that a variable
 declared to be of type <certain-type> and all of whose assigned objects
 are created in accordance with that type, may still have none of its
 values ever satisfy the TYPEP predicate with that type-specifier.

 One type-specifier with this property is  
         (ARRAY <element-type>) 
 for various implementation dependent values of <element-type>.  For
 example, in most implementations of CL, an array X created with an
 element-type of (SIGNED-BYTE 5) will, depending on the vendor, either
 satisfy
        (TYPEP X '(ARRAY (SIGNED-BYTE 8))), or
        (TYPEP X '(ARRAY T)) 
 but (almost) never will it satisfy 
        (TYPEP X '(ARRAY (SIGNED-BYTE 5))).


Proposal: (ARRAY-TYPE-ELEMENT-TYPE-SEMANTICS:UNIFY-UPGRADING)

 Summary of changes:

 Eliminate the distinction between type-specifiers "for declaration" and
 "for discrimination".  Change the meaning of the <element-type> in the
 ARRAY type-specifier and its subtypes, and in the COMPLEX type-specifier,
 to be the same for TYPEP and SUBTYPEP as for TYPE declarations.
 Specify how SUBTYPEP behaves on these type-specifiers.  Add a function
 to provide access to the implementation-dependent set of array types
 and another function to provide access to the implementation-dependent
 set of complex number types.

 Specifics:

 1. Eliminate references to the distinction between types "for declaration"
 and "for discrimination" in the discussion of array and complex
 type-specifiers. This would include documentation patterned after CLtL:
        a.) The discussion in section 4.5, pp. 45-7
        b.) p. 291, the sentence begining "This set may be larger than the set
        requested when the array was created; for example . . ."
 Instead, (ARRAY <type>) always means all arrays that can result by specifying
 <type> as the :ELEMENT-TYPE argument to the function MAKE-ARRAY, and
 (COMPLEX <type>) always means all complex numbers that can result by
 giving numbers of type <type> to the function COMPLEX, plus all other
 complex numbers of the same specialized representation.

 2. Change the meaning of (TYPEP <x> '(ARRAY <type>)) to be true if and
 only if <x> is an array of the most specialized representation capable
 of holding elements of type <type>.  In other words, it is true if and
 only if <x> is an array and (ARRAY-ELEMENT-TYPE <x>) is type-equivalent
 to (ARRAY-ELEMENT-TYPE (MAKE-ARRAY 0 :ELEMENT-TYPE <type>)).
 Do the same for SIMPLE-ARRAY and VECTOR.

 3. Change the meaning of (TYPEP <x> '(COMPLEX <type>)) to be true if
 and only if <x> is a complex number of the most specialized
 representation capable of holding parts of type <type>,  or if <x> is of 
 any subtype of that representation.  Both the real and imaginary parts
 must satisy (TYPEP <real-or-imag-part> '<type>). 

 4. Define that for all type-specifiers <type1> and <type2>, other than *,
 (ARRAY <type1>) and (ARRAY <type2>) are either equivalent or disjoint,
 depending on whether they use the same specialized representation or
 distinct representations.  This defines the behavior of SUBTYPEP.

 5. Define that for all type-specifiers <type1> and <type2>, other than *,
 (SUBTYPEP '(COMPLEX <type1>) '(COMPLEX <type2>)) is T T if they use the
 same specialized representation, T T if they use distinct specialized
 representations but (SUBTYPEP '<type1> '<type2>) is true, and NIL T
 otherwise.

 6. Require that the resultant ARRAY-ELEMENT-TYPE from a call to
 MAKE-ARRAY is independent of any argument to MAKE-ARRAY except for the
 :ELEMENT-TYPE argument.  Thus the set of specialized array
 representations must be consistent between single-dimensional and
 multi-dimensional, simple and non-simple, short and long arrays.

 7. Add the function IMPLEMENTED-ARRAY-ELEMENT-TYPE of one argument 
 which returns the same result as:
    (DEFUN IMPLEMENTED-ARRAY-ELEMENT-TYPE (TYPE)
      (ARRAY-ELEMENT-TYPE (MAKE-ARRAY 0 :ELEMENT-TYPE TYPE)))
 The type specifiers (ARRAY <type1>) and (ARRAY <type2>), where neither
 <type1> nor <type2> is *, are equivalent if <type1> and <type2> produce
 the same value from IMPLEMENTED-ARRAY-ELEMENT-TYPE, and disjoint
 otherwise.

 8. Add the function IMPLEMENTED-COMPLEX-PART-TYPE of one argument 
 which  returns the part type of the most specialized complex number
 representation that can hold parts of the given argument type.


Test cases:

 Let <aet-x> and <aet-y> be two distinct type specifiers that are
 definitely not type-equivalent in a given implementation, but for which
 make-array will return an object of the same array type.  This will be
 an implementation dependent search, but in every implementation that
 the proposer has tested, there will be some such types; often,
 (SIGNED-BYTE 5) and (SIGNED-BYTE 8) will work.

 Thus, in each case, both of the following forms return T T:

  (subtypep (array-element-type (make-array 0 :element-type '<aet-x>))
            (array-element-type (make-array 0 :element-type '<aet-y>)))

  (subtypep (array-element-type (make-array 0 :element-type '<aet-y>))
            (array-element-type (make-array 0 :element-type '<aet-x>)))

 To eliminate the distinction between "for declaration" and "for
 discrimination" both of the following should be true:

  [A]
   (typep (make-array 0 :element-type '<aet-x>)
          '(array <aet-x>))
   (typep (make-array 0 :element-type '<aet-y>)
          '(array <aet-y>))

 Since (array <aet-x>) and (array <aet-y>) are different names for
 exactly the same set of objects, these names should be type-equivalent.
 That implies that the following set of tests should also be true:

  [B]
   (subtypep '(array <aet-x>) '(array <aet-y>))
   (subtypep '(array <aet-y>) '(array <aet-x>))

 Additionally, to show that un-equivalent type-specifiers that use the
 same specialized array type should be equivalent as element-type
 specifiers, the following type tests should be true:

  [C]
   (typep (make-array 0 :element-type '<aet-y>)
          '(array <aet-x>))
   (typep (make-array 0 :element-type '<aet-x>)
          '(array <aet-y>))


Rationale:

 This proposal legitimizes current practice, and removes the obscure and
 un-useful distinction between type-specifiers "for declaration" and
 "for discrimination".  The suggested changes to the interpretation of
 array and complex type-specifiers follow from defining type-specifiers
 as names for collections of objects, on TYPEP being a set membership
 test, and SUBTYPEP a subset test on collections of objects.

 The small differences between the specification for ARRAY and the
 specification for COMPLEX are necessary because there is no creation
 function for complexes which allows one to specify the resultant type
 independently of the types of the parts.  Thus in the case of COMPLEX
 we must refer to the type of the two parts, and to the fact that a 
 number can be a member of more than one type.  Note that:
     (SUBTYPEP '(COMPLEX SINGLE-FLOAT) '(COMPLEX FLOAT))
 is true in all implementations, but 
     (SUBTYPEP '(ARRAY SINGLE-FLOAT) '(ARRAY FLOAT))
 is only true in implementations that do not have a specialized array
 representation that can hold single-floats but not other floats.


Current Practice:

 Every vendor's implementation that the proposer has queried has a
 finite set of specialized array representations, such that two
 non-equivalent element types can be found that use the same specialized
 array representation; this includes Lucid, Vaxlisp, Symbolics, Franz,
 and Xerox. Most implementations fail tests [A] and [C] part 1, but pass
 tests [A] and [C] part 2; this is a consequence of implementing the
 distinction between "for declaration" and "for discrimination".  Lucid
 and Xerox both pass test [B], and the other implementations fail it.

 No vendor that the proposer has queried has any specialized representation
 for complexes.

Cost to Implementors:

 This proposal is an incompatible change to the current language
 specification, but only a small amount of work should be required in
 each vendor's implementation of TYPEP and SUBTYPEP.


Cost to Users:

 Because of the prevalence of confusion in this area, it seems unlikely
 that any user code will have to be changed.  In fact, it is more likely
 that some of the vendors will cease to get bug reports about MAKE-ARRAY
 returning a result that isn't of "the obvious type".  Since the change
 is incompatible, some user code might have to be changed.


Cost of non-adoption:

 Continuing confusion in the user community.


Benefits:

 It will greatly reduce confusion in the user community.  The fact that
 (MAKE-ARRAY <n> :ELEMENT-TYPE '<type>) frequently is not of type 
 (ARRAY <type>) has been very confusing to almost everyone.  

 Portability of applications will be increased slightly, since
 the behavior of 

 (TYPEP (MAKE-ARRAY <n> :ELEMENT-TYPE <type>) '(ARRAY <type>))

  will no longer be implementation-dependent. 


Esthetics:

 Reducing the confusing distinction between type-specifiers "for
 declaration" and "for discrimination" is a simplifying step -- it is a
 much simpler rule to state that the type-specifiers actually describe
 the collections of data they purport to name.  Thus this is a step
 towards increased elegance.


Discussion:

 This issue was prompted by a lengthy discussion on the Common Lisp
 mailing list. It was the subject of a lengthy discussion in the
 cleanup committee, as well as a number of individual efforts.

 We considered the possibility of requiring that arrays remember
 the element-type given in the make-array call, e.g., require that
 (equal <x> (array-element-type (make-array <n> :element-type <x>)))
 for all valid type specifiers <x>. This has several problems: it
 increases the storage requirement for arrays, and 'hides' a 
 relevant part of the underlying implementation for no apparently 
 good reason. In addition, there might be some problems with
 equivalent but separate types (although this might be handled
 by changing "equal" to "equal-type", given a more rigorous
 definition of SUBTYPEP; see issue SUBTYPEP-TOO-VAGUE.)
 However, it would increase portability, since it would be much
 more difficult to write a program that, for example, created 
 an array with one element-type and then assumed an upgraded
 element-type. It would be valid for an implementation to do so 
 -- to remember the original array element-type or its canonical
 or expanded  form -- and satisfy all of the constraints of this
 proposal.

 We considered a suggestion to restrict the set of "known" array
 element types; this would gain portability at the expense of limiting
 the language.