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

[masinter.pa@Xerox.COM]

I realized that this only went to a couple of individuals rather than the
whole list.  As I would like it Ready for Release by last week, and Benson
asked for the latest version, I'm mailing this one out.

In general, if you're having private discussions on an issue, please keep
me informed so I know what's happening. I'd just as soon you cc'd
cl-cleanup on issues. Please don't cc common-lisp and/or cl-editorial on
the same message unless it is absolutely necessary.

!

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

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)
 

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  
       <certain-type>  =  (ARRAY <element-type>) 
for various implementation dependent values of <element-type>.  For
example,
in  most implementations of CL, an array X created with  and 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))).

This proposal suggests elimination of this distinction for the array types
ARRAY,  SIMPLE-ARRAY, and VECTOR and their subtypes, by guaranteeing that 
arrays constructed with a specific element-type satisfy the typep predicate
with the derived array type-specifier, and by guaranteeing that subtypep 
reflect the type equivalences defined by the behavior of make-array.


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

-- Introduce a function, UPGRADE-ARRAY-ELEMENT-TYPE of one argument, which 
   reveals how the given implementation treats a particular :element-type 
   argument to make-array.  Given a type-specifier <type1> as argument, it
   returns a maximal type-specifier <type2> such that <type2> is the
   actual specialized array element type used whenever <type1> is given as
   an :element-type argument to MAKE-ARRAY.   Note that 
	(upgrade-array-element-type '<type>) = 
	    (array-element-type (make-array 0 :element-type '<type>))
   for all type specifiers <type>.
   
-- Change typep and subtypep  so that:
	    (TYPEP X '(ARRAY <type>)) 
   is true if and only if 
	    (TYPEP X `(ARRAY ,(UPGRADE-ARRAY-ELEMENT-TYPE '<type>)))
   is true.

-- 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 upgrading, if done at all, must be done the same way for
   non-simple and multi-dimensional arrays as it is for simple arrays.

-- Eliminate references to the distinction between types "for declaration"
and
   "for discrimination" in the discussion of array element-types. This
would
   include documentation patterened after CLtL:
	a.) The discussion in section  4.5, p. 45 and 46
	b.) p. 291, the sentence begining "This set may be larger than the set
	requested when the array was created; for example . . ."


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. Let this primitive type be  (ARRAY
<aet-y>).
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, it should be true that:

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

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. In other words,
both describe those arrays specialized to hold elements of type <aet-y>. 

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 are upgraded
to
the same "element 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" for array type-specifiers. The suggested changes to the
interpretation of array 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.


Current Practice:

Every vendor's implementation that the proposer has queried does some
amount
of non-trivial "upgrading"; 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".


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.


Semantically, upgrade-array-element-type is equivalent to:
     (defun upgrade-array-element-type (element-type)
       (array-element-type (make-array 0 :element-type element-type)))
but it might not cons up the 0-element array first.  Also, the presence of 
this name, as a documented function in the language, would serve notice
that
"upgrading" is an important aspect of any real implementation of CL arrays.


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.

There is a strong feeling that the COMPLEX type should have a similar 
handling as ARRAY type. This will be the subject of a separate cleanup
issue.