@c storage-conventions.botex
@c
@c 16-Nov-87, Kent Hoult
@c 31-Mar-88, James Rauen

@chapter Storage Conventions

This chapter defines the storage conventions used by the K processor for
Lisp objects.

@section Structure of Data Words

Words in the machine consist of 33 bits. The most significant bit (bit
32) is referred to as the BOX bit. When zero, the other 32 bits of the
word contain an untyped 32 bit number. The only software which should
explicitly manipulate unboxed data is internal system routines.

@group
@tex
\startbyf
\bif{32}    {0}
\byf{31}{ 0}{Unboxed Data}
\endbyf
\line{\hfil\byfnumbers}
\line{\hfil\byfbox}
@end tex
@end group

When the box bit is set, the word is a typed LISP value. The most
significant 6 bits (31:26) indicate the data type of the word. Bits 25:0
vary in meaning with the data type.  Very often, bits 25:0 are used as
a pointer into virtual memory.  Hence, this field is often called the
"pointer" field.

@group
@tex
\startbyf
\bif{32}    {1}
\byf{31}{26}{Data Type}
\byf{25}{ 0}{Pointer}
\endbyf
\line{\hfil\byfnumbers}
\line{\hfil\byfbox}
@end tex
@end group

@section Tables of Data Types

The six DTP (Data Type) bits can represent up to 64 distinct types.  The
data type definitions currently reside in K-SYS: K; DATA-TYPES LISP.  By
convention, data types 0 to 31 are visible data types.  (They identify
valid Lisp objects.)  Data types 32 to 63 are invisible data types used
by the internal system routines.  This distinction is arbitrary and is
not enforced by the hardware.


Data types 26 through 31 and 49 through 63 are currently unassigned.

@page
@subsection Visible Data Types

@settabs 6 @columns
@sp 1
@< @i[DTP]       @\ @i[DTP] @cr
@< @i[(Decimal)] @\ @i[(Binary)] @\ @i[Data Type] @cr
@sp 1
@< 0  @\ 000000 @\ $$DTP-NIL @cr
@< 1  @\ 000001 @\ $$DTP-FIXNUM @cr
@< 2  @\ 000010 @\ $$DTP-CONS @cr
@< 3  @\ 000011 @\ $$DTP-SYMBOL @cr
@sp 1
@< 4  @\ 000100 @\ $$DTP-BIGNUM @cr
@< 5  @\ 000101 @\ $$DTP-SHORT-FLOAT @cr
@< 6  @\ 000110 @\ $$DTP-SINGLE-FLOAT @cr
@< 7  @\ 000111 @\ $$DTP-DOUBLE-FLOAT @cr
@sp 1
@< 8  @\ 001000 @\ $$DTP-RATIONAL @cr
@< 9  @\ 001001 @\ $$DTP-COMPLEX @cr
@< 10 @\ 001010 @\ $$DTP-LOCATIVE @cr
@< 11 @\ 001011 @\ $$DTP-UNBOXED-LOCATIVE @cr
@sp 1
@< 12 @\ 001100 @\ $$DTP-COMPILED-FUNCTION @cr
@< 13 @\ 001101 @\ $$DTP-CODE @cr
@< 14 @\ 001110 @\ $$DTP-ARRAY @cr
@< 15 @\ 001111 @\ $$DTP-STACK-GROUP @cr
@sp 1
@< 16 @\ 010000 @\ $$DTP-INSTANCE @cr
@< 17 @\ 010001 @\ $$DTP-LEXICAL-CLOSURE @cr
@< 18 @\ 010010 @\ $$DTP-INTERPRETER-CLOSURE @cr
@< 19 @\ 010011 @\ $$DTP-LEXICAL-ENVIRONMENT @cr
@sp 1
@< 20 @\ 010100 @\ $$DTP-STRUCTURE @cr
@< 21 @\ 010101 @\ $$DTP-CHARACTER @cr
@< 22 @\ 010110 @\ $$DTP-EXTEND @cr
@< 23 @\ 010111 @\ $$DTP-ENCAPSULATION @cr
@< 24 @\ 011000 @\ $$DTP-HASH-TABLE @cr
@cleartabs

@page
@subsection Invisible Data Types

