Domain-specific software libraries are becoming an increasingly common means of rapidly building software systems. Such libraries offer numerous software components that implement different algorithms from a given problem domain. For example, consider the domain of data structure algorithms (i.e., containers of objects). Examples include linked lists, arrays, trees, and hash tables. Because each of these structures could be implemented using a variety of algorithms, the domain of data structures is clearly quite large. The FSF's libg++ class library [#!lea88!#] and the C++ Booch Components [#!booch87!#] are examples of data structure software libraries.
Although software libraries offer a simple and effective means of attaining the benefits of reuse, they also expose a basic obstacle that limits the long-term success of software libraries as a reuse paradigm. The Booch Components offers numerous implementations for each basic data structure; for example, it provides 3×3×2 = 18 varieties of deques (double-ended queues)! A developer can choose a deque's algorithm for concurrency control (sequential, guarded, synchronized), memory allocation (bounded, unbounded, dynamic), and priority (ordered, unordered). Each of these feature selections is mutually independent; consequently, the implementor of the component library must laboriously enumerate every permutation of feature selections.
As the number of available features increases, the size of component libraries grows exponentially. For example, suppose a new feature were added which let a library user choose if the elements of a deque should be stored in persistent memory or transient memory; the number of deque components would then double from eighteen to thirty-six. It is apparent that as domain-specific software libraries achieve broader use, they will need to support an even broader range of features, thus aggravating this problem of feature combinatorics.
Feature combinatorics is a serious problem. Consider the following disadvantages for the library implementor:
And the following disadvantages for the library user:
This problem of feature combinatorics is not unique to data structures. Twenty-five years ago, McIlroy [#!mcilroy69!#] postulated that a well-stocked library of sine routines would likely contain as many as 300 components, supporting different degrees of precision, granularity, range, and robustness. Krueger recognized that the problem of feature combinatorics is, unfortunately, inherent to all libraries [#!krueger92!#]. Clearly, we must find a means of populating libraries of software components which is scalable with respect to the number of features offered by the library.