% This is sigproc-sp.tex -FILE FOR V2.6SP OF ACM_PROC_ARTICLE-SP.CLS
% OCTOBER 2002
%
% It is an example file showing how to use the 'acm_proc_article-sp.cls' V2.6SP
% LaTeX2e document class file for Conference Proceedings submissions.
% ----------------------------------------------------------------------------------------------------------------
% This .tex file (and associated .cls V2.6SP) *DOES NOT* produce:
%       1) The Permission Statement
%       2) The Conference (location) Info information
%       3) The Copyright Line with ACM data
%       4) Page numbering
%
%  However, both the CopyrightYear (default to 2002) and the ACM Copyright Data
% (default to X-XXXXX-XX-X/XX/XX) can still be over-ridden by whatever the author
% inserts into the source .tex file.
% e.g.
% \CopyrightYear{2003} will cause 2003 to appear in the copyright line.
% \crdata{0-12345-67-8/90/12} will cause 0-12345-67-8/90/12 to appear in the copyright line.
%
% ---------------------------------------------------------------------------------------------------------------
% It is an example which *does* use the .bib file (from which the .bbl file
% is produced).
% REMEMBER HOWEVER: After having produced the .bbl file,
% and prior to final submission,
% you need to 'insert'  your .bbl file into your source .tex file so as to provide
% ONE 'self-contained' source file.
%
% Questions regarding SIGS should be sent to
% Adrienne Griscti ---> griscti@acm.org
%
% Questions/suggestions regarding the guidelines, .tex and .cls files, etc. to
% Gerald Murray ---> murray@acm.org
%
% For tracking purposes - this is V2.6SP - OCTOBER 2002

\documentclass{sig-alternate} % acm_proc_article-sp}

\usepackage{graphicx}
\usepackage{amsthm}
\usepackage{isolatin1}
\usepackage{charter}
\usepackage{ulem}
\usepackage{eprint}
\normalem    % Don't use underlining for \emph{..}, the default for ulem
\usepackage{epic}
\usepackage{eepicemu}
% \usepackage[numbers,sort&compress]{natbib}
% \usepackage{hypernat}
\usepackage{hyperref}
\usepackage{subfigure}
\input{macros}

