Packages - 4. Approaches to Reuse

Это окончание невероятной информации про .

...

the first reports of success with reuse. The decomposition of systems into routines, functional decomposition, is also provided by the top-down programming method. The approach based on the use of routine libraries works well in cases where a set (possibly large) of separate tasks can be identified, given the following constraints:

[x]. R1 Each task admits a simple specification. More precisely, it is possible to characterize each individual task by a small set of input and output parameters.

[x]. R2 The tasks are clearly distinct from one another, since the routine-based approach does not allow us to take advantage of any significant commonality they might have — except for the reuse of certain constructs.

[x]. R3 There are no complex data structures that would have to be shared among the routines that use them.

Table searching is a good example of the limited capabilities of routines. We have already seen that the search routine on its own does not contain enough context to serve as a functionally complete reuse module. Even setting this shortcoming aside, we run into two equally unpleasant solutions:

[x]. There is a single variant of the search routine. But then, to cover all possible situations, it will need a long list of arguments and will turn out to be very complex.

[x]. There are many search routines, each relating to a specific case and differing from the others only in a few details. This violates the Factoring Out Common Behaviors requirement; potential users can easily get lost in the resulting clutter of routines.

On the whole, routines are not flexible enough to satisfy the needs of reuse. We have already seen the close connection between reusability and extendibility. A reusable module must be open to extension, but in the case of a routine, the only means of adaptation is passing arguments. This makes us hostage to the Reuse-or-Redo dilemma: either use this routine in its original form, or write your own routine.

Packages

In the nineteen-seventies, in connection with the development of the ideas of information hiding and data abstraction, the need arose for a form of module more sophisticated than the routine. Several design and programming languages appeared, the best known of them being CLU, Modula-2, and Ada. They offer a similar form of module, called a package in Ada, a cluster in CLU, and a module in Modula. In our discussion we will use the term package. (4.4)

Packages are units of program decomposition possessing the following properties:

[x]. P1 In accordance with the Linguistic Modular Units principle, a "package" is a language construct, so that every package has a name and a syntactically well-defined scope.

[x]. P2 The description of each package contains a number of declarations of associated elements, such as routines and variables, which will henceforth be called the features of the package.

[x]. P3 Each package can precisely define the access rights restricting the use of its components by other packages. In other words, the package mechanism supports information hiding.

[x]. P4 In a compilable language (one that can be used for implementation, not only for specification and design), independent compilation of packages is supported.

Thanks to property P3, packages can be regarded as abstract modules. Their main contribution to programming is property P2, which satisfies the Routine Grouping requirement. A package can contain any number of associated operations, such as creating a table, inserting, searching for, and removing elements. And it is not hard to see how a package-based solution would work in the table-searching example under discussion here. Below — in a system of notation borrowed from the notation used in the following lectures of this course for OO software — is a sketch of the package INTEGER_TABLE_HANDLING, describing a particular implementation of integer tables based on the use of binary trees:

package INTEGER_TABLE_HANDLING feature

type INTBINTREE is

record

-- Description of the binary tree representation, for example:

info: INTEGER

left, right: INTBINTREE

end

new: INTBINTREE is

-- Return a new initialized INTBINTREE.

do ... end

has (t: INTBINTREE; x: INTEGER): BOOLEAN is

-- Is x contained in t?

do ... Implementation of the search operation ... end

put (t: INTBINTREE; x: INTEGER) is

-- Insert x into t.

do ... end

remove (t: INTBINTREE; x: INTEGER) is

-- Remove x from t.

do ... end

end -- of package INTEGER_TABLE_HANDLING

This package contains the declaration of a type (INTBINTREE), and a number of routines representing operations on objects of this type. In this example, no package variables needed to be declared (although the routines may have local variables).

Client packages can now work with tables using various methods from INTEGER_TABLE_HANDLING. Let us introduce a syntactic convention allowing a client to use method f from a package, for which we borrow the notation from the CLU language: P$f. In our example, typical fragments of client program text might look like this:

