Re: Sample Implementation?
William D Clinger 10 Jun 2016 23:43 UTC
Alan Manuel Gloria asked:
> Where's the sample implementation?
The sample implementations will accompany the second draft
of the SRFI, which I'm hoping to submit tomorrow; if not
tomorrow, then it will probably have to wait until Tuesday.
Current status of sample implementations: the representation
independent layer and test program are complete except for
eight procedures that convert between texts and UTF. The
kernel0 representation is complete but textual-concatenate
does not yet optimize sharing of substructure.
The kernel8 and kernel16 representations do not yet exist,
but they will be almost identical to kernel0, which is why
they're waiting for final tuning of kernel0. The main ideas
of kernel8 were prototyped over a year ago when I implemented
an earlier draft of John Cowan's CharacterSpans API; there
are no doubts concerning whether those kernels will achieve
the SRFI's performance requirements.
> I'm particularly curious of an immutable text implementation with shared
> substructure that can run text-ref in O(1) with a varying-length encoding
> backend.
In Chibi, which uses a variable-width encoding for strings,
kernel0 uses a variable-width encoding. I reported partial
timings for a kernel benchmark at the WG2 discussion list.
(That benchmark had an off-by-two error, so all of those
reported timings are twice as slow as reality, but that
doesn't affect the demonstration of O(1) time for text-ref
despite the variable-width encoding.)
I had originally planned to submit SRFI 135 only after all
sample implementations were complete, but submitted the
first draft without the sample implementations so discussion
could begin.
Will