\subsection{The nonuniform case: $0 < \Hdomain < 1$}

\label{s:nonuniform}
More interesting than the uniform case is the situation when
$0 < \Hdomain < 1$, which implies a nonuniform distribution on
programs.  This models problem domains that have some potential
for code reuse, and libraries are of central importance in
reducing program size.
\ignore{***
In such problem domains libraries let us compress\footnote{In the information theory
sense.} the incompressible.\footnote{In the Kolmogorov complexity sense.}
}
Recall from \refsec{s:diversity} that we can expect to compress programs
in such domains from uncompressed size $s$ to at best $\Hdomain s$ by use of
a library.  A standard result from information theory can be adapted
to show this bound is achievable, at least in a theoretical sense.

\begin{claim}
\label{claim:achieve}
There exists a library with which uncompressed programs of size $s$ can
be compressed to expected size $\sim \Hdomain s$.
\end{claim}

The proof of this is not particularly illustrative
and we banish it to a footnote.\footnote{
\emph{Proof.}
We first describe an encoding that compresses programs to achieve an
expected size $\Hdomain s$, and then explain how to construct the library.
Recall the Shannon-Fano code \cite[\S 1.11]{Li:1997} allows a finite distribution
with entropy $H$ to be coded so that the expected codeword length is
$\leq H+1$.  We adapt this as follows.  For each
$s_0 \in \N$, we produce a Shannon-Fano codebook for all programs of
length $\leq s_0$ achieving average codeword size
$\leq H(p_{s_0}) + 1$ for the distribution $p_{s_0}$ (\refsec{s:diversity}).
By definition $H(p_{s_0}) \leq \Hdomain s$ almost surely, so this achieves
a compression ratio of $\Hdomain$ almost surely for each $s_0$ as $s_0 \rightarrow \infty$.
To combine all the codebooks into one, we preface a compressed program
with an encoding of its uncompressed length, which we use to select the 
appropriate codebook.  This can be done by adding to each codeword $c + 2 \log s$ bits
for some constant $c$, which is negligible with respect to $\Hdomain s$ when
$\Hdomain > 0$.  Therefore this encoding achieves expected program
size $\sim \Hdomain s$.  We use the codebook as the library: each 
component identifier is a Shannon-Fano code, each component is a
program.  Note that the reuse rates vanish for this
construction, i.e., $\lambda(n) \rightarrow 0$ as $s_0 \rightarrow \infty$,
and so the bound of \refthm{thm:lambdabound} is trivially satisfied.
% Note that reuse rates vanish for this construction.
\qed
}
The gist is to place every possible program into the
library as a ``component,'' but ordering them so that the most likely programs for the
problem domain come soonest in the library order and thus are assigned
the shortest codewords.  This is a wildly impractical construction but
demonstrates the claim.  In practice we decompose software into
reusable chunks that we put in libraries; that reusable chunks exist
suggests an ergodic property (see \refsec{s:AEP}).

Unlike the situation of $\Hdomain=1$ where the number of components
useful for a program was at most a constant, when $0 < \Hdomain < 1$ we 
have a much more pleasing situation: the number of useful
components increases steadily as we increase program size.

\subsubsection{The incompleteness of libraries}
\label{s:incompleteness}
Under reasonable assumptions we prove that no finite library
can be complete: there are always more components we can add to
the library that will allow us increase reuse and make programs
shorter.
To make this work we need to settle a subtle
interplay between the Kolmogorov complexity notion of compressibility
(there is a short\-er program doing the same thing)
and the information theoretic notion of compressibility
(low entropy over an \emph{ensemble} of programs).
\ifverbose{
When we defined a problem domain in \refsec{s:distribution},
we did so by stipulating a family of probability distributions
on programs.  From this we derived a bound $\Hdomain$ on the
entropy rate of programs in a problem domain, and said that
we could compress programs to an expected factor of at most $\Hdomain$.
}
Now because we defined probability distributions on programs
(rather than behaviours), we run into the possibility that
the probability distribution might weight heavily
programs that are \emph{Kolmogorov} compressible, i.e.,
the distribution might prefer programs $w$ with $\strlen{w} >> C(w)$.
For example, a problem domain might have programs that are usually
compressible to half their size not
because the probability distribution focuses on a particular
class of problems, but because we artificially defined $p_{s_0}$ to
select only those programs that are twice as large as they might be
(for example, we might pad every likely program with many $\mathsf{nop}$
instructions.)
% If we view uncompressed programs as \emph{specifications} programmers
% set out to realize, honesty seems a good assumption.  If we view 
% uncompressed programs as ``what code would a programmer write without
% a library'' then assuming incompressibility is maybe too strong?
To avoid this difficulty we require the distributions be \emph{honest}
in the following sense.
\begin{defn}[Honesty]
\label{defn:honesty}
We say the distributions $p_{s_0}$ for a problem domain are
\emph{honest} if the programs are 
% (in $p_{s_0}$) 
Kolmogorov incompressible.  Specifically,
\begin{align}
\label{e:honesty}
E\left[ \frac{C(w)}{\strlen{w}} \right] \rightarrow 1 & ~~~~\text{as } s_0 \rightarrow \infty
\end{align}
where the expectation is taken over the distributions $p_{s_0}$.
This requires that the probability distribution does
not artificially prefer verbose programs with $\strlen{w} >> C(w)$.
\end{defn}

