Re: arithmetic issues John.Cowan 23 Oct 2005 16:02 UTC

Thomas Bushnell BSG scripsit:

> > Thomas Bushnell BSG scripsit:
> >
> >> > Can you live with 2^24?
> >>
> >> No.  Have you heard of sparse arrays?  They need indices too.
> >
> > Sparse arrays are not a fundamental R[56]RS type like strings and vectors.
> > The question is whether these native types need to be Really Really Big.
>
> Huh?  Sparse arrays are an *implementation* not a datatype.

Granted, Scheme vectors could be implemented as sparse arrays (and Scheme
strings as cords).  For that matter, both could be implemented as lists,
given a magic first cell that makes them disjoint from Scheme lists.
And for that mattter, Scheme lists could be implemented as machine-level
vectors, provided you are willing to live with all the behind-the-scenes
copying that would be required.  Numbers could be Church numerals, and so on.

But if Scheme vectors don't have O(1) performance (actually O(log k) on
modern hardware) in a given implementation, users are likely to vote
with their feet.

--
A rabbi whose congregation doesn't want         John Cowan
to drive him out of town isn't a rabbi,         http://www.ccil.org/~cowan
and a rabbi who lets them do it                 xxxxxx@reutershealth.com
isn't a man.    --Jewish saying                 http://www.reutershealth.com