🚀 go-pugleaf

> How big should a set be?
> 
> Wirth created the idea of a bitset because it would be easy to implement
> a very efficient way to do sets the size of the computer's word.  This
> means sets are likely to be 8, 16 or 32 bits, possibly other sizes,
> depending on the implementation.
> 
> Bruce MacLennan in his book, Principles of Programming Languages presents
> an idea which I quite agree with.  "The only reasonable numbers are zero,
> one, and infinity."
> 
> Since zero and one are not very usefull numbers when you're dealing with
> sets ( they're rather special case sets ), I would propose a that the limit
> be infinity.  The actual limit would be dependant on the available memory
> for storing the set, but it could be a very large number.  Since the type
> of each set is known, the compiler could determine how much memory is
> required to store the set.  Now, we have the ability to say something
> like SET OF CARDINAL, since most implementations have cardinal values of
> 0 .. 65535.  If you were to store one member per bit, the entire set
> could be represented in 8k {of memory, assuming 8 bit bytes.  This is a
> reasonable size block of memory to consider even on older 8 bit machines.
> 
>                                                      Tom Ruby
>                                                   MSRS002@ECNCDC

Hear hear! The only reason for limiting set sizes is to reduce (by a tiny
amount) the work required to implement the compiler. Long bit vectors are
not difficult to implement, and can be very useful. The presence of long
bit vectors in no way reduces the efficiency of short bit vectors, so it
is fallacious to claim that set sizes must be limited for efficiency
reasons. The element type of a set should be able to be ANY SCALAR TYPE
including LONGINT and LONGCARD (and, of course, CHAR).

That being said, I must give some credit to the opposition. I think the
proposal here is that these long sets be implemented as bit vectors. It
certainly is a major problem for the compiler implementer if they are to
be anything else. Long bit vectors are NOT an efficient way to represent
large sparse sets, but they are a nice way to handle large dense sets like
bitmaps. Any user who has an application for large sparse sets should
choose some other representation (such as binary trees) and write a
module to handle them.

Now for the crux of the matter. I believe that it should be explicit in
any eventual Modula-2 standard that "sets" are indeed "bit vectors". It
is simply not possible to choose an implementation for large sets that
will handle every application well, so the language-supported implementation
(if there is to be one at all) should be the simplest available.

Stuart Lomas
Myrias Research Corporation
Edmonton, Alberta, Canada
{ihnp4,ubc-vision,rutgers}!alberta!myrias!sjl