-- Auxiliary declarations:

x: INTEGER; b: BOOLEAN

-- Declaration of t, of the type defined in INTEGER_TABLE_HANDLING:

t: INTEGER_TABLE_HANDLING$INTBINTREE

-- Initialization of t with a new table, created by the package's new function:

t := INTEGER_TABLE_HANDLING$new

-- Inserting x into the table, using the package's put procedure:

INTEGER_TABLE_HANDLING$put (t, x)

-- Assigning True or False to the variable b,

-- the package's has function is used for the search:

b := INTEGER_TABLE_HANDLING$has (t, x)

Note the need to introduce two interrelated names: one for the module, here INTEGER_TABLE_HANDLING, and one for its main data type, here INTBINTREE. One of the key steps toward OO programming will be the merging of these two notions. But let us not get ahead of ourselves.

with INTEGER_TABLE_HANDLING then

... Here has means INTEGER_TABLE_HANDLING$has, and so on ... end

Another obvious drawback of packages of the kind considered here is their inability to satisfy the requirement of Type Variation: the module presented above is suitable only for tables of integers. However, we will soon see how to remove this drawback by making packages generic.

The package mechanism provides information hiding by restricting clients' rights to access components. The client shown above was able to declare one of its own variables using the type INTBINTREE obtained from its supplier, and to call the routines described by that supplier. But it has access neither to the internal description of this type (to the record structure defining the implementation of the tables), nor to the body of the routines (here, the do clauses). Moreover, it is possible to hide some of the package's components (variables, types, routines) from clients, making them usable only within the text of the package.

To further strengthen information hiding, languages with encapsulation often propose declaring a package consisting of two parts, an interface and an implementation (see also the course "Fundamentals of Object-Oriented Design"). Closed elements, such as the type declaration or the routine body, are included in the implementation section. However, this approach leads to extra work for module developers, forcing them to duplicate component declaration headers. On closer examination of the Information Hiding rule, none of this is actually required. This issue is discussed in more detail in later lectures.

Packages: an assessment

Compared to routines, the package mechanism leads to a significant improvement in partitioning software systems into abstract modules. Gathering the needed components "under one roof" is extremely useful both for suppliers and for clients:

[x]. The author of a supplier module can store in one place, and compile together, all the elements pertaining to a given concept. This makes debugging and changes easier. By contrast, when using separate independent routines there is always a danger of forgetting to update some routines when the design or implementation changes; for example, one might update new, put and has, but forget to update remove.

[x]. For the authors of client modules it is undoubtedly easier to find and use a set of interrelated components if they are all gathered in one place.

The advantage of packages over routines is especially clear in cases such as the table example considered here, where the package gathers all the operations applicable to a specific data structure.

However, packages still do not provide a complete solution to the problems of reuse. As already noted, they satisfy the requirement of Routine Grouping, but do not satisfy all the other requirements. In particular, they do not provide the ability to factor out common behavior — to "factor out" common components. Note that INTEGER_TABLE_HANDLING in our sketch of the package text is based on one particular implementation choice — binary search trees. Of course, thanks to information hiding, clients need not be concerned with this choice. But a library of reusable components will need to contain modules for many different implementations. The resulting situation is not hard to foresee: a typical package library will offer a mass of similar, but not identical, modules for a given application area, for example for working with tables, but without any account being taken of their commonality. While providing reuse for clients, such a technique sacrifices the possibility of reuse on the part of suppliers.

But even from the client's side, the situation remains not entirely acceptable. Every use of the table by a client requires the declaration mentioned above:

t: INTEGER_TABLE_HANDLING$INTBINTREE

The client is forced to choose a specific implementation. This violates the requirement of Representation Independence: the authors of client modules would need to know more about the implementations of the supplier module's representations than is strictly necessary.

Overloading and genericity

Two technical devices — overloading and genericity — offer their own solutions aimed at achieving greater flexibility for the mechanisms described above. Let us consider what they can provide.

