Lecture
The main advantage of object-oriented programming languages such as C++ and Smalltalk is the high degree of reuse in well-designed systems. This means that developing each subsequent application requires far less new code; consequently, less code has to be maintained and supported.
Reuse takes various forms: borrowing individual lines of code, individual classes, or logically related groups of classes. Reusing lines is the simplest (which programmer has not at least once used an editor to copy the implementation of some algorithm from one program into another?), but the least profitable (the very same fragment of code is simply duplicated in various applications). We do far better by using object-oriented programming languages and turning to existing classes, modifying them or inheriting from them. But still greater success can be achieved by using sets of classes organized into tool libraries - frameworks. As was already noted in Chapter 4, a framework is understood to be a collection of classes that provide a set of services in a particular domain; thus a framework exports a number of individual classes and mechanisms that clients can use directly or adapt.
Frameworks may be quite universal and applicable to a wide range of applications. This category includes general foundation classes, mathematical libraries, and graphical user interface libraries. Frameworks may also be found in quite narrow problem domains, such as, for example, hospital patient records, the textile trade, management, or telephone systems. Wherever there exists a family of programs solving similar problems, there is a reason to create an application framework.
In this chapter we will apply the object-oriented approach to creating a foundation class library. In the previous chapter our main tasks were implementing real-time control of a system and optimally dividing functional properties among several relatively autonomous and static objects. Here two different aspects will dominate: the striving for flexibility of the architecture with a wide choice of alternatives for optimizing time and memory, and the need to use common mechanisms for memory management and synchronization.
9.1. Analysis
Defining the boundaries of the problem domain
The sidebar presents the requirements for the foundation class library, formulated in detail. Unfortunately, these requirements are hardly practically achievable: a library containing the abstractions needed for all possible programs would turn out to be far too large. The analyst's first duty, therefore, is to reduce the problem domain to reasonable dimensions and to formulate a problem that is amenable to solution. The problem in the form in which it is presented now may entail the failure of the analysis as a whole, and therefore it is necessary to concentrate attention only on the most general abstractions and mechanisms suitable for wide use, rather than trying to be all things to all people (which would most likely lead to the creation of a framework that gives nobody anything). We will begin the analysis with a survey of the theory of data structures and algorithms, and then move on to the abstractions inherent in standard software.
Those interested in the theoretical foundations may be advised to turn to the fruitful work of Knuth , as well as of other researchers in this area, above all: Aho, Hopcroft and Ullman , Kernighan and Plauger , Sedgewick , Stubbs and Webre , Tenenbaum and Augenstein and Wirth . As we study the theory we will be able to identify a number of basic abstractions for our library, such as queues, stacks, and graphs, as well as algorithms for quick sorting, matching against a pattern given by a regular expression, and directed search of a tree.
The first discovery in the course of our analysis is a clear separation of structural abstractions (such as queues, stacks, and graphs) from algorithmic ones (sorting, pattern matching, and searching). The first category of concepts corresponds well to classes. The second category, at first glance, does not lend itself to object-oriented decomposition. However, with the proper approach it turns out to be entirely possible: we can introduce classes whose instances will be agents that carry out these functions. As will be seen later, objectifying algorithmic abstractions provides the advantages of generality, thanks to the fact that algorithms can be placed in a "generalization/specialization" hierarchy.
Requirements for the foundation class library
The library must contain universal data structures and algorithms capable of satisfying the needs of most standard C++ applications. In addition, the library must be:
| ® Complete | The library must contain a family of classes united by a consistent external interface but with different representations, so that developers can choose the one whose semantics most precisely matches the application. |
| ® Adaptable | All platform-dependent fragments of code must be identified and isolated in separate classes so as to make local changes to them possible. In particular, the developer must have control over the mechanisms of data storage and process synchronization. |
| ® Efficient | The procedure for connecting various fragments of the library to an application must be simple (efficiency at compile time). The overhead in RAM and processor time for servicing and linking must be reduced to a minimum (efficiency at run time). The library must ensure more reliable operation than mechanisms developed by the user by hand (efficiency during development). |
| ® Safe | Every abstraction must be type-safe, so that static assumptions about the behavior of a class can be enforced by the compiler. To detect violations of the dynamic semantics of classes, an exception mechanism must be used. Raising an exception must not corrupt the state of the object that raised the exception. |
| ® Simple | The library must have a transparent structure, giving the user the ability easily to find its fragments and connect them to an application. |
| ® Extensible | The user must be given the ability to include new classes in the library. In doing so, the architectural integrity of the framework must not be violated. |
The library must be of relatively small size; one must always remember that a user will more willingly set about developing his own code than studying someone else's barely comprehensible class.
C++ translators supporting parameterized classes and exception handling are assumed to be available. In order to ensure the portability of the library, it must not depend on operating system services.
Thus, the first result of our analysis will be the division of all abstractions into two categories:
| ® Structures | Contains all the structural abstractions. |
| ® Tools | Contains all the algorithmic abstractions. |
As we shall soon see, a using relationship exists between these two categories: some tools are built on the basis of more primitive properties provided by the structures.
At the second stage of the analysis we will try to identify the foundation classes that can be used in various standard programs (the wider the range of applications considered, the better). If it turns out as a result that some of these classes have much in common with the abstractions defined at the first stage of the analysis, this will be a sign that the key abstractions were identified correctly. One could compile a long list of specific abstractions inherent in particular kinds of human activity: currency, astronomical coordinates, units of measurement of mass and length. We will not include such abstractions in our library, since they either lend themselves too poorly to formalization (currency), or are very specific (astronomical coordinates), or are so primitive that there is no sense in organizing separate classes especially for them (units of measurement of mass and length).
Having carried out the analysis, we will identify the following types of structures:
| ® Bag | A set of various elements (including duplicates). |
| ® Set | A collection of non-repeating elements. |
| ® Collection | An indexable set of elements. |
| ® List | A sequence of elements having a beginning; structural sharing is permitted. |
| ® Stack | A sequence of elements; elements may be removed and added only at one end. |
| ® Queue | A sequence of elements to which elements may be added at one end and removed from the other. |
| ® Deque | A sequence of elements to which elements may be added and from which they may be removed at both ends. |
| ® Ring | A sequence of elements to which elements may be added and from which elements located at the top of the circular structure may be removed. |
| ® String | An indexable sequence of elements in which operations on substrings are possible. |
| ® Map | A dictionary of "element/value" pairs. |
| ® Tree | A set (having a beginning - the root of the tree) of vertices and edges that cannot form cycles or intersect; structural sharing is permitted. |
| ® Graph | A set of vertices and edges (without a distinguished initial element) that may contain cycles and intersections; structural sharing is permitted. |
As was already said in Chapter 4, ordering the abstractions presented above is a problem of classification. We chose precisely this model because it makes it possible to attach particular behavior to each category of objects.
Note the kinds of behavior that were used as criteria in dividing things into classes: some structures behave like collections (bags and sets), and others like sequences (deques and stacks). In some structures (graphs, lists, and trees) structural sharing is possible, while the rest are more monolithic and do not permit structural sharing of their elements. As we shall see later, such a classification will help in due course to shape a fairly simple architecture for the system.
For some classes, the desirability of functional variation came to light during the analysis. In particular, we may need ordered collections, deques, and queues (the latter are often called priority queues). In addition, we can distinguish directed and undirected graphs, singly linked and doubly linked lists, binary, multiway, and AVL trees [An AVL tree is a construction of a balanced binary tree proposed by G. M. Adelson-Velsky and E. M. Landis. - Ed.]. These specialized abstractions can be obtained by refining one of those listed above; they should not be singled out into separate large categories.
Despite the fact that we have already discovered signs of commonality of behavior, we will not yet occupy ourselves with working out a hierarchical structure. At the analysis stage it is important to understand the roles of each abstraction.
We will identify the following types of tools:
| ® Date/Time | Operations on dates and times. |
| ® Filters | Input, processing, and output. |
| ® Pattern matching | Operations for finding sequences within other sequences. |
| ® Searching | Operations for finding elements within structures. |
| ® Sorting | Operations for ordering structures. |
| ® Utilities | Composite operations based on the basic structural operations. |
Undoubtedly, there exists a multitude of different functional variants of these abstractions. One could, for example, single out several kinds of sorting (quicksort, bubble sort, heap sort, etc.) or of searching (sequential, binary, various ways of traversing a tree, etc.). As before, we will defer decisions regarding the inheritance of these abstractions.
Models of interaction
So, we have defined the main functional elements of our library; however, isolated abstractions by themselves are not yet a framework. As Wirfs-Brock noted: "A framework provides the user with a model of interaction between the objects of the classes it comprises... To master a framework, one must first of all study the methods of interaction and the responsibilities of its classes." This is precisely the criterion by which a framework can be distinguished from a mere set of classes: a framework is a collection of classes and mechanisms of interaction among instances of those classes.
The analysis shows that there is a definite set of basic mechanisms needed for a foundation class library:
In designing a system of foundation classes it is necessary to maintain a balance among the technical requirements listed [Indeed, as Stroustrup notes, "designing a universal library is significantly harder than designing an individual program" [10]]. If we try to solve each problem separately, then we will most likely end up with a number of isolated solutions connected to one another neither by common protocols, nor by a common concept, nor by a common implementation. Such a naive approach will lead to an abundance of different approaches that will frighten the potential user of the resulting library.
Let us take the point of view of a user of our library. What abstractions do the classes it contains represent? How do they interact with one another? How can they be adapted to the problem domain? Which classes play a key role, and which can be left unused altogether? These are the questions that must be answered before offering users a library for solving nontrivial problems. Fortunately for the user, he does not have to picture in every detail how the library works, just as one does not need to understand the principles of operation of a microprocessor in order to program in a high-level language. In both cases the lower-level implementation can be demonstrated to any user, but only if he wishes it.
Let us consider the description of the abstractions of our library from two points of view: that of the user, who merely declares objects of already existing classes, and that of the client, who constructs his own subclasses on the basis of the library ones. When designing with the first user in mind, it is desirable to restrict access to the implementations of the abstractions as strongly as possible and to concentrate on their responsibilities; designing with the needs of the second user in mind presupposes the openness of certain internal details of the implementation, though not to such a degree that it becomes possible to violate the fundamental semantics of the abstraction. Thus, one has to note a certain contradictoriness in the basic requirements for the system.
One of the main problems in working with a large library is the difficulty of understanding just which mechanisms it includes. The models listed above constitute, as it were, the soul of the library's architecture: the more a developer knows about these mechanisms, the easier it will be for him to use the components existing in the library rather than to compose his own from scratch. In practice it turns out that the user first becomes acquainted with the content and operation of the simplest classes, and only then, having verified the reliability of their operation, gradually begins to use more and more complex classes. In the course of development, as new abstractions inherent in the user's problem domain begin to take shape, they too may be added to the library. The development of an object-oriented library is a lengthy process passing through a number of intermediate stages.
This is exactly how we will build our library: first we will define that architectural minimum which implements all five of the mechanisms we have identified, and then we will begin gradually to build ever more new functions onto this skeleton.
Comments