Thread View: comp.lang.modula2
2 messages
2 total messages
Started by news
Thu, 17 Sep 1987 21:59
Re: Number of elements in a set
Author: news
Date: Thu, 17 Sep 1987 21:59
Date: Thu, 17 Sep 1987 21:59
47 lines
3082 bytes
3082 bytes
>It
>is not hard to implement sets of effectively unbounded size; further, it is
>usually more efficient, and certainly more readable and useful to have large
>sets than to simulate this with the corresponding user code.
Right! In addition to that you cannot use operators like +, -, /, *,
IN and { ... } on larger sets implemented as user data types, they are
*nonportable* and *inefficient*. Built-in Modula-2 sets are
syntactically much better than Pascal's sets. It is unfortunate that
they are so poorly implemented.
As existing Modula-2 compilers usually don't allow large sets, you
cannot even write a (portable) compiler that uses the method of
passing sets of stopping symbols as parameters to the parsing
procedures. This method is used for error recovery in many Pascal
compilers (written in Pascal).
And how about being able to say: VAR screen[8000H]: SET OF [0..768*512-1] ?
The potential applications of large sets are numerous.
> The British Standards Institute Modula-2 Standardisation effort is
>working on changing the language definition to open up sets to at least
>include enough memebers to define SET OF CHAR. Progress is being made at a
>glacial pace on this . . .
Sarcastically you could imagine the following reasoning behind this
decision:
"These one-word sets, aren't they a little too restricting? Let's
represent sets as the bits of an *array* of words."
"Yes, but let's not generalize too much: surely there must be some upper
limit on the size of this array. Shall we say *four* 32-bit words?"
The point is: because the size of the set is always known at compile
time, the size of this array can also be determined at compile time.
If you only use small sets that fit in one word, then you don't even
need an array: *no* runtime overhead. Even indexing the array can be
efficient, on a 32-bit machine, divide the number of the bit to be
tested/included/excluded/etc. by 32, that is, shift the bits five
places to the right. And if you are accessing a constant member of the
set then you don't even have to do that, the compiler can figure out
the address of the word in which to look for the appropriate bit.
-----------------------------------------------------------------------
Johan Myreen UUCP: ...!mcvax!hutcs!jem
Bistervagen 6 B 416 Bitnet: jem%hutcs.uucp@fingate.bitnet
SF-02150 Esbo, Finland Internet: jem@hutcs.hut.fi
Re: Number of elements in a set
Author: Erik van Konijnenburg
Date: Tue, 22 Sep 1987 09:52
Date: Tue, 22 Sep 1987 09:52
124 lines
5507 bytes
5507 bytes
In article <8709192023.AA27593@jade.berkeley.edu>, jem@hutcs.hut.fi writes:
> As existing Modula-2 compilers usually don't allow large sets, you
> cannot even write a (portable) compiler that uses the method of
> passing sets of stopping symbols as parameters to the parsing
> procedures. This method is used for error recovery in many Pascal
> compilers (written in Pascal).
>
> And how about being able to say: VAR screen[8000H]: SET OF [0..768*512-1] ?
>
> The potential applications of large sets are numerous.
Yep. But, as you say, your code won't be very portable, since
now you not only depend on the accepted size of the set, but
also on its implementation (that it is implemented as a bitmap,
and assumptions about which set element is which pixel).
Our VAX and mc68020 compilers allow 524288 elements in a set
value, the amount that can be moved by an efficient copy loop,
so your screen would fit with room to spare, but you are still
being forced to accept an arbitrary limit.
The only inherent limit to the size of a Modula-2 set is that
the base type must be representable. Because the set size is
known at compile time, this should not be a performance issue
except for _very_ large sets as complex code will only need to
be generated for those specific cases.
Part of the task of a standardisation committee is to define a
standard that can be accepted by a majority of users (that is,
implementors as well as programmers). If this involves the
inclusion of minimal requirements for values of data types,
these really must be _minimal_. Current Modula-2 practice is
based on Wirth's "Programming in Modula-2" which states that
the maximal set size is a _small_ constant determined by the
implementation, usually the computer's word size, or a small
multiple thereof (ed. 2 page 147, ed. 3 page 150).
In view of this, and assuming that it should be specified in
the standard at all, a minimum set size of 128 or 256 might
be a reasonable requirement (though _any_ value will lead to
endless discussion). These values are still arbitrary, but
arguably make _some_ sense because of current character set
sizes (though what about Japanese?), and can be implemented
on any(?) machine.
Requiring an implementation to support a set size determined
by the value of MAX(INTEGER), as was suggested, can hardly be
called minimal.
Defining the minimum in terms of CHAR, as was also suggested,
would probably not be a good choice either, as CHAR itself is
implementation dependent. If a minimum set size is indeed
felt to be necessary perhaps it should be something along the
lines of "A minimal conforming implementation will support
set values of at least (some number, e.g. 256) elements,
however, it is recommended that such an implementation
support SET OF CHAR".
Compilers that are intended for serious work will of course
have to set their own limits (and given the growth in screen
sizes, we may have to increase ours pretty soon :-).
By the way, what about the minimum size of ARRAY types ...
(don't answer that!)
---------
Erik van Konijnenburg, <konijn@ace.nl>, ...!mcvax!ace!konijn,
ACE Associated Computer Experts bv, Amsterdam, the Netherlands
The article really stops here.
You had the signature already.
Don't forget about the 'n' key.
F.y.i. this is a brief summary of an article that appeared in
comp.newprod.
Subject: announcing the ACE Modula-2 compiler
- strict adherence to the language, the only extension is the inter-
face to C-compatible subroutines such as from the Unix system-
call library.
- accepts edition 2 and edition 3, including NEWPROCESS, TRANSFER
and IOTRANSFER.
- high reliability, through a proprietary validation suite as well
as through the BSI validation suite for which ACE is a beta-test
site.
- easy reconfiguration, allowing most runtime support routines to
be redeclared.
- good run-time checking: falling out of functions, NIL pointer
dereferencing, missing defaults in case statements, range errors,
uninitialised variables etc., are all checked.
- amongst others, a Unix interface module and Wirth's I/O modules
are available as Modula-2 source.
- comprehensive documentation including all implementation defined
decisions and how to interface to Unix and standalone systems.
- a global optimiser that performs constant folding, expression
reduction, size-conversion elimination and common sub-expression
and loop-invariant code detection and other optimisations.
- a register allocation optimiser
- a peep-hole optimiser
- IEEE floating point
- Motorola 68020 code generation
- Motorola 68881 support
- generation of COFF or a.out images
- mixing of code from different languages
- available native on 68K and VAX Bsd and cross for 68K on
VAX Bsd, VAX VMS and Gould
Thread Navigation
This is a paginated view of messages in the thread with full content displayed inline.
Messages are displayed in chronological order, with the original post highlighted in green.
Use pagination controls to navigate through all messages in large threads.
Back to All Threads