Saturday 3 March 2012

Types of arrays in common lisp

Here's a gotcha that I've finally understood (with some hand-holding from stassats on #lisp).
The type of a lisp array describes how specialised it is, not the objects it contains.
How to tell if you're confused in the same way that I was: you think that (simple-array T (*)) should be a super-type of (simple-array '(signed-int 32) (*)). But see here:
CL-USER> (defparameter *x*
           (make-array 5 :element-type '(signed-byte 32)
                         :initial-element 0))
*X*
CL-USER> (typep *x* '(simple-array (signed-byte 32)))
T
CL-USER> (typep *x* '(simple-array T))
NIL
What's going on is that (simple-array (signed-byte 32)) means an array that is specialised to hold 32-bit integers more efficiently. If I was on an old 8-bit machine or was using a less enthusiastically optimising lisp implementation, the make-array call might not have managed to make a specialised array. In which case, it would have fallen back to making a (slower / less efficient) array that can hold any old thing. The resulting object would have type (simple-array T). In fact, the two types are disjoint. The SIMPLE-ARRAY documentation in the hyperspec makes it clear:
The types simple-vector, simple-string, and simple-bit-vector are disjoint subtypes of type simple-array, for they respectively mean (simple-array t (*)), the union of all (simple-array c (*)) for any c being a subtype of type character, and (simple-array bit (*)).
Well, now that makes sense. So what do you do if you want to allow specialised arrays or generic arrays in your type? There's one magic option (also explained in the CLHS at the link above). Use (simple-array *) and it'll match anything.

No comments: