[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Issue: ARRAY-TYPE-ELEMENT-TYPE-SEMANTICS (Version 8)
- To: email@example.com
- Subject: Issue: ARRAY-TYPE-ELEMENT-TYPE-SEMANTICS (Version 8)
- From: masinter.pa@Xerox.COM
- Date: 8 Oct 88 12:32 PDT
- Cc: Masinter.pa@Xerox.COM
- Line-fold: NO
- Reply-to: firstname.lastname@example.org
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).
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
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)
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
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))).
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.
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
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
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.
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 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.
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
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.
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.
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.
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
We considered a suggestion to restrict the set of "known" array
element types; this would gain portability at the expense of limiting