\subsection{Derivation of reuse rate bound}

\label{s:newderiv}

We now derive an asymptotic upper bound on the rates $\lambda(n)$
at which library components may be reused.  We do this under
the assumption that each time a library component is used in
a program, the same identifier is used to refer to it, i.e.,
there is no \emph{recoding of identifiers}.\footnote{
There are two reasons for this assumption.  (1) On the architectures
from which we collect empirical data, there is no recoding of
identifiers in programs.
(2) The reason one
might want to recode identifiers is to save
space by introducing shorter aliases for components for use
within the program, after the initial reference.
However, this only saves space if a component is more likely to be used
again given it is used once.  While this is intuitively true of
real programs, it is false under a maximum entropy assumption
(\refsec{s:entropy}): in an encoding that maximizes entropy,
the sequence of identifiers in a program behaves statistically as
if independent and identically distributed. 
}
Our argument follows standard lines \cite{Powers:ACL:1998}
but adapted to coding of library references under the model laid 
out in \refsec{s:model}.

\begin{thm}
\label{thm:lambdabound}
Without recoding of identifiers, the asymptotic reuse rates $\lambda(n)$
must satisfy $\lambda(n) \prec (n \log n \log^+ n)^{-1}$.
\end{thm}

\begin{proof}
We count the size of the references to library components within
compressed programs (i.e., those written with use of a library).
Consider programs of length at most $s$.  As $s \rightarrow \infty$, the
expected number of occurrences
of the $n^{\mathit{th}}$ component tends to $\lambda(n) s + o(s)$ under
\refassume{ass:meanlambda}.  Referring to
the $n^{\mathit{th}}$ component requires at least $\log^+ n$ bits (\refprop{prop:logplus}).
We need only
consider components whose identifier length is less than $s$,
since identifiers longer than the program would not fit.
Therefore we consider only up to component number $2^s$ since
$\log^+ 2^s \geq s$.

