Sets in Pascal, etc. (Henry G. Baker)
Wed, 9 Feb 1994 17:19:29 GMT

          From comp.compilers

Related articles
Pascal compiler and sets (1994-02-08)
Sets in Pascal, etc. (1994-02-09)
Re: Sets in Pascal, etc. (1994-02-11)
| List of all articles for this month |

Newsgroups: comp.compilers
From: (Henry G. Baker)
Keywords: Pascal
Organization: NETCOM On-line Communication Services
References: 94-02-051
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
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


Post a followup to this message

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