Re: why are there [v e c t o r s] in Lisp?

[Pascal J. Bourguignon]

Random832 <random832@fastmail.com> writes:

> "Pascal J. Bourguignon" <pjb@informatimago.com> writes:
>> Random832 <random832@fastmail.com> writes:
>>> Well, what happens if you cdr that list? Does it make a
>>> copy? 
>>
>> cdr'ing is no problem you just increment your pointer.
>>
>>> The thing is, if you can car a string people will wonder why
>>> you can't cdr it. And with mutable objects it's hard to make
>>> cdr work right. (fsvo "right")
>>
>> It's rplacd which becomes much more complex.
>
> You didn't mention my issue with "list of 5000 elements, cdr
> 4000 times" - does the garbage collector know to discard the
> first 4000 elements which are no longer reachable?

Well, I don't know if the implementations that had cdr-coding could
collect the prefix of the vector of cars that wasn't referenced anymore.
It's a little complexity for the garbage collector, but not too hard to
implement. The problem is more when you want to discard the 1 element
which is no longer reachable: this becomes quite costly.


>> Also, when you program with such a system, you might be afraid that
>> rplacd leads to fragmented chains, and will have a tendency to call
>> copy-list to compact them.
>
> Hmm... can the garbage collector compact them?

Compacting lists at garbage collection time is indeed a good idea, when
you have cdr-coding.  On the other hand, I believe the implementations
that had cdr-coding had a simple mark-and-sweap garbage collector, not a
copying one.  Some archeology would be in order there.


>>  But indeed, copy-list means that less
>> structure is shared, and therefore would waste time and memory.  This is
>> what they do in C++ and why they believe lists are costly.
>
> Also with this kind of list I think you still lose the
> ability to have constant-time indexing, since you have to
> check every cell for the cdr bit.

Of course.  Worse, to have O(1) indexing, you'd need to know the length
in advance, and this is what is killing, you cannot have an efficient
length when you have mutation and structure sharing.  rplacd would have
to update an unbound number of length slots.




However, it is possible to have a compiler that will map lists to
vectors in the generated code, as long as this compiler is able to
perform global analysis to ensure the semantics.  With global analysis,
you can easily determine whether there is structure sharing, whether
rplaca is used, and determine the length of the list at compilation time
or know to store it.

-- 
__Pascal Bourguignon__                 http://www.informatimago.com/
“The factory of the future will have only two employees, a man and a
dog. The man will be there to feed the dog. The dog will be there to
keep the man from touching the equipment.” -- Carl Bass CEO Autodesk