1

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.

  1. The descriptions should be precise and unambiguous
  2. They should be complete — or at least as complete as we want them in each case(we may decide to leave some details out)
  3. 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.

  1. How these operations can be used.
  2. 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

  1. STACK is a generic ADT which describe all kind of STACK, and STACK is not quite a type, but rather a type pattern
  2. G is a type with arbitrary and unspecified, called formal generic parameter.
  3. 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.

  • I guess the easiest way to understand this is simply learn a programming language which provides generics (like Java or C#), or templates (like C++). Then you could play around with example programs, or make your own ones, which use types or classes exactly in the shown manner. Using standard language features of C to "simulate" generics/templates will probably only confuse you. – Doc Brown May 11 at 11:19
  • @DocBrown Thanks bro. I'm specialized in C and no need to touch OOP. I was suggested to learn C and object-oriented concept separately and I think it's a good idea. – Andy Lin May 11 at 11:24
  • In C++, one can have a generic class Stack<G>, which makes it possible to declare variables of types like Stack<int>, Stack<Account> or Stack<Stack<Account> >. – Doc Brown May 11 at 11:28
  • The concept you're describing here is that of parameterised types (type parameters -- i.e. where data types themselves are used as parameters to help write generic code). This concept doesn't really belong to the object-oriented paradigm, it belongs to the generic programming paradigm: en.wikipedia.org/wiki/Generic_programming – Ben Cottrell May 11 at 12:09
  • @DocBrown: The book's examples are in Eiffel, which is a programming language which provides generics. (In fact, Eiffel had everything Java has, five years before the design of Java even started.) – Jörg W Mittag May 11 at 12:43
4

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?

Strangely enough, for no better reason than because it happens to be one.

STACK[int] makes just as much sense. STACK is an ADT and int is a concrete primitive. You just don't find many languages that happen support that.

STACK[ACCOUNT] really isn't that different an idea. It's just that where STACK[int] tells you concretely, exactly what goes into the collection of whatever STACK, STACK[ACCOUNT] says we have some ACCOUNT like things in some STACK like thing.

a type is a collection of objects characterized by functions, axioms and preconditions

The authors choice to describe the things that can be a STACK as a set or a collection is a tad confusing because any stack is itself a collection. That's just setting the reader up for bit of pain. Those are different meanings.

When you dump things (ACCOUNTs or ints) in a STACK you are collecting them. When you have multiple things that can be STACK what you have is a type. If I have a pile of code that I called QUEUE that can do everything STACK can do I can say it's also a STACK. That puts it in the STACK type "collection". Eew, what a needless name collision.

ACCOUNT is also something that multiple things could be. BANKACCOUNT, WITNESSACCOUNT, NOCOUNT. As long as code can use them the same way without knowing what they are beyond some type of ACCOUNT they fall under the ACCOUNT Abstract Data Type. It's only because of that that ACCOUNT is an ADT. Not because we happened to shove it in a STACK.

That may leave you feeling a little unsatisfied. I suspect that's because if ACCOUNT isn't concrete then how do you know what you have? Well you don't. That's the point. If we do this right only one place gets to say what the concrete ACCOUNT or STACK thing is. That's a nice thing to pull off because it means we can make that decision in one place. We can change that decision in one place. And everything else doesn't care so it just keeps working.

In Java it'd look like this:

Stack<Account> stackOfAccounts = new Queue<Account>();
stackOfAccounts.push(new NoCount("Billy Bob"));

Now you might be thinking, wait stacks and queues behave differently. Yes they do. But so long as the using code sticks with push and pop the decision about order isn't something the using code has to control. The STACK implementation decides that.

The same with NOCOUNT. We'd normally want to keep a record of transactions but in Billy Bob's case he's not an account holder so he gets nothing. That doesn't break the system. It just makes it work differently.

In both cases the rest of the code doesn't have to know about these changes in behavior. That not knowing free's you write code that doesn't care about those decisions. That's the power of abstraction.

0

Responding to myself:

Let's put this way. If there are "only" three ways to present a stack(array up, array down, and linked list),

STACK [G]

is a notation/set/group on behalf of these three physical representations where element is unspecified.

A stack written by array up, whose element is unspecified.

A stack written by array down, whose element is unspecified.

A stack written by linked list, whose element is unspecified.

In the same manner,

STACK [ACCOUNT]

is a notation/set/group on behalf of these three physical representations where element is account.

Finally,

STACK [STACK[ACCOUNT]]

is a notation/set/group on behalf of these three physical representations where element is a stack(one of these three physical representations) whose element is account.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.