Issue: ARRAY-TYPE-ELEMENT-TYPE-SEMANTICS (version 6)

[David A. Moon <Moon@STONY-BROOK.SCRC.Symbolics.COM>]

I mostly agree with version 5, but found that it didn't address all of
my concerns presented in June and in private discussions with JonL.  To
be constructive, I've made a new version of the proposal, instead of
just commenting.  The changes are:
 - fix typographical errors
 - use the same terminology as CLtL as much as possible
 - cover SUBTYPEP in the proposal, not just in the test case
 - cover all cases of declaration vs. discrimination (i.e. add COMPLEX)
 - add a complete list of affected type-specifiers
 - change the name of UPGRADE-ARRAY-ELEMENT-TYPE
 - change the presentation of the proposal to make it easier to understand
 - numbered the proposal points, and added a summary of them, to
   make the proposal easier to discuss

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

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)

Problem description:

 CLtL occasionally draws a distinction between type-specifiers "for
 declaration" and "for discrimination".  Many people are confused by
 this situation, which may be one of the more insidious flaws in the
 current CL design.  A consequence of this "flaw" 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)

 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.

 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 the same
 type-specifier as (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 components of type <type>,
 or <x> is of any subtype of that representation.

 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 IMPLEMENTATION-ARRAY-ELEMENT-TYPE which returns the
 same result as
    (DEFUN IMPLEMENTATION-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 IMPLEMENTATION-ARRAY-ELEMENT-TYPE, and disjoint
 otherwise.

 8. Add the function IMPLEMENTATION-COMPLEX-COMPONENT-TYPE which returns
 the component type of the most specialized complex number
 representation that can hold components of the given 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
 MAKE-COMPLEX function, thus in the case of COMPLEX we must refer to the
 type of the components, and a number can be a member of more than one
 type.  Thus
     (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 vendors fail it.


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.  That is, in
 practice, the distinction between "for declaration" and "for
 discrimination" has been a disaster.


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:

 To get a sense of how the community is confused, see the arpanet mailing 
 list for Common Lisp, in a series of exchanges started on Thu, 
 17 Dec 87 10:48:05 PST by Jeff Barnett <jbarnett@nrtc.northrop.com>
 under the subject line of "Types in CL".  Also see the exchange started 
 Wed, 6 Jan 88 23:21:16 PST by Jon L White <edsel!jonl@labrea.stanford.edu>
 under the subject line of "TYPEP warp implications".
 
 Many senior implementors at Lucid favor this proposal.  In network mail 
 "Date: Sat, 9 Jan 1988  15:54 EST" Rob McLaughlin favored the gist of this 
 proposal -- namely that upgrading should be continued, and that TYPEP
 should be fixed.  Here is an excerpt of his words:
    There are two obvious solutions, one of which has already been
    proposed:
     -- Make the mapping more direct.  Eliminating "array element type
        upgrading" would be an instance of this.
     -- Make the mapping explicitly ill-defined in a more useful way.
    I think we need to do the latter because the former won't work.  I
    don't see how to eliminate "array element type upgrading" without
    creating more problems [than] we solve.  . . .

    My conclusion [JonL's] is that it isn't array types that are wrong,
    it is the understanding of the meaning of TYPEP that is wrong.

 Many persons are in favor of the permission to upgrade; but they would
 not like to see CL become a language like C where there are a
 prescribed set of kinds of arrays that must be implemented (e.g, "int",
 "long int", "single", "double" etc), and no others can exist.  In short,
 no one would want to gain portability at the expense of limiting the
 language to the architectural features of the hardware on which it was
 first implemented.
 
 It may also be the case that portability will be improved since the
 identity
 (typep (make-array N :element-type '<type>) '(array <type>)) will be
 observed.