bit vectors, exact integers, and sets

*Brad Lucier* 24 Jul 2002 07:06 UTC

The SRFI says
<excerpt>
- This is a purely functional, side-effect-free implementation of bit
operations -- all operations produce new, fresh results, rather than
modifying old values. This can be implemented very efficiently for small
bit vectors -- small enough to be unboxed values. Algorithms that work
on larger bit vectors, however (such as data-flow analysis engines), might
wish an alternate data-structure and associated set of operations that
permits side-effecting or linear-updating operations (or both) on bit
vectors. MIT Scheme, for example, provides such a facility. This should
be considered for another SRFI. (See the short summary of the MIT Scheme
system below.)
I suggest that the design of such a system be deferred until SRFIs for
strings and vectors have been finalised. Than a bit-vector SRFI could
be designed that would preserve common structure with these other SRFIs,
as well as the bitwise library in this SRFI.
Note also that finite bit vectors have an isomorphism to finite sets.
The design of both set-package and bit-vector SRFIs would probably want to
keep this in mind -- maintaining parallel functional structure in the
design.
</excerpt>
I don't think bit-vectors are that useful; you should stick with
<excerpt>
Bitstrings are represented by integers, using a two's-complement encoding of
the bitstring. Thus every integer represents a semi-infinite bitstring, having
either a finite number of zeroes (negative integers) or a finite number of
ones (non-negative integers).
</excerpt>
Bitstrings represents sets of integers that are either finite or have finite
complements. These seem to have very little to do with strings and vectors.
Brad