Thanks for your analysis, Marc!

On 2020-09-03 08:47 +0200, Marc Nieper-Wißkirchen wrote:
> Finally, we have this statement in the specification section:
> "Statements about running time exclude time spent in the indexer
> procedure. However, this SRFI recommends that indexers run in O(1)
> time." The first of the two sentences assumes that there is a definite
> indexer procedure for each range. But the only general indexer
> function we have is (lambda (i) (range-ref i range)), but this cannot
> be meant. And the second sentence about that the running time of
> indexers is recommended to be O(1) does not make sense unless the
> independent variables are known.

The concept of an indexer is no longer essential and is only mentioned
in `range', where it's a caller-supplied procedure.  It makes little
sense to have requirements for an entity that isn't explained anywhere
else in the document.  Since this is now only a (slightly cryptic)
implementation suggestion, I agree that these sentences should be
removed, or moved to an "implementation notes" section.

> [snip]
>
> Luckily, the analysis above that takes care to distinguish between n
> and k helps us here to find the correct solution (that will also apply
> to range-reverse). In the implementation (not necessarily exposed to
> the user), range objects receive another field, namely a "complexity
> number" k. Ranges created by range, numeric-range, vector-range or
> string-range have complexity 0. When "range-append" appends k ranges,
> the resulting complexity is the sum of the complexities. Likewise,
> "range-reverse" increases the complexity number by one. When, and only
> when, the complexity number reaches an implementation-defined
> threshold (or the logarithm of the length of the resulting range), the
> constructor unpacks all values in a newly allocated vector and resets
> the complexity to 0. To make it even more efficient, the unpacking
> happens lazily, so not before the first access through range-ref.

I agree that this is the Right Thing, but, as things stand, a major
reimplementation effort might be needed to make it happen.  In any
case, I suggest that anything (e.g. the complexity requirements)
preventing such an approach be removed from the SRFI document.

What we've been discussing is essentially a simple-minded version of
the above, where ranges are "forced" as soon as they're passed to
range-append, etc., and without any heuristics for determining whether
this forcing is actually a win.

Again, I'm not inclined to rewrite a large chunk of the sample
implementation.  Can you briefly sketch what would have to change?
Could the changes be concentrated in a small set of forms, e.g.
range-append, -reverse, etc.?

--
Wolfgang Corcoran-Mathe  <xxxxxx@sigwinch.xyz>

"Personally, I get a little tired of the argument: My worse-is-better
is better than your worse-is-better because I'm better at being
worser!" --Larry Wall