Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/17/84; site nbires.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!allegra!mit-eddie!think!harvard!seismo!hao!nbires!rcd
From: rcd@nbires.UUCP (Dick Dunn)
Newsgroups: net.lang.mod2
Subject: Re: large SETs desired
Message-ID: <132@nbires.UUCP>
Date: Tue, 15-Oct-85 05:13:09 EDT
Article-I.D.: nbires.132
Posted: Tue Oct 15 05:13:09 1985
Date-Received: Sat, 19-Oct-85 03:56:39 EDT
References: <43@noscvax.UUCP> <12107@rochester.UUCP> <212@rtp47.UUCP>
Organization: NBI,Inc, Boulder CO
Lines: 38

> > 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).
> 
> Your tack seems to be that supporting sets beyond a machine word is hard
> for the compiler, and that sets should therefore be dropped.  I
> disagree...

I'll also go along with the position that multi-word sets are not that hard
to implement.  In a project using a language based on Pascal some years
ago, we implemented LARGE sets--the upper limit on set size was (for some
arcane reasons) 100 000 000 elements.  This is more nearly a storage
limitation than a limit on set size, and certainly answers most desires for
large sets!  It did, however, introduce two restrictions which were not
present in Pascal's set mechanism:

	- First, the basetype of a set was required to be evident from its
	  left context.  This was due in part to the simplistic analysis in
	  the compiler we were using.  It turns out to be a very odd re-
	  striction to explain but one which causes no trouble in practice.
	  An example of a statement violating the constraint is
		if [1,3,5]=S1 then ...
	  (which can be fixed by exchanging the operands of =)
	  The constraint is always met in assignments and procedure calls.
	  We could have eliminated it.
	
	- Second, set types were considered distinct if their basetypes
	  were distinct.  This avoids the problems associated with
	  performing set operations on sets with, say, disjoint basetypes
	  which are nonetheless subranges of the same parent type.  This is
	  an area in which Pascal is surprisingly (needlessly?) lenient,
	  and may be one of the reasons that large sets are not allowed--
	  all sets would have to be maximum size, where in our scheme sets
	  were stored in the smallest natural storage unit that would
	  contain the required number of bits.
-- 
Dick Dunn	{hao,ucbvax,allegra}!nbires!rcd		(303)444-5710 x3086
   ...Simpler is better.