Sets in Pascal, etc.

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
1992), 18-21.)


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
          hbaker@netcom.com
--

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