\subsection{Object Format}
The port of CMU Common Lisp to the DECStation~3100 (which is based on
the MIPS R2000 RISC architecture) involves a radical departure in heap
object layout fro the previous port of CMU Common Lisp to the IBM RT
PC \cite{cmu-internal-design}.  The section briefly describes the new
object layout; it is discussed in detail elsewhere
\cite{cmu-new-object}.

In the new object format, all objects fit in a machine word which is
32 bits in the MIPS R2000 RISC architecture and all objects contain a
tag in their low three bits.  Figure~\ref{fig:new-object} illustrates
this layout.
\begin{figure}
\centerline{\psfig{figure=new-object.PS,width=15cm}}
\vspace*{2ex}
\caption{New Object Format}
\label{fig:new-object}
\end{figure}
The low-tag indicates the type of the object and, consequently, the
the format of the object.  There are eight low tags:

\begin{center}
\begin{tabular}{l|l|l}
Tag & Object Type & Format \\
\hline
000 & Even Fixnum & Immediate Data \\
001 & Function Pointer & Pointer \\
010 & Other Immediate Escape 0 & Immediate Data \\
011 & List Pointer & Pointer \\
100 & Odd Fixnum & Immediate Data \\
101 & Structure Pointer & Pointer \\
110 & Other Immediate Escape 1 & Immediate Data \\
111 & Data Block Pointer & Pointer \\
\end{tabular}
\end{center}
All objects contain either immediate data or a pointer.

\subsubsection{Immediate Data Objects}
There are essentially two types of immediate data objects.  The first
type of immediate data object is used only for representing the Common
Lisp FIXNUM data type (shown in Figure~\ref{fig:fixnum}) and these
objects are distinguished by one of two low tags: Even Fixnum or Odd
Fixnum.  The use of two low tags and specifically two low tags with
the same two least significant bits effectively gives all fixnums a
single two-bit low tag of $00$; more importantly, the use of these two
low tags lends an extra bit to the low end of the 29-bit immediate
field giving fixnums a 30-bit immediate data field.  This allows
fixnums to represent the full range of a 30-bit two's complement
integer: $- {2}^{30}$ to ${2}^{30} - 1$.
\begin{figure}
\centerline{\psfig{figure=fixnum.PS,width=15cm}}
\vspace*{2ex}
\caption{Common Lisp FIXNUM Data Type}
\label{fig:fixnum}
\end{figure}

The second type of immediate data object is used to represent all
other immediate objects manipulated by the system: characters, data
block headers, and implementation-internal objects such as the unbound
marker.  All of these objects have one of two low tags: Other
Immediate Escape 0 or Other Immediate Escape 1.  These two low tags
(which, like the fixnum tags, have been chosen so that they lend an
extra bit to the low end of the immediate data field) are escape codes
which indicate that the true type of object is in the bottom eight
bits of the object.  The Other Immediate Data Type is illustrated in
Figure~\ref{other-immed}.
\begin{figure}
\centerline{\psfig{figure=other-immed.PS,width=15cm}}
\vspace*{2ex}
\caption{Other Immediate Data Types}
\label{fig:other-immed}
\end{figure}
There may be up to 64 different immediate types represented with the
Other Immediate Data Type.

\subsection{Pointer Objects}
Pointer objects point into the middle of data blocks in the heap due
to their non-zero low tags.  A pointer object's low tag must be
subtracted or masked out before dereferencing the pointer.  Since
there are only 29 bits available for each pointer, all data blocks in
the heap are aligned on dual-word boundary.

Pointers point either to all boxed data (list pointers to conses or to
NIL; structure pointers to structures) or to a data block (function
pointers and data block pointers).

\subsection{Data Blocks}
Data blocks are blocks of memory in the heap which represent composite
objects.  Data blocks are always aligned on a dual-word boundary and
always begin with a data block header.  For composite objects which
are not represented like vectors, the immediate data of the data block
header contains the length of the object in words including the
header.  For composite objects which are 