Syntactic overloading

Overloading is the association of more than one meaning with a single name. The names most often overloaded are variable names: in almost all programming languages, variables with different meanings can have the same name if they belong to different modules (different blocks — as in the Algol language and its relatives).

More relevant to this discussion is the overloading of routines, a special case of which is operator overloading, which allows the same names to be used for several routines. This possibility almost always applies to arithmetic operators: the same notation, a +b, denotes different kinds of addition depending on the types of a and b (integers, single-precision reals, double-precision reals). Starting with the Algol 68 language, which allowed overloading of the basic operators, some programming languages extended the possibility of overloading to user-defined operations and to ordinary routines.

For example, in the Ada language a package may contain several routines with the same name but with different signatures, defined here by the number and types of the arguments. In general, the signature of a function also includes the result type, but the Ada language allows overloading that takes only the arguments into account. For example, a package may contain several square functions:4.5)

square (x: INTEGER): INTEGER is do ... end

square (x: REAL): REAL is do ... end

square (x: DOUBLE): DOUBLE is do ... end

square (x: COMPLEX): COMPLEX is do ... end

Then, when square (y) is called, the type of the argument y determines which variant of the routine was intended.

In a similar way, a package can describe a set of search functions of the same kind:

has (t: "SOME_TABLE_TYPE"; x: ELEMENT) is do ... end

Each of them defines its own implementation and differs in the actual type used in place of "SOME_TABLE_TYPE". The type of the first actual argument, in any client call to has, makes it possible to determine which of the routines was intended.

From these considerations follows a general characterization of overloading, which will be useful later when this property is compared with genericity:

The role of overloading

Routine overloading is a device intended for clients. It allows one to write the same text while using different implementations of some concept.

So what does routine overloading contribute to solving the problem of reuse? Not much. It is a syntactic device that frees developers from having to invent different names for different implementations of some operation and essentially shifts that burden onto the computer. But it does not solve any of the key problems of reuse. In particular, overloading does nothing to satisfy the requirement of Representation Independence. When the call

has (t, x)

is written, t will still need to be declared, and therefore (even if information hiding frees you from worrying about the details of each search algorithm variant) you need to know exactly what kind of table t is! The sole merit of overloading is that the same name can be used in every case. Without overloading, each implementation would require a different name, for example

has_binary_tree (t, x)

has_hash (t, x)

has_linked (t, x)

But is avoiding the use of different names really an advantage? Probably not. The fundamental rule of software construction, whether object-oriented or not, is the principle of non-deception: differences in semantics should be reflected in differences in program texts. This makes it possible to significantly improve the understandability of software and to minimize the risk of errors. If the has routines are different, then using the same name for them can be misleading — reading the program text creates the assumption that these are the same routine. It is better to offer the client a slightly more verbose text (as in the case of the individual names introduced above) and eliminate any risk of confusion.

The more one analyzes overloading, the more limited it appears.

The criterion used to resolve ambiguity in calls — the signatures of argument lists — has no specific merit of its own. It works in the examples above, where all the different overloaded square and has procedures have different signatures, but it is easy to imagine many cases where the signatures of different variants coincide. One of the simplest examples of overloading is apparently the set of functions of a computer graphics system used to create new points, for example in the form:

p1 := new_point (u, v)

A point can be specified by: Cartesian coordinates x and y; or polar coordinates r and q (the distance from the origin and the angle measured from the horizontal axis). But if the function new_point is overloaded, a difficulty arises because both variants have the same signature:

new_point (p, q: REAL): POINT

This example, like many similar ones, shows that a type signature may fail to resolve the ambiguity of overloaded variants. But nothing better has been proposed.

Semantic overloading (a preliminary look)

The form of routine overloading described above can be called syntactic overloading. The OO approach will offer a much more interesting technique, dynamic binding, which meets the goals of Representation Independence. Dynamic binding can be called semantic overloading. Using this technique, with an appropriately chosen syntax, one can write some equivalent of has (t, x) as a request for execution.