The expected total size of all the references to components is then at least:
\begin{align*}
\sum_{n=1}^{2^s} \underbrace{\bigl( \lambda(n) s + o(s)\bigr)}_{\text{\# refs}} \underbrace{\log^+ n}_{\text{ref size}}
\end{align*}

The references to components are contained within the program, and
therefore their total size must be less than $s$, the size of the program.
Therefore we have an inequality:\footnote{
\refineqn{e:balancerefs} becomes an equation if we consider programs to
consist solely of a sequence of component references, with
no control flow or other distractions.  This is
possible by building components and programs from combinators,
which can be made self-delimiting \cite[\S 3.2]{Li:1997}.
This provides a theoretically
elegant framework, if not entirely intuitive.
% The Invariance Theorem of Kolmogorov
% complexity ensures that translating programs and libraries
% into combinatory form is not costly in program size (\reffact{fact:invariance}).
}
\begin{align}
\label{e:balancerefs}
\sum_{n=1}^{2^s} \bigl(\lambda(n) s + o(s)\bigr) \log^+ n &\leq s
\end{align}
Dividing through by $s$ and taking the limit as $s \rightarrow \infty$,
\begin{align}
\lim_{s \rightarrow \infty} \sum_{n=1}^{2^s} \frac{1}{s} \bigl(\lambda(n) s + o(s) \bigr) \log^+ n \leq 1
\end{align}
Since $\lim_{s \rightarrow \infty} \frac{1}{s} o(s) = 0$ by definition,\footnote{Recall that $f \in o(g)$ means $\lim_{x \rightarrow \infty} \frac{f(x)}{g(x)} = 0$.} 
\ifverbose{
\begin{align}
\lim_{s \rightarrow \infty} \sum_{n=1}^{2^s} \lambda(n) \log^+ n \leq 1
\end{align}
or simply
}
\begin{align}
\sum_{n=1}^{\infty} \lambda(n) \log^+ n \leq 1
\label{eqn:eight}
\end{align}
We now consider conditions under which this sum converges.
(\refsec{s:asymptotics} summarizes the asymptotic notations
used here.)
We argue using \refprop{fact:seqbound}, using a diverging
series to bound the terms of \refeqn{eqn:eight}.
The simple argument is to note that the harmonic series diverges,
and therefore the terms of \refeqn{eqn:eight} must grow slower
than this, so $\lambda(n) \log^+ n \prec \frac{1}{n}$, or
$\lambda(n) \prec \frac{1}{n \log^+ n}$.  However,
this bound is quite loose.
\ifverbose{
Tighter bounds follow from the following reasoning.
Suppose $F(x)$ is some rapidly growing invertible function 
\editor{Only need be invertible for $x > 0$}
such as
$e^x$ or $e^{e^x}$.  Then $F^{-1}$ is a slowly growing but unbounded
function, and the series 
\begin{align*}
\sum_{n=0}^\infty \left[ \frac{d}{dx} F^{-1} \right] (n)
\end{align*}
diverges.  (For example, taking $F(x)=e^x$ yields 
$\left[\frac{d}{dx} F^{-1}\right](n) = [\frac{d}{dx} \ln x](n) = \frac{1}{n}$, the harmonic series).
Applying \refprop{fact:seqbound} to \refeqn{eqn:eight}, we have:
\begin{align*}
\lambda(n) \log^+ n \prec \left[ \frac{d}{dx} F^{-1} \right] (n)
\end{align*}
for any rapidly growing invertible function $F$.  Choosing
$F(x) = e^{e^{x}}$ and ignoring constant factors, we obtain:
}
\ifnotverbose{
A more slowly diverging series is $\sum_n \frac{1}{n \log n}$.  Using this,
}
\begin{align*}
\lambda(n) \log^+ n &\prec \frac{1}{n \log n}
\end{align*}
or,
\begin{align}
\boxed{\lambda(n) \prec \frac{1}{n \log n \log^+ n}}
\end{align}
This completes the proof.
\qed
\end{proof}

\ifverbose{
A slightly weaker but simpler bound is 
\begin{align*}
\lambda(n) \prec \frac{1}{n \log^2 n}
\end{align*}
obtained by taking only the first term of $\log^+ n$.
}

The bound of \refthm{thm:lambdabound} is not tight.  No tightest
bound is possible using this line of argument
since there is no slowest diverging sequence with which
to bound a convergent sequence, a classical result due to Niels Abel.\ifverbose{\footnote{
By choosing (say) $F(x)=e^{e^{e^x}}$, we could obtain the bound:
\begin{align*}
\lambda(n) \prec \frac{1}{n \log n \log \log n \log^+ n}
\end{align*}
Even tighter bounds are possible by choosing $F$ to be fast-growing
functions such as the power tower, Ackermann's or the busy beaver function
(using first difference, rather than continuous derivative).
For example, the limiting case of taking $F$ to be iterated exponentials
gives a bound $\lambda(n) \prec (n \log^\ast n \log^+ n)^{-1}$
where $\log^\ast n = \log n \log \log n \log \log \log n \cdots$
and the product is taken only over positive real terms (see, e.g.,
\cite{Powers:ACL:1998}).
}}
However, the bound is tight to within a factor $n^\epsilon$ for any $\epsilon > 0$.
\ifverbose{
That is,
\begin{align*}
\lambda(n) \prec \frac{1}{n^{1+\epsilon} \log n \log^+ n} \preceq \frac{1}{n \log n \log^+ n}
\end{align*}
is a valid bound only if $\epsilon = 0$.
%   (Series of the form
% $\frac{1}{n^{1+\epsilon}f(n)}$ with $f \in \Omega(n)$ and
% $\epsilon > 0$ are convergent.)
}

\tinysection{Entropy maximization and Zipf's Law.}
\refthm{thm:lambdabound} provides an upper bound on $\lambda(n)$, but it could well be the
case that $\lambda(n) \sim \frac{1}{n^3}$, for example.  Why do the
curves we see in practice (e.g., \reffig{f:rates})
hug the bound of \refthm{thm:lambdabound}?
We believe the answer to why we observe $\lambda(n) \approx \frac{1}{n}$ 
is due to the tendency of libraries to evolve so that 
programmers can write as little code as possible, which in turn
implies evolution toward maximum entropy in compiled code
(\refprin{prin:entropy}).  
The entropy rate of
component references is maximized when $\lambda(n) \approx \frac{1}{n}$
(see, e.g., \cite{Harremoes:E:2001}).

\ignore{***
\begin{thm}
If a reuse strategy achieves a compression ratio of $\Hdomain$,
then 
\begin{align*}
\frac{1}{n^{1+\epsilon}} \preceq \lambda(n) \preceq \frac{1}{n}
\end{align*}
\end{thm}

\begin{proof}
\editor{(1) Show that entropy is maximized when $1/n$.  (2) If entropy
were not maximized, then we could further compress programs, conradicting
that the maximum achievable compression ratio is $H$...}
\end{proof}
***}

\ifverbose{
A maximum-entropy explanation for Zipf's law in natural languages has been
advocated by Harremo{\"e}s and Tops{\o}e \cite{Harremoes:E:2001}.  They
suggest that vocabulary learning be modelled by convergence to a Zipf-like
distribution and gradually increasing communication bit rate, a possibly
interesting model both for library development within a problem domain,
and for library learning progressions.
}

\ignore{***
\editor{Problem here: entropy rate of compiled programs is a function of the
code too.  There are $\lambda(n) \sim n^{-2}$ such that the entropy rate
is maximized (see Rissanen, p. 10).  Answer is probably that when $\Hdomain > 0$
rates of the form $\lambda(n) \sim n^{-1-\epsilon}$ are untenable.}

Recall our \refprin{prin:entropy} that the process of writing libraries
tends to maximize the entropy of compiled code.  This leads to a
testable prediction of what the empirically measured distributions
$\lambda(n)$ should look like.

We say a rate curve $\lambda(n)$ is acceptable if it conforms to
the bound of \refthm{thm:lambdabound}.
\begin{thm}
Among acceptable rate curves of the form 
$\lambda(n) \sim \frac{1}{n^a \cdot f(n)}$
where $a \geq 1$ and $f(n) \prec n^\epsilon$ for any $\epsilon > 0$,
entropy of the compressed program is maximized when $a = 1$.
\end{thm}

\editor{Now I am not so sure of this.}
This is a well-known result from information theory and we
leave the proof to a footnote.\footnote{
\begin{proof}
The entropy rate due to component references in a compressed program is:
\begin{align*}
H_\lambda & = \sum_{n=1}^\infty H(\lambda(n))
\end{align*}
where $H(\lambda) = - \lambda \log \lambda$.  
\editor{Use Gibb's inequality that we can switch the probability under
the log and have an upper bound.}
Note $H(\lambda)$ is
strictly increasing for $0 \leq \lambda < e^{-1}$.  If
$b < c$ then $\frac{1}{n^b} > \frac{1}{n^c}$ and so
for $n > 1$,
\begin{align*}
H\left(\frac{1}{n^b f(n)}\right) > H\left(\frac{1}{n^c f(n)}\right)
\end{align*}
Hence
\begin{align*}
\sum_{n=1}^\infty H\left(\frac{1}{n^b f(n)}\right) > \sum_{n=1}^\infty H\left(\frac{1}{n^c f(n)}\right)
\end{align*}
Therefore the entropy $H_\lambda$ is a strictly decreasing function
of the exponent $a$ in $\frac{1}{n^a f(n)}$.  We know $a \geq 1$
by \refthm{thm:lambdabound}, so therefore $a=1$ maximizes
entropy. 
\end{proof}
}

\tinysection{A measurable prediction.}
If library development drives compiled programs 
toward maximum entropy as proposed
in \refprin{prin:entropy}, we ought to see
rates of the form $\lambda(n) \sim \frac{1}{n f(n)}$ in
practice for mature problem domains in which there is
a good culture of reuse.  In fact, one might be able to gauge
how mature the reuse culture of a problem domain is by
looking at the observed rates $\lambda(n)$ and seeing how
close to $1$ the value of $a$ is.  Note that if the
rates $\lambda(n)$ are plotted on a log-log scale then
the exponent is easy to read as the slope:
\begin{align*}
\log \lambda(n) = - a \log n - O(\log \log n)
\end{align*}
The $O(\log \log n)$ term is negligible.  In \refsec{s:data} we
show that on several Unix platforms the rates support this
prediction.

***}

