% The so-called \emph{software crisis} is the chronic realization that
% \emph{software is hard}, and nothing we invent seems to make it easy.
% Thirty years in it has become more a crisis of faith than a crisis
% of matter.

\label{s:intro}
Software reuse offers the hope that software construction can be made
easier by systematic reuse of well-engineered components.  
\ifverbose{The
importance of developing libraries of reusable components has
been recognized since the very earliest days of computing (e.g.,
\cite{Wheeler:ACM:1952}), but received  a substantial push with 
M. Douglas McIlroy's famous paper \emph{Mass Produced Software Components}
\cite{McIlroy:NATO:1969}.  }
In practice reuse has been found to
improve productivity and reduce defects
\cite{Basili:CACM:1996,Griss:IBMSJ:1993,Krueger:CSUR:1992,Mohagheghi:ICSE:2004,Poulin:1997}.
But what of the limits of reuse --- will large-scale reuse make software 
construction easier?  Thinking here is varied, but for the sake of
argument let me artificially divide the opinions into two competing 
hypotheses.  First the more enthusiastic end of the spectrum, which I associate
with the Component-Based Software Engineering (CBSE) movement.

\begin{hypothesis}[Strong reuse]
Large-scale reuse will allow mass-production
of software, with applications being assembled by composing
large, pre-existing components.  The activity of programming will consist
primarily of choosing appropriate components from libraries, adapting and
connecting them.
\end{hypothesis}

Strong reuse is thought to thrive in problem domains with
great concentration of effort and similarity of purpose, i.e.,
many people writing similar software whose requirements show
only minor variation.
\ifverbose{
One offshoot
of ``strong reuse'' thinking has been the development of special-purpose
languages for describing the composition of components, variously
called composition languages \cite{Achermann:FMDP:2001}, module
interconnection languages \cite{Prieto-Diaz:JSS:1986}, coordination
languages \cite{Gelernter:CACM:1992}, configuration languages
\cite{Bishop:ICCDS:1996}, or simply scripts \cite{Schneider:1999}.
A hallmark of such languages is that they are not intended for
general-purpose programming, but specialized for describing
how pre-existing components are wired together.
}
However, the question of
whether strong reuse can succeed for software construction considered
globally, across disciplines and organizations, remains uncertain.
A more cautious view of reuse is the following.

\begin{hypothesis}[Weak reuse]
Large-scale reuse will offer useful
reductions in the effort of implementing software, but these savings
will be a fraction of the code required for large projects.  Nontrivial
projects will always require the creation of substantial quantities of new
code that cannot be found in existing component libraries.  
\end{hypothesis}

Representative of weak reuse thinking is the following prescription
for code reuse in well-engineered software from Jeffrey Poulin 
\cite{Poulin:1997}:
up to 85\% of code ought be reused from libraries,
with a remaining 15\% custom code, written specifically for
the application and having little reuse potential.
\ifverbose{
Weak reuse is most likely to succeed in problem domains where there
are substantial numbers of people writing code,
and there is enough commonality between the software projects undertaken
to support the development of libraries for the problem domain.
Weak reuse is also thought to
work in organizations that produce many software products with greatly
overlapping functionality --- the impetus behind the ``Software Product
Lines'' movement, e.g., \cite{Clements:2001}. 
}
The percentage of code that may be reused from libraries
varies greatly across problem domains, but
weak reuse paints a fairly accurate
picture of the software landscape of today.
Many explanations
are proposed for why strong reuse is not happening on a global
scale (cf. \cite{Frakes:SE:1996}).  A common position in the reuse
literature is that if we can only get the right environment in place --- the
right tools, generalizations, economics, a ``culture of reuse'' --- 
then reuse of software will soar, with consequent improvements in productivity
and software quality.
% Some of the major reasons might
% be insufficient commitment and education about reuse
% \cite{???}, inadequate retrieval systems to find relevant
% components \cite{...}, the need for component generation/generalization e.g.,
% \cite{Biggerstaff:CSR:1994,Batory:FSE:1993}, and architectural mismatch
% \cite{Garlan:ICSE:1995,Shaw:SSR:1995}.
% Each of these have spawned entire subfields of proposed solutions.