The meaning of such a request is roughly as follows:

Dear Computer (Hardware-Software Machine):

Please figure out what t is; I know it must be a table, but I don't know which implementation of this table its creator chose — and, frankly, I would rather remain unaware of that. After all, I am not in the business of table management, but of banking investments [or compilation, or computer-aided design, etc.]. Someone else is in charge of tables here. So figure it out yourselves, and once you get the answer, look for an algorithm suitable for 'has', matching this particular kind of table. Then use the algorithm you found to determine whether 'x' is contained in 't', and let me know the result. I look forward to your reply.

I regret to inform you that, apart from the information that 't' is some kind of table and 'x' is one of its possible elements, you will get no further help from me.

Please accept my best regards,

Sincerely, the application developer.

Unlike syntactic overloading, this kind of semantic overloading is a direct answer to the requirement of Representation Independence. There still remains a suspicion of violating the principle of non-deception, and the answer will be the use of assertions specifying the common semantics of a routine that has many different variants (for example, the common properties characterizing has across all possible table implementations).

Since the proper functioning of the semantic overloading mechanism requires the use of the entire OO apparatus, in particular inheritance, it is clear that syntactic overloading is only a half-measure. In an OO language, the presence of syntactic overloading alongside dynamic binding can only cause confusion, as happens in the C++ and Java languages, which allow a class to use several procedures with the same name, leaving the resolution of call ambiguity to the compiler and to the person reading the program text.

Genericity

Genericity is a mechanism for defining parameterized module patterns whose parameters are types. This device is a direct answer to the requirement of Type Variation. It removes the need to use many modules, such as:

INTEGER_TABLE_HANDLING

ELECTRON_TABLE_HANDLING

ACCOUNT_TABLE_HANDLING

Instead, it is permissible to write a single module pattern in the form:

TABLE_HANDLING [G]

The name G, representing an arbitrary type, is called the formal generic parameter. (Later we may encounter the need to have two or more generic parameters, but for now we will limit ourselves to one.)

Such a parameterized pattern is called a generic module, although it is not yet an actual module, but only a general scheme — a pattern for many possible modules. To obtain an actual module from the pattern, one must supply some type, called the actual generic parameter. Modules obtained from the pattern by replacing the formal parameter G with the actual one are written, for example, as:

TABLE_HANDLING [INTEGER]

TABLE_HANDLING [ELECTRON]

TABLE_HANDLING [ACCOUNT]

The types INTEGER, ELECTRON and ACCOUNT were used, respectively, as actual generic parameters. This process of obtaining an actual module from a generic module (module pattern) is called generic derivation, and the module itself will be called "generically derived" (generically derived.).

Two brief remarks about terminology. First, generic derivation is sometimes called generic instantiation, and the derived module is then called a generic instance. This terminology can cause confusion in an OO context, since the term "instance" is applied to objects created at run time from the corresponding types (or classes). So we will stick to the term "derivation".

Another possible source of confusion is the word "parameter". A routine can have formal arguments, representing values that the routine's clients will supply on each call. In the literature, the term "parameter" (formal, actual) is commonly used as a synonym for argument (formal, actual). Using either of these terms is not an error, but as a rule we will use the term "argument" for routines, and "parameter" for generic modules.

Internally, the description of the unified module TABLE_HANDLING will resemble the description of INTEGER_TABLE_HANDLING given above, except that G is used instead of INTEGER to refer to the type of the table elements. For example:

package TABLE_HANDLING [G] feature

type BINARY_TREE is

record

info: G

left, right: BINARY_TREE

end

has (t: BINARY_TREE; x: G): BOOLEAN

-- Is x contained in t?

do ... end

put (t: BINARY_TREE; x: G) is

-- Insert x into t.

do ... end

(etc.)

end -- of package TABLE_HANDLING

