From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.3 required=5.0 tests=BAYES_00,INVALID_MSGID autolearn=no autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 103376,955fad43713fdf44 X-Google-Attributes: gid103376,public From: mheaney@ni.net (Matthew Heaney) Subject: Data Structures as ADTs (was: NFA to DFA) Date: 1996/05/16 Message-ID: #1/1 X-Deja-AN: 155092915 references: <4n1its$rtt@news2.h1.usa.pipeline.com> <31973BF5.41C67EA6@avions.aerospatiale.fr> <31987C20.167EB0E7@escmail.orl.mmc.com> organization: Estormza Software newsgroups: comp.lang.ada Date: 1996-05-16T00:00:00+00:00 List-Id: In article <31987C20.167EB0E7@escmail.orl.mmc.com>, "Theodore E. Dennison" 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