[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

the array type mess....

Well, I certainly agree that there is a mess here, but it seems to me
that an obvious solution is being overlooked.  It is possible to have
both implementation-dependent array specialization and the identity:

  (typep (make-array ... :element-type <type>) '(array ... <type>)) => T

Array type specialization is just one instance of the implementation
process of mapping user specifications into the implementation.  In
order to understand the Common Lisp type system, you have to start
thinking about two different conceptions of type:

Definitional type
    This is the type system as seen by the user of the implementation.
    It is a collection of promises made by the language definition to
    the user.

Implementation type
    This is an abstraction of the implementation chosen for an object.
    The implementation type of an object is basically a name for the
    representation chosen for that object, and often had more to do
    with the details of the implementation of the object than with the
    user visible meaning of the object.  Consider the FIXNUM type or
    the type that has been hypothesized in previous discussions
    POWER-OF-TWO-BIGNUM.  Implementation types are usually of little
    direct concern to the user: his concern is to somehow use the
    defined language facilities in a way that permits efficient

Traditionally, these two conceptions of type have been used largely
interchangeably in Lisp.  I think that there are two main reasons for
 -- Before Common Lisp, Lisp systems didn't have type systems elaborate
    enough to say anything very interesting about the types of objects.
    In these simple systems, it was easier to maintain an approximate
    equivalence between the definitional and implementation type.
 -- Before Common Lisp, the distinction between the implementation and
    the definition was generally only casually made.  This was
    acceptable, since these Lisp dialects had only one implementation.

The problem that we are seeing with arrays is that the relationship
between definitional and implementation types is under-defined,
causing problems in functions that straddle the
definition=>implementation boundary.  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 we solve.  Even if this can be done, the ill-defined
nature of the to-implementation mapping will crop up again and again.
We already had a long discussion about TYPE-OF, ARRAY-ELEMENT-TYPE and
SUBTYPEP.  This discussion was prompted by what superficially appeared
to be compile questions about TYPE-OF.

The main reason that the problem is so blatant with arrays is that an
array is currently the only way that Common Lisp lets the user get his
hands on a specializable cell as something approaching a first-class
object.  I think that array element types should treated in much the
same way as the primary other kind of specializable cell: variables.

It is widely accepted that a Common Lisp compiler is free to implement a
variable however it damn well pleases as long as it preserves the
language semantics during normal execution.  When compilers start using
non-standard representations such as "unboxed numbers" and playing games
like introducing spurious copies during register allocation, then
extra-linguistic environment features such as debuggers can detect the
funny business, but this is of little concern to the normal programmer.

With arrays, it is somewhat more awkward to play free and loose with
representations, since the user has been given operations (such as
ARRAY-ELEMENT-TYPE) that manipulate the implementation type of the
object in terms of definitional types.  The user has been given enough
rope to hang himself, mainly because array types were being thought of
more in terms of implementation types than definitional types.

My conclusion is that it isn't array types that are wrong, it is the
understanding of the meaning of TYPEP that is wrong.  TYPEP should be
thought of as a query: 
    Could this value be the implementation of an object defined by the
    language to have this type?
and not:
    Is this the implementation type of this object?

The first definition is the only one that works in Common Lisp, since
the Common Lisp definition is implementation-independent.  Under this
interpretation, it is obvious that the TYPEP/MAKE-ARRAY identity holds.
In terms of the TYPEP implementation, this means that TYPEP will
automatically do the to-implementation mapping on the type specifier
before comparing it to the implementation type.