I’ve been learning object-oriented concept from this book, and stuck in a specified concept in the middle of chapter 6.

Because with no brief explaining beforehand, no one could understand my question; so I’m giving it first.

The purpose of chapter 6 is *teaching how to describe objects* by *using abstract data descriptions*; three criteria are given.

- The descriptions should be precise and unambiguous
- They should be complete — or at least as complete as we want them in each case(we may decide to leave some details out)
- They should not be overspecifying.

Then the author decided to demonstrate how to describe objects **in a wrong way by using physical representation**, instead of in a right way by ADTs.

Three physical representations(array up, array down, and linked list) of stack are taken as an example.

After briefly describing these three kind of stack, author then said:

In the stack example, what unites the various representations in spite of all their differences is that they describe a “container” structure, where certain operations are applicable and enjoy certain properties. By focusing not on a particular choice of representation but on these operations and properties, we may be able to obtain an abstract yet useful characterization of the notion of stack.

Then

We are interested in individual agents not so much for what they are internally as for what they have to offer to each other.

That is to say, we are interested in what operations objects can do, rather than what objects internally are. From the stack example, we interested in push and pop rather than which physical representation is that stack.

Based on this conclusion, author started to teach how to write a specification in a right way for describing objects.

Something called *abstract data type specification* is responsible for describing objects. It offers client(the user of software module) two information.

- How these operations can be used.
- What these operations will do for client.

Abstract data type specification consists of four paragraphs.

- TYPES
- FUNCTIONS
- AXIOMS
- PRECONDITIONS

Author started from types first, where is I’m stuck in; so I just paste context for not to mislead you.

## Specifying types

The TYPES paragraph indicates the types being specified. In general, it may be convenient to specify several ADTs together, although our example has only one, STACK.

By the way, what is a type? The answer to this question will combine all the ideas developed in the rest of this chapter; a type is a collection of objects characterized by functions, axioms and preconditions. If for the moment you just view a type as a set of objects, in the mathematical sense of the word “set” — type STACK as the set of all possible stacks, type INTEGER as the set of all possible integer values and so on — you are not guilty of any terrible misunderstanding. As you read this discussion you will be able to refine this view. In the meantime the discussion will not be too fussy about using “set” for “type” and conversely.

On one point, however, you should make sure to avoid any confusion: an abstract data type such as STACK is not an object (one particular stack) but a collection of objects (the set of all stacks). Remember what our real goal is: finding a good basis for the modules of our software systems. As was noted in the previous chapter, basing a module on one particular object — one stack, one airplane, one bank account — would not make sense. O-O design will enable us to build modules covering the properties of all stacks, all airplanes, all bank accounts — or at least of some stacks, airplanes or accounts.

An object belonging to the set of objects described by an ADT specification is called an instance of the ADT. For example, a specific stack which satisfies the properties of the STACK abstract data type will be an instance of STACK. The notion of instance will carry over to object-oriented design and programming, where it will play an important role in explaining the run-time behavior of programs.

The TYPES paragraph simply lists the types introduced in the specification. Here:

**STACK[G]**

Our specification is about a single abstract data type **STACK**, describing stacks of objects of an arbitrary type **G**.

## Genericity

In **STACK [G], G** denotes an arbitrary, unspecified type. **G** is called a *formal generic parameter* of the abstract data type **STACK**, and **STACK** itself is said to be a generic ADT. The mechanism permitting such parameterized specifications is known as genericity; we already encountered a similar concept in our review of package constructs.

It is possible to write ADT specifications without genericity, but at the price of unjustified repetition. Why have separate specifications for the types “stack of bank accounts”, “stack of integers” and so on? These specifications would be identical except where they explicitly refer to the type of the stack elements — bank accounts or integers. Writing them, and then performing the type substitutions manually, would be tedious. Reusability is desirable for specifications too — not just programs! Thanks to genericity, we can make the type parameterization explicit by choosing some arbitrary name, here G, to represent the variable type of stack elements.

As a result, an ADT such as **STACK** is not quite a type, but rather a type pattern; to obtain a directly usable stack type, you must obtain some element type, for example **ACCOUNT**, and provide it as *actual generic parameter* corresponding to the formal parameter G. So although **STACK** is by itself just a type pattern, the notation

**STACK [ACCOUNT]**

is a fully defined type. Such a type, obtained by providing actual generic parameters to a generic type, is said to be *generically derived*.

The notions just seen are applicable recursively: every type should, at least in principle, have an ADT specification, so **you may view ACCOUNT as being itself an abstract data type**; also, a type that you use as actual generic parameter to **STACK** (to produce a generically derived type) may itself be generically derived, so it is perfectly all right to use

**STACK [STACK [ACCOUNT]]**

specifying a certain abstract data type: the instances of that type are stacks, whose elements are themselves stacks; the elements of these latter stacks are bank accounts.

## Here is my question

I can roughly understand

**STACK[G]**

where

- STACK is a generic ADT which describe all kind of STACK, and STACK is not quite a type, but rather a type pattern
- G is a type with arbitrary and unspecified, called formal generic parameter.
- We can provide an actual generic parameter, in this example ACCOUNT, in place of G to obtain a fully defined type “STACK[ACCOUNT]”, which is said to be generically derived.

If I put above three in this way, why ACCOUNT itself is an abstract data type? How comes ACCOUNT at the same time is parameter as well as abstract data type?

I cannot figure out author’s mind, let alone STACK [STACK [ACCOUNT]]

Can you explain it to me in the author’s way? If C Code is accompanied, that would be awesome.

I’m willing to pay bounty if this feature is available in this website.