[comp.lang.pascal] Pascal sets

djones@megatest.UUCP (Dave Jones) (01/19/90)

I'm writing a Pascal compiler. I've got to be compatible with a previous
compiler, but when possible I am attempting to reconcile that with the
new ISO Standard.

I've finished most everything except for the implementation of sets, and that
has me a bit puzzled. The standard seems to dictate an implementation which
is much more involved than the usual ones. (I'm getting my info from
'Standard Pascal' by Doug Cooper, which is known not to be bugless,
and from a very old preliminary draft standard, so I may be tilting at
wind-turbines. If so, please let me know. I'm trying to obtain a new copy
of the standard, but it has yet to arrive.)

Here's the deal: Except for considerations of 'packed' and 'unpacked',
the new Standard says that sets can be compared, combined, or assigned,
provided that they have the same 'canonical set of T' type. When all
the gobbledygook is deciphered -- and believe me, it takes some
deciphering -- the 'canonical set of T' notion simply discards subrange
information. It is an 'error', (which the implementation is allowed to
disregard), if at runtime a set-expression E is assigned to a variable
or value-parameter of type 'set of R', and E contains an element not in
the range of R. (Implementations are also allowed to impose limits on the
ranges of sets.)

The following program is legal:

program foo(input, output);
  type
     t2 = set of 1..2;
     t35 = set of -35..35;
  var
     s2 : t2;
     s35: t35;
     i,j: integer;
     f: file of t35;
begin

    s35 := [1];

    { Assignment to a set with small range
    | from a potentially larger set
    }
    s2 := s35;

    { Assignment of small set to set with large range
    }
    s35 := s2;  
                

    { Combining small set with larger constructed set, then
    | assigning the combination to a still larger set.
    }
    s35 := s2 + [-20..20];


    { Comparison of sets with no obvious ranges.
    }
    i := -128;    j := 127;
    if([i..j] <> [j] ) then
       writeln('How big are constructed sets?');


    { Writing a set with a small range to a file of
    | sets with a large range.
    }
    reset(f);
    write(f, s2);

end.

Think about how you would implement this with bit-vectors of
fixed sizes. It's possible, but not nearly so simple as history
would seem to mandate.

How do the compilers you use implement sets, and how do they represent
them externally? When are sets compatible for +, -, and *, and
when are they assignment-compatible? I am particularly interested in
compilers which claim to be ISO Standard-conforming. Any anecdotal info,
example error-messages, etc., will be welcome.


     Thanks a bunch,

		Dave Jones
		Megatest Corp.
		880 Fox Lane
		San Jose, CA.
		95131

		(408) 437-9700 Ext 3227
		sun!megatest!djones

brians@hpcljms.HP.COM (Brian Sullivan) (01/23/90)

  Most of the Pascal compiliers that I know which implement the above set
constructs use one of these two methods.

  Method 1.  Used by UCSD Pascal is to require that sets by limited to 256
elements or less.  They choose 256 because it allow them to use set of char
in the compiler.  I belive that it would reject the use of a set constant
that contained an element outside the range 0..255.  In this implementation
all integer based sets are represent by a bit array of 256 bits. 


  Method 2. This method rejects any overloaded set constant.  Instead each
set constant must be qualified by the type it is a member of.  For example
your statement:

>     if([i..j] <> [j] ) then
>        writeln('How big are constructed sets?');

 would have to be written


>     if(t35([i..j]) <> t35([j]) ) then
>        writeln('How big are constructed sets?');

  For references on this method see Oregon Pascal, Microsoft Pascal and 
Meridian Pascal.

                -- Brian --