I am seemingly repeatedly unable to CC the list as well...

---------- Forwarded message ---------
Von: Marc Nieper-Wißkirchen <xxxxxx@nieper-wisskirchen.de>
Date: Sa., 5. Sept. 2020 um 20:09 Uhr
Subject: Re: Remaining changes
To: John Cowan <xxxxxx@ccil.org>

Am Sa., 5. Sept. 2020 um 19:44 Uhr schrieb John Cowan <xxxxxx@ccil.org>:

>> Please take into consideration that, as Wolfgang observed, vectors have no O(1) random access guarantee. There are meaningful implementions of vectors conceivable that have, say, O(log n) random access time.
>
>
> In principle, yes [insert Radio Yerevan joke here].  But I prefer to have my prose say "This procedure must run in O(1) time" rather than defile it with "This procedure must run in a time that is asymptotically equivalent to the random access time of vectors on the Scheme implementation in use", which adds nothing to the meaning of the text and actually decreases its intelligibility, all in pursuit of a theoretical correctness without practical significance.  It is undoubtedly possible to construct an implementation of vectors where the access time is O(n^3), but nobody will, so why bother about it?

As the R7RS (small) just makes soft guarantees ("A vector typically
occupies less space than a list of the same length, and the average
time needed to access a randomly chosen element is typically less for
the vector than for the list."), I am wondering whether it makes sense
for a SRFI to choose the same soft language.

>> That it does not matter in practice, is due to the fact that n is
>> usually bounded by the size of the computer's memory.

> In CL, array size is explicitly restricted to the size of a fixnum (vectors and strings are special cases of arrays).  But if we were to worry about size limitations, we would have to conclude that computers are not Turing-complete, and for that matter there is not room in the universe for even one Turing machine.

Whenever one speaks about asymptotic complexity, one has to imagine
unlimited space (and time). If we don't do this, even list-ref has
O(1) access time.

>> What is it supposed to mean that the indexer procedure runs in O(1)? As the indexer procedure is just a procedure of an argument that takes only finitely many values, such a statement is meaningless.

> Not at all.  It means that the running time of the indexer is independent of the size of the range, or of its argument, which is the same thing in big-O terms.  For example, an indexer that computes n! is not O(1), and the range created by (range 20 factorial) will not respond to range-ref in O(1) time; a fortiori, range-count will not run in O(n) on this range either.

The indexer procedure in the case of (range 20 factorial) is a
procedure that has to accept the values 0, ..., 19. Whether (factorial
20) or (factorial 2000) is well-defined or not (or what the running
time is) is irrelevant.

What you want to impose only makes sense for a family of ranges like
the family of ranges given by (range N factorial) where N runs over
all natural numbers. But there is no such language in the SRFI.

> I have reworded the sentence to say: "This SRFI recommends that the <em>indexer</em> procedure have a running time that is independent of the value of its argument", to avoid further confusion.

This guarantee will almost never be fulfilled. It is like saying that
the running time of the division of two fixnums is independent of
their values, which is usually not even guaranteed on the level of CPU
clock ticks.