|Pascal compiler and sets email@example.com (1994-02-08)|
|Sets in Pascal, etc. firstname.lastname@example.org (1994-02-09)|
|Re: Sets in Pascal, etc. email@example.com (1994-02-11)|
|From:||firstname.lastname@example.org (Henry G. Baker)|
|Organization:||NETCOM On-line Communication Services|
|Date:||Wed, 9 Feb 1994 17:19:29 GMT|
When I taught Pascal, I found sets to be extremely useful, but I also
found their arbitrary size limitations very irritating.
For twenty years, I have been one of the champions of extending boolean
operations to Lisp's bignums, which then have the capability of emulating
any finite (positive) or co-finite (negative numbers) set.
Most implementations of Lisp make these operations very efficient, and I
believe that the logical operations on bignums in the Lisp Machines used
the same code as bitblt.
As one example of the use of these logical bignums, I made Baskett's
"puzzle" benchmark (one of the Gabriel benchmarks) run an order of
magnitude faster through bit-vectors. (ACM Lisp Pointers V,3 (Jul/Sep
Compiler people doing lattice operations require high performance
bitvector operations, as well.
Vaughan Pratt's Lingol natural language parser makes heavy use of
bit-vectors to incorporate top-down information in a bottom-up parser.
A word on set implementation. While you might get a "bit" higher
performance from sets which are specialized for the number of elements, I
have found that the bignum approach can wring most of the performance from
a processor (when properly implemented--ACM Lisp Pointers 3 (Apr/Jun 1990)
8-22), and thus multiple implementations for sets of different sizes is
not necessary. The one exception to this would be when the set is
representable within one word.
-- Henry Baker
Return to the
Search the comp.compilers archives again.