[r6rs-discuss] Re: [Formal] formal comment (ports, characters, strings, Unicode)

From: Shiro Kawai <shiro>
Date: Tue Mar 20 16:39:42 2007

I agree that r6rs shouldn't be affected just because it can't be
implemented easily by some specific implementing languages
(otherwise we wouldn't have call/cc). I don't mind to put
extra harness around utf-8 or whatever if O(1) string-ref
is such important.
But, is it?

I assume the primary benefit of O(1) string-ref is that it is
probably the simplest and the most portable way to point a
position in a string. "Portable" here is that I can safely
save it to file and read it by other implementation, or
send it over the network. But for internal use, like
implementing search operation, or passing its results to
substring operation, it is an illusion that O(1) string-ref
is enough to implement efficient algorithms. The efficient
one differs greatly among implementations (e.g. using Boyer-Moore
directly on utf-8 octet sequence), so it's better to have
higher-level APIs.

I don't have a complete proposal of this higher-level API
yet, though, so I won't push this further now.


From: William D Clinger <will_at_ccs.neu.edu>
Subject: Re: [r6rs-discuss] Re: [Formal] formal comment (ports, characters, strings, Unicode)
Date: Tue, 20 Mar 2007 09:53:47 -0400

> > If it is intentional, is it beacause you think that O(1)
> > string-set! is less important?
>
> string-set! is definitely less important than string-ref,
> but it's still important.

Sorry for my ignorance, but is there an important algorithm
that requires string-set!, even if you have both (a) means
to construct strings sequentially, like string ports, and
(b) means to create a vector of characters then convert it
to a string efficiently, like vector->string?

If there are such algorithms, then again, which is important,
O(1) string-set! or O(1) substring (assuming that string
positions are given in a way to guarantee O(1) access),
under existence of preemptive threads? (It is highly likely
that I don't have enough brain; can we have both?)

--shiro
Received on Tue Mar 20 2007 - 16:39:14 UTC