\newcommand{\ifverbose}[1]{}
\newcommand{\ifnotverbose}[1]{#1}

\begin{document}
%
% --- Author Metadata here ---
%\conferenceinfo{WOODSTOCK}{'97 El Paso, Texas USA}
%\setpagenumber{50}
%\CopyrightYear{2002} % Allows default copyright year (2002) to be over-ridden - IF NEED BE.
%\crdata{0-12345-67-8/90/01}  % Allows default copyright data (X-XXXXX-XX-X/XX/XX) to be over-ridden.
% --- End of Author Metadata ---

% Platonic Libraries and the Limits of Reuse
\title{Software Libraries and Their Reuse: \\ Entropy, Kolmogorov Complexity, and Zipf's Law \titlenote{Accepted for Library-Centric Software Design (LCSD'05), an OOPSLA 2005 workshop.  \href{http://arxiv.org/abs/cs.SE/0508023}{arXiv:cs.SE/0508023}}}
% \titlenote{(Produces the permission block, copyright information and page numbering). For use with ACM\_PROC\_ARTICLE-SP.CLS V2.6SP. Supported by ACM.}}
\subtitle{[Extended Abstract]}
%
% You need the command \numberofauthors to handle the "boxing"
% and alignment of the authors under the title, and to add
% a section for authors number 4 through n.
%
% Up to the first three authors are aligned under the title;
% use the \alignauthor commands below to handle those names
% and affiliations. Add names, affiliations, addresses for
% additional authors as the argument to \additionalauthors;
% these will be set for you without further effort on your
% part as the last section in the body of your article BEFORE
% References or any Appendices.

\numberofauthors{1}
%
% You can go ahead and credit authors number 4+ here;
% their names will appear in a section called
% "Additional Authors" just before the Appendices
% (if there are any) or Bibliography (if there
% aren't)

% Put no more than the first THREE authors in the \author command
\author{
%
% The command \alignauthor (no curly braces needed) should
% precede each author name, affiliation/snail-mail address and
% e-mail address. Additionally, tag each line of
% affiliation/address with \affaddr, and tag the
%% e-mail address with \email.
\alignauthor Todd L. Veldhuizen \\
       \affaddr{Open Systems Laboratory}\\
       \affaddr{Indiana University Bloomington}\\
       \affaddr{Bloomington, IN, USA}\\
       \email{tveldhui@acm.org}
}
\maketitle
\begin{abstract}
We analyze software reuse from the perspective of information theory
and Kolmogorov complexity, assessing our ability to ``compress'' programs
by expressing them in terms of software components reused from libraries.
A common theme
in the software reuse literature is that if we can only get the right
environment in place--- the right tools, the right generalizations,
economic incentives, a ``culture of reuse'' --- then reuse of software
will soar, with consequent improvements in productivity and software
quality.  The analysis developed in this paper paints a different picture:
the extent to which software reuse can occur is an intrinsic property
of a problem domain, and better tools and culture can
have only marginal impact on reuse rates if the domain is inherently
resistant to reuse.
% That software libraries are useful is something of a paradox.  Kolmogorov
% complexity tells us almost no programs can be made shorter, and hence
% reuse of code from libraries should not be shortening programs; yet
% it is.  The paradox arises from two somewhat contradictory notions of
% compressibility: that of Kolmogorov complexity, and that of information
% theory.  Their interplay leads to some surprising results and a nice
% characterization of the role libraries play in reducing program size.
We define an entropy parameter $H \in [0,1]$ of problem domains that measures 
program diversity, and deduce from this upper bounds on code reuse and the 
scale of components with which we may work.  For ``low entropy'' domains with
$H$ near $0$, programs are highly similar to one another and
the domain is amenable 
to the Component-Based Software Engineering (CBSE) dream of programming by 
composing large-scale components.
For problem domains with $H$ near $1$, programs require substantial
quantities of new code, with only a modest proportion of
an application comprised of reused, small-scale components.
Preliminary empirical results from Unix platforms support
some of the predictions of our model.
\ignore{***
A concrete prediction arising from our analysis is that the frequencies
with which library components are reused should follow a Zipf-style law,
confirmed by empirical measurements we make of reuse rates on several
Unix platforms.
Finally, we prove an incompleteness result for domain-specific libraries,
that there are infinitely many useful software components and no finite
library can achieve optimal reductions in program size.
***}
\end{abstract}

% A category with the (minimum) three required fields
%\category{H.4}{Information Systems Applications}{Miscellaneous}
%A category including the fourth, optional field follows...
%\category{D.2.8}{Software Engineering}{Metrics}[complexity measures, performance measures]

\terms{Software Libraries, Reuse, Entropy, Information Theory, Kolmogorov
Complexity, Zipf's Law, Component-Based Software Engineering}

%\keywords{ACM proceedings, \LaTeX, text tagging} % NOT required for Proceedings

%\tableofcontents

\ignore{***
\section*{Todo}

Define $H$ to coincide with AEP.

Simplify the presentation of the distribution: define a notation for
all programs less than $s_0$ bits in size.

Citations for the use of a family of distributions (Levin).

What's going on with linux data?

Include tutorial on information theory

Cite better book on information theory.

Rework the ``size'' section derivation.

Get data on subroutine growth.

Prove the theorem for "Entropy maximization"

Does the existence of a mean program size imply $H=0$?

Write a better conclusion.  What does the analysis say about
the viability of strong reuse?

Heap's law: mention the role of software library evolution and
growth, ``effective $H$''.

Revised explanation for Zipf's law: (1) it maximizes entropy; (2)
if there was a significant departure from Zipf's law then the
entropy rate would be less than optimal, and therefore there would
be local exploitable patterns as per the Asymptotic Equipartition
Property.
***}

\section{Introduction and Overview}

\input{intro}
\input{summary}

\subsection{Organization}

The remainder of this paper is organized as follows.
\refsec{s:model} introduces an abstract model of software
reuse from which we derive our results.
In \refsec{s:background} we give a brief overview of 
Kolmogorov complexity.
In \refsec{s:reusebound} we derive bounds on the rates at
which software components may be reused, and give an account
for the appearance of Zipf-style empirical laws.
\refsec{s:reusepotential} examines the potential for software
reuse as a function of the parameter $\Hdomain$.
In \refsec{s:data} we present some preliminary experimental
results, and \refsec{s:conclusion} concludes.

\section{Modelling library reuse}
\input{model}

\section{Kolmogorov Complexity}

\label{s:background}

%\input{infotheory}
\input{kolmogorov}

\section{A bound on reuse rates}

\label{s:reusebound}
In this section we derive a bound
on the reuse rate $\lambda(n)$ at which the $n^\mathit{th}$ library component
is reused in `compressed' programs written with use of a library.

\input{coding}
\input{newderiv}

%\input{bound}
% \input{naive}
% \input{criterion}
% \input{poisson}
% \input{gaussian}

\section{Reuse potential}

\label{s:reusepotential}
In the following sections we consider the possibilities of
code reuse in two cases: (1) when $\Hdomain = 1$ and we
have a uniform distribution on programs; (2)
when $0 < \Hdomain < 1$ and we have some degree of
compressibility in the problem domain.
The case $\Hdomain=0$ is left for future work.

\input{uniform}
\input{nonuniform}
% \input{primes}
\input{size}
%\input{expectuse}
%\input{strong}
%\input{growth}

\input{data}
\input{conclusion}
%\input{compare}
%\input{related}

%\input{future}

\section{Acknowledgments}

This paper benefited immeasurably from discussions with my colleagues
at Indiana University Bloomington.  In particular I thank
Andrew Lumsdaine, Chris Mueller, Jeremy Siek, Jeremiah Willcock, 
Douglas Gregor, Matthew Liggett, Kyle Ross, and Brian Barrett for their 
valuable suggestions.  
I thank Harald Hammerstr{\"o}m for letting me disappear with
his copy of Li and Vitányi \cite{Li:1997} for most of a year.

%\setlength{\bibsep}{0in}  % {0.05in}
\bibliographystyle{plain}
\input{biblio}

\appendix
\section{Background}
\input{asymptotics}
% \section{Working notes}
% \input{notes}

\end{document}