@settabs 6 @columns
@sp 1
@< @i[DTP]       @\ @i[DTP] @cr
@< @i[(Decimal)] @\ @i[(Binary)] @\ @i[Data Type] @cr
@sp 1
@< 32 @\ 100000 @\ $$DTP-UNBOXED-HEADER @cr
@< 33 @\ 100001 @\ $$DTP-SYMBOL-HEADER @cr
@< 34 @\ 100010 @\ $$DTP-ARRAY-HEADER-SINGLE @cr
@< 35 @\ 100011 @\ $$DTP-ARRAY-HEADER-MULTIPLE @cr
@sp 1
@< 36 @\ 100100 @\ $$DTP-ARRAY-HEADER-EXTENSION @cr
@< 37 @\ 100101 @\ $$DTP-EXTERNAL-VALUE-CELL-POINTER @cr
@< 38 @\ 100110 @\ $$DTP-GC-FORWARD @cr
@< 39 @\ 100111 @\ $$DTP-ONE-Q-FORWARD @cr
@sp 1
@< 40 @\ 101000 @\ $$DTP-INDEXED-FORWARD @cr
@< 41 @\ 101001 @\ $$DTP-INSTANCE-HEADER @cr
@< 42 @\ 101010 @\ $$DTP-ARRAY-LEADER-HEADER @cr
@< 43 @\ 101011 @\ $$DTP-UNBOUND @cr
@sp 1
@< 44 @\ 101100 @\ $$DTP-HEADER-FORWARD @cr
@< 45 @\ 101101 @\ $$DTP-BODY-FORWARD @cr
@< 46 @\ 101110 @\ $$DTP-COMPILED-FUNCTION-HEADER @cr
@< 47 @\ 101111 @\ $$DTP-STRUCTURE-HEADER @cr
@< 48 @\ 110000 @\ $$DTP-HASH-TABLE-HEADER @cr
@cleartabs

@section Numbers

@subsection Fixnums

Fixnums have a data type of $$DTP-FIXNUM. Bits 23:0 of the pointer field
contain a 24-bit two's complement value. Bits 25:24 are unused and
should be zero.

@tex
Fixnums have a range of $-2^{23}$ through $2^{23} - 1$.
@end tex

