Lecture
"Follow the example set by computer hardware design! It is wrong that every new piece of software development should start from a blank sheet of paper. There ought to be catalogs of software modules, just as there are catalogs of VLSI devices (very large-scale integrated circuits). When building a new system, we should order components from these catalogs and assemble the system out of them, rather than reinventing the wheel every time. By writing fewer new programs, we might find a better use for our efforts. And perhaps some of the difficulties everyone complains about — high costs, insufficient reliability — would disappear. Isn't that so?"
You have probably heard, or even made, remarks of this kind yourself. Back in 1968, at the well-known NATO conference on software engineering problems, Doug McIlroy advocated the idea of "mass production of software components." Thus the dream of reusing software components is nothing new. It would be absurd to deny that reuse already occurs in programming. In fact, one of the most striking results of the development of the software industry since the first edition of this book appeared in 1988 has been the gradual emergence of reusable components. They have become increasingly widespread, ranging from small modules meant for use with Microsoft's Visual Basic (VBX) and OLE 2 (OCX, and now ActiveX), all the way up to extensive class libraries, also known as "framework applications."
Another remarkable achievement is the growth of the Internet: the arrival of a wired society has eased, or in a number of cases removed, some of the logical obstacles that seemed almost insurmountable just a few years ago. But this is only the beginning. We are still far from McIlroy's vision of software engineering turning into an industry built on the use of software components. However, the object-oriented software construction methodology has, for the first time, made it possible to imagine a practical realization of this vision. And this can bring considerable benefit not only to software developers but, more importantly still, to those who need their products to arrive on time and at high quality.
First of all, one must understand why it is so important to improve software reuse capabilities. There is no need here to resort to arguments along the lines of "motherhood and apple pie." As we shall see, our struggle for reuse pursues proper goals, will help us avoid mirages, and will yield a good return on the corresponding investment.
Reuse can bring progress along the following lines:
[x]. Timeliness (in the sense defined when discussing quality factors: speed in bringing projects to completion and products to market). When existing components are used, less needs to be developed, and so the software is produced faster.
[x]. Decreased maintenance effort. If someone developed a piece of software, that same person is also responsible for its subsequent evolution. There is a well-known paradox of the competent software developer: "the more you work, the more work you create for yourself." Satisfied users of your product will start asking for new features and for ports to new platforms. Short of relying on "someone else," the only way out of the paradox is to become an incompetent developer, so that no one is interested in your product anymore. This book does not encourage that solution.
[x]. Reliability. When you obtain components from a vendor with a good reputation, you have a certain guarantee that the developers have taken all the necessary measures, including thorough testing and other quality-control methods. In most cases you can expect that someone has already exercised these components before you and found any errors that might have remained. Note that this does not at all imply that the component developers are smarter than you. For them, the components being built — whether graphics modules, database interfaces, or sorting algorithms — are a professional duty, the very goal of their work. For you, they are merely a secondary, routine matter, since your goal is to build some application system in your own field of activity.
[x]. Efficiency. The factors that favor software reuse push component developers to use the best algorithms and data structures known in their specific field. However, in a team developing a large application project, it is hard to expect specialists to be on hand for every problem touched on by the project. When building a large project, it is impossible to optimize every one of its details. One should strive for the best solutions in one's own area of expertise, and for everything else rely on professional work.
[x]. Consistency. If a good, modern OO library is used, its style will, through a natural "diffusion process," influence the style of the entire piece of software being developed. This substantially helps to improve the quality of the software product.
[x]. Investment. Building reusable software makes it possible to preserve the fruits of the knowledge and discoveries of the best developers, turning a temporary resource into a permanent one.
Many of those who acknowledge that reuse is desirable have in mind only the first of the factors in this list — increased productivity. But this is not always the most important contribution that reuse makes to the software development process. Increased reliability, for example, is no less significant a factor. The same can be said of efficiency.
In this respect, reuse can be regarded as a special indicator, distinct from the other factors discussed in Lecture 1. Improving it makes it possible to improve almost all the other software quality factors. And the reason is purely economic: if a piece of software serves not one but many projects, it is economically sound to use the best methods for producing high-quality software — formal verification, thorough optimization. In ordinary development, such techniques are often dismissed as an unnecessary luxury. For reusable components, however, the reasoning changes substantially — improving just a single element can pay off for thousands of projects.
Of course, these considerations are not entirely new — they are, in part, a transfer to software production of ideas that have already substantially affected other fields of activity when they moved from individually crafted products to mass-production industry. Manufacturing a VLSI chip costs far more than the series production of a simple special-purpose circuit, but if it is well made, it will prove itself in countless computer systems and improve their quality thanks to all the work invested once and for all by its designers.
In the list of benefits given above, two situations can be distinguished — the use of professional components or of one's own. The first four items in the list describe the situation of using existing, professionally developed components. The last item in the list characterizes the reuse of one's own software product. The item concerning consistency applies to both cases.
This distinction between the two kinds of merit reflects two aspects of reuse: the point of view of the consumer, who makes use of the products of component developers, and the point of view of the producer, who provides the ability for his own work to be reused.
Software developers who do not yet have much experience should be consumers of components. It is essentially impossible to start out right away as a producer of reusable software. The only possible path to becoming a producer is to study and copy already existing good examples. Such an approach will immediately bear useful fruit, since in your own work you will make use of the merits of these components.
The Road to Reuse
Become a consumer of reuse before trying to become a producer of it.
Having convinced yourself that Reuse Is Good, it remains to find out how to achieve it.
The first question that arises is at what level reuse should be carried out: of personnel, of specifications, of designs, of design patterns, of source code, of components, or of abstract modules.
The simplest thing to reuse is developers, and this is widely practiced in industry. By moving software developers from one project to another, companies avoid losing the experience they have accumulated and ensure that it is put to worthy use in new projects.
Given the high turnover of programming staff, the possibilities of this approach are limited.
This approach is, in essence, a more organized version of the previous one — the reuse of knowledge, skills and experience. As the discussion of documentation showed, the very notion of treating a design as an independent software product, with its own life cycle independent of the corresponding implementation, seems questionable, since it is hard to guarantee that the design and its implementation will remain consistent as the software system changes.
Thus, if only the design is reused, there is a risk of reusing elements that work incorrectly or have already fallen out of use.
These remarks also apply to another, related kind of reuse: the reuse of specifications.
Among software developers there was for a long time a belief that only the reuse of designs and specifications was truly worth attention. This idea stood substantially in the way of progress, since it meant that building components was aimed only at satisfying minor needs and did not solve the truly hard problems. This view used to be the prevailing one; it was overcome through the combined effect of theoretical arguments (considerations from OO technology) and practical achievements (the successful implementation of reusable components).
The term "overcome" is perhaps too strong here, since, as often happens in such debates, both sides contributed their share to reaching a useful outcome. The idea of design reuse becomes far more interesting when one adopts an approach (such as the view of OO technology developed in this book) that substantially eliminates the gap between a design and its implementation. Then the difference between a module and the design for a module is not one of principle but merely of degree: the design of a module is simply a module whose individual fragments have not yet been fully implemented, while a fully implemented module can, thanks to abstract representation facilities, be used as the design of a module. With this approach, the distinction between module reuse (discussed below) and design reuse gradually disappears.
In the mid-1990s, specialists were drawn to the idea of design patterns. A pattern is an architectural principle applicable in many application domains; by following a pattern one can construct a solution to some problem. (A design pattern involving a history of commands is discussed in the course "Fundamentals of Object-Oriented Design.")
Here is a typical example, discussed in detail in one of the following lectures. The problem: how to equip an interactive system with a mechanism allowing its users to undo a previously executed command if they decide it was inappropriate, and to redo the undone command if they change their minds. The pattern: use a COMMAND class of a certain structure (which we will examine later) together with an associated "history list." Many other design patterns will be examined as well.
One of the reasons the idea of the design pattern was successfully adopted was that it was not merely an idea: the book4.1), in which this notion was first proposed, and the editions that followed it, contained a catalog of directly applicable patterns that readers could study and use.
Design patterns have already made a substantial contribution to the development of OO technology, and as more and more new patterns are published they will help developers draw on the experience of their predecessors and contemporaries. How, then, should this general principle be applied to the problem of reuse? Design patterns should not encourage a return to the idea, mentioned earlier, that "all one needs is to reuse designs." A pattern, which is essentially nothing more than a book pattern — however excellent and universal — is only a "teaching aid," not a reuse tool. After all, for the last three decades, computer science textbooks have discussed the optimization of relational databases, AVL trees (the balanced trees of Adelson-Velsky and Landis), Hoare's Quicksort algorithm, and Dijkstra's algorithm for finding the shortest path in a graph, without ever mentioning that these methods achieved a breakthrough in solving the reuse problem. In a certain sense, the patterns developed over the last few years are just further additions to the set of standard techniques used by software development specialists. Understood this way, the new contribution to OO technology should be credited not to the idea of the pattern itself, but to the specific patterns being proposed.
A thorough examination of the pattern problem shows that this view turns out to be overly narrow (see "Programs with holes"). It appears that the very notion of a pattern is indeed a genuinely new contribution, even if this is not yet fully recognized. But further work is needed on patterns to move them beyond their purely pedagogical value. A successful pattern cannot be represented merely by some textual description — it must be a software component, or a set of such components. At first glance, this goal may seem rather distant, since many patterns are so universal and abstract that it seems impossible to implement them as program modules.
But the use of OO technology makes a radical contribution here — it makes it possible to build reusable modules that have the ability to change. They will not be "frozen" elements, but will serve as general schemes, as patterns — here the term pattern is genuinely appropriate in the fullest sense of the word — capable of being adapted to various specific situations. We call this new notion a behavior class (the more figurative term is programs with holes). This notion, based on the notion of the deferred (abstract) class, will be examined in later lectures. Combining it with the idea of a group of components meant to work together — often called frameworks, or simply libraries — yields a remarkable tool that combines reuse with the capacity for adaptation.
Despite the usefulness of reusing personnel, designs, and specifications, this does not achieve the key goal of reuse. If we wanted to find the programming equivalent of reusable parts from other engineering disciplines, this would mean having to reuse the "stuff" our software products are actually made of: executable programs.
If so, in what form should they be reused? The natural answer is: in their original form, as source text. In some cases this approach has proved quite effective. For example, the improvement of the Unix operating system, originally distributed to universities and research laboratories, became possible largely thanks to the availability of source code accessible online. This allowed users to study, copy, and extend the system's range of uses. The same holds for the community of Lisp users.
There are economic and psychological obstacles to the distribution of source code. The more serious limitations are:
[x]. Identifying reusable software with reusable source text rules out the possibility of information hiding. It should be kept in mind that reuse of genuinely large projects is impossible unless a systematic effort is made to shield reusers from having to know countless details.
[x]. In complex systems, many of the parts may depend on others in non-obvious ways. This often makes it hard to reuse individual elements, forcing everything else to be reused as well.
A form of reuse that satisfies the requirements of modularity must remove these limitations by supporting abstraction and providing a "fine-grained" implementation of reuse.
All the preceding approaches, despite their limited applicability, have shed light on important aspects of the reuse problem:
[x]. Reuse of personnel is necessary but not sufficient. The best reusable components are useless in the absence of well-trained developers who have enough experience to recognize a situation in which the use of existing components can help.
[x]. Design reuse requires not only ready-made solutions to specific problems, but also a sufficiently high conceptual level and generality of the reusable components. The classes we will encounter when discussing OO technology can be viewed both as design modules and as implementation modules.
[x]. The possibility of reusing source code serves as a reminder that software is ultimately defined by program texts. A sound reuse policy must lead to the creation of reusable software elements.
This discussion has made it possible to narrow the search for suitable units of reuse. Such a unit must be a software element (or collection of elements). It must be a module of acceptable size, satisfying the modularity requirements from the previous lecture. In particular, its dependencies must be strictly limited, in order to make independent reuse easier. The information characterizing a module's capabilities, which forms the primary documentation for the programmers who reuse it (reusers), must be abstract: in keeping with the Information Hiding principle, it must cover only the properties that matter to clients, rather than describing all of the module's details (as is done in the source code).
The term abstract module will be used for reusable units that are part of directly applied software, and access to which from the outside world can take place through a description containing only a subset of each unit's properties.
Lectures 3–6 of this course go on to propose a rigorous definition of such abstract modules; their properties will then be examined in lectures 7–18.
| The emphasis on the notion of abstraction, and the rejection of source code as the means for reuse, does not at all stand in the way of distributing modules in source form. The contradiction here is only apparent: this discussion is not about how modules will be delivered to the programmers who reuse them, but about what they will use as the primary source of information about the modules. It may well be acceptable for a module to be distributed as source text, yet be reused on the basis of an abstract description of its interface. |
In the search for the ideal abstract module, one should consider the essence of the software construction process. Watching development at work, one cannot help but notice the periodically recurring actions in this process. Again and again, programmers "weave" a program out of a host of standard elements: sorting, searching, reading, writing, comparing, tree traversal — it all repeats. Experienced developers are familiar with this sense of de_ja vu (deja vu — the feeling that the present has already been encountered in the past), so characteristic of their profession.
To gauge this situation (for those who develop software or manage such development), it is useful to answer the following question:
How many times over the last six months have you, or those who work for you, developed some variant of table lookup?
| Table lookup is understood here as determining whether a given element x is contained in a table t. This task has many variants depending on the type of the elements, the data structure representing t, and the search algorithm chosen. |
It is quite possible that you or your colleagues have repeatedly searched for and found your own solution to this problem. An outside observer would consider table lookup an easily accessible and obvious candidate for the application of reusable components. After all, it is one of the most extensively studied areas in computer science, the subject of hundreds of papers and many books, starting with volume 3 of Knuth's famous treatise. The basic university computer science course at every relevant department covers the most important algorithms and data structures. There is undoubtedly nothing incomprehensible about this subject. Furthermore:
[x]. As already noted, it is hardly possible to build a useful piece of software that does not contain some form of table lookup.
[x]. As will be shown in more detail below, most search algorithms follow a common pattern, which apparently provides an ideal basis for a reusable solution. (See the bibliographical references at the end of this lecture.)
Why, then, is reuse still not universally accepted?
The most serious obstacles to it are technical ones; ways of overcoming them will be discussed in later sections of this lecture (as well as in the rest of the course's lectures). But there are, of course, also some organizational, economic, and political obstacles.
A psychological obstacle to reuse is a well-known syndrome: "Not Invented Here" (or "NIH"). Software developers are said to be individualists who prefer to do everything themselves rather than rely on someone else's work.
But in practice this is not borne out. Software developers are no more prone to pointless work than other specialists. If a good, widely known, and easily accessible reusable solution exists, it will be used.
Consider the typical case of lexical and syntactic analysis. It is far simpler to build a parsing program for a command language or a simple programming language using parser generators — for example, the well-known Lex-Yacc combination — than to build everything from scratch. The conclusion is obvious: wherever tools exist, competent software developers make widespread use of them.
In some cases it does make sense to build one's own custom parser, since the tools mentioned above have their own limitations. But usually developers prefer to turn to one of these tools. This can lead to a new syndrome, the opposite of NIH, which might be called the "Habit Inhibiting Novelty" syndrome (or "HIN"). A reusable solution, however useful, that has limitations narrowing developers' options and stifling the adoption of new ideas becomes useless. Try convincing one of the Unix developers to use a parser generator other than Yacc, and you may experience the HIN syndrome firsthand.
Of course, there is something that resembles NIH, but often this is simply the entirely understandable reaction of cautious developers to new and unfamiliar components. They may fear that bugs or other problems in a program that is new to them will be harder to deal with than a solution over which they have full control. Such fears are often justified by earlier unsuccessful attempts at component reuse. But if the new components are of high quality and ensure the program works properly, such fears quickly disappear.
Thus, ensuring high quality when building reusable components is substantially more important than for other kinds of software.
Let N denote the cost of a unique solution, and R the cost of a solution based on reusable components. The value of R will never be zero: it will include training costs, the cost of integrating the components into the system, and the need to build a calling interface. So even if the savings from reuse and other benefits
r=(N - R)/ N
from reuse are potentially small, it will still be necessary to convince prospective "reusers" that, for the sake of the high quality of the reusable solution, it is worth giving up the desire for full control over every element of the system.
| This explains why it is a mistaken goal for a company's policy to focus on working with prospective reusers (or "consumers," as developers call them). Instead, one should tighten the requirements placed on the producers of external components, demanding guarantees of the quality and suitability of the products they offer. Developers of application systems will use your components not because of your recommendations, but because you worked hard to make it worthwhile to use reusable components in application programs. |
A software company is always tempted to build solutions that deliberately fail to meet the criteria for reuse, out of fear of not getting the next order — since if the capabilities of a solution already purchased turn out to be too broad, the customer won't need a follow-up order!
I happened to hear an extremely candid remark on this subject after one of my lectures on reuse and OO technology.
A senior manager from a large software supply company told me that although he recognized the great value of these ideas, he would never introduce them at his company, because he did not want to kill the goose that lays the golden eggs. More than 90% of his company's revenue comes from "renting out" personnel, providing customers with the services of its analysts and programmers, and the company's management is trying to push that figure to 100%. With such an attitude toward software development, the prospect of publicly available libraries of reusable components is unlikely to be met with enthusiasm.
This remark was notable for its candor, but it provoked an obvious objection: if it is at all possible to build reusable components that would replace some of the expensive consulting services offered by a software supply company, then sooner or later someone will build them. And then a company that refused to go down that road, and that has nothing left but the trade in its consultants' services, may come to regret having, like a frightened ostrich, buried its head in the sand.
The engineering part of software development is not identical to the corresponding part in mass-production industry; the human factor will probably continue to play a key role in the software construction process.
The goal of reuse is not to replace people with tools (which, despite all sorts of claims, often does happen in other industries), but to change the balance between what should be entrusted to people and what to tools. So for a company that has built its reputation on its consultants, these innovations are not so bad after all. In particular:
[x]. In many cases, developers who use reusable components can still successfully draw on the help of specialists who advise them on the best way to apply these components. This preserves a substantial role for software supply companies and their consultants.
[x]. As will be shown below, the ability to reuse is inseparable from extendibility: good reusable components will remain open to adaptation to specific circumstances. The consultants of the company that developed the corresponding program library are in an ideal position to customize the components for individual customers. So selling components and selling services are not necessarily mutually exclusive activities; trading in components can serve as a basis for trading in services.
[x]. A good reusable library can play a strategic role in the policy of a successful software company, even if the company sells solutions rather than the library itself, using it only for internal purposes. Such a library can give the company a competitive advantage in developing custom solutions that meet customer requirements faster and more cheaply than could be done by competitors who do not have such a ready-made foundation to build on.
Here is what the skeptics say: progress in producing reusable software will result in developers being "buried" under such a large number of components, and this will complicate their lives so much, that it would have been better if these components did not exist at all.
This remark should be viewed as a warning to developers of reusable software that the best reusable components in the world are useless if no one knows they exist, or if obtaining them takes too much time and effort. For reuse methods to succeed in practice, appropriate databases of components must be built, allowing a query to quickly determine whether any existing component satisfies the required needs.
Network services must also be available, allowing the ordering and immediate network delivery of the selected components.
Achieving these goals requires solving technical and organizational problems. Indexing, searching for, and delivering reusable components are technical problems that can be solved with well-known tools, in particular methods based on the use of databases. Clearly, handling software components is no harder than handling customer data, airline flight information, or library books.
With the creation of the World Wide Web, powerful search tools appeared that make it far easier to publish and find useful information, whether on the Internet or on a corporate network (an Intranet). Undoubtedly, even better solutions will appear (perhaps obtained with the help of OO technology). From all this it becomes clear that the main difficulty in implementing reuse is not organizing the use of reusable components, but, first and foremost, building these blasted things in the first place.
At the intersection of technical and organizational problems, a question arises: how should indexing information, such as keywords, be linked to software components?
The Self-Documentation principle states that all information about a module, including indexing information and other kinds of documentation, must be contained within the module itself. This important requirement has been taken into account in the design of the class notation developed in lectures 7–18 of this course. The mechanism provides for the ability to attach indexing data to each component.
Describing the corresponding syntactic structure presents no difficulty. At the beginning of the module's text, it is suggested that an indexing clause be written in the form
Indexing
index_word1: value, value, value ...
index_word2: value, value, value ...
...
... Standard description of the module (see lectures 7–18) ...
Here, each index_word (that is, an index word) is an identifier; each value is a constant (integer, real, etc.), an identifier, or some other standard lexical element. (For more detail, see "Indexing clauses" in the course "Fundamentals of Object-Oriented Design.")
There are no specific restrictions on the choice of index words and their corresponding values, but any industry, standards group, organization, or project team may, if needed, define its own rules. Indexing and search tools can then extract this information to help software developers find components that satisfy particular criteria.
As the discussion of the Self-Documentation problem showed, keeping such information within the module itself — rather than in an external document or database — reduces the likelihood of entering false information and, in particular, will not let one forget to update the information when the module is modified (or vice versa). Indexing clauses, seemingly quite simple at first glance, significantly help developers put their software components in order and record their properties so that other developers can learn about them.
Another issue spanning both technical and organizational concerns is the choice of representation for distribution: source text or binary format? This is a contentious question, and we will limit ourselves to considering just a few arguments from both sides.
Developers of commercial software often distribute only the interface description (the corresponding short form is discussed in one of the following lectures) and the executable code. In doing so, developers protect trade secrets and their investments. ("Using Assertions for Documentation: The Short Form of a Class", )
Binary code is indeed the preferred form of distribution for commercial applications, operating systems, and other tools, including compilers, interpreters, and development environments for OO languages. Despite ongoing attacks on this concept, coming in particular from the group calling itself the League for Programming Freedom, it is unlikely that this method of distributing commercial software will be abandoned any time soon. But our discussion does not concern ordinary tools or applications: here we are considering libraries of reusable components. In this case as well, some arguments can be found in favor of distributing source text.
For the maker of a software component, the benefit of distributing the source text is that it makes porting efforts easier. One can avoid the tedious and low-return work of adapting software to the multitude of incompatible platforms that exist in today's computing world, relying on the developers of OO compilers and program environments to do that work for you. (For the consumer, this is of course a counterargument, since installing source text is more labor-intensive and can lead to unforeseen errors.)
Perhaps a more important argument in favor of distributing the source text is that attempts to protect one's inventions and trade secrets by removing the source text from the implementation of a software product may bring no significant benefit. The most labor-intensive work in composing a good reusable library relates to the design of component interfaces, not to their implementation; and it is precisely this that you are forced to publish. This is especially evident in the world of data structures and algorithms, for which almost all of the necessary methods are described in the computer science literature. To successfully build a library, you need to embed these methods into modules whose interface will make them useful to developers of many other applications. Such interface design is part of what you must release to the world.
It is important to note that in the case of OO modules there are two forms of component reuse: by clients of the class and by heirs of the class. The second of these forms combines reuse with extendibility. Interface descriptions (short form) are sufficient for clients, but not always sufficient for reuse based on inheritance.
Finally, a word about the pedagogical side of the issue. Distributing the source text of library modules is a means of presenting the best examples of software development, encouraging software consumers to develop in the corresponding style. The standardization that results from this is one of the merits of reuse. To some extent this will hold even when only interfaces are available, but it is best to have the full text. (This question is discussed in the lecture devoted to teaching OO technology, in the course "Foundations of Object-Oriented Design".)
| Note that even when source code is available, it should not serve as the primary means of documentation: the module interface will still be used for that purpose. |
This discussion has touched on some controversial economic issues, arising in part from the emergence of industrial production of software components and, more generally, from progress in the field of software. How can developers be fairly rewarded for their achievements and their inventions given an acceptable degree of protection, without infringing on the legitimate interests of users? There are two opposing points of view:
[x]. On one hand, there are the principles of the League for Programming Freedom: all software should be free and available in the form of source text. (See the bibliographical notes.)
[x]. On the other hand, there is the idea of superdistribution, proposed by Brad Cox in several articles and a book. Superdistribution is meant to let users freely copy programs while paying not for acquiring them but for each use. Imagine a small counter attached to every software component, which "rings up" a sum of a few pennies every time you use that component, and at the end of each month presents you with the corresponding bill. This apparently rules out distributing source text, since it would then be very easy to remove the counter's instructions from the program. The Japanese Electronic Industry Development Association (JEIDA) is working on mechanisms for creating the technical and software computer tools to support this concept. Cox himself recently emphasized the special role not so much of technological methods as of enforcement mechanisms based on the corresponding legal norms (similar to copyright). For now, the idea of superdistribution raises numerous technical, economic, and psychological questions.
Any comprehensive approach to the problems of reuse should, alongside the technical aspects, consider organizational and economic issues: how to make reuse part of the culture of software development, how to find the right cost structure and the right form of component distribution, and how to create appropriate tools for indexing and searching for components. It is not surprising that these issues have underlain the major reuse initiatives launched by governments and large corporations, such as the STARS program (Software Technology for Adaptable, Reliable Systems) of the U.S. Department of Defense, and the "software factories" put into operation by several large Japanese firms.
While important in the long run, these issues should not divert attention from the main problems, which remain technical in nature. Successfully realizing the possibilities of reuse requires creating proper modular structures and high-quality libraries containing the tens of thousands of components that the industry needs.
The remainder of this lecture is devoted to the first of these questions. It explains why the commonly accepted notions of a module are unsuitable for large-scale reuse, and it sets out the requirements that a better solution, proposed in the following lectures, must satisfy.
What, then, should a reusable module look like?
Software development, as already mentioned, is largely bound up with repetition. To understand the technical difficulty of reuse, one must understand the nature of repetition.
Although programmers usually repeat the same actions from time to time, these actions are not quite identical. Indeed, if they were identical, the solution would be simple, at least on paper. In practice, however, so many details of the task may change that any naive attempt to unify it will fail.
| A vivid illustration is the work of the Norwegian painter Edvard Munch, much of which can be seen in the museum dedicated to him in Oslo, the birthplace of the Simula programming language. Munch's art was dominated by a handful of vital, profound themes: love, suffering, jealousy, dance, death. He reproduced them endlessly in his drawings and paintings, using the same models each time but varying the technique, the colors, the sharpness of the contours, the size, the lighting, the mood. |
A software developer is in the same position, creating new variants that develop the same basic themes.
Take the example mentioned at the beginning of this lecture: table searching. There is no doubt that the general form of a table-searching algorithm always looks the same: start at some position in table t, then proceed to scan the table sequentially, each time checking whether the element at the current position is the one sought and, if not, moving on to the next position. The process ends either when the desired element is found or when checking all the elements has proved unsuccessful. This general scheme applies to many possible representations of data and algorithms for table searching, including arrays (sorted or unsorted), linked lists (sorted or unsorted), sequential files, binary trees, B-trees, and various hash tables.
It is not hard to turn this informal description into a partially detailed routine:
has (t: TABLE, x: ELEMENT): BOOLEAN is -- Is x present in t? local pos: POSITION do from pos := INITIAL_POSITION (x, t) until EXHAUSTED (pos, t) or else FOUND (pos, x, t) loop pos := NEXT (pos, x, t) end Result := not EXHAUSTED (pos, t) end
A few clarifications about the notation used here: from ... until ... loop ... end describes a loop, with an initial condition in the from clause, executing the actions of the loop clause zero or more times, and terminating when the condition of the until clause is satisfied. The variable Result holds the value returned by the function has. If you are not familiar with the or else operator (the or else operator is explained in ), just treat it as a plain logical or.
Although the text above describes the general scheme of how the algorithm works, it is not directly executable, since it contains some not-fully-defined fragments (written in capital letters). These correspond to aspects of the table-searching problem that depend on the chosen implementation: the type of the table elements (ELEMENT), which position to start the search from (INITIAL_POSITION), how to move from the current position to the next (NEXT), how to check whether the sought element is present at a given position (FOUND), and how to determine that all the positions of interest have already been checked (EXHAUSTED).
The text above is therefore not so much a routine as a routine template, which can be turned into a working routine only after the fragments written in capital letters have been made precise.
The existence of all these variants brings to the fore the problems that arise in any attempt to think about creating general-purpose modules in a given application domain: how can the existence of a single template be used to accommodate such a large number of different variants? This is not only an implementation problem: it is almost as hard to specify a module in such a way that client modules can rely on interacting with it without having access to its implementation.
For these reasons, simple solutions to the reuse problem are doomed to fail. Because of the many-sidedness and changeability of software — it is not for nothing that it is called "soft" — modules that lack "flexibility" cannot lay claim to reusability.
The "frozenness" of a module leads to the reuse-redo dilemma: reuse the module as it is, or redo everything from scratch. Both approaches are too restrictive. A typical situation is one where a module exists that provides only a partial solution to the task at hand, and the module needs to be adapted to specific needs. In this case it is desirable both to reuse and to redo: to reuse some part and redo another part — or, best of all, to reuse a great deal and redo very little. Without the ability to combine the possibilities of reuse and adaptation, reuse techniques cannot satisfy the practical needs of software development.
It is therefore no accident that almost every discussion of reuse problems in this book also touches on the problem of extendibility (leading to the term "modularity," which covers both notions and was the subject of discussion in the previous lecture). Whenever you start looking for answers to one of these requirements, you will immediately run into the other requirement as well.
This interdependence between reuse and extendibility was noted earlier in the discussion of the Open-Closed principle. (See "The Open-Closed Principle", )
The remainder of this lecture and several of the following lectures are devoted to the search for a suitable module representation. We will need to reconcile reusability and extendibility, closedness and openness, persistence and changeability. We need to satisfy today's needs while trying to guess what will be needed tomorrow.
How, then, can we find modular structures that will allow us to create components that are directly ready for reuse, while at the same time allowing them to be adapted?
The table-searching problem and the has routine template illustrate the strict requirements placed on any solution. This example can be used to work out what must be done to move from detecting a relatively vague commonality among variants to an actual set of reusable modules. Such an analysis reveals five important issues:
[x]. Type Variation.
[x]. Routine Grouping.
[x]. Implementation Variation.
[x]. Representation Independence.
[x]. Factoring Out Common Behaviors.
The has routine template assumes that the table contains objects of type ELEMENT. When refining this routine for a particular case, one can use a specific type, such as INTEGER or BANK_ACCOUNT, for a table of integers or bank accounts.
But that is not quite what is needed. A reusable search module must be applicable to many different element types without forcing users to make changes to the program text "by hand." In other words, we need a means of describing modules in which types act as parameters (type-parameterized), or, more briefly, generic (polymorphic) modules. Genericity (the ability of modules to be generic) will turn out to be an important part of the OO method; an overview of this concept is given later in this lecture. (See "Genericity", )
The has routine template, even if fully detailed and given type parameterization, will still not be suitable as a reusable component. Searching a table depends on how the table was created, how elements are inserted into it, and how they are removed from it. A search routine taken on its own is not yet a reuse module. A self-contained, reusable module must include a set of routines providing each of the operations mentioned — creation, insertion, removal, search.
This idea underlies the formation of a module as a "package," as found in languages with encapsulation such as Ada, Modula-2, and related languages. More will be said about this below.
The has template is quite general; and, as we have already seen, there is in practice a wide choice of corresponding data structures and algorithms. One cannot expect a single module to handle such a variety of conditions — it would simply be enormous. Covering all the possible implementations requires a family of modules.
The general methodology for creating and applying reusable modules must support the idea of a family of modules.
The general structure of a reusable module must allow client modules to define their actions in the absence of any knowledge of the module's implementation. This requirement is called Representation Independence.
Suppose that a client module C of some application system (bank asset management, a compiler, a geographic information system) needs to determine whether a certain element x is contained in a certain table t (of deposits, of words of a language, of cities). Representation Independence for C means the ability to obtain this information through a call to the routine
present := has (t, x)
without knowing what form the table t takes at the time of this call. The author of module C only needs to know that t is a table of elements of a certain type, and that x denotes an object of the same type. It makes no difference to C whether t is a binary search tree, a hash table, or a linked list. C should be able to focus on its own task of asset management, compilation, or geography.
Choosing the appropriate search algorithm, based on the implementation of the table t, is the concern solely of the module that organizes that table.
The client module C, containing the routine call mentioned above, might obtain t from one of its own clients (as an argument of the routine call). In that case, for C the name t is merely an abstract identifier of a data structure whose detailed description C cannot access.
Representation Independence can be viewed as an extension of the Information Hiding (encapsulation) rule, essential for the smooth development of large systems: implementation decisions can often change, and clients must be protected from that (See "Information Hiding", ). But the Representation Independence requirement goes even further. Taken to its full extent, it means protecting a module's clients from changes not only over the lifetime of the project, but also at run time — a much shorter time span! In the example under discussion, it is desirable for the has routine to adapt automatically to the form of the table t at run time, even if that form has changed since the last call to the routine.
Satisfying the Representation Independence requirement will also help implement the related Single Choice principle, formulated during the discussion of modularity, which directs us to avoid situations involving case analysis such as
if "t is a hash-managed array" then "Apply hash-based search" elseif "t is a binary search tree" then "Apply binary search tree traversal" elseif (etc.) end
It would be equally inconvenient to have such a structure inside the module itself (one cannot expect a module that organizes a table to know about all current and future variants) as to reproduce it in every client module. (See "Single Choice", ) The solution is to provide an automatic choice, made by the runtime system. That will be the role of dynamic binding, a key component of the OO approach, which will be examined in detail when we discuss inheritance. (See "Dynamic Binding", )
If the Representation Independence requirement reflects the client's position — ignoring internal details and implementation variants — then the last requirement reflects the position of the developers of reusable classes. Their goal is to take advantage of any commonality that may exist within a family or subfamily of implementations.
The variety of implementations found in some problem domains requires, as already noted, a solution based on a family of modules. Often this family is so large that it is natural to look for corresponding subfamilies. In the case of table searching, a first attempt at classification might lead to three broad subfamilies:
[x]. Tables organized according to some hashing scheme.
[x]. Tables organized as some kind of tree.
[x]. Tables organized sequentially.
Each of these categories covers many variants, but in most cases significant commonality can be found among these variants. Consider, for example, the family of sequential implementations — those in which elements are stored and retrieved in the order of their original insertion into the table.
Figure 4.1. Some possible implementations of a table
Possible representations of a sequential table are an array, a linked list, and a file. But regardless of the particular implementation chosen, clients should be able, for any sequentially organized table, to examine its elements one by one, moving an (imaginary) cursor that indicates the position of the element currently under consideration. With this approach, the search routine for sequential tables can be rewritten as:
has (t: SEQUENTIAL_TABLE; x: ELEMENT): BOOLEAN is -- Is x contained in the sequential table t? do from start until after or else found (x) loop forth end Result := not after end
This representation is based on the use of four routines that must be present in any sequential implementation of a table (The technique of working with a cursor will be examined in detail in the course "Foundations of Object-Oriented Design," "Active Data Structures". ):
[x]. start, move the cursor to the first element, if there is one.
[x]. forth, move the cursor to the next position.
[x]. after, a boolean query, has the cursor moved past the last element.
[x]. found (x), a boolean query returning true when the cursor points to an element with value x.
Figure 4.2. A sequential structure with a cursor
Despite its resemblance to the routine template used at the beginning of this discussion, the new text is no longer a template — it is an actual routine, written in a directly executable notation (this notation is used in lectures 7-18 of this course). Given implementations of the four operations start, forth, after, and found, this latest version of has can be compiled and executed.
Each representation of a sequential table requires a corresponding representation of the cursor. Three examples of such representations are based on working with an array, a linked list, and a file.
In the first of these, an array of capacity elements is used, and the table occupies positions from 1 to count + 1. (The last value is needed for the case where the cursor has moved to the position after ("after") the last element.)
Figure 4.3. An array-based representation of a sequential table with a cursor
In the second representation, a linked list is used, in which access to the first element is provided by the reference first_cell, and each element is linked to the next by the reference right. Here the cursor can be represented by the reference cursor.
Figure 4.4. A linked-list-based representation of a sequential table with a cursor
In the third representation, a sequential file is used, in which the cursor simply represents the current read position.
Figure 4.5. A sequential-file-based representation of a sequential table with a cursor
The implementation of the operations start, forth, after, and found will differ for each of the variants. The following table (4.3) shows the implementation for each case. Here t @ i denotes the i-th element of array t, written as t [i] in Pascal or C; Void denotes an "empty" reference; the notation f^, from Pascal, for a file f, denotes the element at the current read position of the file.
| start | forth | after | found (x) | |
| Array | i :=1 | i :=i + 1 | i >count | t @ i =x |
| Linked list | c := first_cell | c :=c. right | c =Void | c. item =x |
| File | rewind | read | end_of_file | f -=x |
Table 4.1. Classes and Methods
Reuse makes it possible to avoid unnecessary duplication by exploiting the commonality among variants. If identical or nearly identical fragments appear in different modules, it becomes difficult to maintain their integrity and to guarantee that changes or corrections reach every place in the system where they are required. Problems with system configuration management can then arise once again.
All variants of the sequential table share the function has, and differ only in the implementation of the operations. A good solution to the reuse problem requires that, in such a situation, the text of has exist in only one place, tied to the general notion of a sequential table. To describe each new variant, one no longer needs to worry about the has routine; one need only prepare suitable versions of start, forth, after, and found.
Along with the modularity requirements set out in the previous lecture, the five requirements of Type Variation, Routine Grouping, Implementation Variation, Representation Independence, and Factoring Out Common Behaviors define what we should expect from our reusable components — abstract modules.
Let us examine the solutions that preceded the OO approach, in order to understand what does not satisfy us, and what should be carried over into the OO world.
The classical approach to reuse consists in building libraries of routines. Here the term routine denotes a program element that can be called by other elements to carry out some algorithm, using certain input data, producing certain output data, and possibly modifying other data. The calling element passes its input data (and sometimes output data and data to be modified) in the form of actual arguments. A routine may also return output data as a result; in that case it is called a function.
Routine libraries have been used successfully in various application areas, in particular for numerical computation, where the use of excellent libraries led to
продолжение следует...
Часть 1 4. Approaches to Reuse
Часть 2 Packages - 4. Approaches to Reuse
Comments