Data Structures as ADTs (was: NFA to DFA)

[mheaney@ni.net (Matthew Heaney)]

In article <31987C20.167EB0E7@escmail.orl.mmc.com>, "Theodore E. Dennison"
<dennison@escmail.orl.mmc.com> wrote:

>JEAN CLAUDE GALLO wrote:
>> 
>> Boaz Chow wrote:
>> >
>> > do you know how to implement SET adt and the operations in Ada?
>> >
>> 
>> generic packages
>> You may found examples of SETS in "Software Components with Ada"
>> (G.Booch). He explain theory of Set algorithm and Ada83 generic packages
>
>Being an old Modula-2 programmer (where Sets are basic structure types,
>like records), I have several times sat down to implement a generic
>SET ADT package. Every time, I have discovered that arrays of boolean
>give me exactly what I want with one simple type declaration. This
>is because Ada defines the boolean operators AND and OR to work on 
>ARRAYS of boolean in a bitwise fashion. So why bother with some fancy
>generic ADT package (that might have bugs)?

Well, then, why bother with abstraction at all?  Why even bother programming 
in a language that offers direct support for programmer-defined abstractions?

The whole point is that an abstract data type hides inessential information
from the complexity-challanged human programmer.

Indeed, the whole purpose of "software engineering" is to figure out what
tools humans need to build large, complex systems constructed from
software.  Abstract data types are in fact one of those tools; witness the
popularity of object-oriented programming.

There's a hidden assumption in the statement that "some fancy  ADT package might
have bugs": that you could do it some other way, not using an ADT, and
have fewer bugs.

But just the opposite is true: not only will the system you build without
using ASTs have more bugs, you might very well fail to get the system even
built!

Time and time again I've seen programmers use an array as a data structure, when
they should have been using an abstract data type.  You have to consider
much more
state information when manipulating arrays than you do when manipulating a
higher-level (more abstract) structure, so the likelihood of an error is
much, much greater.

If you don't believe me, then read

   Data Structured Programming: Program Design without Arrays and Pointers
   Harlan D. Mills and Richard C. Linger
   IEEE Transactions on Software Engineering, Vol SE-12, No 2, Feb 1986

  On the Criteria To Be Used In Decomposing Systems into Modules
   D.L. Parnas
   Communications of the ACM, Dec 1972

and while you're at it, be sure to read

   The Magical Number Seven, Plus or Minus Two: 
    Some Limits on Our Capacity for Processing Information
   G.A. Miller
   The Psychological Review, 1956


Booch specifically includes a form for discrete types, which is *implemented*
as you suggested: as an array of Booleans.  See the discussion of The
Discrete Form
in Chapter 10, Sets and Bags, of his book Software Components with Ada.

The rule is: Never use an array, or a linked list for that matter, as a
data structure; they
are much too primitive.  Use an array or linked list only to *implement*
data structures that are abstract data types.

Now ya know!

Matt

--------------------------------------------------------------------
Matthew Heaney                       Estormza Software
Software Development Consultant      4765 Bellflower Ave F
mheaney@ni.net                       North Hollywood CA 91602
                                     (818) 985-1271