ABSTRACT Software Libraries and Their Reuse:

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 ∈ [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