@group
@tex
\startbyf
\bif{32}    {1}
\byf{31}{26}{000001}
\byf{25}{24}{00}
\byf{23}{ 0}{24-Bit Two's Complement Value}
\endbyf
\line{\hfil\byfnumbers}
\line{\hfil\byfbox}
@end tex
@end group

@subsection Bignums

Bignums have a data type of $$DTP-BIGNUM. A bignum is a pointer to a
memory structure. The memory structure consists of a header word with
data-type $$DTP-UNBOXED-HEADER and a pointer field containing the number
of words of storage used for the bignum data words. The words after the
header form an N-word two's complement number stored least significant
word first. Bignum storage is allocated in structure space.

@tex
Bignums may use up to $2^{18}$ words of storage for a number.
The range of bignums is $-2^{2^{23}}$ to $2^{2^{23}} - 1$.  However, a
bignum may not have a value in the fixnum range ($-2^{23}$ to $2^{23} - 1$).
If the result of a bignum operation lies in that range, it must be converted
to a fixnum.
@end tex

@group
@tex
\startbyf
\bif{32}    {1}
\byf{31}{26}{000100}
\byf{25}{ 0}{Pointer (P)}
\endbyf
\line{\hfil\byfnumbers}
\line{\hfil\byfbox}
\vskip 0.2in

\startbyf
\byf{31}{26}{100000}
\byf{25}{19}{Unknown}
\byf{18}{ 0}{Number of data words (N)}
\endbyf
\line{\hfil\byfnumbers}
\line{\hfil$P\rightarrow$\byfbox}

\startbyf
\byf{31}{ 0}{Least Significant Word}
\endbyf
\line{\hfil$P+1\rightarrow$\byfbox}

\startbyf
\byf{31}{ 0}{Middle Words $\ldots$}
\endbyf
\line{\hfil$\ldots$\byfbox}

\startbyf
\byf{31}{ 0}{Most Significant Word}
\endbyf
\line{\hfil$P+N\rightarrow$\byfbox}
@end tex
@end group

@subsection Rationals

Rational numbers consist of a numerator and a denominator.  Each may be
either a fixnum or a bignum. A rational has a data-type of
$$DTP-RATIONAL. The pointer field points to a pair of words in memory
which contain the numerator and denominator. The storage for
rationals is allocated in CONS space.

@group
@tex
\startbyf
\bif{32}    {1}
\byf{31}{26}{001000}
\byf{25}{ 0}{Pointer (P)}
\endbyf
\line{\hfil\byfnumbers}
\line{\hfil\byfbox}
\vskip 0.2in

\startbyf
\byf{31}{26}{Data Type}
\byf{25}{ 0}{Fixnum or Bignum (Numerator)}
\endbyf
\line{\hfil\byfnumbers}
\line{\hfil$P\rightarrow$\byfbox}

\startbyf
\byf{31}{26}{Data Type}
\byf{25}{ 0}{Fixnum or Bignum (Denominator)}
\endbyf
\line{\hfil$P+1\rightarrow$\byfbox}
@end tex
@end group

@subsection Complex

Complex numbers consist of a real and an imaginary part. Each may be of
any numeric type other than Complex. A complex has a data type of
$$DTP-COMPLEX.  The pointer field points to a pair of words in memory,
the real and imaginary parts of the number.  The storage for complex
numbers is allocated in CONS space.

@group
@tex
\startbyf
\bif{32}    {1}
\byf{31}{26}{001001}
\byf{25}{ 0}{Pointer (P)}
\endbyf
\line{\hfil\byfnumbers}
\line{\hfil\byfbox}
\vskip 0.2in

\startbyf
\byf{31}{26}{Data Type}
\byf{25}{ 0}{Any number except Complex (Real Part)}
\endbyf
\line{\hfil\byfnumbers}
\line{\hfil$P\rightarrow$\byfbox}

\startbyf
\byf{31}{26}{Data Type}
\byf{25}{ 0}{Any number except Complex (Imaginary Part)}
\endbyf
\line{\hfil$P+1\rightarrow$\byfbox}
@end tex
@end group

@subsection Short Floating Point

Short floating point numbers have a data type of $$DTP-SHORT-FLOAT. The
pointer field contains the high order 26 bits of an IEEE single
precision floating point number.  This includes a sign bit, an 8-bit
excess 127 exponent, and a 17-bit mantissa.

@group
@tex
\startbyf
\bif{32}    {1}
\byf{31}{26}{000101}
\bif{25}    {S}
\byf{24}{17}{Exponent}
\byf{16}{ 0}{Mantissa}
\endbyf
\line{\hfil\byfnumbers}
\line{\hfil\byfbox}
@end tex
@end group

@subsection Single Precision Floating Point

A single float value has a data-type of $$DTP-SINGLE-FLOAT.  The pointer
field points to a memory structure introduced by an unboxed header
($$DTP-UNBOXED-HEADER) whose pointer field contains a length of one.
The data word contains a single precision IEEE floating point number.

@group
@tex
\startbyf
\bif{32}    {1}
\byf{31}{26}{000110}
\byf{25}{ 0}{Pointer (P)}
\endbyf
\line{\hfil\byfnumbers}
\line{\hfil\byfbox}

\startbyf
\byf{31}{26}{100000}
\byf{25}{ 0}{00 00000000 00000000 00000001}
\endbyf
\line{\hfil\byfnumbers}
\line{\hfil$P\rightarrow$\byfbox}

\startbyf
\bif{31}    {S}
\byf{30}{23}{Exponent}
\byf{22}{ 0}{Mantissa}
\endbyf
\line{\hfil$P+1\rightarrow$\byfbox}
\line{\hfil\byfnumbers}
@end tex
@end group

@subsection Double Precision Floating Point

A double float value has a data type of $$DTP-DOUBLE-FLOAT.  The pointer
field points to a memory structure introduced by an unboxed header
($$DTP-UNBOXED-HEADER) whose pointer field contains a length of two.
The first data word contains the least significant part of an double
precision IEEE floating point number. The second word contains the most
significant part of the number.

@group
@tex
\startbyf
\bif{32}    {1}
\byf{31}{26}{000111}
\byf{25}{ 0}{Pointer (P)}
\endbyf
\line{\hfil\byfnumbers}
\line{\hfil\byfbox}

\startbyf
\byf{31}{26}{100000}
\byf{25}{ 0}{00 00000000 00000000 00000010}
\endbyf
\line{\hfil\byfnumbers}
\line{\hfil$P\rightarrow$\byfbox}

\startbyf
\byf{31}{ 0}{Mantissa - Low}
\endbyf
\line{\hfil$P+1\rightarrow$\byfbox}

\startbyf
\bif{31}    {S}
\byf{30}{21}{Exponent}
\byf{20}{ 0}{Mantissa - High}
\endbyf
\line{\hfil$P+2\rightarrow$\byfbox}
\line{\hfil\byfnumbers}
@end tex
@end group

@section Unboxed Structures

Unboxed structures are used for storage of untyped non-array data in
memory.  Unboxed structures do not indicate what kind of data they are
storing; this is determined by the data type of the Lisp object which
points to the unboxed structure.  For exampes of data types which use
unboxed structures, see bignums, single floats, and double floats.

An unboxed structure is introduced by a word of type $$DTP-UNBOXED-HEADER
whose pointer field contains the number of data words following the
header.  In the following chart, P is the pointer field of the Lisp object
which points to the unboxed structure.

@group
@tex
\startbyf
\byf{31}{26}{100000}
\byf{25}{ 0}{Number of Data Words (N)}
\endbyf
\line{\hfil\byfnumbers}
\line{\hfil$P\rightarrow$\byfbox}

\startbyf
\byf{31}{ 0}{First Unboxed Data Word}
\endbyf
\line{\hfil$P+1\rightarrow$\byfbox}

\startbyf
\byf{31}{ 0}{More Unboxed Data Words}
\endbyf
\line{\hfil$\cdots$\byfbox}

\startbyf
\byf{31}{ 0}{Last Unboxed Data Word}
\endbyf
\line{\hfil$P+N\rightarrow$\byfbox}
@end tex
@end group


@section Characters

@section Conses

A cons has a data type of $$DTP-CONS.  Its pointer field points to a
pair of words in memory, the car and cdr of the cons cell.  The storage
for conses is allocated in CONS space.

@group
@tex
\startbyf
\bif{32}    {1}
\byf{31}{26}{000010}
\byf{25}{ 0}{Pointer (P)}
\endbyf
\line{\hfil\byfnumbers}
\line{\hfil\byfbox}

\startbyf
\byf{31}{26}{Data Type}
\byf{25}{ 0}{Car}
\endbyf
\line{\hfil\byfnumbers}
\line{\hfil$P\rightarrow$\byfbox}

\startbyf
\byf{31}{26}{Data Type}
\byf{25}{ 0}{Cdr}
\endbyf
\line{\hfil$P+1\rightarrow$\byfbox}
@end tex
@end group

@section Arrays

Arrays have two related storage formats, simple arrays and hard arrays.
Simple arrays are one-dimensional arrays that are not adjustable, not
displaced, and do not have fill pointers or leaders.  Hard arrays (also
referred to as "full" or "multiple" arrays) can have up to seven
dimensions, can be adjustable, can be displaced, and can have leaders
and fill pointers.  Simple arrays are faster to access and require less
overhead for storage than do hard arrays.

All arrays consist of an array pointer of type $$DTP-ARRAY which points
to the header of the array. The header either has type
$$DTP-ARRAY-HEADER-SINGLE, for simple arrays, or
$$DTP-ARRAY-HEADER-MULTIPLE, for hard arrays.  The array's data begins
in the word following the header. If the array is hard, then there are
more words of header information preceding the header word in memory.

@group
@tex
\startbyf
\bif{32}    {1}
\byf{31}{26}{001110}
\byf{25}{ 0}{Pointer (P) to Array Header}
\endbyf
\line{\hfil\byfnumbers}
\line{\hfil\byfbox}
@end tex
@end group

@subsection Array Element Types

The array header information contains a five-bit field called the "Array
Type".  This number describes the types of elements the array can
contain.  In simple arrays, this number is contained in bits 25:21 of
the array header.  In hard arrays, bits 25:21 of the array header are
11111, and the array type is found in bits 13:9 of the extension header.

@settabs 6 @columns
@sp 1
@<          @\ @\ @i[Bits per] @\ @i[Array] @\ @i[Range or Type] @cr
@< @i[Type] @\ @\ @i[Element] @\ @i[Type] @\ @i[of Elements] @cr
@sp 1
@< ART-Q    @\ @\ 32 @\ 00000 @\ Any Lisp object @cr
@< ART-1B   @\ @\ 1  @\ 00001 @\ 0 to 1 @cr
@< ART-2BS  @\ @\ 2  @\ 00010 @\ -2 to 1 @cr
@< ART-2B   @\ @\ 2  @\ 00011 @\ 0 to 3 @cr
@sp 1
@< ART-4BS  @\ @\ 4  @\ 00100 @\ -8 to 7 @cr
@< ART-4B   @\ @\ 4  @\ 00101 @\ 0 to 15 @cr
@< ART-8BS  @\ @\ 8  @\ 00110 @\ -128 to 127 @cr
@< ART-8B   @\ @\ 8  @\ 00111 @\ 0 to 255 @cr
@sp 1
@< ART-16BS @\ @\ 16 @\ 01000 @\ -32768 to 32767 @cr
@< ART-16B  @\ @\ 16 @\ 01001 @\ 0 to 65536 @cr
@< ART-32BS @\ @\ 32 @\ 01010 @\ -2147483648 to 2147483647 @cr
@< ART-32B  @\ @\ 32 @\ 01011 @\ 0 to 4294967296 @cr
@sp 1
@< ART-STRING @\ @\ 8 @\ 01100 @\ Characters @cr
@< ART-FAT-STRING @\ @\ 16 @\ 01101 @\ Characters w/fonts @cr
@< ART-SINGLE-FLOAT @\ @\ 32 @\ 01110 @\ Single precision floats @cr
@< ART-DOUBLE-FLOAT @\ @\ 64 @\ 01111 @\ Double precision floats @cr
@sp 1
@< ART-CONTROL-PDL @\ @\ ?? @\ 11100 @\ ?? @cr
@< ART-EXTRANEOUS-PDL @\ @\ ?? @\ 11101 @\ ?? @cr
@< ART-SPECIAL-PDL @\ @\ ?? @\ 11110 @\ ?? @cr
@< ART-HARD @\ @\ ?? @\ 11111 @\ In extension header @cr
@cleartabs

@subsubsection ART-Q

An ART-Q (array type 00000) array can store any Lisp object in each
array location. The elements of the array use one word of storage each.

The array type of ART-Q is 00000 as an optimization for array
reference software since this is the most common array type.

@subsubsection Bit array types

Bit arrays store either a signed or unsigned integer in each element.
Types that are smaller than a word have multiple elements packed into
each word. The element with the lowest array index is stored in the
least significant bits of the word. When a value is read by the @l[AREF]
function, it is converted to a fixnum (except for large 32 bit numbers,
which are converted to bignums). The signed bit array types are stored
as two's complement numbers.

Bit arrays have array types from 00001 to 01001.

@subsubsection Strings

There are two array types used for strings, ART-STRING (array type
01100) and ART-FAT-STRING (array type 01101).  Elements of ART-STRING
arrays are eight-bit characters.  Elements of ART-FAT-STRING arrays are
sixteen-bit characters (they also allow font and bit information).

ART-STRING arrays are stored like ART-8B arrays. However, data read out
is converted to a character instead of a fixnum. This array type is the
Common Lisp string type.

ART-FAT-STRING arrays are stored like ART-16B arrays. Data read out is
also converted to characters, but the high 8 bits are now converted into
font and bit information for the character.


@subsubsection Floating point

There are two types of floating point arrays, ART-SINGLE-FLOAT (array
type 01110) and ART-DOUBLE-FLOAT (array type 01111). Both hold IEEE
standard format floating point values. The ART-SINGLE-FLOAT arrays use
one word to store a number, whereas ART-DOUBLE-FLOAT arrays use two
words to contain a value.  The least significant part of the double
precision number is stored in the first word, and the most significant
part is stored in the second word.

@subsection Format of Array Data

@tex
Depending on the array type, an array element can be anywhere from 1 bit
to 64 bits long.  In general, if there are $N$ elements in an array,
and each element requires $B$ bits of storage, the number of words in the
array's data will be $S = \lceil NB/32\rceil$, where $\lceil x\rceil$
represents the lowest integer greater than or equal to $x$.
@end tex

The elements are laid out in memory with lower indices corresponding to
lower memory locations.  Within a word, lower array indices correspond
to less significant bits.  Multidimensional arrays are arranged in
row-major form.  For a detailed description of how these arrays are laid
out, see @i[Common Lisp, the Language], pp. 286-298.

(& example?)


@subsection Simple Arrays

Simple arrays are one dimensional arrays ("vectors") of any of the
allowed array types. They are not adjustable, not displaced, and do not
have fill pointers or leaders. A simple array has data type $$DTP-ARRAY
(001110).  Its pointer field points to a header with data type
$$DTP-ARRAY-HEADER-SINGLE (100010).  Bits 25:21 of the header contain
the array type.  Bits 20:0 of the header indicate the number of elements
in the array.

@group
@tex
\startbyf
\bif{32}    {1}
\byf{31}{26}{001110}
\byf{25}{ 0}{Pointer (P) to Array-Header-Single}
\endbyf
\line{\hfil\byfnumbers}
\line{\hfil\byfbox}
\vskip 0.2in

\startbyf
\byf{31}{26}{100010}
\byf{25}{21}{ArType}
\byf{20}{ 0}{Number of elements (N)}
\endbyf
\line{\hfil\byfnumbers}
\line{\hfil$P\rightarrow$\byfbox}

\startbyf
\byf{31}{ 0}{First Word of Array Contents}
\endbyf
\line{\hfil$P+1\rightarrow$\byfbox}

\startbyf
\byf{31}{ 0}{Middle Words of Array Contents $\ldots$}
\endbyf
\line{\hfil$\ldots$\byfbox}

\startbyf
\byf{31}{ 0}{Last Word of Array Contents}
\endbyf
\line{\hfil$P+N\rightarrow$\byfbox}
@end tex
@end group

@subsection Hard Arrays

Hard arrays have a more complicated format than do simple arrays.  A
hard array has data type $$DTP-ARRAY (001110).  Its pointer field points
to a header with data type $$DTP-ARRAY-HEADER-MULTIPLE (100011).  The
array's data follows the header.  Additional array information appears
in memory locations @i[before] the header.  This additional information
is introduced with a header of data type $$DTP-ARRAY-HEADER-EXTENSION
(100100), and it extends from the array-header-extension header up to
the array-header-multiple header.

@group
@tex
\startbyf
\bif{32}    {1}
\byf{31}{26}{001110}
\byf{25}{ 0}{Pointer (P) to Array-Header-Multiple}
\endbyf
\line{\hfil\byfnumbers}
\line{\hfil\byfbox}

\startbyf
\byf{31}{26}{100100}
\byf{25}{ 0}{Offset (K) to Main Header}
\endbyf
\line{\hfil\byfnumbers}
\line{\hfil$P-K\rightarrow$\byfbox}

\startbyf
\byf{31}{26}{Data Type}
\byf{25}{ 0}{Last Leader Word}
\endbyf
\line{\hfil\byfbox}
\centerline{$\cdots$}

\startbyf
\byf{31}{26}{Data Type}
\byf{25}{ 0}{First Leader Word}
\endbyf
\line{\hfil\byfbox}

\startbyf
\byf{31}{26}{000001}
\byf{25}{ 0}{Number of Leader Words (FIXNUM)}
\endbyf
\line{\hfil\byfbox}

\startbyf
\byf{31}{26}{000001}
\byf{25}{ 0}{Displacement Offset (FIXNUM)}
\endbyf
\line{\hfil\byfbox}

\startbyf
\byf{31}{26}{Data Type}
\byf{25}{ 0}{Displaced-To (ARRAY or LOCATIVE)}
\endbyf
\line{\hfil\byfbox}

\startbyf
\byf{31}{26}{000001}
\byf{25}{ 0}{Extent of Dimension J (FIXNUM)}
\endbyf
\line{\hfil\byfbox}
\centerline{$\cdots$}

\startbyf
\byf{31}{26}{000001}
\byf{25}{ 0}{Extent of Dimension 2 (FIXNUM)}
\endbyf
\line{\hfil\byfbox}

\startbyf
\byf{31}{26}{000001}
\byf{25}{ 0}{Additional Header Word (FIXNUM)}
\endbyf
\line{\hfil$P-1\rightarrow$\byfbox}

\startbyf
\byf{31}{26}{100011}
\byf{25}{21}{11111}
\byf{20}{0}{Extent of Dimension 1}
\endbyf
\line{\hfil$P\rightarrow$\byfbox}

\startbyf
\byf{31}{ 0}{First Word of Array Contents}
\endbyf
\line{\hfil$P+1\rightarrow$\byfbox}

\centerline{$\cdots$}

\startbyf
\byf{31}{ 0}{Last Word of Array Contents}
\endbyf
\line{\hfil$P+S\rightarrow$\byfbox}
@end tex
@end group

@subsubsection Extension Header Format

An array header extension has data type $$DTP-FIXNUM (000001).  It has
the following format:

@settabs 6 @columns
@sp 1
@< @i[Bit(s)] @\ @i[Meaning] @cr
@sp 1
@< 31:26 @\ Data Type field (000001) @cr
@< 25:23 @\ Spare @cr
@< 22 @\ Is the array adjustable? (0 = no, 1 = yes) @cr
@< 21 @\ Does the array have a fill pointer? (0 = no, 1 = yes) @cr
@< 20 @\ Is the array a named structure? (0 = no, 1 = yes) @cr
@< 19 @\ Is the array displaced? (0 = no, 1 = yes) @cr
@< 18 @\ Spare @cr
@< 17 @\ Does the array have a leader? (0 = no, 1 = yes) @cr
@< 16:14 @\ Number of array dimensions (J) @cr
@< 13:9 @\ Array type.  11111 is an error. @cr
@< 8:4 @\ Spare @cr
@< 3:0 @\ Leader offset (L) @cr

@subsubsection Fill Pointer

        The fill pointer is a fixnum that indicates the number of
        words currently used in an array. If present, it is the first 
	leader word.

@subsubsection Displaced Arrays

@subsubsection Leaders

If the has leader bit is set then the array has an array leader. The
offset from the main header to the "Number Of Leader Words" word is in the
leader-offset field.


@section Compiled Functions

A compiled function has a data type of $$DTP-COMPILED-FUNCTION (001100).
The pointer field points to a memory structure consisting of a
$$DTP-COMPILED-FUNCTION-HEADER (101110) whose pointer field contains
the number of instructions in the function.  Following the header are
six more words whose purposes are described below.  

@tex 
The code pointer CP is computed from the PC according to the rule
given in the Program Counter chapter ($CP = 2\times PC + 2^{25}$).  
@end tex

@group
@tex
\startbyf
\bif{32}    {1}
\byf{31}{26}{001100}
\byf{25}{ 0}{Pointer (P) to Compiled Function Header}
\endbyf
\line{\hfil\byfnumbers}
\line{\hfil\byfbox}

\startbyf
\byf{31}{26}{101110}
\byf{25}{ 0}{Number of Instructions in Function (N)}
\endbyf
\line{\hfil\byfnumbers}
\line{\hfil$P\rightarrow$\byfbox}

\startbyf
\byf{31}{26}{Data Type}
\byf{25}{ 0}{Compiled Function Name}
\endbyf
\line{\hfil$P+1\rightarrow$\byfbox}

\startbyf
\byf{31}{26}{Data Type}
\byf{25}{ 0}{Compiled Function Entry Points}
\endbyf
\line{\hfil$P+2\rightarrow$\byfbox}

\startbyf
\byf{31}{26}{Data Type}
\byf{25}{ 0}{Compiled Function Local Refs}
\endbyf
\line{\hfil$P+3\rightarrow$\byfbox}

\startbyf
\byf{31}{26}{Data Type}
\byf{25}{ 0}{Compiled Function Refs}
\endbyf
\line{\hfil$P+4\rightarrow$\byfbox}

\startbyf
\byf{31}{26}{Data Type}
\byf{25}{ 0}{Compiled Function Length}
\endbyf
\line{\hfil$P+5\rightarrow$\byfbox}

\startbyf
\byf{31}{26}{Data Type}
\byf{25}{ 0}{Compiled Function Code Pointer (CP)}
\endbyf
\line{\hfil$P+6\rightarrow$\byfbox}

\line{\hfil\byfnumbers}
\startbyf
\byf{31}{26}{001100}
\byf{25}{ 0}{Back Pointer to Compiled Function (P)}
\endbyf
\line{\hfil$CP-2\rightarrow$\byfbox}

\startbyf
\byf{31}{ 0}{{\#}x 7FFFFFFE}
\endbyf
\line{\hfil$CP-1\rightarrow$\byfbox}

\startbyf
\byf{31}{ 0}{First Instruction, Low Word}
\endbyf
\line{\hfil$CP\rightarrow$\byfbox}

\startbyf
\byf{31}{ 0}{First Instruction, High Word}
\endbyf
\line{\hfil$CP+1\rightarrow$\byfbox}

\startbyf
\byf{31}{ 0}{More Instructions$\ldots$}
\endbyf
\line{\hfil$\ldots$\byfbox}

\startbyf
\byf{31}{ 0}{Last Instruction, Low Word}
\endbyf
\line{\hfil$CP+2N-2\rightarrow$\byfbox}

\startbyf
\byf{31}{ 0}{Last Instruction, High Word}
\endbyf
\line{\hfil$CP+2N-1\rightarrow$\byfbox}
@end tex
@end group

@subsection Compiled Function Name

        This is the first word after the function header. It is a symbol,
the name of the function.

@subsection Compiled Function Entry Points

        This is the second word after the function header. It is a
simple array containing the entry point information.

        All even locations in the vector contain the number of
        arguments required to use this entry point. The odd
        locations contain the offset to the PC for the corresponding entry point.
        There will be more than one entry point only if optional
        arguments are used by the function.

        When the function takes a @l[&rest] argument, then the last even
        location contains a negative fixnum. If you subtract
        this number from -1 you will get the minimum number of
        arguments required to use this entry point.

@subsection Compiled Function Local Refs

        This is the third word after the function header. It is
a simple array containing the
        local reference information. This is used to adjust the
        branch instructions inside the function when loading it.

        The local references are stored as pairs. The first location
        of each pair contains the number of instructions to offset
        to the one to be adjusted.

        The second location of the pair contains the number of
        instructions into the function that the branch is to.

@subsection Compiled Function Refs

This is the fourth word after the function header.  It is a simple
array containing the external reference information.

        Each entry in the vector is a triple. The first word of the
        triple contains the number of arguments that the function is
        calling with.
        The second word of the triple contains the instruction
        offset to the call instruction.
        The third word contains a symbol pointer to the function
        being referenced.

@subsection Compiled Function Length

This is the fifth word after the function header.  It is a fixnum, the
number of instructions in the function. This is redundant with the
information in the function header word.

@subsection Compiled Function Code Pointer

This is the sixth word after the function header.  It has data type
$$DTP-CODE and a PC in the pointer field.  It points to the first
instruction of the code before entry point offsetting. 

@subsection Instruction Back Pointer

      The instruction just before the one that the code pointer
      points to contains a special illegal instruction. The top 32
      bits of this instruction are the "magic number" #x7FFFFFE and the low word
      contains a compiled function pointer back to the compiled
      function structure for this function.

      This is used to convert from a PC to a function pointer by
      scanning backwards in memory from the PC until the illegal
      instruction is found, and then following the pointer.

@subsection Changes to Format

The starting-address field has been eliminated; it and the code field
were redundant.

@section Symbols

    A symbol pointer has the data type $$DTP-SYMBOL (000011).  Its pointer field points to
    a symbol structure in memory. The symbol structure contains
    five words, which are described below.

@group
@tex
\startbyf
\bif{32}    {1}
\byf{31}{26}{000011}
\byf{25}{ 0}{Pointer (P)}
\endbyf
\line{\hfil\byfnumbers}
\line{\hfil\byfbox}

\startbyf
\byf{31}{26}{100001}
\byf{25}{ 0}{Pointer to Array Header of Print Name}
\endbyf
\line{\hfil\byfnumbers}
\line{\hfil$P\rightarrow$\byfbox}

\startbyf
\byf{31}{26}{Data Type}
\byf{25}{ 0}{Value Cell}
\endbyf
\line{\hfil$P+1\rightarrow$\byfbox}

\startbyf
\byf{31}{26}{Data Type}
\byf{25}{ 0}{Function Cell}
\endbyf
\line{\hfil$P+2\rightarrow$\byfbox}

\startbyf
\byf{31}{26}{Data Type}
\byf{25}{ 0}{Package Cell}
\endbyf
\line{\hfil$P+3\rightarrow$\byfbox}

\startbyf
\byf{31}{26}{Data Type}
\byf{25}{ 0}{Property List}
\endbyf
\line{\hfil$P+4\rightarrow$\byfbox}
@end tex
@end group


@subsection Symbol Header

      The first word of a symbol structure has the data type
      $$DTP-SYMBOL-HEADER. Its pointer field points to an array
      header of an array containing the print name of the symbol.

@subsection Symbol Value 

      The second word of a symbol structure contains the value of
      the symbol. This can be either a visible Lisp object or the special
      unbound object. The unbound object is a word with a
      data type of $$DTP-UNBOUND whose pointer field points to the beginning of
      the symbol structure.

@subsection Symbol Function

      The third word of a symbol structure (the "function cell") contains the function
      information for the symbol.  Although it may contain any Lisp value,
only the following are valid:

@subsubsection Unbound

The function cell contains the unbound object.  The symbol has no
function or macro definition.

@subsubsection Compiled Function

The function cell contains an object whose data type is
$$DTP-COMPILED-FUNCTION.  

@subsubsection Interpreted Function

The function cell contains either an object whose data type is
$$DTP-INTERPRETER-CLOSURE or a list whose CAR is the symbol LISP:LAMBDA.

@subsubsection Compiled Macro

The function cell contains a cons cell whose CAR is the symbol LISP:MACRO
and whose CDR is a compiled function.

@subsubsection Interpreted Macro

The function cell contains a cons cell whose CAR is the symbol LISP:MACRO
and whose CDR is either an interpreter closure or a list whose CAR is the
symbol LISP:LAMBDA.

@subsection Symbol Package

      The fourth word of a symbol structure is the symbol's package.
During the cold and warm loads, before the package system is installed, this
word is a string which names the package.  After the package system is
installed, this word is the actual package object.

@subsection Symbol Property List

      The fifth word of the symbol strucure contains the property
      list of the symbol.

@section NIL

NIL is a word whose data type is $$DTP-NIL (000000) and whose
pointer field also contains all zeros.
This makes it easy to test for NIL. Location zero in memory contains a
    degenerate symbol structure for NIL. All of its words
    are normal, except for the header. Both the header and value
    cell contain NIL (so CAR and CDR of NIL give NIL). The
    SYMBOL-NAME function knows this and handles the print name
    of NIL specially.

@group
@tex
\startbyf
\bif{32}    {1}
\byf{31}{26}{000000}
\byf{25}{ 0}{00 00000000 00000000 00000000}
\endbyf
\line{\hfil\byfnumbers}
\line{\hfil\byfbox}
@end tex
@end group

@section T

    T is a normal symbol. The only thing odd about it is that it has an
 absolute location of five, and the SET function won't
    let you change its value.

@section Defstruct Structure Instances

A structure instance has the data type $$DTP-STRUCTURE.  The pointer
field points to a memory structure introduced by a structure header.  
The structure header has data type $$DTP-STRUCTURE-HEADER (101111).
Its pointer field contains the number of words
in the structure, plus one for the name.  The first word after the header
is a symbol, the name of the structure.  The subsequent words are the
structure elements.

@group
@tex
\startbyf
\bif{32}    {1}
\byf{31}{26}{010100}
\byf{25}{ 0}{Pointer (P)}
\endbyf
\line{\hfil\byfnumbers}
\line{\hfil\byfbox}

\startbyf
\byf{31}{26}{101111}
\byf{25}{ 0}{Number of structure elements + 1 ($N+1$)}
\endbyf
\line{\hfil\byfnumbers}
\line{\hfil$P\rightarrow$\byfbox}

\startbyf
\byf{31}{26}{000011}
\byf{25}{ 0}{Name of Structure (SYMBOL)}
\endbyf
\line{\hfil$P+1\rightarrow$\byfbox}

\startbyf
\byf{31}{26}{Data Type}
\byf{25}{ 0}{First Structure Element}
\endbyf
\line{\hfil$P+2\rightarrow$\byfbox}

\line{\hfil$\cdots$\hfil}

\startbyf
\byf{31}{26}{Data Type}
\byf{25}{ 0}{Last Structure Element}
\endbyf
\line{\hfil$P+(N+1)\rightarrow$\byfbox}
@end tex
@end group


@section Undocumented So Far

Storage conventions for the following visible data types are either not
documented or not established.

LOCATIVE, UNBOXED-LOCATIVE, CODE, STACK-GROUP,
INSTANCE, LEXICAL-CLOSURE, INTERPRETER-CLOSURE, LEXICAL-ENVIRONMENT,
EXTEND, ENCAPSULATION, HASH-TABLE.