\tinysection{A contrary view.}
The perspective developed in this paper
suggests that the extent to which reuse can happen is an intrinsic property
of a problem domain, and that improving the
ability of programmers to find, adapt, deploy, generalize and market components
will have only marginal impact on reuse rates if the domain is 
resistant to reuse.
We propose to associate with problem domains an entropy parameter 
$0 \leq \Hdomain \leq 1$
measuring the diversity of a problem domain.
When $\Hdomain=1$, software is
extremely diverse and we should expect very little potential
for reuse; in fact, we show that the proportion of an application
we can draw from libraries approaches zero for large projects.  For
problem domains with $\Hdomain < 1$, software is somewhat homogeneous,
and with decreasing $\Hdomain$ comes increasing potential for reuse.
The theory we develop suggests that an expected proportion of \emph{at most}
$(1-\Hdomain)$ of an application's code may be reused from libraries,
with a remaining proportion $\Hdomain$ being custom code written
specifically for the application.  As $\Hdomain$ nears $0$ we enter
the strong reuse utopia of ``programming by composing large
components.''  The possibilities of reuse are 
\emph{strictly limited} by the parameter $\Hdomain$, which is an intrinsic 
property of the problem domain.

\ignore{***
A cynical view of reuse is that the availability of vast libraries
of reliable components will succeed in making us more productive, but
at the same time make the activity of programming increasingly difficult.
Lisanne Bainbridge, a psychologist studying industrial automation,
wrote a wonderful paper \emph{Ironies of Automation} \cite{Bainbridge:NTHE:1987}.  She observed that automation often makes an operator's job harder, 
in part because the tasks easy to automate are largely those easy for the
operator to perform, and their
removal may leave the operator with an arbitrary collection of
difficult tasks.  Thomas Green suggested this style of cautionary
thinking might apply to software also, and we should beware ``Ironies
of Abstraction.'' \cite{Green:unpub:...}
Perhaps large-scale reuse will take away the simple parts of programming,
and we shall have to think very hard about everything we do.

But cautionary tales aside, let us return to this question of
strong reuse.  
***}

We develop this theory by examining
our ability to compress or compactify software by the use
of libraries.
We shall speak throughout this paper of \emph{compressed programs}, by
which we mean programs written using libraries, and \emph{uncompressed
programs} that are stand-alone and do not refer to library components.
The principle tools we employ 
are information theory and Kolmogorov complexity.
Both of these carry subtly different notions of compressibility that
we shall have to juggle.
The information theory notion deals with
compressing objects by identifying 
patterns that appear frequently and giving them short descriptions
--- as in English we have taken
to saying ``car'' for ``automobile carriage.''  The Kolmogorov 
version of compressibility describes our ability to find for a
given program a shorter program with the same behaviour, without
appealing to how typical that program might be
for the problem domain within which we are working.
We assume some basic familiarity with information theory as 
might be found in e.g. \cite[Ch. 2]{Cover:1991} or \cite{Li:1997}.
The essentials of Kolmogorov complexity are reviewed in
\refsec{s:kolmogorov}.

\tinysection{Library components and prime numbers.}
Integers factor into a product of primes;
software can be factored into an assembly of components.
Library components are the prime numbers of software.
This would be a terribly naive thing to say were it not for the many 
wonderful parallels that turn up:
\begin{itemize}
\item There are infinitely many primes; in \refsec{s:incompleteness}
we prove there are infinitely many components for a problem domain that
reduce expected program size (thus guaranteeing employment for
library writers.)
\item The $n^\mathit{th}$ prime is a factor of $\sim \frac{1}{n \ln n}$
of the integers.  Theory predicts the $n^\mathit{th}$ most
frequently used library component has an ideal reuse rate of about
$\frac{1}{n \log n \log^+ n}$ (\refsec{s:newderiv}).
\item The Erd{\"o}s-Kac theorem states that the number of factors of
an integer tends to a normal distribution; we measure experimental
data that suggests a similar theorem might be provable for software
components (\reffig{f:erdos}).
\item The Prime Number Theorem states that the $n^\mathit{th}$
prime is $\sim \log (n \ln n)$ bits long.  We show that the ideal
configuration for libraries is that the $n^\mathit{th}$
most frequently used component is of size $\geq \log n$ and
$\leq \frac{1-\Hdomain}{\Hdomain} o(n^\epsilon)$ for $\epsilon \geq 0$
(\refsec{s:size}).
\end{itemize}
\ignore{***
There are limits to the analogy ---
unique factorization
of software into components would contradict undecidability of program
equivalence, for example \editor{Only if you assumed an effective procedure
for such a factorization?} --- but the similarities are
intriguing.
\editor{Would it contradict index theorems in computability?  with
an infinite undecidable library?}
***}

\input{pyramid}

