Thanks very much for the clarification. I understand the issue quite
better now, and I agree that adding the (ARRAY NIL) and companion
machinery for U-A-E-T is the most sensible way of doing things.
PS. Sorry for the cross posting before.
On Sep 28, 2004, at 9:55 AM, Christophe Rhodes wrote:
> Marco Antoniotti <marcoxa@...> writes:
>> Please correct me if you think this is bogus.
> I think it's bogus. (And please stop adding irrelevant mailing lists:
> I've trimmed cmucl-imp because I'm sure that anyone who's even
> remotely interested in this point is on sbcl-devel anyway.)
> Thinking of type relationships in terms of disjointness is a losing
> practice, because in doing so one loses information. It is more
> helpful to examine these issues in terms of conjunction and
> disjunction: union and intersection, or supertype and subtype
> relationship. (See Baker's "Decision Procedure for SUBTYPEP" for
> NIL specifies the empty type. This makes it the universal subtype:
> for any (known) type <T>, (subtypep nil <T>) must return true. This
> is only mildly relevant to what follows: only to the behaviour of the
> objects that I "show" must exist.
> For any known type <U>, (vector <U>) specifies those objects which are
> one-dimensional arrays specialized to hold
> (upgraded-array-element-type <U>). So, trivially, (vector nil) is a
> valid type specifier, if (upgraded-array-element-type nil) does not
> signal an error. What grounds would we have to signal an error? Only
> if there were no arrays at all in the implementation: because all
> arrays can hold objects of their specialized types, and these
> specialized types are always supertypes of type NIL, by definition.
> So, we've shown that (vector nil) must be a valid type specifier; now
> all we need to do is work out what it denotes.
> What does upgraded-array-element-type do? It
> Returns the element type of the most specialized array
> representation capable of holding items of the type denoted by
> The sharp-eyed might spot a problem here: we implicitly have a total
> order on the specialized array types, because
> upgraded-array-element-type must return the most specialized upgraded
> type. This would lead to a contradiction if the only specialized
> array types we had (other than (vector t)) were bit-vector and string:
> because it would then not be clear whether
> (upgraded-array-element-type nil) should be BIT or CHARACTER: NIL is a
> subtype of both, and there isn't an ordering between them.
> We rescue ourselves from the implosion of the Universe, however, by
> requiring the existence of another specialized vector whose
> array-element-type is NIL: that is, it can hold no objects. While
> this may not have many practical uses to the application programmer --
> despite various airy speculations on comp.lang.lisp by people who
> should have known better -- it does prevent the implementation world
> from disappearing in a puff of logic, at the expense of two tags.
> Thus, (upgraded-array-element-type nil) returns nil, the type (vector
> nil) denotes vectors which cannot hold anything, for which the
> implementation must provide a specialized representation, and all is
> in fact well. This view is supported by CLHS 184.108.40.206, in addition:
> Type upgrading implies a movement upwards in the type hierarchy
> lattice. A type is always a subtype of its upgraded array element
> type. Also, if a type Tx is a subtype of another type Ty, then the
> upgraded array element type of Tx must be a subtype of the upgraded
> array element type of Ty. Two disjoint types can be upgraded to the
> same type.
> To see this, try the two (Tx, Ty) pairs (NIL, BASE-CHAR) and (NIL,
> BIT), which shows that the upgraded array element type of NIL must be
> a subtype of BASE-CHAR and a subtype of BIT.
> I hope this clears things up,
Marco Antoniotti http://bioinformatics.nyu.edu
NYU Courant Bioinformatics Group tel. +1 - 212 - 998 3488
715 Broadway 10th FL fax. +1 - 212 - 998 3484
New York, NY, 10003, U.S.A.