\label{s:model}
In this section we propose an abstract model capturing some
essential aspects of software reuse within a problem domain.
The basic scenario is this:
we have a library, possibly many libraries that we collectively
consider as one, that contains a great number of software components.
These components may be subroutines, architectural skeletons, design
patterns, generics, component generators, or whatever form of abstraction we
may yet invent; their precise nature is unimportant for the argument.
In using a component from the library we achieve some reduction in
the size of the program, and perhaps consequently, in the effort
required to implement it.  
Program size serves as a rough lower
bound to effort, but it would be a grave error to confuse the two.
\ignore{***
and I shall avoid this.\footnote{If program size were the determining
factor in programming effort, we could write programs ten times
faster by writing binary representations of source code such as
those produced by running data compression tools on source code.  This 
is of course absurd.
Program length is a factor in effort, but usability of the program 
representation is crucial.  Since programming effort is not easy to 
formalize, we reason about program length instead, but do not pretend 
this is equivalent to effort.} 
***}
\ifverbose{
One consequence of
adopting the stance that using library components ``saves code''
is that components that could be reimplemented in less than the
space required to refer to them are ruled out.  But practical
examples of this are scarce, and their omission seems justified.
}

\ifverbose{
We briefly summarize the key points of the model:
\begin{enumerate}
\item Problem domains are modelled by a probability distribution on
programs that weights programs by how likely they are to be implemented
by programmers working in that domain (\refsec{s:distribution}).
\item We associate with problem domains an \emph{entropy parameter}
$0 \leq \Hdomain \leq 1$ measuring how diverse software is within that domain
(\refsec{s:diversity}).
\item The social processes by which programmers build libraries 
tend to maximize the
\emph{entropy rate} of compiled code (\refsec{s:entropy}).
\item For each problem domain we pretend there exists already an infinite 
`Platonic library' of components.  The libraries we have at any instant 
in time are finite fragments of this library (\refsec{s:platonic}).
\item Reuse of the $n^\mathit{th}$ component in the library is measured by its
\emph{reuse rate} $\lambda(n)$, giving the expected number of references
per bit of compiled code (\refsec{s:rates}).
\item The library components are arranged in descending order of reuse rate
so that $\lambda(n) \leq \lambda(n+1)$ (\refsec{s:ordering}).
\end{enumerate}
}

\subsection{Distribution of programs in a domain}

\label{s:distribution}
We presume that the projects undertaken by programmers working in a
problem domain can be modelled by
a probability distribution on programs.
The probability distribution is defined on ``uncompressed'' programs
that do not use any library components.
These uncompressed programs can be viewed as \emph{specifications}
that programmers set out to realize.

We consider compiled programs modelled by binary strings 
on the alphabet $\{0,1\}$.
We write $\strlen{w}$ for the length of a string $w$.\ignore{\footnote{
The use of $|w|$ for string length, while traditional in some quarters,
leads to confusing notations such as $P(w ~|~ |w| < m)$ for 
probability conditioned on string length.  We use
$\strlen{\cdot}$ to avoid this.
}}
Finite programs are countably infinite in number, so we immediately encounter
the problem of defining a probability distribution in which the
probability of encountering individual programs may be infinitesimal.
A rigorous approach would be to employ measure theory,
for example Loeb measure, which would allow us to speak of the probability
of individual programs.
This would require some rather daunting
machinery and we instead settle for a more accessible
approach similar to that used by 
\cite{Ben-David:JCSS:1992,Compton:NATO:1988,Rissanen:1989}.
% (but standard) approach, used for example in 
% \cite{Ben-David:JCSS:1992,Compton:NATO:1988,Rissanen:1989}.

Let $A^{\leq n} = \{ w \in \{0,1\}^\ast ~:~ \strlen{w} \leq n \}$ denote
compiled programs of length at most $n$ bits.
We introduce a family of conditional distributions
$\{p_{s_0}\}_{s_0 \in \N}$ whose domains consist of programs
$\leq s_0$ bits in size, that is,
\begin{align*}
p_{s_0} : A^{\leq s_0} \rightarrow \R
\end{align*}
and satisfying $\sum p_{s_0} = 1$ and $p_{s_0}(w) \geq 0$.
The intent is that $p_{s_0}(w)$ gives the
probability that someone working in the problem
domain will set out to realize the particular (uncompressed) program $w$, 
given that $w$ is at most $s_0$ bits long.
For this family of distributions to be compatible with one another we 
require that 
$p_{s_0}(w) = p_{s_0+1}(w ~|~ \strlen{w} \leq s_0)$,
i.e., we can get the distribution on length $\leq s_0$ programs by
taking a conditional probability on the distribution for length
$s_0+1$ programs.
We do not presume that such distributions can be effectively
described.

\ifverbose{
One misgiving we might have is that programmers do not
set out to duplicate a given program, but rather to realize
some specification or behaviour.  However, it turns out that
almost every compiled program is the smallest program with
its behaviour (\refsec{s:kolmogorov}),
so programs are a reasonable stand-in for specifications.
}

In what follows we use the usual notation for expectation
with the implied assumption of $s_0 \rightarrow \infty$; for
example, if $f : \{0,1\}^\ast \rightarrow \R$ maps programs to
real numbers, then by $E[f(w)]$ we mean:
\begin{align*}
E\bigl[ f(w) \bigr] &\equiv \lim_{s_0\rightarrow \infty} \sum_{w : \strlen{w} \leq s_0} f(w) p_{s_0}(w)
\end{align*}
if such a limit should exist.
For example, a mean program size $E\bigl[\strlen{w}\bigr]$ may exist for a
problem domain, but we do not require nor expect this.

\subsection{The entropy parameter $\Hdomain$}

\label{s:ergodic}
\label{s:diversity}
A key, perhaps defining, feature of a problem domain is
that there is similarity of purpose in the programs people write.
We do not expect the distribution of programs written in a
problem domain to be uniform over all possible programs, 
but rather concentrated on programs that solve certain classes
of problems typical for the domain.
We formalize this intuition by introducing a parameter
$\Hdomain$ for problem domains
measuring how far their probability distribution departs from 
uniform.  This $H$ is very similar to
entropy rate from information theory, and coincides if we are willing to
assume programs are drawn from a stationary stochastic process.
When $\Hdomain=1$
the distribution over programs is uniform, modelling extreme diversity
of software, with little opportunity for reuse.
For $\Hdomain < 1$ there is some potential for reuse.
In fact as we shall see shortly, we may expect that
up to a proportion $1-\Hdomain$ of programs may be reused
from libraries.

% In the case where $p_s(w)$ is a constant $c$ for every $\strlen{w} \leq s$,
% the distribution is uniform.  This is an extreme model of
% software diversity: every program is equally possible,
% and programmers embark on projects that are purely random.
% As we shall see in \refsec{s:uniform}, libraries are of
% limited use in this case.  
%We measure the departure from uniformity by examining the entropy of the 
%distributions $\{ p_{s_0} \}$.  
Define the entropy of
each distribution $p_{s_0}$ in the standard way
(see, e.g., \cite{Cover:1991,Li:1997}):
\begin{align*}
H(p_{s_0}) &= \sum_{w : \strlen{w} \leq s_0} - p_{s_0}(w) \log_2 p_{s_0}(w)
\end{align*}
This is the expected number of bits required
to represent a program of size $\leq s_0$ in this domain.
We are interested in the limit behaviour of
$\frac{1}{|A^{\leq s_0}|} H(p_{s_0})$, 
akin to the entropy rate of a random process. 
In general this limit may not exist --- there might be 
oscillations --- so we need some weaker notion of
limit.  We settle for a limsup, which gives an almost sure
upper bound on the limit behaviour.
% \editor{Ah.  Probably better to use the Ce{\`s}aro limit here.}
% \editor{See also \url{http://wcl3.tamu.edu/itw2004/program/viswananthan_inv.pdf}
% and the reference [15].}

\begin{defn}[Entropy parameter]
Define the \emph{entropy parameter} $\Hdomain$ of a problem domain
to be the greatest value that
$\frac{1}{|A^{\leq s_0}|} H(p_{s_0})$ attains infinitely
often as $s_0 \rightarrow \infty$:
\begin{align*}
\Hdomain &= \limsup_{s_0 \rightarrow \infty} \left( \frac{1}{|A^{\leq s_0}|} H(p_{s_0}) \right)
\end{align*}
\ignore{\footnote{We do not assume $\lim_{s_0 \rightarrow \infty} \frac{1}{s_0} H(p_{s_0})$
exists; there might be oscillations in
$H(p_{s_0})$.
% (for example, if all problems were of size $2^{2n}$ for some
% integer $n$ in the problem domain.)
% That a least $\Hdomain$ exists follows from 
% all such $\Hdomain$ being bounded by $0 \leq \frac{1}{s_0} H(p_{s_0}) \leq 1$.
This definition of $\Hdomain$ differs slightly from the usual definition
of entropy rate from information theory, in which the entropy rate of
infinite streams or random processes are considered.  But the two
can be considered equivalent for most purposes as $s_0 \rightarrow \infty$.
}}
As a consequence of this definition we are guaranteed
that $H(p_{s_0}) \leq s_0 H$ almost surely as $s_0 \rightarrow \infty$.
\end{defn}

We cannot hope to calculate $\Hdomain$ from first principles
except for toy scenarios, but there is hope we might estimate it
empirically.
We introduce $\Hdomain$ primarily as a theoretical tool
to model problem domains in which
people have great similarity of purpose
($\Hdomain \rightarrow 0$) or diffuse interests 
($\Hdomain \rightarrow 1$).  The main impact of $\Hdomain$
is the following.

\begin{figure}
\begin{centering}
\input{Hdomain.eepicemu}

\caption{
\label{f:Hdomain}The basic scenario: programmers in a
problem domain set out to realize a program that can
be represented in $s$ bits when compiled without the use of a library.
By using library components, they are able to reduce the
size of the compiled program, down to an expected size of
$\geq \Hdomain s$ bits.
}
\end{centering}
\end{figure}

\begin{claim}
In a problem domain with entropy parameter $\Hdomain$,
the expected proportion of code that may be reused from a library is at
most $1-\Hdomain$.
\end{claim}

This is a consequence of the Noiseless Coding Theorem of information
theory (e.g., \cite[\S 2.5]{Ash:1967}),
which states that coding random data with entropy $H$ requires
(on average) at least $H$ bits.  
Suppose an uncompressed program has size $s \leq s_0$.  
We defined $\Hdomain$ so that
$H(p_{s_0}) \leq s \Hdomain$ 
almost surely, so we can compress programs to an expected size of at best
$s \Hdomain$ by the Noiseless Coding Theorem.  
Therefore the expected amount of code saved by use of the library is at most
$(1 - \Hdomain) s$, and it is reasonable to equate this with
the amount of code reused from the library.
An immediate implication is that blanket reuse prescriptions
such as ``effective organizations reuse 70\% of
their code from libraries'' are unrealistic; reuse goals need to be pegged
to the problem domain's value of $\Hdomain$.

\reffig{f:Hdomain} illustrates the scenario we consider in
this paper: programmers set out to implement the capabilities of
some uncompressed program of length $s$
written without use of a library, drawn from the distribution for the 
problem domain.  A programmer implements the program making use of
the library, effectively ``compressing'' it.  The expected size
of the compressed program is at least $\Hdomain s$ bits, by the
previous arguments.  The library consists of a set of components,
each with an identifier or \emph{codeword} by which they are referred to.
We always take programs to be \emph{compiled}, so as not to care
about the high compressibility of source representations.

% Maybe talk about ``typical sets'' of programs for the problem domain?

\subsubsection{Motifs and the AEP}
\label{s:AEP}
One question we should like to answer is whether when $H < 1$
there are commonly occurring patterns or ``motifs'' in programs
that we can put in libraries and reuse to compress programs.
If we are willing to assume that programs in
a problem domain behave as if excerpted from a stationary ergodic source, then
the Shannon-McMillan-Breiman theorem (asymptotic equipartition property or
AEP) \cite[\S 15.7]{Cover:1991}
ensures that when $H < 1$ there are commonly occurring
finite subsequences in programs that can be exploited, and indeed
that we can achieve optimal compression of programs merely by having
libraries of common instruction sequences.
That more complex software components
prove necessary in practice suggests the stationary ergodic 
assumption is too strong,
and a weaker ergodic property 
is needed to account for the emergence 
of motifs in software when $H < 1$.
It is unclear yet exactly what this property might be; in
the remainder of this paper we do not assume AEP.
% For example, it is easy to define distributions that have a low
% entropy rate and yet have no commonly occurring subsequences
% whatsoever.  Just pick for each value of $s$ some randomly
% chosen programs.  Then there will be no AEP.  Or for example
% Champerdowne's number, where the locally measured entropy
% rate must be $1$, but is highly compressible given a greater
% resource bound.  What resource classes corresponds to ``locality''?
% Total computable functions?  (Any total computable function has
% a computable bound on its ``neighbourhood'', namely the running time
% of the function itself.)
% Perhaps some resource bound corresponding to FO logic, whatever
% that would be.  Wow, this is another dimension of the whole
% ``tradeoffs'' cluster of ideas.  What logic expresses
% just subsequences?  What is the correspondence between "typical set"
% (see Cover) and the "almost sure theory"?
% If you interpret the "random" in "random process" in the
% Martin-Lof sense of random, how do ergodic properties fit in?
% The generators for the invariance group have an action on
% formulas in the logic: e.g., for the motif "xyz", this can
% be expressed as $(w_1 = x)\wedge(w_2 = y)\wedge(w_3 = z)$.
% The invariance group generates a set of formulas from this,
% one for each location.  (Recall the correspondence between
% the sigma algebra and infinitary logic!)
% What is the ergodic property that guarantees the AEP and
% emergence of *local* motifs?
% Why do you get a Zipf-like distribution when you choose a
% ``basis'' of stochastically independent properties?
% We can think about our ability to compress finite structures
% drawn from a given distribution in various resource-bounded
% classes, and the $H$ we can achieve.  This collapses the resource
% classes into a one-dimensional total order... but what does the
% ordering reflect?  Maybe some ideas from "Kolmogorov minimal statistic"
% and "structure function" would be helpful.
% An iid random process has an invariance group that allows arbitrary
% permutation of the sequence.

\subsection{Libraries maximize entropy}

\label{s:entropy}
\begin{quote}
A truly great computer programmer is lazy, impatient and full of hubris. Laziness drives one to work very hard to avoid future work for a future self. --- Larry Wall
\end{quote}

Programmers, so we read, are lazy--- they write libraries to capture
commonly occurring abstractions so they do not have to write them over and
over again. 
%  Libraries serve (in part) to minimize the effort of programming.  
The social processes that drive programmers to develop
libraries have an interesting theoretical effect.  We can view
programmers contributing to domain-specific libraries as collectively 
defining a system 
for \emph{compressing programs} in that domain.  If there is a common pattern,
eventually someone will identify it and put it in a library.
Since the absence of common patterns in code is implied by
high entropy, we propose the following principle.

\begin{principle}[Entropy maximization]
\label{prin:entropy}
Programmers develop domain-specific libraries that minimize the
amount of frequently rewritten code for 
the problem domain.   This tends to maximize the entropy of 
compiled programs that use libraries.
\end{principle}

% Note that we do not mean thermodynamic entropy, which might suggest
% that libraries serve to maximize the disorganization of programs!
As evidence for this principle, we show in \refsec{s:data}
that the rate at which library components are reused is 
empirically observed to approach a maximum entropy configuration.\footnote{
Note that \refprin{prin:entropy} is \emph{not} intended to appeal to the
maximum entropy principle as advocated by Jaynes, which deals with
maintaining uncertainty in inference.
}

In practice programmers have to strike a balance between
the succinctness of their programs and their readability; see, e.g.,
\cite{Green:HCI:1989} for an elegant discussion of such tradeoffs.
However, we maintain that the drive toward terseness and factoring
common patterns
is a defining pressure on library development: entropy is essentially
a measure of \emph{communication efficiency}, and programmers edge
as close to maximum entropy as they can while maintaining 
source-code understandability.\footnote{We re-emphasize that we are speaking of the
entropy rate of \emph{compiled} programs; source representations
are highly compressible to support readability.}

\subsection{The Platonic library}

\label{s:platonic}
In the early days of computing
libraries held a hundred subroutines at most; these days it is
common for computers to have a hundred thousand subroutines available
for reuse (cf. \refsec{s:data}).  Let us suppose that as time goes on we shall
continue to add components to our libraries as we discover
useful abstractions and algorithms.
% \footnote{
% Which is to say, we shall not find ourselves in the year 2100 having
% implemented every possible useful component, with the prospect of
% spending the rest of the life of the universe wiring them together in
% unique combinations that have no prospect of reuse.
% }
Our current libraries might be viewed as a truncated version of some
infinite (but countable) 
library toward which we are slowly converging.  It is convenient
to pretend
that this limit already exists as some infinite ``Platonic library'' 
for the problem domain,
and that we are merely discovering ever-larger fragments of it, recalling
Erd{\"o}s' book of divine mathematical proofs.\footnote{A Platonic object
is an abstract entity thought to dwell in some realm outside 
spacetime.
Our stance with respect to software libraries echoes
mathematical Platonism, that mathematical objects about which we reason
exist in some idealized form outside the physical universe (see, 
e.g., \cite{Balaguer:SEP:2004}).
\ifverbose{Regarding Erd{\"o}s' idea: ``God has a transfinite Book, which
contains all the theorems and their best proofs, and if He is well
intentioned toward those [mathematicians], He shows them the Book
for a moment.  And you wouldn't even have to believe in God, but
you must believe that the Book exists.'' } }
Were we granted access
to the entire library, we might write software in a very efficient
way.  We use the Platonic library as a device --- a convenient
fiction --- to reason about how useful finite libraries might be.

Infinite objects need to be treated with care.
We shall not assume that some ``optimal
infinite library'' exists that is the best possible such
library.  Nor shall we assume there is some finite description or
computable enumeration of its contents.
We merely assume that fragments of the Platonic library
give us snapshots of what shall be in our software libraries over time.

\subsection{Existence of reuse rates}

\label{s:rates}
Numerous metrics have been proposed for measuring reuse.
We focus on the \emph{reuse rate} of a component, which we write
$\lambda(n)$ and define as the expected rate at which
references are made to the $n^\mathit{th}$ library component in
a compressed program.
% For example, in the linux kernel the
% the C subroutine $\mathsf{strcmp}$ is reused at an average rate of
% approximately 0.5 references per kloc (thousand lines of source code).
The units of $\lambda(n)$ are expected references per bit of compiled code.
We assume mean reuse rates exist in a problem domain,
in the following sense.

% \editor{Oops.  ``the compressed version'' is a big problem: which
% version?  Do we need to define a maximally compressed version?
% Shall we just say ``of typical programmers''?}

\begin{assume}
\label{ass:meanlambda}
Let $\mathrm{Refs}_n(w)$ count the number of references
to the $n^\mathit{th}$ component in a compressed program
$w$ of size $\leq s_0$.  We assume that
\begin{align}
E\Bigl[\mathrm{Refs}_n(w) ~\Bigm|~ \strlen{w} = s \Bigr] ~~\sim~~ \lambda(n) s + o(s)
 ~~~~\mathrm{as}~s_0 \rightarrow \infty
\end{align}
where $o(s)$ denotes some error term growing asymptotically
slower than $s$.
\end{assume}

We unfortunately do not have a good sense of how to go from
the problem domain's distributions $p_{s_0}$ on \emph{uncompressed}
programs to rates of components in \emph{compressed} programs;
this is tied up with the ergodic process issues mentioned in
\refsec{s:ergodic}.
We dodge the issue by simply \emph{assuming} that the mean 
rates $\lambda(n)$ exist.
This is not a demanding assumption; many sensible
random process models would imply \refassume{ass:meanlambda},
for example modelling component uses as a renewal process
% We do not assume any random process model for the appearance of 
% component uses, although renewal processes would be a natural choice.
% A renewal process model would make the stronger assumption that the 
% intervals between references to a component are independent and identically
% distributed; under these conditions our weaker \refassume{ass:meanlambda}
% is assured 
(see, e.g., \cite[\S 3]{Ross:1996}).\footnote{
For readers familiar with coding theory we
forestall confusion by mentioning that the rates $\lambda(n)$ are
not the same as the usual notion of probabilities over countable
alphabets.  The rates $\lambda(n)$ are 
drawn from compressed programs and so already incorporate code lengths.
}
\ignore{***
We offer two arguments to support \refassume{ass:meanlambda}, one from empirical
observations and one theoretical.

\tinysection{Empirical justification.}
\editor{Here I will throw in a graph showing the observed reuse rates
for some C functions in the linux kernel, plotting number of occurrences
vs. the amount of code measured, hopefully showing convergence to a 
linear function.}

\tinysection{Theoretical justification.}
Another piece of evidence that average reuse rates might exist for certain 
classes of random programs comes from the extensive literature
on the occurrence of patterns in random 
strings.
For example, Nicod{\`e}me et al study the occurrence
of ``motifs'' (patterns defined by regular expressions)
in random strings \cite{Nicodeme:ESA:1999}.  They
prove that the distribution of the number of occurrences of motifs in
large random strings of length $s$ converges to a Gaussian distribution
with mean $\lambda s + c + O(A^s)$, where $\lambda$ is a rate parameter,
$c$ is a constant, and $|A| < 1$.  Thus the mean rate is $\lambda s + o(s)$
as in \refassume{ass:meanlambda}.
If reuse opportunities may be
approximated by finite sets of patterns against which programs are matched,
the occurrence of these patterns is itself Gaussian with some
mean rate parameter.  (However, it is unclear if the results of
Nicod{\`e}me et al. extend to infinite sets of patterns, or to
random strings with low entropy rates, so this evidence for
\refassume{ass:meanlambda}, while suggestive,
is not incontrovertible.)
Similar ideas of pattern matching are used in program compactification to find
opportunities to reuse subroutines 
\cite{Marks:IBMJRD:1980,Runeson:LCTES:2001}.
% with a mean 
% $\sum_i \lambda_i s + c_i + O(A^s_i)$, where $\lambda_i$ is the 
% occurrence rate of the $i^\mathit{th}$ pattern.  The collective 
% rate parameter converges to $(\sum_i \lambda_i) + O(c s^{-1})$.

***}

\subsection{Ordering of library components}

\label{s:ordering}
For convenience we shall suppose the library components are arranged
in decreasing order of expected reuse rate in the problem domain: that is,
\begin{align*}
\lambda(n) \geq \lambda(n+1)
\end{align*}

There are two reasons for this.  The first is tidiness,
so that when we plot
$\lambda(n)$ vs $n$ we see a monotone function and not noise.  
The asymptotic bounds we derive on $\lambda(n)$ do not rely on this 
ordering.  The second reason is that to derive bounds on how well we
might compress programs
we need to assign shorter identifiers to more frequently used components.
This is easiest to reason about if the Platonic library is
sorted by use frequency.\footnote{Jeremiah Willcock made the useful suggestion 
that we may regard the Platonic library as containing already every possible 
component, and the only question is the order in which they
are placed.}


