William D Clinger wrote:
> I do think most implementors have enough brains to provide
> efficient O(1) amortized time string-ref,
Well, there may be constraints that complicate that. For example
a Java-based implementation may want to use java.lang.String
for immutable strings. The implementations of java.lang.String
is fixed and inaccessible. Java provides O(1) access for
UTF-16 code points, but not Unicode scalar values. One can
get O(1) by adding extra data - but then one is adding an extra
object and thus extra space for each String, plus one loses some
level of compatibility/interoperability with Java. One can restrict
use of java.lang.String to strings in the Basic plan, and use
some other representation for strings containing charactesr about
2^16. I.e. there are solutions, none of them great.
> Conclusion: The R6RS should not mandate any particular
> encoding or representation of strings.
> The current draft doesn't.
However, it seems to prohibit an implementation that is simple
(the way a raw array is), space-efficient, and O(1) for
string-ref/set! Pick any two.
--
--Per Bothner
per_at_bothner.com http://per.bothner.com/
Received on Tue Mar 20 2007 - 01:34:59 UTC