\subsection{Coding of references}

We need some rudimentary accounting of what we gain and lose
by use of the library: we save some 
by using a library component, at the cost of having to refer
to it.  Let us first consider the cost of referring to
components.

We presume that unique identifiers are assigned 
to library components; we call these \emph{codewords}.
Let $c(n)$ be the binary codeword for the $n^{\mathit{th}}$ library
component, and $\strlen{c(n)}$ its length.
Optimal strategies such as Shannon-Fano or Huffman codes assign
shortest codewords to the most frequently
needed components.  Since our library is sorted in order of use
frequency (\refsec{s:ordering}), we may presume that 
$\strlen{c(n)} \leq \strlen{c(n+1)}$, i.e.,
codeword lengths are nondecreasing as we go down the list of components.

In what follows we want to make asymptotic arguments, and
fixing an identifier size (e.g., 64 bits)
would lead to wildly wrong conclusions.\footnote{If we fix memory addresses 
to be representable in 64 bits,
then the time to search an acyclic linked list is $O(1)$ since there are at 
most $2^{64}$ steps the algorithm must go through.
}
Instead we require that the identifier size grows with the number
of components, albeit slowly.  That $\strlen{c(n)} \geq \log_2 n$ 
follows from the pigeonhole principle.
\ifverbose{
\begin{prop}
\label{prop:idlength}
$\strlen{c(n)} \geq \log_2 n$.
\end{prop}
\begin{proof}
Were $\strlen{c(n)} < \log_2 n$, by pigeonhole there would be two components
with the same codeword, contradicting uniqueness.
\qed
\end{proof}
}
Having identifiers of length only $\log_2 n$ leads to difficulties,
because they are not \emph{uniquely decodable}.  That is, if I
am presented with a string of such identifiers I have no way to tell
where one identifier stops and the next starts.  (This does not arise
in current architectures because of fixed word size, but as we said,
care is needed in asymptotic arguments).
A more accurate requirement is the following, which draws on
Kraft's inequality that uniquely decodable codes must satisfy
$\sum_{n=1}^\infty 2^{- \strlen{c(n)}} \leq 1$.

\begin{prop}
\label{prop:logplus}
For identifiers to be uniquely decodable, 
\begin{align*}
\strlen{c(n)} \geq \log^+ n
\end{align*}
where $\log^+ n = \log n + \log \log n + \log \log \log n + \cdots$
and the sum is taken only over the positive real terms.
\ifverbose{\footnote{The notation $\log^\ast x$ is more standard.
However $\log^\ast$ is also widely used
for the \emph{product} of iterated logarithms
$\log n \log \log n \cdots$ that arises in the
context of Zipf's law \cite{Powers:ACL:1998};
$\log^\ast x$ is also commonly used in
algorithm analysis to mean the inverse of a power tower.
Hence we adopt the notation $\log^+ x$ which we hope is
slightly less likely to confuse.
}
}
\end{prop}
We omit the proof; see e.g., \cite[\S 2.2.4]{Rissanen:1989} or
\cite[\S 1.11.2]{Li:1997} (in particular problem 1.11.13).

