what's inside of an array?

[Andrei Zorine]

Hi,
I thought about this question: when I define a data type as
(deftype maybe-fixnum () '(or null fixnum))
and then make an array with
(make-array sz :element-type 'maybe-fixnum)
what is stored in this array at low level, integer values ot pointers to the values? I understand that data in lis is tagged, so fixnum uses fewer bits in 32-a bit integer (two machine words), and nil constant might be some other tagged 32-bit entity.
Moreover, if I define a data type as
(deftype maybe-float () '(or null double-float))
now a double-float quant of data uses all bits in quadword, no place for a tag there. What will be stored in an array then, the values or pointers?
I'd also like to know how this kind of questions can be studied by hacking lisp internals? Examples with SBCL are welcome.

Kindly yours,
AZ

[Pascal J. Bourguignon]

The exact answer is implementation dependent and can be introspected
using the UPGRADED-ARRAY-ELEMENT-TYPE function.

However, in this case, there's a concensus:

$ clall -r '(upgraded-array-element-type (quote (or null fixnum)))'

Armed Bear Common Lisp --> T
Clozure Common Lisp --> T
CLISP --> T
ECL --> T
SBCL --> T


ie, indeed the array will contain references to the objects.
However, since fixnum are immutable, the implementation is allowed to
make copies of them any time, so it may avoid a pointer, and instead
store the value of the fixnum directly in the array slots. And
similarly, since NIL is such a common and important symbol, it is (or
was) often implemented as a special immediate value and therefore stored
without a pointer to the NIL symbol structure. (But probably in all
those modern implementations, it's actually just a pointer to the NIL
symbol structure, I've not checked them all).

Really, to learn more about it, you need to check the very low-level of
your implementation.


Notice for double-float it's the same:

$ clall -r '(upgraded-array-element-type (quote (or null double-float)))'

Armed Bear Common Lisp --> T
Clozure Common Lisp --> T
CLISP --> T
ECL --> T
SBCL --> T


In the case of fixnum, you could encode a "nil" value if you have one
unused fixnum (possibly most-negative-fixnum, since
(- most-negative-fixnum) will often not be a fixnum.
(it is not in all the above implementations, but notice that an
implementation may choose to make it a fixnum (ie. if it uses more than
16 bits, most-negative-fixnum can be (- most-positive-fixnum).
It could as well be (* (- most-positive-fixnum) 10)
or (truncate (- most-positive-fixnum) 10) or anything else, as long as
it's less than -2^15…))).

In the case of double-float, again, it will be implementation dependent,
but if your implementation uses IEEE floating point numbers, then you
could choose one NAN to represent a "nil", and thus be able to use a
specialized array too.


--
__Pascal J. Bourguignon
http://www.informatimago.com