[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

bit vectors, exact integers, and sets

This page is part of the web mail archives of SRFI 33 from before July 7th, 2015. The new archives for SRFI 33 contain all messages, not just those from before July 7th, 2015.



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