% This definition might be unnecessary if we considered probability distributions
% on \emph{specifications} rather than programs.
If the distribution for a problem domain is honest and has $\Hdomain < 1$, the 
programs are expected to be \emph{information-theoretically compressible}
by use of a library, but not
\emph{Kolmogorov compressible}.  
In other words, our ability to compress programs
is due to a ``focus'' on a class of problems of interest to the domain,
not just an artificial selection of overly-verbose programs.

Inspired by Euclid's proof that there are infinitely many primes,
with the honesty assumption we can prove there are infinitely many
reusable software components that make programs shorter.

First we need two smaller pieces of the puzzle. 
\ignore{***, which proves a `concentration of
measure' result, that when $\Hdomain > 0$, 
almost all the programs with $\strlen{w} \leq s_0$
are of size nearly $\sim \Hdomain s_0$ or greater.
***}
\begin{lem}
\label{lem:concentration}
If $\Hdomain > 0$ then for any finite $k$, 
$Pr(\strlen{w} \leq k) \rightarrow 0$ as $s_0 \rightarrow \infty$.
\end{lem}
\begin{proof}
We know from definition of $\Hdomain$ that $H(p_{s_0}) = \Hdomain s_0$
infinitely many times as $s_0 \rightarrow \infty$ (\refsec{s:diversity}).  
% I am referring to a notion of limsups, limit superiors.
Consider how probability 
must be distributed among programs of different lengths to account for 
this much entropy.  We try to account for as much
entropy as we can by short programs, setting a uniform distribution
$p(w) = \frac{1}{2^{\Hdomain s_0}}$ on the first $2^{\Hdomain s_0}$ programs---
this is the fewest number of programs that would produce this much entropy.
To programs of length $\leq k$ we can account for
\begin{align*}
\sum_{i=0}^k 2^i \cdot \left( - \frac{1}{2^{\Hdomain s_0}} \log \frac{1}{2^{\Hdomain s_0}} \right)
\sim 2^{k+1-\Hdomain s_0}\Hdomain s_0
\end{align*}
bits of entropy.  But as $s_0 \rightarrow \infty$, 
$2^{k+1-\Hdomain s_0}\Hdomain s_0 \rightarrow 0$ so we can account for
none of the entropy by programs of length $\leq k$.  Therefore
$Pr(\strlen{w} \leq k) \rightarrow 0$ as $s_0 \rightarrow \infty$.
\end{proof}

\begin{lem}
\label{lem:recipzero}
If $\Hdomain > 0$ then $E\left[ \frac{1}{\strlen{w}} \right] \rightarrow 0$ as
$s_0 \rightarrow \infty$.
\end{lem}

\begin{proof}
Suppose $E\left[ \frac{1}{\strlen{w}} \right] = c$ for some $c > 0$.
Then there would be a finite probability that $\strlen{w} \leq c^{-1}$
as $s_0 \rightarrow \infty$, contradicting \reflem{lem:concentration}.
\end{proof}

Now we are ready for the main theorem, which proves no finite library
can be ``complete'' in the sense of achieving a compression ratio of
$\Hdomain$ when $0 < \Hdomain < 1$.

\begin{thm}[Library Incompleteness]
\label{thm:incompleteness}
If a problem domain has $0 < \Hdomain < 1$ and 
honest distributions (\refdefn{defn:honesty}), no
finite library can achieve an asymptotic compression ratio of $\Hdomain$.
\end{thm}

\begin{proof}
% This library situation is also starting to look like an oracle.
Suppose a finite library of components achieves
a compression factor $1 - \epsilon$, with optimal compression when
$1-\epsilon = H$.
Call the programming language $\phi$
and the library $L$.  We can write an interpreter for $\phi$ that
incorporates the library $L$; since the library is finite this is
a finite program.  We call the resulting machine model $\phi+L$.
Consider Kolmogorov complexity for this machine, writing
$C_{\phi +L}(w)$ for the size of the smallest $\phi$-program using $L$ that
has the same behaviour as $w$.  Saying the machine $\phi+L$ achieves the
compression factor $1-\epsilon$ implies
\begin{align}
E\left[ \frac{C_{\phi+L}(w)}{\strlen{w}} \right] = 1 - \epsilon
\end{align}
From the invariance theorem of Kolmogorov complexity (\reffact{fact:invariance})
we have that there exists a constant $c$ such that
\begin{align}
\label{e:zz}
C(w) \leq C_{\phi+L}(w) + c
\end{align}
\noindent
for every program $w$.  Dividing through by $\strlen{w}$ and taking expectation,
\begin{align}
\label{e:zjk}
E\left[ \frac{C(w)}{\strlen{w}} \right] \leq \underbrace{E\left[ \frac{C_{\phi+L}(w)}{\strlen{w}}\right]}_{= 1 - \epsilon} + E\left[ \frac{c}{\strlen{w}} \right] 
\end{align}
From honesty $E\left[ \frac{C(w)}{\strlen{w}} \right] \rightarrow 1$,
and from \reflem{lem:recipzero}
we have
$E\left[\frac{c}{\strlen{w}}\right] \rightarrow 0$.  Therefore (\ref{e:zjk}) is, in the limit as $s_0 \rightarrow \infty$:
\begin{align*}
1 \leq (1 - \epsilon) + 0
\end{align*}
For this inequality to hold,
$\epsilon \rightarrow 0$ for any finite library.  Therefore
no finite library can achieve an asymptotic compression ratio $< 1$
when the distributions are honest.
\qed
\end{proof}

% Ah, a more careful argument could use a Cauchy sequence and
% translate $H < 1$ into $H = 1 - \epsilon$ where $\epsilon > 0$.

% \editor{Double check this line of reasoning.  For example 
% $1 - \frac{1}{2^n} < 1 + \frac{1}{2^n}$ even though in the limit they 
% are equal.}

\refclaim{claim:achieve} showed that an infinite library can achieve
expected size $\sim \Hdomain s$; \refthm{thm:incompleteness} shows
that no finite library can.  Therefore only infinite libraries can
compress programs of size $s$ to expected size $\Hdomain s$.  
However, this is an asymptotic argument; if we restrict ourselves
to programs of size $\leq s_0$ for some fixed $s_0$, finite
libraries can approach a compression ratio of $\Hdomain s$ by including
more and more components.
\ignore{***\footnote{
This can be modelled by considering truncated versions of the entropy
series
\begin{align}
\label{s:entropyseries}
\sum_{n=1}^\infty H(\lambda)
\end{align}
\noindent
where $H(\lambda) = - \lambda \log \lambda$ is the usual definition of
entropy.  The convergence of the sum \refeqn{s:entropyseries} 
is very slow, suggesting there are always more components to
add to the library that add practical savings in expected codeword size.
\editor{It would be nice to show a plot!  The ``very slow'' part
comes because we choose the series to be just on the cusp of a
divergent series?}
}
***}
Doug Gregor suggested calling
\refthm{thm:incompleteness}
the \emph{Full Employment Theorem for Library Writers}, after 
Andrew Appel's boon to compiler writers.
\refthm{thm:incompleteness} has a straightforward implication:
no finite library can be complete; there are always more useful
components to add.  In practice we have a tradeoff between the
utility of larger libraries and the economic cost of
producing them; this suggests the importance of designing libraries
for extensibility. 

% With finite
% libraries we can get arbitrarily close to achieving $\Hdomain s$ by including
% more and more components.

A minor change to the above proof yields a similar but slightly stronger
result.
\begin{cor}
\label{cor:noce}
If a problem domain has $0 < \Hdomain < 1$ and honest distributions, no
\emph{computably enumerable} library can achieve a compression ratio of
$\Hdomain$.
\end{cor}
\begin{proof}
Repeat the proof of \refthm{thm:incompleteness}, replacing ``finite library''
with ``c.e. library.''  In particular the choice of a c.e. library guarantees
that the interpreter for $\phi+L$ is a finite program: whenever a library
subroutine is required, it can be generated from the program enumerating the
library.
\qed
\end{proof}

We may casually equate ``not computably enumerable'' with ``requires
human creativity.''  \refcor{cor:noce} indicates that the process of
discovering new and useful library components is not a process that can
can be fully automated.

% Application of truncating the entropy series to resource-constrained
% computing.
