Common Lisp the Language, 2nd Edition

4.5. Type Specifiers That Specialize

Some type specifier lists denote specializations of data types named by symbols. These specializations may be reflected by more efficient representations in the underlying implementation. As an example, consider the type (array short-float). Implementation A may choose to provide a specialized representation for arrays of short floating-point numbers, and implementation B may choose not to.

If you should want to create an array for the express purpose of holding only short-float objects, you may optionally specify to make-array the element type short-float. This does not require make-array to create an object of type (array short-float); it merely permits it. The request is construed to mean ``Produce the most specialized array representation capable of holding short-floats that the implementation can provide.'' Implementation A will then produce a specialized array of type (array short-float), and implementation B will produce an ordinary array of type (array t).

If one were then to ask whether the array were actually of type (array short-float), implementation A would say ``yes,'' but implementation B would say ``no.'' This is a property of make-array and similar functions: what you ask for is not necessarily what you get.

Types can therefore be used for two different purposes: declaration and discrimination. Declaring to make-array that elements will always be of type short-float permits optimization. Similarly, declaring that a variable takes on values of type (array short-float) amounts to saying that the variable will take on values that might be produced by specifying element type short-float to make-array. On the other hand, if the predicate typep is used to test whether an object is of type (array short-float), only objects actually of that specialized type can satisfy the test; in implementation B no object can pass that test.

X3J13 voted in January 1989 (ARRAY-TYPE-ELEMENT-TYPE-SEMANTICS)   to eliminate the differing treatment of types when used ``for discrimination'' rather than ``for declaration'' on the grounds that implementors have not treated the distinction consistently and (which is more important) users have found the distinction confusing.

As a consequence of this change, the behavior of typep and subtypep on array and complex type specifiers must be modified. See the descriptions of those functions. In particular, under their new behavior, implementation B would say ``yes,'' agreeing with implementation A, in the discussion above.

Note that the distinction between declaration and discrimination remains useful, if only so that we may remark that the specialized (list) form of the function type specifier may still be used only for declaration and not for discrimination.

X3J13 voted in June 1988 (FUNCTION-TYPE)   to clarify that while the specialized form of the function type specifier (a list of the symbol function possibly followed by argument and value type specifiers) may be used only for declaration, the symbol form (simply the name function) may be used for discrimination.

The valid list-format names for data types are as follows:

(array element-type dimensions)

This denotes the set of specialized arrays whose elements are all members of the type element-type and whose dimensions match dimensions. For declaration purposes, this type encompasses those arrays that can result by specifying element-type as the element type to the function make-array; this may be different from what the type means for discrimination purposes. element-type must be a valid type specifier or unspecified. dimensions may be a non-negative integer, which is the number of dimensions, or it may be a list of non-negative integers representing the length of each dimension (any dimension may be unspecified instead), or it may be unspecified. For example:

(array integer 3)           ;Three-dimensional arrays of integers 
(array integer (* * *))     ;Three-dimensional arrays of integers 
(array * (4 5 6))           ;4-by-5-by-6 arrays 
(array character (3 *))     ;Two-dimensional arrays of characters 
                            ; that have exactly three rows 
(array short-float ())      ;Zero-rank arrays of short-format 
                            ; floating-point numbers

Note that (array t) is a proper subset of (array *). The reason is that (array t) is the set of arrays that can hold any Common Lisp object (the elements are of type t, which includes all objects). On the other hand, (array *) is the set of all arrays whatsoever, including, for example, arrays that can hold only characters. Now (array character) is not a subset of (array t); the two sets are in fact disjoint because (array character) is not the set of all arrays that can hold characters but rather the set of arrays that are specialized to hold precisely characters and no other objects. To test whether an array foo can hold a character, one should not use

