Re: Pascal compiler and sets

dallison@bfsec.bt.co.uk (Dave Allison) writes:
>How are sets usually implemented in Pascal? Is there a small limit placed
>on the size of sets? I can think of a number of implementation methods,
>but would like to see how it is normally done so that I dont have to do
>much more work.


samiam@netcom.com (Scott Moore) writes:
=> Gee, I was hoping (for your sake) that sets would not be included in your
=> subset:)


Yep, sets is one of the parts in PASCAL where one has to think twice.
In contrast to some, I did see people use PASCAL set like:
s = set of [-4096 .. 4095 ];


For my runtime lib I decided to allow sets as big as memory takes, with a
starting elements some where in the full integer range. The elements of
the set are alligned on (index mod 32) ranges. Thus making operations on
mixed set possible without having to shuffel bits within the subblocks.


In Pascalish the structure would look like:
record
size :integer;
offset :integer;
bits :array of [0..<open>] of integer.
end


where (offset mod 32) gives the starting position of the actual set in the
bits[0] part.


When the size of sets can be calculated at compile time, only just enough
storage is allocated. Set constants are also stored in minimum size.


This allows a relatively efficient implementation for dense sets. Sparse
set are perhaps beter done using something like tree-sets. But it's rather
impossible to see compile time if a large set is going to be dense or not.


The only real problem is in (constant) set expressions. Unless you'd do
those at compile time as well. Doing them runtime requires a bit of extra
work in detecting what the size of the intermediate results is.


The problems is that you might have to allocate a real large set on the
fly when doing some thing like:
s1 := (s1-s2) * (s3-s4)
(where al sets are very very big)


Now the last "problem" is the EMPTY set, which is just any set with it's
size set to "0", or a regular set with normal size but none of the bits
on. This require a little bit of special code in the set operators, but
it stands for an efficient implementation.


=> if x in [102355..934343433] then writeln('Boy, this is some compiler');


Thank you.
--
Digital Information Systems Group, Tel: +31-40-473401, Fax: +31-40-433066
Room EH 10.35 Eindhoven University of Technology
P.O. 513, 5600 MB Eindhoven, The Netherlands
Internet:wjw@eb.ele.tue.nl, X400:C=nl;A=400net;P=surf;O=tue;OU=ele;OU=eb;S=WJW;
--

Return to the comp.compilers page.
Search the comp.compilers archives again.