[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Update, near finalization
| 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
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.