(typep foo '(array character))

but rather

(subtypep 'character (array-element-type foo))

See array-element-type.

X3J13 voted in January 1989 (ARRAY-TYPE-ELEMENT-TYPE-SEMANTICS)   to change typep and subtypep so that the specialized array type specifier means the same thing for discrimination as for declaration: it encompasses those arrays that can result by specifying element-type as the element type to the function make-array. Under this interpretation (array character) might be the same type as (array t) (although it also might not be the same). See upgraded-array-element-type. However,

(typep foo '(array character))

is still not a legitimate test of whether the array foo can hold a character; one must still say

(subtypep 'character (array-element-type foo))

to determine that question.

X3J13 also voted in January 1989 (DECLARE-ARRAY-TYPE-ELEMENT-REFERENCES)   to specify that within the lexical scope of an array type declaration, it is an error for an array element, when referenced, not to be of the exact declared element type. A compiler may, for example, treat every reference to an element of a declared array as if the reference were surrounded by a the form mentioning the declared array element type (not the upgraded array element type). Thus

(defun snarf-hex-digits (the-array) 
  (declare (type (array (unsigned-byte 4) 1) the-array)) 
  (do ((j (- (length array) 1) (- j 1)) 
       (val 0 (logior (ash val 4) 
                      (aref the-array j)))) 
      ((< j 0) val)))

may be treated as

(defun snarf-hex-digits (the-array) 
  (declare (type (array (unsigned-byte 4) 1) the-array)) 
  (do ((j (- (length array) 1) (- j 1)) 
       (val 0 (logior (ash val 4) 
                      (the (unsigned-byte 4) 
                           (aref the-array j))))) 
      ((< j 0) val)))

The declaration amounts to a promise by the user that the aref will never produce a value outside the interval 0 to 15, even if in that particular implementation the array element type (unsigned-byte 4) is upgraded to, say, (unsigned-byte 8). If such upgrading does occur, then values outside that range may in fact be stored in the-array, as long as the code in snarf-hex-digits never sees them.

As a general rule, a compiler would be justified in transforming

(aref (the (array elt-type ...) a) ...)

into

(the elt-type (aref (the (array elt-type ...) a) ...)

It may also make inferences involving more complex functions, such as position or find. For example, find applied to an array always returns either nil or an object whose type is the element type of the array.

(simple-array element-type dimensions)

This is equivalent to (array element-type dimensions) except that it additionally specifies that objects of the type are simple arrays (see section 2.5).

(vector element-type size)

This denotes the set of specialized one-dimensional arrays whose elements are all of type element-type and whose lengths match size. This is entirely equivalent to (array element-type (size)). For example:

(vector double-float)     ;Vectors of double-format 
                          ; floating-point numbers 
(vector * 5)              ;Vectors of length 5 
(vector t 5)              ;General vectors of length 5 
(vector (mod 32) *)       ;Vectors of integers between 0 and 31

The specialized types (vector string-char) and (vector bit) are so useful that they have the special names string and bit-vector. Every implementation of Common Lisp must provide distinct representations for these as distinct specialized data types.

X3J13 voted in March 1989 (CHARACTER-PROPOSAL)   to eliminate the type string-char and to redefine the type string to be the union of one or more specialized vector types, the types of whose elements are subtypes of the type character.

(simple-vector size)

This is the same as (vector t size) except that it additionally specifies that its elements are simple general vectors.

(complex type)

Every element of this type is a complex number whose real part and imaginary part are each of type type. For declaration purposes, this type encompasses those complex numbers that can result by giving numbers of the specified type to the function complex; this may be different from what the type means for discrimination purposes. As an example, Gaussian integers might be described as (complex integer), even in implementations where giving two integers to the function complex results in an object of type (complex rational).

X3J13 voted in January 1989 (ARRAY-TYPE-ELEMENT-TYPE-SEMANTICS)   to change typep and subtypep so that the specialized complex type specifier means the same thing for discrimination purposes as for declaration purposes. See upgraded-complex-part-type.

(function (arg1-type arg2-type ...) value-type)

This type may be used only for declaration and not for discrimination; typep will signal an error if it encounters a specifier of this form. Every element of this type is a function that accepts arguments at least of the types specified by the argj-type forms and returns a value that is a member of the types specified by the value-type form. The &optional, &rest, and &key markers may appear in the list of argument types. The value-type may be a values type specifier in order to indicate the types of multiple values.

X3J13 voted in January 1989 (FUNCTION-TYPE-REST-LIST-ELEMENT)   to specify that the arg-type that follows a &rest marker indicates the type of each actual argument that would be gathered into the list for a &rest parameter, and not the type of the &rest parameter itself (which is always list). Thus one might declare the function gcd to be of type (function (&rest integer) integer), or the function aref to be of type (function (array &rest fixnum) t).

X3J13 voted in March 1988 (FUNCTION-TYPE-KEY-NAME)   to specify that, in a function type specifier, an argument type specifier following &key must be a list of two items, a keyword and a type specifier. The keyword must be a valid keyword-name symbol that may be supplied in the actual arguments of a call to the function, and the type specifier indicates the permitted type of the corresponding argument value. (The keyword-name symbol is typically a keyword, but another X3J13 vote (KEYWORD-ARGUMENT-NAME-PACKAGE)   allows it to be any symbol.) Furthermore, if &allow-other-keys is not present, the set of keyword-names mentioned in the function type specifier may be assumed to be exhaustive; for example, a compiler would be justified in issuing a warning for a function call using a keyword argument name not mentioned in the type declaration for the function being called. If &allow-other-keys is present in the function type specifier, other keyword arguments may be supplied when calling a function of the indicated type, and if supplied such arguments may possibly be used.

As an example, the function cons is of type (function (t t) cons), because it can accept any two arguments and always returns a cons. The function cons is also of type (function (float string) list), because it can certainly accept a floating-point number and a string (among other things), and its result is always of type list (in fact a cons is never null, but that does not matter for this type declaration). The function truncate is of type (function (number number) (values number number)), as well as of type (function (integer (mod 8)) integer).

X3J13 voted in January 1989 (FUNCTION-TYPE-ARGUMENT-TYPE-SEMANTICS)   to alter the meaning of the function type specifier when used in type and ftype declarations. While the preceding formulation may be theoretically elegant, they have found that it is not useful to compiler implementors and that it is not the interpretation that users expect. X3J13 prescribed instead the following interpretation of declarations.

A declaration specifier of the form

(ftype (function (arg1-type arg2-type ... argn-type) value-type) fname)

implies that any function call of the form

(fname arg1 arg2 ...)

within the scope of the declaration can be treated as if it were rewritten to use the-forms in the following manner:

(the value-type 
     (fname (the arg1-type arg1) 
            (the arg2-type arg2) 
            ... 
            (the argn-type argn)))

That is, it is an error for any of the actual arguments not to be of its specified type arg-type or for the result not to be of the specified type value-type. (In particular, if any argument is not of its specified type, then the result is not guaranteed to be of the specified type-if indeed a result is returned at all.)

Similarly, a declaration specifier of the form

(type (function (arg1-type arg2-type ... argn-type) value-type) var)

is interpreted to mean that any reference to the variable var will find that its value is a function, and that it is an error to call this function with any actual argument not of its specified type arg-type. Also, it is an error for the result not to be of the specified type value-type. For example, a function call of the form

(funcall var arg1 arg2 ...)

could be rewritten to use the-forms as well. If any argument is not of its specified type, then the result is not guaranteed to be of the specified type-if indeed a result is returned at all.

Thus, a type or ftype declaration specifier describes type requirements imposed on calls to a function as opposed to requirements imposed on the definition of the function. This is analogous to the treatment of type declarations of variables as imposing type requirements on references to variables, rather than on the contents of variables. See the vote of X3J13 on type declaration specifiers in general, discussed in section 9.2.

In the same manner as for variable type declarations in general, if two or more of these declarations apply to the same function call (which can occur if declaration scopes are suitably nested), then they all apply; in effect, the types for each argument or result are intersected. For example, the code fragment

(locally (declare (ftype (function (biped) digit) 
                         butcher-fudge)) 
  (locally (declare (ftype (function (featherless) opposable) 
                           butcher-fudge)) 
    (butcher-fudge sam)))

may be regarded as equivalent to

(the opposable 
     (the digit (butcher-fudge (the featherless 
                                    (the biped sam)))))

or to

(the (and opposable digit) 
     (butcher-fudge (the (and featherless biped) sam)))

That is, sam had better be both featherless and a biped, and the result of butcher-fudge had better be both opposable and a digit; otherwise the code is in error. Therefore a compiler may generate code that relies on these type assumptions, for example.

(values value1-type value2-type ...)

This type specifier is extremely restricted: it may be used only as the value-type in a function type specifier or in a the special form. It is used to specify individual types when multiple values are involved. The &optional, &rest, and &key markers may appear in the value-type list; they thereby indicate the parameter list of a function that, when given to multiple-value-call along with the values, would be suitable for receiving those values.