In this approach, some confusion arises from the fact that the type declared as BINARY_TREE would ideally be made generic and declared as BINARY_TREE [G]. There is no obvious way to achieve this within the "package" approach. However, object technology will unify the notions of module and type, so the problem will be solved automatically. We will see this when we learn how to integrate genericity into the OO world.

It is interesting to compare the definition of genericity with the definition of overloading given earlier:

The role of genericity

Genericity is a device intended for suppliers. It allows one to write the same text, using the same implementation of some concept, applied to different kinds of objects.

How, then, does genericity contribute to achieving the goals of this lecture? Unlike syntactic overloading, genericity makes a real contribution to solving our problems, since, as noted above, it fulfills one of the fundamental requirements, Type Variation. And in presenting object technology in lectures 7-18 of this course, considerable attention will be devoted to genericity.

The basic modularity techniques: an assessment

We have obtained two main results. One of them is the idea of creating a single syntactic "home," such as the package construct, for a set of routines that all operate on homogeneous objects. The second result is genericity, leading to a more flexible form of module.

All this, however, covers only two of the reuse problems, Routine Grouping and Type Variation, and provides some help toward solving the remaining three problems — Implementation Variation, Representation Independence and Factoring Out Common Behavior. Genericity, in particular, is not sufficient to solve the Factoring problem, since it defines only two levels. We obtain a generic module, parameterized and hence open to change, but not directly applicable. At the other level we have individual generic derivations, suitable for direct application, but closed to further changes. This does not allow us to capture the subtle differences that may exist between competing representations of a given general idea.

As for Representation Independence, we have made almost no progress here. None of the methods examined — apart from a brief look at semantic overloading — allows a client to use different implementations of some general concept without knowing which implementation will be chosen in each case.

To solve these problems we will need the full power of OO concepts.

Key concepts

[x]. Software development is characterized by recurring activity involving frequent use of common patterns. But there are significant variations in how these patterns are used and combined, so naive attempts to work with the components already available tend to fail.

[x]. Practical implementation of reuse raises economic, psychological and organizational problems. The latter are related, in particular, to the need to create mechanisms for indexing, storing and searching a large number of reusable components. More important are the technical problems: commonly accepted views of modules are insufficient to seriously support reuse.

[x]. The main difficulty in implementing reuse is the need to combine reuse with extendibility. The dilemma "reuse or redo" is unacceptable. A good solution must make it possible to preserve some properties of a reused module while adapting others.

[x]. Simple approaches to the problem — personnel reuse, design reuse, source code reuse, routine libraries — have achieved some success, but have not made it possible to fully realize the potential benefits of reuse.

[x]. A reusable program component is an abstract module that provides encapsulation of functionality through a well-defined interface.

[x]. Packages provide a better implementation of the encapsulation technique than routines, since they combine a data structure with the operations associated with it.

[x]. Two techniques make it possible to increase the flexibility of packages: routine overloading and genericity.

[x]. Routine overloading is a syntactic device that does not solve the important problems of reuse, but makes program texts harder to read.

[x]. Genericity contributes to reuse, but solves only the problem of type variation.

[x]. What we need, then, is a technique that helps the supplier account for commonality across groups of interrelated implementations of data structures; and a technique that frees clients from having to know which implementation variant the supplier has chosen.

Bibliographical notes

