Lecture
If you are eager to dive into the depths of object technology and study multiple inheritance, dynamic binding and other toys in detail, then, at first glance, this lecture may seem like an unnecessary delay on that path, since it is mainly devoted to studying some mathematical concepts (although all the mathematics used in it is elementary).
But just as the most talented musician will benefit from studying the fundamentals of music theory, knowledge of abstract data types will help you understand and enjoy the practice of OO analysis, design and programming, even though the appeal of these concepts may already have become apparent without the help of theory. Since abstract data types are the theoretical basis for the entire method, the consequences of the ideas introduced in this lecture will be felt throughout the rest of the course.
Moreover, as will be seen at the end of the lecture, these ideas go beyond software itself and lead to principles of intellectual inquiry that may be applicable in other disciplines as well.
This opened my eyes, I began to understand what it means to use a tool called algebra. Damn it, no one had ever told me anything like that before. Monsieur Dupuis [the mathematics teacher] uttered pompous phrases about the subject, but never once said these simple words: it is a division of labor, which, like every other division of labor, produces wonders and allows the mind to concentrate all its powers on only one side of objects, on only one of their qualities.
How different it would have appeared to us if Monsieur Dupuis had told us: "This cheese is soft or hard, it is white, it is blue, it is old, it is young, it is yours, it is mine, it is light or it is heavy. Of all its many qualities, let us consider only weight. Whatever this weight may be, let us call it A. And now, without thinking any more about weight, let us apply to A everything we know about quantity."
Such a simple thing, yet no one had told us about it until now in this remote province...
Stendhal, "The Life of Henry Brulard"
As for abstraction, it consists in separating the perceptible properties of bodies either from their other properties, or from the bodies themselves that possess them. When this separation is made unsuccessfully or applied incorrectly, errors arise, which is possible both in philosophical matters and in physical and mathematical matters. The direct path to error in philosophy is not simplifying the objects under study enough, and the sure path to obtaining erroneous results in physics and mathematics is to consider objects less complex than they actually are.
Denis Diderot, "Letter on the Blind for the Use of Those Who See"
To obtain proper descriptions of objects, our method must satisfy three conditions:
[x]. Descriptions must be precise and unambiguous.
[x]. They must be complete - or, at least, have in each specific case the completeness we need (some details can be deliberately omitted).
[x]. They must not be over-specified.
The last point makes the answer nontrivial. After all, it is easy to make a description precise, unambiguous and complete if we are willing to "give away all the secrets" by specifying all the details of the object representation. But such a description will typically include far too much information for the authors of programs who need access to such objects.
These remarks are similar to the comments that led to the notion of information hiding. There, the point was that, by providing the source code of a module (implementation-related elements) as the primary source of information to the authors of client programs that depend on that module, we may plunge them into a flood of details that will prevent them from concentrating on their own work and will make it harder to see the prospects for the project's development. The same danger awaits us here as in the case where we allow modules to use some data structure based on information that pertains to the representation of that structure rather than to its essential properties.
To better understand the full importance of descriptions of abstract data types, let us explore more deeply the potential consequences of using a physical implementation as the basis for describing objects.
A convenient and well-studied example is the description of objects of stack type. A stack object serves to accumulate and retrieve other objects in "last in - first out" ("LIFO") mode: the element inserted into the stack last will be the first one retrieved from it. The stack is used ubiquitously in computer science and in many software systems; in particular, compilers and interpreters are studded with various kinds of stacks.
| It must be said that stacks appear in didactic presentations of abstract data types in such great numbers that E. Dijkstra once wittily remarked that "abstract data types are a beautiful theory whose purpose is to describe stacks". Quite fair. But in the following lectures of the course, the notion of abstract data types is applied so often to much more complex cases that I feel no shame in beginning the discussion with this key example. It is the simplest example I know of that contains within it almost all the important ideas of abstract data types. |
There are several physical representations of stacks:
Fig. 6.1. Three possible representations of stacks
This figure illustrates the three most popular representations of stacks. For ease of reference, let us give each of them its own name:
[x]. ARRAY_UP: represents the stack by means of an array representation and an integer count, with a range of values from 0 (for an empty stack) to capacity - the size of the array representation; the stack elements are stored in the array and indexed from 1 to count.
[x]. ARRAY_DOWN: similar to ARRAY_UP, but elements are placed at the end of the stack rather than at the beginning. Here the number, called free, is the index of the topmost free position in the stack, or 0 if all positions in the array are occupied, and it varies in the range from capacity for an empty stack to 0 for a full one. The stack elements are stored in the array and indexed from capacity down to free+1.
[x]. LINKED: in the linked representation, each stack element is stored in a cell with two fields: item, containing the element itself, and previous, containing a pointer to the cell with the previous element. This representation also needs a pointer last to the cell containing the top of the stack.
Next to each representation in the figure is a program fragment (in the spirit of Pascal), with the corresponding implementation of the basic stack operation: pushing an element x onto the top of the stack (push).
For the array representations ARRAY_UP and ARRAY_DOWN, the commands increment or decrement the pointer to the top (count or free) and assign x to the corresponding array element. Since these representations support stacks with no more than capacity elements, correct implementations must contain overflow-protecting tests of the appropriate form:
if count " capacity then ...
if free " 0 then ...,
(they are omitted in the figure for simplicity).
For the LINKED representation, pushing an element requires four actions:
[x]. creating a new cell n (here it is done using the Pascal procedure new, which allocates memory for a new object);
[x]. assigning x to the item field of the new cell;
[x]. attaching the new cell to the top of the stack by assigning to its previous field the current value of the pointer last;
[x]. changing last so that it refers to the just-created cell.
Although these representations occur most often, there are also many other representations of stacks. For example, if you need two stacks with elements of the same type and the memory for their representation is limited, you can use a single array with two top markers, count as in the ARRAY_UP representation and free as in ARRAY_DOWN. In this case one stack will grow upward and the other downward. The condition for this representation being completely full is count = free.
The advantage of such a representation is a reduced risk of overflowing memory: with two arrays of size n representing stacks in the ARRAY_UP or ARRAY_DOWN way, memory will run out as soon as either of the stacks reaches n elements. But in the case of a single array of size 2n containing two stacks facing each other, operation continues until their combined length exceeds 2n, which is less likely if the stacks grow independently of each other. (For any variables p and q, max (p +q) "= max (p) + max (q)).
Fig. 6.2. Representation of two stacks facing each other
Each of these and other possible representations is useful in different situations. Choosing one of them as the standard for defining a stack would be a typical example of over-specification. Why should we, for instance, prefer ARRAY_UP to the LINKED representation? Most of the visible properties of the ARRAY_UP representation - the array, the number count, the upper bound - are inessential to understanding the structure they represent.
Why is it so bad to use a concrete representation as a specification?
One can recall the results of Lientz and Swanson's study of maintenance costs. It was found that more than 17% of software cost is spent on changes to data formats. It is clear that a method which makes analysis and design dependent on the physical representation of data structures will not enable the development of sufficiently flexible software.
Therefore, when using objects or object types as the basis for a system's architecture, one needs to find a better way of description than a concrete representation.
Lest stacks make us forget that, besides the examples favored by computer scientists, there are data structures closely tied to real-life objects. Here is an amusing example, taken from the mail of the Risks forum (the Usenet newsgroup comp.risks), which illustrates the dangers of a view of data that depends too heavily on its concrete properties. A certain Darrell D. E. Long, whom his parents blessed with two middle initials, received a credit card on which only the first of them, "D", was printed. After contacting the manager of the TRW company, he was sent another card, on which there was only the second initial, "E". He writes:
| I called the credit bureau, and it turned out that, apparently, the programmer who designed the TRW database decided that every good American is granted a middle name with only one initial. As the lady on the phone politely explained to me: "They allocated enough megabytes (sic) in the system for only one middle initial, and it's extremely difficult to change." |
Besides the typical example of technocratic justification ("megabytes"), the lesson in this case is that programs should avoid being oriented toward the physical properties of data.
The author of the letter quoted above was mainly troubled by unwanted mail, which is annoying but not fatal; the archives of the Risks forum are full of cases of computer-caused confusion with far more serious consequences. The already-mentioned "millennium problem" is another example of the danger that arises from organizing data access based on its physical representation; its consequences cost hundreds of millions of dollars.
How can we preserve completeness, accuracy, and unambiguity without paying for it with excessive specification?
Stack representations, for all their differences, share the fact that they describe a "storage" structure (i.e., a structure used to store other objects) to which certain operations with certain properties are applied. By focusing not on the choice of a particular representation of the structure, but on these operations and properties, we can obtain a sufficiently abstract, yet nonetheless useful, description of the concept of a stack.
Usually the following operations are considered for stacks:
[x]. A command to push some element onto the top of the stack. Let's call this operation put.
[x]. A command to remove the top element of the stack. Let's call it remove.
[x]. A query for the element located at the top of the stack (if the stack is not empty). Let's call it item.
[x]. A query to check whether the stack is empty. (It will allow clients to check in advance whether the remove and item operations are possible.)
In addition, we will need a constructor operation to create an empty stack. Let's call it make.
| Two things deserve more detailed explanation later in this lecture. First, the names of the operations may seem unusual; for now, let's assume that put means push, remove means pop, and item means top. Second, the operations are divided into three categories: constructors, which create objects; queries, which return information about objects; and commands, which can change objects. This classification also requires additional explanation. |
With the traditional view of data structures, we would consider the concept of a stack given by means of some data declaration corresponding to one of the representations above, for example for the ARRAY_UP representation. In Pascal-like style, this looks like
count: INTEGER
representation: array [1 .. capacity] of STACK_ELEMENT_TYPE
where the constant capacity is the maximum number of elements in the stack. Then put, remove, item, empty, and make will be routines that operate on structures defined by this object declaration.
To take the main step toward data abstraction, one needs to take the opposite point of view: forget for a while about the specific representation and take the operations themselves as the definition of the data structure. In other words, a stack is any structure to which clients can apply the operations listed above.
The method of describing data structures just outlined looks like a rather self-centered approach in the world of data structures. We are not so much interested in what they represent internally as in what they can offer each other. In this we resemble an economist - an ardent adherent of theories of production priority and the invisible hand, raised in the spirit of the "let-the-free-market-decide-everything" school. The world of objects (and, consequently, of software architecture) will be a world of interacting objects, communicating on the basis of precisely defined protocols.
The analogy with economics will continue to accompany our presentation further on: agents - software modules - are called suppliers and clients, protocols will be called contracts, and much of OO development can, in fact, be regarded as "Design by Contract" - this is the title of one of the following lectures.
One should not get too carried away with this analogy (as with any other): this work is not a textbook on economics, and it does not contain even a hint of the author's point of view in this field. For now it is enough for us to note the striking analogies between the abstract data type approach and certain theories about the interaction of human agents.
Let's make sure that the specification given above and its details are sufficiently convenient. For someone who has previously encountered stacks, the names chosen here for the stack operations may seem strange or even shocking. To every self-respecting computer science specialist, stack operations are known under other names:
| Standard name of the stack operation | Name used here |
| Push | Put |
| Pop | Remove |
| Top | Item |
| New | Make |
Table 6.1. Names of stack operations
Why use terminology different from the generally accepted one? The reason lies in the desire to achieve a higher level of understanding of data structures - especially "containers", which are used for storing objects.
Stacks are just one kind of container; more precisely, they belong to the category of containers that can be called dispensers. A dispenser provides its clients with a mechanism for storing (put), retrieving (item), and removing (remove) objects, but does not give them the ability to control which object will be retrieved or removed. For example, the LIFO access method used in stacks allows only the element that was stored last to be retrieved or removed. Another kind of dispenser is the queue, which uses the "first in, first out" (FIFO) access method: elements are added at one end of the queue, and retrieved and removed from the other end. An example of a container that is not a dispenser is an array, in which you choose for yourself the integer position numbers at which objects are inserted or from which they are retrieved.
Since the similarity of different kinds of containers (dispensers, arrays, etc.) is more important than the differences in how they store, retrieve, or remove objects, this book firmly adheres to a standardized terminology that smooths over the differences between variants of data structures and, conversely, emphasizes their commonality. Therefore, the basic operation of retrieving an element will always be called item, the basic operation of removing an element will always be called remove, and so on.
Naming issues may at first seem superficial - "cosmetic", as programmers sometimes say. But do not forget that one of our ultimate goals is to create a foundation for powerful, professional libraries of reusable software components. Such libraries will contain tens of thousands of available operations. Without a systematic and clear nomenclature for them, both the developers and the users of these libraries will quickly drown in a flood of special-purpose and incomparable names, which will create a strong (and unjustifiable) obstacle to large-scale reuse.
Thus, naming issues are not cosmetics. Good, reusable software is software that provides users with the appropriate set of functions and provides them under the right names.
The names used here for stack operations are part of the naming conventions that we adhere to throughout the book.
In software development, as in other scientific and technical disciplines, a fruitful idea, once uncovered, may seem obvious, even if it took a long time for it to arise. At first, bad and confused ideas (which is often the same thing) tend to appear, and it takes time for simpler and more elegant ones to take their place.
This observation also holds true for abstract data types. Although good software developers have always applied abstraction usefully (due to a good education or simply intuitively), many of the systems existing today were designed without this goal in mind.
In the previous sections we managed to take the first steps along the road to ADTs. They are enough to understand that a program written in accordance with the most elementary notions of data abstraction would have to treat MAIL_MESSAGE as a precisely defined abstract concept. One of the operations of a message could be a query, called, for example, sender, returning information about the sender of the message. Any element of the mail program that needed this information would obtain it only through this sender query. If the mail program had been designed in accordance with this seemingly obvious principle, then for my small exercise it would have been enough to change only the code of the sender query. Moreover, it is quite likely that in this case the program would also provide a set_sender operation, which would make the required work even simpler.
Note that the mail program in question was used quite successfully. But it is a typical representative of the current standard in the software industry. Until we go far beyond this standard, the phrase "software design" will remain an example of wishful thinking.
The brief sketch of data abstraction presented above is too informal to be used consistently. Let's return to our main example. A stack, as we have understood it, must be defined in terms of the operations applicable to it, but then we need to define these operations!
The descriptions given above are clearly insufficient - put pushes an element onto the "top" of the stack, remove pops the element located at the top. We need to know precisely how clients can use these operations and what they must do in order to do so.
The ADT specification will provide this information. It consists of four sections, explained in the following sections:
Simple mathematical notation will be used in these sections to specify the ADT.
| This notation - a mathematical formalism - should not be confused with the programming notation used in the rest of the book, even though for consistency it uses the same style of syntax. It has no special name, and it is not the notation of any programming language. It could serve as a starting point for a formal specification language, but we will content ourselves with using self-explanatory conventions for an unambiguous specification of the ADT. |
The TYPES section indicates the types being specified. In general, it may be convenient to define several ADTs at the same time, although in our example there is only one type, STACK. By the way, what is a type? The answer to this question will unify all the points developed further in this lecture: a type is a collection of objects characterized by functions, axioms, and preconditions. It will not be a great mistake, for now, to regard a type as a set of objects in the mathematical sense of the word "set" - the type STACK as the set of all possible stacks, the type INTEGER as the set of all integers, and so on.
However, there should be no confusion here: an ADT such as STACK is not an object (one particular stack), but a collection of objects (the set of all stacks). Let us recall what our main goal is: to find a suitable basis for the modules of our software systems. Clearly, it makes no sense to base a module on one particular object - one stack, one airplane, one bank account. OO design will give us the ability to build modules that reflect the properties of all stacks, all airplanes, all bank accounts, or at least a significant part of them.
An object belonging to the set of objects described by an ADT specification is called an instance of that ADT. For example, a particular stack possessing the properties of the abstract data type STACK will be an instance of the ADT STACK. The notion of an instance runs through all of OO design and programming, and will play an important role in explaining the behavior of programs at run time.
The TYPES section simply lists the types introduced in a given specification. Here:
Types
[x]. STACK[G]
Thus, our specification pertains to a single abstract data type - STACK, defining stacks of objects of an arbitrary type G.
In the description STACK[G], the name G denotes an arbitrary, undefined type. G is called the formal generic parameter for the element types of the ADT STACK, and STACK itself is called a generic, or universal, ADT. The mechanism allowing such parameterized specifications is known as genericity; we have already encountered a similar notion in the review of package constructs.
It is possible to write ADT specifications without parameterization, but at the cost of unjustified repetition. Moreover, the possibility of reuse is desirable not only for programs, but for specifications as well! Thanks to the genericity mechanism, it is possible to parameterize types explicitly, choosing some arbitrary name for the parameter (here - G) representing a variable for the type of the stack elements.
As a result, an ADT such as STACK is not simply a type, but rather a type pattern. To obtain a directly usable stack type, one must define the type of the stack elements, for example ACCOUNT, and pass it as the actual generic parameter corresponding to the formal parameter G. Therefore, although STACK itself is a type pattern, the notation STACK[ACCOUNT] denotes a fully defined type. Such a type, obtained by passing actual type parameters to a generic type, is said to be derived from the generic by an instantiation of the pattern.
These notions can be applied recursively: every type must, at least in principle, have an ADT specification, so the type ACCOUNT can also be regarded as an abstract data type. Moreover, a type substituted as an actual type parameter into STACK (to obtain a type derived from the pattern) may itself be derived from a pattern. For example, one can quite correctly use the notation STACK[STACK[ACCOUNT]] to define the corresponding abstract data type: the elements of this type are stacks whose elements, in turn, are bank accounts.
As this example shows, the previous definition of "instance" needs some modification. Strictly speaking, a particular stack is an instance not of the type STACK (which, as we noted, is rather a type pattern than a type), but of some type derived from the type STACK, for example, the pattern instantiation STACK[ACCOUNT]. Nevertheless, it is convenient for us to continue speaking of instances of the type S and other type patterns, understanding thereby that we mean instances of the types derived from them.
Similarly, it is not quite correct to speak of the type STACK as an ADT: the correct term in this case is "ADT pattern". But for simplicity, in this discussion we will continue to omit the word "pattern" wherever this does not lead to confusion.
This distinction will also carry over into OO design and programming, but there we will not need two different terms:
[x]. The basic notion will be the class, which may have generic parameters.
[x]. Describing real data requires types. A class without parameters is also a type, but a class with parameters is only a type pattern. To obtain a specific type from such a class, one must pass it actual type parameters, exactly as we did when obtaining the ADT STACK[ACCOUNT] from the ADT pattern STACK[G].
Following the TYPES section comes the FUNCTIONS section, which lists the operations applied to instances of the given ADT. As already mentioned, these operations will be the main components of the type definition; they describe what its instances can offer, not what they are.
Below is the FUNCTIONS section for the abstract data type STACK. If you are a software developer, this style of description will be familiar to you: the lines of this section resemble declarations in typed programming languages such as Pascal or Ada. The line for the operation new looks like a variable declaration, the rest like procedure headers.
Functions
[x]. put: STACK [G] × G STACK [G]
[x]. remove: STACK [G] STACK [G]
[x]. item: STACK [G] G
[x]. empty: STACK [G] BOOLEAN
[x]. new: STACK [G]
Each line introduces a specific mathematical function modeling the corresponding operation on the stack. For example, the function put represents the operation that pushes an element onto the top of the stack.
Why functions? Most programmers would not consider an operation such as put to be a function. When, during the execution of a software system, the operation put is applied to a stack, it generally modifies that stack by adding an element to it. As a result, in the classification of operations given above, put was a "command" - an operation that can modify objects. (The other two categories of operations are constructors and queries.)
However, an ADT specification is a mathematical model, and correct mathematical methods must underlie it. In mathematics, the notion of a command, or more generally of changing something as such, does not exist: computing the square root of the number 2 does not change that number itself. Mathematical expressions simply define some mathematical objects in terms of certain other mathematical objects. Unlike the execution of a program on a computer, they never change any mathematical objects. But since we need some mathematical object to model computer operations, the notion of a function appears to be the closest approximation. A function is a mechanism for obtaining some result belonging to a certain result set for any admissible input belonging to a certain source set. For example, if R denotes the set of real numbers, then the definition of the function
square_plus_one: R R
square_plus_one(x)= x2 + 1 (for every x in R)
introduces the function square_plus_one, for which R is both the source and the result set, and which yields, for any input, as its result the square of that input increased by 1.
Abstract data type specifications use exactly this notion. For example, the operation put is defined as
put: STACK [G] × G STACK [G]
and means that put will take two arguments: a STACK of instances of type G and an instance of type G, and return as its result a new STACK [G]. (More formally, the domain of the function put is the set STACK [G] _ G, the Cartesian product of the sets STACK [G] and G, i.e. the set of pairs in which the first element s belongs to STACK [G], and the second element x belongs to G.) Here is a figure illustrating this:
Fig. 6.3. Application of the function put
ADTs deal only with mathematical functions that have no side effects and that, in fact, change nothing. When we leave the refined realm of specification and enter the confusion of program design and implementation, we will have to restore the notion of change, since, because of the overhead involved, few would approve of a software environment in which every execution of the "push" operation on a stack begins by copying that stack. We will consider later the transition from the change-free world of ADTs to the change-filled world of software development. But since right now we want to understand how best to define types, the mathematical view of things suits us quite well.
From our discussion follow the roles of the operations modeled by each of the functions in the STACK specification:
[x]. The function put returns a new state of the stack with one new element placed on its top. The figure on the previous page illustrates the operation put(s, x), performed on a stack s and an element x.
[x]. The function remove returns a new state of the stack with the top element popped, if there was one. Like put, this function, during design and implementation, must turn into a command (an operation that modifies an object, usually implemented as a procedure). We will see later how to account for the possibility of an empty stack, from whose top there is nothing to remove.
[x]. The function item returns the top element of the stack, if there is one.
[x]. The function empty detects whether the stack is empty; its result is a Boolean value (true or false). It is assumed that the ADT BOOLEAN, defining Boolean values, is defined separately.
[x]. The function new creates an empty stack.
In the FUNCTIONS section these functions are not fully defined; only their signatures are introduced - lists of the types of their arguments and result. The signature of the function put
STACK [G] × G STACK [G]
shows that put takes as an argument a pair of the form , in which s is an instance of type STACK [G], and x is an instance of type G, and returns as its result an instance of type STACK [G]. Generally speaking, the value set of a function (its type indicated in the signature to the right of the arrow, here STACK [G]) can itself be a Cartesian product. This can be used when describing operations that return two or more results.
In the signature of the functions remove and item, instead of the usual arrow a crossed-out arrow is used. This means that these functions are not applicable to all elements of the input set. The description of the function new looks simply like
new: STACK
without any arrow in the signature. In fact, this is a shorthand for writing
new: STACK,
defining a function without arguments. No arguments are needed here, since new must always return the same result - an empty stack. Therefore, for simplicity, we have removed the arrow here. The result of applying this function (i.e., the empty stack) will be written as new, as a shorthand for new(), denoting the result of applying new to an empty list of arguments.
At the beginning of this lecture, operations on types were divided into constructors, queries, and commands. In the ADT specification for a new type T, for example for STACK [G] in our example, this classification can be defined more rigorously. This classification simply checks where, relative to the arrow, the type T is located in the signature of each function:
| In alternative terminology, these three categories are called "constructor", "accessor", and "modifier". Here we adhere to terms more directly related to the interpretation of ADT functions as models of operations on program objects. |
[x]. A function in whose signature T appears only to the right of the arrow, such as new, is a constructor function. It models an operation that creates instances of T from instances of other types, or that uses no arguments at all, as in the case of the constant constructor new.
[x]. Functions such as item and empty, in which T appears only to the left of the arrow, are query functions. They model operations that establish properties of T expressed in terms of instances of other types (in our examples - these are BOOLEAN and the type parameter G).
[x]. Functions such as put and remove, in which T appears on both sides of the arrow, are command functions. They model operations that, from existing instances of T and possibly instances of other types, produce new instances of type T.
We have already seen how data types (such as STACK) are described by specifying a list of functions applicable to their instances. All that is known about these functions is their signatures.
To indicate that we are talking about a stack, and not some other data structure, the ADT specification we have so far is completely insufficient. Any dispenser, for example a "first in, first out" queue, would also satisfy this specification.
This, of course, should not be surprising, since in the FUNCTIONS section the functions themselves are only declared (just as variables are declared in a program), but not fully defined. In the previously considered example of a mathematical definition:
square_plus_one: R R
square_plus_one (x)= x2 + 1 (for every x in R)
the first line plays the role of a signature, but there is also a second line, in which the value of the function is defined. How can we achieve the same for ADT functions?
We will not use explicit definitions in the spirit of the second line of the definition of the function square_plus_one, because that would force us to choose an interpretation, and all the preceding discussion has shown us the danger of choosing a representation too early.
Just to make sure that we understand what an explicit definition might look like, let's write one such definition for the previously given ARRAY_UP representation of a stack. From a mathematical point of view, choosing this representation means that an instance of type STACK is a pair , where representation is an array and count is the number of elements placed in the stack. Then the explicit definition of the function put (for any instance x of type G) looks like this:
put (, x)=
where a [n: v] denotes the array obtained from a by changing the value of the element with index n to v (all other elements remain unchanged).
This definition of the function put is simply a mathematical version of the implementation of the operation put, a sketch of which in Pascal-like style was given following the ARRAY_UP representation in the figure with possible stack representations at the beginning of this lecture.
But this is not the definition that would satisfy us. "Free us from the slavery of representations!" - this slogan of the Object Liberation Front and its military wing (the ADT brigades) is also ours. (Note that its political wing specializes in litigation: class action.)
Since every explicit definition forces us to choose some representation, let us turn to implicit definitions. In doing so, we will refrain from defining the values of the functions in the ADT specification and instead describe the properties of these values - all their essential properties, but only these properties.
They are formulated in the AXIOMS section. For the type STACK it looks as follows.
Axioms
For all x: G, s: STACK [G],
[x]. (A1) item (put (s, x)) = x
[x]. (A2) remove (put (s, x)) = s
[x]. (A3) empty (new)
[x]. (A4) not empty (put (s, x))
The first two axioms express the basic property of stacks - last in, first out (LIFO). To understand them, suppose we have a stack s and an instance x, and define s' as the result of put(s, x), i.e., as the result of pushing x onto s. Let's adapt one of the previous figures:
Fig. 6.4. Application of the function put
Here axiom A1 states that the top of s' is x - the last element we pushed, and axiom A2 explains that when we remove the top element of s', we again get the same stack s that existed before pushing x. These two axioms give a concise description of the main property of stacks in purely mathematical terms, without any help from imperative reasoning or references to properties of representations.
Axioms A3 and A4 state when a stack is empty and when it is not: a stack obtained as a result of the constructor new is empty, and any stack obtained after pushing an element onto an already existing stack (empty or not) is not empty.
These axioms, like the others, are predicates (in the logical sense), expressing the truth of certain properties for all possible values of s and x. Some prefer to view A3 and A4 in another equivalent form, as a definition of the function empty by induction on the size of stacks:
For all x: G, s: STACK [G]
A3' · empty (new) = true
A4' · empty (put (s, x)) = false
Two or Three Things We Know About Stacks
ADT specifications are implicit. There are two kinds of "implicitness":
[x]. The ADT method implicitly defines a certain set of objects by specifying the functions applicable to them. This definition never implies that all operations are listed in it; often, on the way to a representation, others will be added as well.
[x]. The functions themselves are also defined implicitly. Instead of explicit definitions, axioms are used that specify the properties of these functions. Here too nothing is asserted about completeness: when you eventually get to implementing these functions, they will acquire additional properties.
This implicitness is a key aspect of abstract data types and, consequently, of their future counterparts in the construction of OO software - classes. When we define an abstract data type or a class, we always state something about that type or class simply by listing those of its properties that we know, and we take them as the definition. It is never assumed, in doing so, that there are no other applicable properties.
Implicitness also implies the openness of definitions: it is always possible to add new properties to an ADT or a class. The main mechanism for performing such extensions without destroying the already existing original definition is inheritance.
This "implicit" approach has far-reaching consequences. In the "additional topics" section at the end of this lecture, some further comments on implicitness are given.
The specification of any realistic example, even one as simple as stacks, inevitably runs into problems of operations that are not defined everywhere: some operations are not applicable to all possible elements of the source sets. This is the case, for example, for the functions remove and item: you cannot remove an element from an empty stack, and an empty stack has no top element.
The solution to this problem used in the specification above consists in defining these functions as partial. A function from a source set X to a result set Y is partial if it is not defined for all elements of X. A function that is not partial is called total. A simple example of a partial function in ordinary mathematics is the reciprocal function for real numbers inv, whose value at a real number x is equal to
inv(x)= 1/x.
Since inv is not defined at x = 0, we can define it as a partial function on the set R of all real numbers:
Inv: R R
To indicate that a function is partial, a crossed-out arrow is used, while an ordinary arrow will mean that the function is known to be total.
The domain (of definition) of a partial function of type X Y is the subset of those elements of X for which this function has some value. In our example, the domain of the function inv is R - {0}, i.e., the set of real numbers other than 0.
In the ADT specification STACK, these ideas are used for stacks when declaring remove and item as partial functions in the FUNCTIONS section - this is indicated by the crossed-out arrows in their signature. This raises a new problem, discussed in the next section: how should the domains of such functions be specified?
In some cases it is also desirable to describe the function put as partial; for example, this is required in implementations such as ARRAY_UP and ARRAY_DOWN, which support only a finite number of consecutive put operations for each given stack. It is actually a useful exercise to adapt the STACK specification so that it describes bounded stacks of finite capacity, since in the form given above it contains no restrictions on stack size.
This would be a new application of partial functions, reflecting implementation constraints. In contrast, declaring the functions remove and item as partial reflects an abstract property of these operations, applicable to all implementations.
Partial functions are an unavoidable fact of the software design process, reflecting the obvious observation that not every operation is applicable to all objects. But they are also a potential source of errors: if a function f from X to Y is partial, one cannot be sure that the expression f(e) makes sense even if e belongs to X - it is necessary to guarantee that this value belongs to the domain of f.
For this, every ADT specification containing partial functions must specify their domains. This is precisely the role of the PRECONDITIONS section. For the ADT STACK, this section looks like this:
[x]. remove (s: STACK [G]) require not empty (s)
[x]. item (s: STACK [G]) require not empty (s)
In it, for each of the functions, the "require" clause lists the conditions that the function's arguments must satisfy in order to belong to its domain.
A Boolean expression that defines the domain of a function is called the precondition of the corresponding partial function. In our case, the preconditions of both functions remove and item state that the stack must be non-empty. Before "require" comes the name of the function together with the names of its arguments (in the example, s is used for the stack argument), so that the precondition can refer to these arguments.
| From a mathematical point of view, the precondition of a function f is the characteristic function of the domain of f. The characteristic function of a subset A of a set X is called the total function ch: X |
The PRECONDITIONS section completes the simple specification of the abstract data type STACK. For ease of reference, it is useful to gather together the various components of the specification given above. Here is the complete specification.
Specification of stacks as an ADT
TYPES
[x]. STACK [G]
FUNCTIONS
[x]. put: STACK [G] × G STACK [G]
[x]. remove: STACK [G] STACK [G]
[x]. item: STACK [G] G
[x]. empty: STACK [G] BOOLEAN
[x]. new: STACK [G]
AXIOMS
For all x: G, s: STACK [G]
[x]. (A1) item (put (s, x)) = x
[x]. (A2) remove (put (s, x)) = s
[x]. (A3) empty (new)
[x]. (A4) not empty (put (s, x))
PRECONDITIONS
[x]. remove (s: STACK [G]) require not empty (s)
[x]. item (s: STACK [G]) require not empty (s)
The power of ADT specifications comes from their ability to reflect only the essential properties of data structures, without unnecessary detail. The stack specification given above expresses everything one essentially needs to know about the concept of a stack, and includes nothing pertaining to any particular stack implementations. This is the whole truth about stacks, and nothing but the truth.
Such specifications define a general model of computation on the corresponding data structures. The functions defined in an abstract data type specification allow us to build complex expressions, and the ADT axioms allow us to simplify such expressions and obtain simpler results. A complex stack expression is the mathematical equivalent of a program, and the process of simplification is the mathematical equivalent of the computation or execution of that program.
Here is an example. Consider, for the STACK ADT specification given above, the following expression stackexp:
item (remove (put (remove (put (put (
remove (put (put (put (new, x1), x2), x3)),
item (remove (put (put (new, x4), x5)))), x6)), x7)))
Apparently, the expression stackexp will be easier to understand if we represent it as a sequence of auxiliary expressions:
s1 = new
s2 = put (put (put (s1, x1), x2), x3)
s3 = remove (s2)
s4 = new
s5 = put (put (s4, x4), x5)
s6 = remove (s5)
y1 = item (s6)
s7 = put (s3, y1)
s8 = put (s7, x6)
s9 = remove (s8)
s10 = put (s9, x7)
s11 = remove (s10)
stackexp = item (s11)
Whichever variant of the definition you choose, it is not hard to reconstruct from it the computation of which stackexp is the mathematical model: create a new stack; push the elements x1, x2, x3 onto it (in the order given); remove the top element (x3), calling the resulting stack s3; create another empty stack, and so on. This process is represented graphically in .
One can easily find the value of such an ADT expression by drawing a sequence of several such figures. (Here x4 is found.) But the theory allows us to obtain this result formally, without resorting to figures, but simply by successively applying the axioms to simplify the expression, until further simplification becomes impossible. For example:
[x]. Apply A2 to simplify s3 - i.e., replace remove(put (put (put (s1, x1), x2), x3)) with the expression put (put (s1, x1), x2)). (According to A2, any remove-put pair can be dropped.)
Fig. 6.5. Manipulations with the stack
[x]. By the same axiom, s6 equals put(s4, x4). Then one can apply axiom A1 and deduce that y1, i.e. item(put(s4, x4)), is in fact equal to x4, thereby establishing (as indicated by the arrow in the figure) that s7 is obtained as a result of pushing x4 onto the top of the stack s3.
And so on. The sequence of such simplifications, performed mechanically just as easily as a sequence of simplifications in elementary arithmetic, will lead to the value of the expression stackexp, which is indeed equal to x4 (try to verify this yourself by carefully carrying out the whole simplification process).
This example allows us to note one of the most important theoretical roles of abstract data types: they provide a formal model for the notions of a program and program execution. This model is purely mathematical: it contains no imperative notions of program state, variables with values that change over time, or a sequence of executed actions. It is based on the ordinary mathematical methods of expression transformation.
So, we have a starting point - an elegant mathematical theory for modeling data structures and, as we have just seen, programs in general. But our goal is software architecture, not mathematics or even theoretical computer science! Have we strayed from our path? Not at all. In the search for a suitable modular structure based on object types, ADTs provide a high-level description mechanism that is independent of implementation details. This will lead us to the fundamental structures of OO technology.
In the search begun in , ADTs will serve as the direct basis for modules. More precisely, an OO system will be built (at the level of analysis, design, and implementation) as a collection of interacting, partially or fully implemented ADTs. The basic notion here is the class:
Definition: class
A class is an abstract data type equipped with some (possibly partial) implementation
Thus, to obtain a class, we must build an ADT and decide how to implement it. An ADT is a mathematical notion, while an implementation is its computer-oriented version. The definition given above, however, states that the implementation may be partial. The terms introduced below make it possible to separate this case from a fully implemented class:
Definition: deferred and effective classes
A fully implemented class is called effective. A class that is only partially implemented, or not implemented at all, is called deferred. Every class is either deferred or effective.
To obtain an effective class, all implementation details must be provided. For a deferred class, one can choose a certain level of implementation while leaving some implementation aspects incomplete. In the most extreme case of partial implementation, one can forgo making any decisions about refining it at all. In that case, the resulting class will be fully deferred and will be equivalent to an ADT.
How to Create an Effective Class
Let us first consider effective classes. What needs to be done to implement an ADT? The resulting effective class will be formed from elements of three kinds:
[x]. (E1) The ADT specification (a set of functions with the corresponding axioms and preconditions describing their properties).
[x]. (E2) The choice of representation.
[x]. (E3) A mapping from the set of functions (E1) to the representation (E2) in the form of a set of mechanisms (or components ("features")), each of which implements one of the functions in terms of the representation while satisfying the axioms and preconditions. Many of these components will be methods - ordinary procedures - but some may appear as data fields or "attributes" (this will be shown in later lectures).
For example, for the STACK ADT we can choose, as the representation (step E2), the solution named above ARRAY_UP, in which each stack is implemented by the pair
,,
where representation is an array, and count is an integer. When implementing the functions (E3), we will have procedures for the functions put, remove, item, empty, and new, performing the corresponding actions. For example, the function put can be implemented by a program of the form
put (x: G) is -- Push x onto the stack. -- (without checking the stack for possible overflow.) do count := count + 1 representation [count]:= x end
Combining the elements obtained in items (E1), (E2), and (E3) yields a class - the modular structure of object technology.
The definition of an effective class must include complete implementation information (items E2 and E3). If it is incomplete in any way, then the class is deferred.
The more "deferred" a class is, the closer it is to an ADT dressed in some syntactic clothing that is more likely to win the approval of software developers than of mathematicians. Deferred classes are particularly useful in analysis and design:
[x]. In OO design, many implementation aspects will be omitted; the design should focus on high-level architectural properties - on what functionality each module of the system provides, rather than on how it does so.
[x]. As we gradually move toward a full implementation, more and more of its properties will be added until an effective class is obtained.
But this is not the end of the role of deferred classes; even in a fully implemented system, many such classes can often be found. Something follows from the applications just listed: when effective classes are obtained from deferred ones, there is a desire to keep them as ancestors (in the sense of inheritance) of the effective classes, as a living memory of the analysis and design process.
Very often, when software is developed using non-OO approaches, the finished system contains no record whatsoever of the considerable effort that went into producing it. For those who will have to maintain such a system - extend, port, debug it - understanding it without these records will be as difficult as it is for a geologist to understand a visible landscape without access to the sedimentary layers. One of the best ways to provide the information needed for system maintenance is to retain the deferred classes in its final form.
Deferred classes also have a use that is entirely related to implementation. They serve to classify groups of related object types, provide some of the most important reusable high-level modules, capture the common behavioral properties of many variants, and play a key role (together with polymorphism and dynamic binding) in ensuring the decentralization and extensibility of the software architecture.
The next few lectures, which introduce the basic OO methods, will focus on effective classes. But we should keep in mind the notion of a deferred class, whose importance will grow as we master the full power of the OO method.
A particularly interesting consequence of the OO policy in which modules are based on implementations of ADTs (classes) is that it gives a clear answer to a question that remained unresolved when discussing information hiding: how should we separate the public and hidden properties of a module - the visible and invisible parts of the iceberg?
Fig. 6.6. ADT view of a module under information hiding
If a module is a class obtained from an ADT, the answer is clear. Of the three parts involved in this evolution, E1 - the ADT specification - is public, while E2 and E3 - the choice of representation and the implementation of the ADT functions in terms of that
продолжение следует...
Часть 1 6. Abstract Data Types (ADT)
Часть 2 Moving Toward a More Imperative Point of View - 6.
Comments