[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Issue: ARRAY-TYPE-ELEMENT-TYPE-SEMANTICS (version 6)
- To: firstname.lastname@example.org
- Subject: Issue: ARRAY-TYPE-ELEMENT-TYPE-SEMANTICS (version 6)
- From: David A. Moon <Moon@STONY-BROOK.SCRC.Symbolics.COM>
- Date: Thu, 6 Oct 88 22:49 EDT
- In-reply-to: <881005-005724-4531@Xerox>
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
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
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)
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
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
(TYPEP X '(ARRAY (SIGNED-BYTE 8))), or
(TYPEP X '(ARRAY T))
but (almost) never will it satisfy
(TYPEP X '(ARRAY (SIGNED-BYTE 5))).
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
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
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.
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:
(typep (make-array 0 :element-type '<aet-x>)
(typep (make-array 0 :element-type '<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:
(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:
(typep (make-array 0 :element-type '<aet-y>)
(typep (make-array 0 :element-type '<aet-x>)
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
(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.
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.
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.
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.
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 <email@example.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 <firstname.lastname@example.org>
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
-- 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
It may also be the case that portability will be improved since the
(typep (make-array N :element-type '<type>) '(array <type>)) will be