Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/18/84; site rochester.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!allegra!mit-eddie!think!harvard!seismo!rochester!quiroz
From: quiroz@rochester.UUCP (Cesar Quiroz)
Newsgroups: net.lang.mod2
Subject: Re: large SETs desired
Message-ID: <12107@rochester.UUCP>
Date: Mon, 7-Oct-85 00:04:51 EDT
Article-I.D.: rocheste.12107
Posted: Mon Oct  7 00:04:51 1985
Date-Received: Tue, 8-Oct-85 04:19:12 EDT
References: <43@noscvax.UUCP>
Reply-To: quiroz@rochester.UUCP (Cesar Quiroz)
Distribution: net
Organization: U. of Rochester, CS Dept.
Lines: 47
Keywords: Sets, Bits and Not The Meaning of 42
Summary: Sets better left out. Lower level prims. deemed OK.

In the posting of the reference, the problem of supporting reasonably 
large sets is considered.  A comment is also made as to BITSETs being
a good starting point for that.  I want to add a few of my own opinions,
in the hope of public scrutiny. 

Sets are a Good Thing To Have only if you can manage to use them without
undue hassle.  Pascal first and the Modula2 provide powerful *paper* set 
types, that become much less useful thanks to not being supported beyond
the width of a machine's word (just a few elements).  This, of course,
doesn't prevent competent implementors from doing things in a more usable
way, but this still makes the portability-minded user beware.  And so those
enlightened users end up writing routines that amount exactly TO THEIR OWN
IMPLEMENTATION OF SETS!

Now there is a reason for this (so I think).  Doing Sets right in all their
glory is hard.  In some broad sense, it is similar from doing strings right.
Representations that are good for one application slow down another and 
the decision is hard (or impossible) to make statically (at compile time).
So it is almost sure that a good number of applications will end up requiring
a different set implementation.

Why this happens may be left open for discussion.  At any rate, my preference
here would be to left Sets (and Strings, for that matter) out of the language,
but support them with adequate primitives (usable for more than implementing
sets) and standard libraries (you can find a few implementation options that
cover most of the applications).

This connects to the last point, the support for bit strings.  Saying that
*sets* are a good mechanism to handle *bits* is going backwards atrociously.
When you need to think of *bits*, the least you want is something else to
get in your way.  I barely remember that I used to be very pleased with the
way bit-strings were implemented in AlgolW and still think that that is the
way to go.  Provide the ability to refer to arrays of bits (and guarantee
only that they are densely packed in an implementation dependent way, so they
may be different from array of [0..1]) and provide a reasonable way to
denote constants (i.e., "masks") and you get an abstraction that can be 
conveniently mapped to something sensible in most architectures and that 
allows you to write at least one implementation of sets-of-reasonable-length
as a standard library.

Cesar
-- 
Cesar Augusto  Quiroz Gonzalez

Department of Computer Science     {allegra|seismo}!rochester!quiroz
University of Rochester            or
Rochester,  NY 14627               quiroz@ROCHESTER