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: jsa@organon.com (Jon S Anthony) Subject: Re: NFA to DFA Date: 1996/05/15 Message-ID: #1/1 X-Deja-AN: 155025216 sender: news@organon.com (news) references: <4n1its$rtt@news2.h1.usa.pipeline.com> organization: Organon Motives, Inc. newsgroups: comp.lang.ada Date: 1996-05-15T00:00:00+00:00 List-Id: In article <3199D093.41C67EA6@escmail.orl.mmc.com> "Theodore E. Dennison" writes: > > > ARRAYS of boolean in a bitwise fashion. So why bother with some fancy > > > generic ADT package (that might have bugs)? > > > > Simple. If the universe over which you can construct sets is "big", > > but the sets themselves are typically not "so big" relative to the > > universe (the cardinality of the compliment of any set >> cardinality > > of the set - at least typically...) then the array of boolean impl. > > offers poor quality of service (maybe not even plausible...). Also, > > What? You don't LIKE bit arrays that take up 1/8th of your virtual > memory space? :-) > > O.K. But most Modula-2 compilers couldn't handle sets that large either. I believe that the original "definition" of Modula-2 by Wirth had sets being completely lame and virtually useless. They had to fit within a single "machine word". To get sets that were actually useful (in anything like a typical range of applications) you had to build your own - i.e., build a set ADT. Typically this was _implemented_ using the basic set type. This gave you a kind of poor-man's "equivalent" to what you get in Ada with packed arrays of boolean for free. > What you are describing is more of a list than a set. An ADT would be > put to good use in making a list look like a set. Well, I'm not really describing anything - not enough detail for that. But, I am talking about a _set_ type - its implementation (whether by lists or what have you) is not relevant. That is why a set ADT makes sense. You can have the abstraction and the impl. can vary - as I mentioned, in Ada95 it can even vary at runtime. /Jon -- Jon Anthony Organon Motives, Inc. 1 Williston Road, Suite 4 Belmont, MA 02178 617.484.3383 jsa@organon.com