Unexpected (to me) behaviour in Lisp sub-typing
I just encountered some unexpected behaviour in how Common Lisp (or at least SBCL) handles array sub-typing.
Suppose you have a structure declaration like this:
(defstruct A
(a #1A() :type (simple-array integer)))
We can create instances of this struct by providing an initial value, and it will be type-checked.
(make-a :a #1A(1 2 3))
#S(A :A #(1 2 3))
We can also omit the argument and get the default specified in the declaration:
(make-a)
#S(A :A #())
So far so good. But suppose we now specialise the simple-array type
against a type such as (unsigned-byte 16) (the type of unsigned
16-bit integers).
(defstruct B
(b #1A() :type (simple-array (unsigned-byte 16))))
(make-b :b #1A(1 2 3))
This generates an error, as does using the default value.
Why is this? I eventually tracked the problem down to the fact that
the expression #1A() is given type (simple-vector 0) while the expression #1A(1 2 3) is given type (simple-vector 3), and neither
of these are sub-types of (simple-array (unsigned-byte 16)):
(type-of #1A())
(SIMPLE-VECTOR 0)
(type-of #1A(1 2 3))
(SIMPLE-VECTOR 3)
(typep #1A(1 2 3) '(simple-vector 3))
T
(typep #1A(1 2 3) '(simple-array (unsigned-byte 16)))
NIL
So the typing works for integer (and indeed for number and float)
but not for the constrained types like (unsigned-byte 16) –
although it does work for unsigned-byte (with no width).
Interestingly the tests fail for empty arrays as well:
(typep #1A() '(simple-array (unsigned-byte 16)))
NIL
I assume that the behaviour is because the compiler is at liberty to
optimise the storage of arrays with specific types, and doing so
makes it awkward to compare against types like simple-vector that
don’t contain their element type. This would also explain why the
check succeeds for types like integer, whose values are stored
boxed and so can represented uniformly.
There’s a simple way around this, of course, once you know what the problem is: make the type of the value explicit rather than relying on the reader macro. For example:
(defstruct C
(c (make-array '(0) :element-type '(unsigned-byte 16)) :type (simple-array (unsigned-byte 16))))
(make-c)
#S(C :C #())
and also:
(make-c :c (make-array '(3) :element-type '(unsigned-byte 16) :initial-contents (alexandria:iota 3)))
#S(C :C #(0 1 2))
I can’t find this behaviour detailed in the manuals (or anywhere
else) though. However, it seems to be related to the upgraded array
element type. When an array is created, the implementation is
allowed to use a different type to the one specified in its
representation, which must be a supertype of the type requested. For
types like integer and unsigned-byte this is t, the top type in the lattice:
(upgraded-array-element-type 'unsigned-byte)
T
But for the “constrained” types the upgraded type is the type itself:
(upgraded-array-element-type '(unsigned-byte 16))
(UNSIGNED-BYTE 16)
This suggests to me that the compiler (SBCL) is indeed optimising the representation and then also performing more detailed type-checking for elements.
