\chapter{External Representation}
\label{ciobl}

\newcommand{\KW}[1]{{\tt \KWW#1}}
\def\KWW:#1{:\uppercase#1}
\newcommand{\code}[1]{{\tt #1}}
\newcommand{\lispchar}{{\tt \#\char`\\}}

CIOBL stands for ``Compiler Input/Output Base Language'', and is pronounced
``CHO-bul'', as if it were an Italian word.  It refers to a language for
representing various types of data in files.  The ``Compiler'' refers to
the Id Compiler, but CIOBL has applications beyond communicating with the
Id Compiler, such as representing GITA statistics.  It is designed to be
flexible enough to accomodate three broad categories of files:
 \begin{enumerate}
\item 
 Files that have structure to their data but do not imply a particular
representation for the data within programs that manipulate it.  Example: TTDA
object code files produced by the Id Compiler.  TTDA object code files have a
particular structure determined in part by the Tagged-Token Dataflow
Architecture, but do not require a program that uses object code --- GITA,
for example --- to represent object code internally in any particular way.

\item
 Files that have a structure and also a particular representation for certain
components, but whose representation is simple enough to be supported by a
variety of implementations.  Example: GITA statistics files.  The main parts of
these have a particular representation as arrays of data, but arrays are a
simple enough data type that implementations other than Common Lisp can make
use of them.

\item 
 Files that have a structure and a particular representation in a particular
Common Lisp program.  Example:  Id Compiler internal program graph files.
These files contain data structures that are represented by objects defined
within the Id Compiler code, and are not meant to be (easily) read by programs
other than the Id Compiler.
\end{enumerate}

Throughout this document, these three applications will be referred to Category
I, Category II, and Category III.

The main feature of CIOBL is that it provides three different {\em encodings\/} for
files, each useful for different applications.  These encodings are:

\begin{description}
\item[Standard]
An encoding which uses only Common Lisp standard characters (the 94
printing characters of ASCII, plus space and newline), and which is readable
enough to be edited manually by humans.

\item[Compressed]
An encoding which also uses only Common Lisp standard characters,
but uses a variety of tricks to greatly reduce the number of characters
required, at the expense of human readability.  [The Compressed encoding is
currently unimplemented.]

\item[Binary]
An encoding which uses the same compression techniques as the
Compressed encoding, but which is composed of 8-bit bytes rather than standard
characters.  This makes it even more compact than the Compressed encoding.
\end{description}

The Standard and Compressed encodings are useful for transmission over media
which only transmit standard characters, such as electronic mail.  The Standard
encoding is also useful for making manual adjustments to CIOBL files.

The CIOBL software provides a uniform interface between files and programs by
defining a set of {\em CIOBL objects\/} which can appear in CIOBL files.  Programs
that do I/O deal only with CIOBL objects, and the CIOBL software attends to the
details of how the objects are represented in each of the three encodings.  A
program need only be aware of the encodings when opening a file, for at that
time it must select which of the three encodings is to be used.


\section{CIOBL Objects}

A CIOBL file consists of a sequence of CIOBL objects.  CIOBL objects include
the following {\em primitive\/} objects:

\begin{description}
\item[Integers]
These are distinct from floats which happen to have integral values.

\item[Floats]
A ``float'' is a floating point number.  As described later,
CIOBL uses a textual representation for floating point numbers, and so
makes no assumptions about base or precision.

\item[Characters]
The only characters allowed in CIOBL files are Common Lisp standard
characters, which consist of the 94 printing characters of ASCII plus space and
newline.  (This restriction to standard characters has nothing to do with the
fact that the Standard and Compressed encodings use only standard characters.
Instead, it stems from the need to make sure that CIOBL character objects have
a representation in all implementations of CIOBL.)

\item[Strings]
A string is a (possibly empty) character string.  The characters of
a string are limited to the 96 Common Lisp standard characters.

\item[Symbols]
A symbol is a pair of names, the {\em package\/} name and the name of the
symbol itself.  Each name is composed of Common Lisp standard characters.
\end{description}

CIOBL places no practical limit on the magnitude of integers and floats, or on
the length of strings.

Symbols seem superfically similar to strings (or a pair
of strings), but are usually used for different purposes.  One reason is that
an implementation of CIOBL often represents strings and symbols differently:
while strings are generally represented as arrays of characters, symbols are
usually mapped into addresses or serial numbers, with all symbols with the same
pair of names being mapped into the same address or serial number.  Strings are
often decomposed into their component characters, while symbols rarely are.
Instead, the names of symbols are important only insofar as they distinguish
between symbols that are the same and those that are different.

The foregoing explanation might seem strange to readers familiar with Lisp, who
already know why strings and symbols are different.  On the other hand, readers
not familiar with Lisp might wonder what the package name of a symbol is for.
Symbols in Common Lisp are partitioned into ``packages'', each of which is a
namespace for identifying symbols.  The package name of a CIOBL symbol is
usually only important for Category III files, which use CIOBL symbols to
represent Lisp symbols.  When the package of a symbol is not important, which
is usually the case in Category I and Category II files, the name {\tt KEYWORD}
is generally used as the package.\footnote{If you don't know Common Lisp, don't ask
why.}

In addition to the above primitive objects, CIOBL objects include the following
{\em compound objects\/}:

\begin{description}
\item[Lists]
A list is a (possibly empty) delimited sequence of CIOBL objects. {\bf In
CIOBL, the empty list is different from the symbol {\tt NIL}}, although programs
may of course choose to treat them the same in some situations.

\item[Dotted Lists]
A dotted list is like a list, but also includes a special object
at the end.  Dotted lists are mainly used in Category III files; they correspond to
non-{\tt NIL} terminated lists in Common Lisp.

\item[Arrays]
Like a list, an array is a sequence of CIOBL objects.  Unlike a list,
an array carries an indication of how many objects it contains.  Also, arrays
may be multidimensional, up to seven dimensions.  Each dimension has subscripts
running from zero up to but not including the size of the dimension.

\item[User Defined Objects]
Arbitrary compound objects may be defined by user
applications.
\end{description}

For category III files, the difference between arrays and lists is important,
as these are two different kinds of Common Lisp objects.  For category II
files, the difference can also be important since arrays can be
multidimensional (although this can be simulated by lists of lists).  For
category I files, the choice between arrays and lists is fairly arbitrary.
Lists have the advantage when writing a file that the contents may be written
without knowing the length of the list.  When reading a file, this aspect may
be a disadvantage.

The next section describes how compound objects appear in CIOBL files.

\section{CIOBL Tokens}

The contents of a CIOBL file can be viewed from three different levels of
abstraction.  At the lowest level, a CIOBL file is just a sequence of
characters (or 8-bit bytes, in the case of Binary encoding).  At the highest
level, a CIOBL file is a sequence of CIOBL objects, as previously discussed.
At the middle level, a CIOBL file is a sequence of {\em CIOBL tokens\/}.

CIOBL tokens are the smallest indivisible components of CIOBL files, and are
independent of the encoding chosen.  The set of CIOBL tokens consists of all of
the primitive CIOBL objects, as well as some {\em punctuation tokens\/} which serve
to identify compound objects.  Defining a token layer allows the portions of a
CIOBL implementation which understand the various encodings to be separated
from the portions which understand how to put together and pick apart compound
objects.  This is illustrated below.

\begin{figure}
\begin{center}
%%%\illustration{ciobl-01}
\sf [Figure to be included]
\end{center}
\end{figure}

Two punctuation tokens are used to represent lists: \code{list-begin} and
\code{list-end}.  A CIOBL list appears as the token \code{list-begin}, followed by
the CIOBL objects comprising the list (or none if the list is empty), followed
by the token \code{list-end}.  A CIOBL dotted list makes use of another
puncutation token called \code{list-dot}.  A dotted list appears as
\code{list-begin}, followed by one or more CIOBL objects, followed by
\code{list-dot}, followed by exactly one CIOBL object, followed by \code{list-end}.

One punctuation token is used to represent arrays: \code{array-begin}.  A CIOBL
array appears as the token \code{array-begin}, followed by the dimensions,
followed by the elements of the array.  There is no terminating puncuation
token.  The dimensions are either a list of integers, or just an integer
itself, the latter being equivalent to a list of one integer.  The rank of the
array is the number of integers in the dimension list; each dimension has
subscripts from zero, inclusive, to the integer given in the dimensions list,
exclusive.  The elements of the array appear in row-major order.  Here is an
example of a two dimensional array:

\begin{itemize}\item[]
\code{array-begin} \code{list-begin} 3 2 \code{list-end} $a(0,0)$
$a(0,1)$  $a(1,0)$ $a(1,1)$ $a(2,0)$ $a(2,1)$
\end{itemize}

Two more puncuation tokens are used to represent user-defined objects:
\code{user-defined-begin}, and \code{user-defined-end}.  A user-defined object
appears as the token \code{user-defined-begin}, followed by a symbol, followed by
some number of CIOBL objects, followed by the token \code{user-defined-end}.  The
symbol immediately after the \code{user-defined-begin} indicates which user
defined object is being represented; when reading such an object, the symbol is
used to dispatch to user-written code which reads the remaining objects up to
the \code{user-defined-end}\footnote{The \code{user-defined-end} token is not strictly
necessary, but is included to help catch errors in user-written handler code.}.

There is another kind of token that is not associated with any object.  Called
the version token, it indicates what version of CIOBL software was used to
write the file in which it appears.  It also indicates in which of the three
encodings the file is expressed.  Whenever a CIOBL file is opened for writing,
a version token is immediately written.  Thus, every file has a version token
at the beginning.  A file may have more version tokens within, if the file was
ever opened for appending.  When a file is read, the version token is used to
make sure the file uses the expected encoding, and that the file was written
with a compatible version of CIOBL.

To summarize, there are twelve kinds of CIOBL tokens:  the five primitive CIOBL
objects, the six punctuation tokens, and the version token.

\section{CIOBL Streams}

 CIOBL streams are streams to which CIOBL objects are written and from
which CIOBL objects are read.  The following sections describe how to
create CIOBL streams, how to read and write CIOBL objects, and how to
define readable/writable CIOBL objects.

\subsection{Creating CIOBL Streams}

\begin{lispdocs}
\lispdoc make-ciobl-stream stream encoding [Function]
\lispdoc ciobl-stream [Type]
\lispdoc ciobl-stream-p object [Function]
\end{lispdocs}

 {\tt Make-ciobl-stream} creates and returns a CIOBL stream of the
appropriate type from a Common Lisp stream, after first making sure the
encoding chosen is compatible with the underlying stream type.  It ensures
that the version token has been read, so that {\tt read-ciobl}, {\tt
skip-ciobl} do not have to.  The encoding must be one of {\tt :standard},
{\tt :binary} or {\tt :compressed}.

 The function {\tt ciobl-stream-p} returns {\tt t} if {\em object\/} is a
CIOBL stream and {\tt nil} otherwise.

\lispdoc close-ciobl ciobl-stream [Function]
The function {\tt close-ciobl} just does a Common Lisp {\tt close} on the
underlying stream.

\lispdoc with-ciobl-stream \list{var stream binaryp} \body body [Macro]
The macro {\tt with-ciobl-stream} binds a variable to the result of making
a CIOBL stream out of a given stream, and makes sure always to call {\tt
close-ciobl} on it, even if errors occur. 


\lispdoc with-ciobl-file \list{var filename binaryp \rest open-options}
                        \body body [Macro]
The macro {\tt with-ciobl-file} combines {\tt with-ciobl-stream} and {\tt
with-open-file}.

\begin{lispdocs}
\lispdoc clear-ciobl-output ciobl-stream [Function]
\lispdoc force-ciobl-output ciobl-stream [Function]
\lispdoc finish-ciobl-output ciobl-stream [Function]
\end{lispdocs}
 The functions {\tt finish-ciobl-output}, {\tt force-ciobl-output}, and {\tt
clear-ciobl-output} just call the appropriate Common Lisp function on the
underlying stream.

\subsection{Reading and Writing CIOBL Streams}

\begin{lispdocs}
\lispdoc read-ciobl ciobl-stream \key 
        \list{eof-error-p t}
        \list{return-list-p t}
        \list{list-punctuation-error-p t}
        [Function]
\lispdoc read-ciobl-1 ciobl-stream eof-error-p return-list-p list-punctuation-error-p
        [Function]
\end{lispdocs}
The function {\tt read-ciobl} tries to read a returnable element of CIOBL.
It can always return types {\tt :symbol}, {\tt :string}, {\tt :integer},
{\tt :float}, or a user defined type.  If {\em eof-error-p\/} is false, it
can return also {\tt :eof}.  If {\em list-punctuation-error-p\/} is false
it can also return {\tt :list-dot} or {\tt :list-end}.  If {\em
return-list-p\/} is false it can also return {\tt :list-begin}, otherwise
it can also return {\tt :list}.  An error is signalled in every other case.

The function {\tt read-ciobl-1} is the same as {\tt read-ciobl}, except
that it does not incur the overhead of parsing keyword arguments.  The time
spent parsing keyword arguments can be considerable when reading CIOBL
streams.

\begin{lispdocs}
\lispdoc skip-ciobl ciobl-stream  \key 
        \list{eof-error-p t}
        \list{return-list-p t}
        \list{list-punctuation-error-p t} 
        [Function]
\lispdoc skip-ciobl-1 ciobl-stream  eof-error-p return-list-p
list-punctuation-error-p
        [Function]
\end{lispdocs}

The function {\tt skip-ciobl} tries to skip a returnable element of CIOBL.
It can always return types {\tt :symbol}, {\tt :string}, {\tt :integer},
{\tt :float}, or a user defined type.  If {\em eof-error-p\/} is false, it
can return also {\tt :eof}.  If {\em list-punctuation-error-p\/} is false
it can also return {\tt :list-dot} or {\tt :list-end}.  If {\em
return-list-p\/} is false it can also return {\tt :list-begin}, otherwise
it can also return {\tt :list}.  An error is signalled in every other case.
As with {\tt read-ciobl-1}, {\tt skip-ciobl-1} is the same as {\tt
skip-ciobl}, except that it does not use keyword arguments.

\begin{lispdocs}
\lispdoc write-ciobl object ciobl-stream [Function]
\lispdoc write-ciobl-list-begin ciobl-stream [Function]
\lispdoc write-ciobl-list-end ciobl-stream [Function]
\lispdoc write-ciobl-list-dot ciobl-stream [Function]
\lispdoc write-ciobl-newline ciobl-stream [Function]
\end{lispdocs}

The function {\tt write-ciobl} writes a CIOBL object.  It calls a variety
of functions, one for each different CIOBL token.  The functions {\tt
write-ciobl-list-begin} and {\tt write-ciobl-list-end} write the
appropriate delimiter to the given stream.  These functions are exported,
so we do a little extra error checking.  {\tt Write-ciobl-list-dot} writes
the puncutation indicating that the final {\tt cdr} of a list follows.  The
function {\tt write-ciobl-newline} writes a newline to a standard encoding
stream, and is a no-op for a binary encoding stream.  It can be used to get
prettier standard encoding files, if desired.

\subsection{User Defined Objects}

 One adds new object encodings to CIOBL's repertoire by defining read and
write methods for objects of a given type.  The macros {\tt defciobl-read}
and {\tt defciobl-write} define read and write methods, respectively, for a
Lisp type.  Note that CIOBL read/write methods are defined for all of the
types defined by DFCS.

\begin{lispdocs}
\lispdoc defciobl-write type \list{object-var ciobl-stream-var} \body body [Macro]
\lispdoc defciobl-read type \list{ciobl-stream-var} \body body [Macro]
\end{lispdocs}
 The macro {\tt defciobl-write} defines a write method for objects whose
type is {\em type\/}.  The body of the ciobl-write-method should write out
a representation of the object to which {\em object-var\/} is bound using
calls to {\tt ciobl-write}.

 The body of the ciobl-read-method should read the representation of an
object whose type is {\em type\/} using calls to {\em read-ciobl\/}.  A
ciobl-read-method {\em must\/} read exactly as much as the corresponding
write-method wrote to the CIOBL stream.

\section{Encodings}

In the previous section, the translation between CIOBL tokens and CIOBL objects
was described.  Here, we describe how CIOBL tokens are encoded in the three
types of encodings.

\subsection{Standard Encoding}

Standard encoding is the most easily read by humans.  In fact, it is closely
related to the syntax for Common Lisp objects used by the Lisp reader and
printer.  Beware, however, for CIOBL Standard encoding is not compatible with
Lisp.  Each contains objects not present in the other.  Furthermore, CIOBL
Standard encoding has some restrictions that must be observed by CIOBL output
routines, in order that the job of CIOBL input routines may be made easier.

Here is how the twelve CIOBL tokens are represented in the Standard Encoding:

\begin{description}
\item[Integers]
Integers are represented as they are written in base 10: a sequence
of digits, at least one digit long, and immediately preceded by a hyphen if
negative.  Leading zeros are never present (except when the integer is itself
zero).

\item[Floats]
Floats are represented as a sequence of digits containing exactly one
period, with at least one digit on each side of the period.  This may
optionally be preceded by a hyphen, and optionally followed by the letter {\tt E}
(never lowercase {\tt e}) and a sequence of digits, possibly with a hyphen
appearing between the {\tt E} and the digits.  The number after the {\tt E}
indicates by what power of ten the number preceding the {\tt E} should be
multiplied.

\item[Characters]
The 94 printing characters are represented by the three
character sequence {\tt \lispchar}{\em char\/}, where {\em char\/} is the
character to be represented.  For example, the character {\tt A} is
represented as {\tt \lispchar A}, the character backslash as {\tt \lispchar
\verb'\'}, etc.  The character ``space'' is represented as {\tt \lispchar
Space}, and the character ``newline'' is represented as {\tt \lispchar
Newline}.

\item[Strings]
A string is represented by a quotation mark ({\tt "}), followed by the
characters composing the string, followed by another quotation mark.  Each
quotation mark or backslash within the string is itself preceded by a
backslash.  For example, the string \verb|A backslash ("\")|
appears as \verb|"A backslash (\"\\\")"| in a Standard encoding file.

\item[Symbols]

Symbols whose package name is {\tt KEYWORD} are represented as a colon
followed by the name of the symbol, {\em e.g.\/}, {\tt :FRED}.  Symbols
accessible in the {\tt DFCS} package are represented by just the name of
the symbol, while all other symbols are represented by the name of the
package followed by two colons, followed by the name of the symbol.

Names of symbols and packages are represented by a sequence of the
characters composing the name, except that a backslash is inserted before
each character that is not an uppercase letter, a digit, or one of the
characters \verb"+", \verb"-", \verb"*", \verb"/", \verb"\", \verb"$",
\verb"%", \verb"^", \verb"&", \verb"_", \verb"<", \verb">", or \verb"~".
Furthermore, the first character is preceded by a backslash if it is a
digit or a hyphen (this is so that an object begins with a digit or hyphen
if and only if it is an integer or float).  Finally, if the name has no
characters ({\em i.e.\/}, is the empty string), it is represented as two
vertical bars.

\item[\code{list-begin}]
\code{list-begin} appears as a left parenthesis (\verb'(').

\item[\code{list-end}]
\code{list-end} appears as a right parenthesis (\verb')').

\item[\code{list-dot}]
\code{list-dot} appears as a period.

\item[\code{array-begin}]
\code{array-begin} appears as the two-character
sequence \verb'#A'.

\item[\code{user-defined-begin}]
\code{user-defined-begin} appears as as
the two-character sequence \verb'#['.

\item[\code{user-defined-end}]
\code{user-defined-end} appears as the
two-character sequence \verb'#]'.

\item[Version]
The version token is a four-character sequence: {\tt \#}, followed by
{\tt V}, followed by a character indicating the version, followed by {\tt S}.  A
CIOBL version number is an integer from 1 through 63, inclusive, and is
represented in the Standard encoding using the {\em value\/} column of
Section~\ref{CharacterCodeAppendix}.  The fourth character indicates that
this is a Standard encoding file.
\end{description}

Whitespace may appear between any adjacent pair of CIOBL tokens, and is
required between any adjacent pair of tokens which are also primitive
objects.  Whitespace is any non-empty sequence of spaces or newlines.  The
last character of a primitive object is defined to be the last character
preceding the next whitespace, punctuation, or end of file.

CIOBL takes no position as to what character codes are used in Standard
encoding files.  This is because such files are character files, so it is
assumed that an implementation will use whatever codes for characters are
appropriate, and that file transfer programs will take care of any
necessary code conversions when transferring Standard encoding files
between machines.

\subsection{Compressed Encoding}

[The Compressed Encoding is currently unimplemented.]

\subsection{Binary Encoding}

Binary encoding is the most compact of the three encodings.  Unlike the other
encodings, binary encoding is based on 8-bit bytes rather than characters.  A
variety of techniques are used to reduce the space required by a file.

The following describes how the twelve CIOBL tokens are represented in the
Binary encoding.  All tokens begin with a special byte that identifies its
type.  Throughout the discussion, these bytes are represented by a name
enclosed in angle brackets, for example, {\tt <b-pos-integer-8>}.  The numerical
values of these bytes are given later.

\paragraph{Integers}

Integers are represented by a punctuation byte followed by a certain number of
bytes which indicate the magnitude of the integer.  The punctuation byte
indicates the sign of the integer as well as how many magnitude bytes follow;
the magnitude bytes appear least significant byte first.  The punctuation bytes
are:
\begin{center}
\begin{tabular}{cc}
{\em Magnitude Range\/}         &{\em Punctuation Byte\/}\\
\hline
$-2^{32} <   x \le -2^{24}$     &{\tt <b-neg-integer-32>}\\
$-2^{24} <   x \le -2^{16}$     &{\tt <b-neg-integer-24>}\\
$-2^{16} <   x \le -2^{8}$      &{\tt <b-neg-integer-16>}\\
$-2^{8}  <   x < 0$             &{\tt <b-neg-integer-8>}\\
$0       \le x < 2^{8}$         &{\tt <b-pos-integer-8>}\\
$2^{8}   \le x < 2^{16}$        &{\tt <b-pos-integer-16>}\\
$2^{16}  \le x < 2^{24}$        &{\tt <b-pos-integer-24>}\\
$2^{24}  \le x < 2^{32}$        &{\tt <b-pos-integer-32>}\\
\end{tabular}
\end{center}

For example, the number -4000 is represented as {\tt <b-neg-integer-16>}
{\tt 160} {\tt 15}, and zero is represented as {\tt <b-pos-integer-8>} {\tt 0}.
(Throughout, all bytes are given in base ten.)

If the magnitude of the integer is $2^{32}$ or greater, one of the two
punctuation bytes {\tt <b-pos-long-integer>} or {\tt <b-neg-long-integer>}
is used, followed by a byte giving the number of bytes in the magnitude,
followed by the bytes which comprise the magnitude.  For example, five
trillion $(5 \times 10^{12})$ appears as {\tt <b-pos-long-integer>} {\tt 6}
{\tt 0} {\tt 80} {\tt 57} {\tt 39} {\tt 140} {\tt 4}.  Integers with
magnitudes greater than or equal to $256^{256}$ cannot be represented
(fortunately).

\paragraph{Characters}
\label{BinaryCharacterParagraph}

A character appears as two bytes:  {\tt <b-character>} followed by the character
itself.  Because Binary encoding files are not character files, CIOBL must
explicitly specify how characters are encoded into bytes.  The 94 printing
characters are encoded as they are in the ASCII character set.  The remaining
two standard characters, Space and Newline, are encoded as {\tt 32} and {\tt 10},
respectively.

This encoding was chosen because it is exactly the encoding used in some
systems ({\em e.g.\/}, Unix), and very close to the encoding used in most others
({\em e.g.\/}, the Lisp Machine, where Newline is {\tt 141}).  CIOBL implementations
on non-ASCII systems will have to explicitly translate when reading or writing
Binary encoded files.

\paragraph{Strings}
\label{BinaryStringParagraph}

Strings of length 255 or less are encoded as {\tt <b-string>}, followed by a byte
giving the length of the string, followed by the characters of the string
itself.  Paragraph \ref{BinaryCharacterParagraph} explains how characters are
translated into bytes.

Strings whose length is greater than 255 are encoded as {\tt <b-long-string>},
followed by a byte giving the number of bytes which will represent the length,
followed by the bytes comprising the length, followed by the characters of the
string itself.  As with integers, the bytes comprising the length appear least
significant byte first.  Strings with length $256^{256}$ or longer cannot be represented
(not that your file system has room for all those characters, anyway).

\paragraph{Floats}

Floats are not encoded into a two's complement or similar representation.
Instead, they appear just like strings, except that the bytes {\tt <b-float>} and
{\tt <b-long-float>} are used instead of {\tt <b-string>} and {\tt <b-long-string>}
(note that the latter is extremely unlikely).  For example, the number
$-6.023 \times 10^{-23}$ appears as {\tt <b-float>} {\tt 10} {\tt 45} {\tt 54}
{\tt 46} {\tt 48} {\tt 50} {\tt 51} {\tt 69} {\tt 45} {\tt 50} {\tt 51}.

\paragraph{Symbols}

The symbol {\tt NIL} (not the same as {\tt NIL} in the {\tt KEYWORD} package) is
represented by a single byte, {\tt <b-nil>}.

Keyword symbols are represented by encoding their names in a similar manner as
strings (see Paragraph \ref{BinaryStringParagraph}), except that the bytes
{\tt <b-keyword-symbol>} and {\tt <b-long-keyword-symbol>} are used instead of
{\tt <b-string>} and {\tt <b-long-string>}, respectively.

All other symbols are represented by encoding their names in a similar manner
as strings, except that the bytes {\tt <b-symbol>} and {\tt <b-long-symbol>} are
used instead of {\tt <b-string>} and {\tt <b-long-string>}.  The package name is
not included in the name that follows the {\tt <b-symbol>} or {\tt <b-long-symbol>}
byte.  Instead, the package name of a symbol read from a Binary encoded file is
taken to be the ``current'' package name.  The current package name is changed
by including in the file one of the bytes {\tt <b-set-current-package>} or
{\tt <b-long-set-current-package>}, which are used like {\tt <b-string>} and
{\tt <b-long-string>} to encode the package name.

For example, if the following sequence appeared in a Standard encoding file:

\begin{example}
    :A  NIL  B::C  :NIL  NIL  B::D  Q::R
\end{example}

It would be rendered in a Binary encoding file as:

\begin{example}
    <b-keyword-symbol> 1 65 <b-nil> <b-set-current-package> 1 66
    <b-symbol> 1 67 <b-keyword-symbol> 3 78 73 76 <b-nil>
    <b-symbol> 1 68 <b-set-current-package> 1 81 <b-symbol> 1 82
\end{example}

The first symbol in a Binary encoding file that is not a keyword or {\tt NIL} is
always preceded by a set-current-package directive.  Note that the
set-current-package directive is not a CIOBL token, but only controls the
interpretation of symbols that follow it.

One additional trick is used to encode symbols.  If the same symbol (same
package name and symbol name) appears more than once in the same file, only the
first occurence is encoded as described earlier.  All future occurences are
encoded as an integer which indicates position within the file of its first
occurence.  These remarks do not apply to the symbol {\tt NIL}, which is always
encoded as the byte {\tt <nil>}.

As a Binary encoded file is written, a table is maintained which associates
symbols and serial numbers.  When a non-{\tt NIL} symbol is to be written, it is
looked up in the table.  If an entry for that symbol is present, its serial
number is written in a format to be described shortly.  If an entry is not
present, the symbol is written in the format described earlier, preceded by a
set-current-package directive if necessary.  The symbol is then assigned the
next highest serial number, and entered in the table for future reference.
The unique non-{\tt NIL} symbols in a file are assigned consecutive serial
numbers beginning with zero.  Note that when a symbol is encoded as a serial
number, it is never necessary to issue a set-current-package directive, as the
serial number identifies both components of the symbol's name.

A predefined symbol is encoded as one of the three bytes
{\tt <b-predefined-symbol-8>}, {\tt <b-predefined-symbol-16>}, or
{\tt <b-predefined-symbol-24>}, followed by one, two, or three bytes of serial
number, respectively, least significant byte first.

Another example:  suppose the following appeared at the beginning of a Standard
encoding file:

\begin{example}
    :D :A  NIL  B::C  :NIL  NIL  Q::R  B::C  B::D
\end{example}

It would be rendered in a Binary encoding file as:

\begin{example}
    <b-keyword-symbol> 1 68 <b-keyword-symbol> 1 65 <b-nil>
    <b-set-current-package> 1 66 <b-symbol> 1 67
    <b-keyword-symbol> 3 78 73 76 <b-nil>
    <b-set-current-package> 1 81 <b-symbol> 1 82
    <b-predefined-symbol-8> 2 <b-set-current-package> 1 66
    <b-symbol> 1 68
\end{example}

Only the first $2^{24}$ different non-{\tt NIL} symbols in a file can be encoded
by serial number.

\paragraph{The Version Token}

The version token appears in a Binary file as the four-byte sequence {\tt 35}
{\tt 86} {\em version\/} {\tt 66}, where {\em version\/} is the version number plus 32.
The last byte indicates that this is a Binary file.

When reading a Binary encoding file, {\tt 163} (35 plus 128) should also be
accepted as the beginning of a version token.  In other words, only the lower
seven bits are used in recognizing the beginning of the version token.  The
number 35 was chosen for the version token because it is the ASCII code for
{\tt \#}, so that a version will be recognized even when read from a file in the
wrong encoding (at least on systems that use ASCII to represent characters).
This facilitates early detection of an attempt to read the wrong kind of file.

\paragraph{Other Tokens}

The CIOBL tokens \code{list-begin}, \code{list-dot}, \code{list-end}, \code{array-begin},
\code{user-defined-begin}, and \code{user-defined-end} are represented in Binary
encoding as the bytes {\tt <list-begin>}, {\tt <list-dot>}, {\tt <list-end>},
{\tt <array-begin>}, {\tt <user-defined-begin>}, and {\tt <user-defined-end>},
respectively.

\paragraph{Run Length Encoding}

Long sequences of repeated tokens are represented in the Binary encoding using
one of two special bytes, {\tt <b-repeat-8>} or {\tt <b-repeat-16>}.  A
{\tt <b-repeat-8>} byte is followed by one byte, which indicates how many times
the previous token is to be repeated, from 0 through 255.  {\tt <b-repeat-16>} is
similar, except that it is followed by two bytes giving the repeat count, up to
65,535.  For example, the following seuence:

\begin{example}
    <b-pos-integer-8> 34 <b-pos-integer-8> 34 <b-pos-integer-8> 34 <b-nil>
    <b-nil> <b-nil> <b-nil> <b-nil> <b-nil> <b-list-close> <b-list-close>
    <b-list-close>
\end{example}

could instead appear as

\begin{example}
    <b-pos-integer-8> 34 <b-repeat-8> 2 <b-nil> <b-repeat-8> 5
    <b-list-close> <b-repeat-8> 2
\end{example}

Note that the repeat bytes indicate the repetition of {\em tokens\/}, not objects.

\paragraph{Values of Binary Punctuation Bytes}

The following table gives the values of each of the 30 binary punctuation
bytes.

\begin{center} \tt
\begin{tabular}{cc@{\hspace{3em}}cc}
{\em Name\/}   &{\em Value\/}      &{\em Name\/}   &{\em Value\/}\\ \hline
<b-symbol>     &0                  &<b-pos-long-integer>   &24\\
<b-keyword-symbol>     &1          &<b-neg-integer-8>      &25\\    
<b-long-symbol>        &2          &<b-neg-integer-16>     &26\\    
<b-long-keyword-symbol>        &3  &<b-neg-integer-24>     &27\\    
<b-nil>        &4                  &<b-neg-integer-32>     &28\\    
<b-set-current-package>        &5  &<b-neg-long-integer>   &29\\    
<b-long-set-current-package>   &6  &<b-float>      &30\\            
<b-predefined-symbol-8>        &7  &<b-long-float> &31\\            
<b-predefined-symbol-16>       &8  &<b-version>    &35\\            
<b-predefined-symbol-24>       &9  &<b-list-begin> &40\\            
<b-string>     &10                 &<b-list-end>   &41\\            
<b-long-string>        &11         &<b-list-dot>   &42\\            
<b-character>  &15                 &<b-repeat-8>   &45\\            
<b-pos-integer-8>      &20         &<b-repeat-16>  &46\\            
<b-pos-integer-16>     &21         &<b-user-defined-begin> &50\\    
<b-pos-integer-24>     &22         &<b-user-defined-end>   &51\\    
<b-pos-integer-32>     &23         &<b-array-begin>        &55\\    
\end{tabular}
\end{center}

\subsection{Character Codes}
\label{CharacterCodeAppendix}


The following table lists the 96~standard characters.  The {\em
byte\/} column gives the representation (in base~10) for each character in the
Binary encoding.  The {\em value\/} column gives the value assigned to
characters when used to encode integers in the Compressed encoding, and when
used as part of the version token in both the Compressed and the Standard
encoding.

$$\vbox{\offinterlineskip
\halign{\hfil\strut\tt#\hfil&\quad\hfil#\hfil&\quad\hfil#\hfil\cr
\it Char.&\it Byte&\it Value\cr
\omit\hfil\hrulefill\hfil&\hrulefill&\hrulefill\cr
\noalign{\vskip 3pt}
\rm Space&\ 32&\ 0\cr
!&\ 33&\ 1\cr
"&\ 34&\ 2\cr
\#&\ 35&\ 3\cr
\$&\ 36&\ 4\cr
\%&\ 37&\ 5\cr
\&&\ 38&\ 6\cr
'&\ 39&\ 7\cr
(&\ 40&\ 8\cr
)&\ 41&\ 9\cr
*&\ 42&10\cr
+&\ 43&11\cr
,&\ 44&12\cr
-&\ 45&13\cr
.&\ 46&14\cr
/&\ 47&15\cr
0&\ 48&16\cr
1&\ 49&17\cr
2&\ 50&18\cr
3&\ 51&19\cr
4&\ 52&20\cr
5&\ 53&21\cr
6&\ 54&22\cr
7&\ 55&23\cr
8&\ 56&24\cr
9&\ 57&25\cr
:&\ 58&26\cr
;&\ 59&27\cr
<&\ 60&28\cr
=&\ 61&29\cr
>&\ 62&30\cr
?&\ 63&31\cr
}}
\quad\quad\quad\quad
\vbox{\offinterlineskip
\halign{\hfil\strut\tt#\hfil&\quad\hfil#\hfil&\quad\hfil#\hfil\cr
\it Char.&\it Byte&\it Value\cr
\omit\hfil\hrulefill\hfil&\hrulefill&\hrulefill\cr
\noalign{\vskip 3pt}
@&\ 64&32\cr
A&\ 65&33\cr
B&\ 66&34\cr
C&\ 67&35\cr
D&\ 68&36\cr
E&\ 69&37\cr
F&\ 70&38\cr
G&\ 71&39\cr
H&\ 72&40\cr
I&\ 73&41\cr
J&\ 74&42\cr
K&\ 75&43\cr
L&\ 76&44\cr
M&\ 77&45\cr
N&\ 78&46\cr
O&\ 79&47\cr
P&\ 80&48\cr
Q&\ 81&49\cr
R&\ 82&50\cr
S&\ 83&51\cr
T&\ 84&52\cr
U&\ 85&53\cr
V&\ 86&54\cr
W&\ 87&55\cr
X&\ 88&56\cr
Y&\ 89&57\cr
Z&\ 90&58\cr
[&\ 91&59\cr
\char`\\&\ 92&60\cr
]&\ 93&61\cr
\char`\^&\ 94&62\cr
\char`\_&\ 95&63\cr
}}
\quad\quad\quad\quad
\vbox{\offinterlineskip
\halign{\hfil\strut\tt#\hfil&\quad\hfil#\hfil&\quad\hfil#\hfil\cr
\it Char.&\it Byte&\it Value\cr
\omit\hfil\hrulefill\hfil&\hrulefill&\hrulefill\cr
\noalign{\vskip 3pt}
`&\ 96\cr
a&\ 97\cr
b&\ 98\cr
c&\ 99\cr
d&100\cr
e&101\cr
f&102\cr
g&103\cr
h&104\cr
i&105\cr
j&106\cr
k&107\cr
l&108\cr
m&109\cr
n&110\cr
o&111\cr
p&112\cr
q&113\cr
r&114\cr
s&115\cr
t&116\cr
u&117\cr
v&118\cr
w&119\cr
x&120\cr
y&121\cr
z&122\cr
\char`\{&123\cr
|&124\cr
\char`\}&125\cr
\char`\~&126\cr
\rm Newline&\ 10\cr
}}$$

%%% Character codes lifted from CIOBL II documentation.
