Am Fr., 9. Okt. 2020 um 19:41 Uhr schrieb Arthur A. Gleckler
<xxxxxx@speechcode.com>:
>
> On Fri, Oct 9, 2020 at 8:54 AM Marc Nieper-Wißkirchen <xxxxxx@nieper-wisskirchen.de> wrote:
>>
>> Why do you think that "vectorlist" is self-contradictory? Java has ArrayList.

> Because "vector" and "list" have long-established meanings in Scheme that differ strongly in access time.  When teaching SICP, we took great pains to make sure that students understood the difference in performance characteristics.  Even if it's O(lg n) vs. O(n), that's a big difference.  (And are there actually any Schemes whose vector type does not have O(1) access time?)

A simple implementation of a large vector uses malloc or mmap to
acquire some contiguous piece of *virtual memory* to store the vector
elements. This virtual memory is (at least for common architectures)
mapped to physical memory through nested page tables. So one can say
that the performance is O(log n) (with a large base of the logarithm).
Of course, for all practical purposes, this is a constant. But the
O(f(n)) notation only makes sense with unlimited memory (as otherwise
even lists have O(1)). And applying the page table concept to
unlimited memory gives O(log n).

> The name ArrayList always struck me as self-contradictory, but I put that down to Java programmers not coming from a Lisp background.

In some sense, this is my argument against the name vector for things
that do not have a fixed dimension. C++ programmers may nevertheless
use the vector for growable collections, but I don't blame them for
not understanding the meaning of the word.

;)

Tongue-in-cheek aside, a Java ArrayList is a list with some array
characteristics, isn't it?

>
>>
>> I cast doubt on that a SRFI 214 entity is a flexible version of a
>> Scheme vector. It supports the API of a list and a deque (but has
>> usually better random access timings). Just because something is
>> implemented with vectors, doesn't make it into a vector.
>
>
>  That makes it even more flexible.  And it certainly supports the vector API, too.

As do Scheme lists.