The first publication discussing the problems of reuse, mentioned at the beginning of this lecture, apparently belongs to McIlroy (McIlroy's 1968 Mass-Produced Software Components). His article [McIlroy 1976] was presented in 1968 at the first software engineering conference, convened by the NATO Science Affairs Committee. 1976 is the publication date of the conference proceedings, [Buxton 1976], whose publication was delayed by several years. McIlroy advocated the development of industrial-scale production of software components.

Here is an excerpt from his article:

"Software manufacture today is, in terms of industrialization, below the level of even the most backward branches of the construction industry. I believe its proper place is considerably higher, and I would like to explore the prospects for implementing mass-production methods for software ...

When we set out to write a compiler, we start with the question: "What table-handling mechanism shall we build?". Instead, the question should be: "What mechanism shall we use?" ...

I put forward the thesis that the software industry has a weak foundation, partly because of the absence of a subindustry producing software components... Such component production could be highly successful."

One of the important questions addressed in the article was the need for families of modules, discussed above as one of the requirements for any comprehensive solution to the problems of reuse.

The most important characteristic of a software-component industry is that it must offer families [of modules] for performing a given task.

A special issue of Transactions on Software Engineering, edited by Biggerstaff and Perlis [Biggerstaff 1984], played an important role in drawing the attention of the software development community to questions of reuse; see in particular, in that issue, the articles [Jones 1984], [Horowitz 1984], [Curry 1984], [Standish 1984] and [Goguen 1984]. The same editors included all these articles (except the first of those mentioned above) in an expanded two-volume collection [Biggerstaff 1989]. Another collection of articles on reuse is [Tracz 1988]. Later, Tracz gathered a number of his pieces from IEEE Computer into a useful book [Tracz 1995], which places special emphasis on organizational issues.

One approach to reuse, based on ideas from artificial intelligence, is embodied in the Massachusetts Institute of Technology's Programmer's Apprentice project; see the articles [Waters 1984] and [Rich 1989], reproduced in the first and second Biggerstaff-Perlis collections, respectively. This system does not use actual reusable modules, but templates (called cliches and plans) representing general program development strategies.

In the discussion of packages, three "encapsulation languages" were mentioned: Ada, Modula-2 and CLU. The Ada language is discussed in one of the following lectures, whose bibliographic section contains references to the Modula-2 and CLU languages, as well as to Mesa and Alphard, the latter two encapsulation languages belonging to the "modular generation" of the nineteen-seventies and early nineteen-eighties. The equivalent of a package in the Alphard language was called a form.

The important STARS project of the U.S. Department of Defense in the nineteen-eighties focused on the problem of reuse, especially on the organizational aspects of this problem, using the Ada language as the language for software components. A number of articles on these questions can be found in the proceedings of the 1985 STARS DoD-Industry conference [NSIA 1985].

The two best-known books on "design patterns" are [Gamma 1995] and [Pree 1994].

The work [Weiser 1987] is a call for distributing software in the form of source text. However, this article underestimates the need for abstraction; as shown in this lecture, when necessary one can retain access to the source text while using its high-level form as default documentation for module users. On other grounds, Richard Stallman, founder of the League for Programming Freedom, argued that a representation in the form of source text should always be available; see [Stallman 1992].

The work [Cox 1992] describes the idea of superdistribution. Some form of overloading existed in the Algol 68 language [van Wijngaarden 1975]; in the Ada (where it extends to routines), C++ and Java languages, which will be examined in later lectures, this mechanism is widely used.

Genericity, or polymorphism (genericity), appears in the Ada and CLU languages, and in an early version of the Z specification language [Abrial 1980]; in that version the syntax of Z is close to the one used to represent genericity in this book. The LPG language [Bert 1983] was explicitly designed for exploring genericity. (The name of this language is an acronym formed from the initial letters of "Language for Programming Generically.")

The work cited at the beginning of this lecture as the main reference for table search is [Knuth 1973]. Among the many textbooks on algorithms and data structures that address this topic, it is worth noting [Aho 1974], [Aho 1983] or [M 1978].

Two books by the author of this book contain further analysis of the reuse question. The book Reusable Software [M 1994a], entirely devoted to this topic, presents the design and implementation principles for building high-quality libraries, and a full specification of a set of basic libraries. The book Object Success [M 1995] discusses the organizational aspects of the reuse problem, especially the areas of activity in which a firm interested in reuse should invest effort, and the areas in which such efforts are likely to be useless (for example, recommending reuse to application developers, or encouraging them to practice reuse). See also the short article on this topic, [M 1996].

Продолжение:

Часть 1 4. Approaches to Reuse
Часть 2 Packages - 4. Approaches to Reuse