| Date: Wed, 13 Apr 2005 11:44:07 -0700 (PDT)
 | From: bear <xxxxxx@sonic.net>
 |
 | 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
  arrays.

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.