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

Re: Update, near finalization

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

 | Date: Wed, 13 Apr 2005 11:44:07 -0700 (PDT)
 | From: bear <bear@xxxxxxxxx>
 | On Mon, 11 Apr 2005, Aubrey Jaffer wrote:
 | >But this pissing contest should be largely irrelevant to R6RS --
 | >SRFI-63 is more capable (uniform arrays), better integrated with
 | >R5RS (specifying vector, string, and EQUAL? behavior), compatible
 | >with SRFI-58 array syntax, and better designed than SRFI-25.
 | Actually, I think that specifying string behavior in a document
 | about arrays is a mistake.
 | The operations we want to do on strings are in many cases
 | fundamentally different from the operations that are efficient to
 | do on arrays.  For example, inserting or deleting text at an
 | arbitrary point in the string are two of the most fundamental
 | operations in text editing, and if strings are represented as
 | arrays, they require the program to touch all subsequent characters
 | in the string every time one character is inserted or deleted.

I had similar thoughts writing the initial version (Nov 2004) of
SRFI-63; and put in its issues section:

  I removed character arrays (from SRFI-47) because, as I read R5RS,
  the number of distinct characters an implementation supports need
  not be finite; thus character elements might require an unbounded
  size of representation.

  Character arrays are can be supported based on strings; but they do
  not necessarily have access times comparable to other types of

But then I realized that access of shared arrays of vectors mandates
separation of the rank-n to rank-1 index calculation from the vector
access.  Since array-ref and array-set! must be able to separate index
calculation from vector access, this same principle can be used to
separate index calculation from string access.

The bounds which SRFI-63 gives for access time are the bounds for this
separated access:

  Except for character arrays, array access time is O(R)+V, where R is
  the rank of the array and V is the vector access time.

  Character array access time is O(R)+S, where R is the rank of the
  array and S is the string access time.

Thus SRFI-63 does not constrain the representation of strings.  An
implementation is welcome to employ representations with faster
ARRAY-REF and ARRAY-SET! than STRING-REF and STRING-SET!, but must not
have slower ones.