TYPEP warp implications

[Jon L White <edsel!jonl@labrea.stanford.edu>]

Recent mail under the subject line of "Types in CL" brought to light an
inconsistency in CLtL that may have gone unnoticed by most people.

-- The second paragraph of page 11 makes it clear that "data types" are
   just sets of objects; subsequent discussion makes it clear that the
   second argument to TYPEP (a type specifier) is a name for some such
   set, and that there may be several distinct names specifying the same
   set (or type).  The first paragraph of section 6.2.1 on page 72 says
   that TYPEP is a set membership test, and SUBTYPEP is a subset test.

-- The first two paragraphs of section 4.5, on page 45, describe a
   permission for what I call "element-type upgrading" on arrays; the 
   documentation fo ARRAY-ELEMENT-TYPE on page 291 also makes it clear 
   that a conforming implementation is permitted to "collapse" array
   element types into some more limited set of types, providing that
   the array returned by make-array is at most an "upgrade".  

For example, depending on how primitive arrays are actually implemented, 
       (make-array <dims> :element-type '(signed-byte 5))
and
       (make-array <dims> :element-type '(signed-byte 16))
might legitimately create exactly the same set of objects.  The only
constraint seems to be that that (array (signed-byte 16)) be the most
specific type *** in that implementation *** which can hold all the 
objects made by (make-array <dims> :element-type '(signed-byte 5)).
In this case, we say that the array element type has been upgraded from
(signed-byte 5) to (signed-byte 16), and we imply that there is no
particular special provisions for arrays of element type, say, 
(signed-byte 8).  [Every vendor's implementation I have looked at does some
amount of non-trivial "upgrading" on the element type (signed-byte 5).]

By the bulletted paragraphs above, (array (signed-byte 5)) and
(array (signed-byte 16)) are in fact names for exactly the same
set of objects.

However pages 45 and 46 go at length to specify that these two different
names for the same set of objects must be treated differently by TYPEP
and SUBTYPEP.  This seems to "warp" the utility of TYPEP since it puts
it at variance with the fundamental principle: "SUBTYPEP means subsetp".

No one I've asked has tried to defend this "warp".  I conjecture that it
was added to CLtL in a mistaken belief that it would promote portability.
I say "mistaken" because the source of non-portability is the permission
to upgrade; if two different implementations do any upgrading differently,
then the effect will be the same kind of non-portability that results
when two different implementations set the boundary between fixnums and 
bignums differently.  

Yet I'm in favor of the permission to upgrade; I 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, I would not want to gain portability
at the expense of limiting the language to the architectural features of
the hardware on which it was first implemented.

I would like to suggest that the flaw be fixed as follows:

-- Delete all the documentation that suggests the :element-type argument
   to make-array mignt not be a satisfactory element-type in the type
   specifier for the kind of array produced;

-- Introduce a function UPGRADE-ARRAY-ELEMENT-TYPE, which will tell you
   how a particular :element-type argument to make-array will be treated
   (so that you don't have to cons up an array to find out).

Does anyone have any strong feeling on this dichotomy one way or the other?
Have you been affected by variations in the vendors treatement of arrays?


-- JonL --



P.S. A clarifying note on the definition of "type specifier".  I called it
     a "name" in the above message.  This means that it is either a symbol
     like FIXNUM, or ARRAY, or one of the permissible list conbinations
     of type specifiers like (OR FIXNUM BIGNUM) etc.  [But note that he 
     Object System proposal may have to permit class-objects themselves to 
     be considered as type-specifiers because it is possible to create classes
     that don't have (proper) symbolic names; however, we can still view
     "the object itself" as its own name in the sense that the address of
     an object is a hidden name.]  Thus the set of type-specifiers forms
     a mathematical language, and the SUBTYPEP relation is generated by some 
     basic, generating set of relations between these names.  I want to see
     this language actually describing the implementation in which it is
     running -- that the objects of the implementation are a model for that
     language -- rather than seeing it be limited to some theoretical
     model which no vendor bothers to implement.