  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. 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.
