Re: Basic questions about elisp

[Pascal J. Bourguignon]

Francis Moreau <francis.moro@gmail.com> writes:

> On 6 nov, 22:18, p...@informatimago.com (Pascal J. Bourguignon) wrote:
>> Francis Moreau <francis.m...@gmail.com> writes:
>> >>> When I wrote '(2), I suppose the elisp interpreter to create a new
>> >>> list.
>>
>> >> It does so, but at read time.  Not execution time.
>>
>> > Ah ok I see what you mean now.
>>
>> > That's a pretty important point, is this part covered by the elisp info ?
>>
>> Yes.
>>
>> > Actually the same stands for the implementation of the list, where
>> > nconc, length... are O(n). I wouldn't have thought that lists are really
>> > implemented by the car & cdr thing only.
>>
>> Why not?  If people have been repeating for 50 years that lisp lists
>> are implemented with cons, car and cdr...
>
> Because I can understand there were some memory constraints 50 years
> ago that force lisp lists to be as small as possible. But I would have
> thought lisp lists (or (e)lisp) to evolve as computer memories did.

Well, contrarily to Microsoft, we don't have enough time and money to
grow a bloatware out of the language.  If lists as chains of cons
cells could be held in small memories 50 years ago, they can still be
held in big memories nowadays, there's no point in changing that.

However, if you need a "smarter" list abstract data type, you can
always implement it (or use a library).

Note however that you might have a hard time to reach the level of
efficiency given by cons cells.  That is, if you consider cons cells
as immutable, then you can easily share them amongst several prefix
lists, and therefore you spare a lot of cycles and a lot of memory not
copying them.  

If you try to invent a list ADT where you keep references to both the
first and last cells for "efficiency" reasons (so you can append an
element in O(1)), then you lose this ability to share lists, and
therefore you will have to copy these lists all over (copying the list
is O(n), and you lost the benefit of O(1) element appending).

If on the contrary you learn to use cons cell based lists, and you
avoid appending elements at the end, but push them on the head (which
is O(1)), then you can share them O(0) for no copying and spare memory
at the same time.  (Even if you need a final result in the other
order, adding a call reverse (O(n)) won't be less efficient than
making copies all the time).

-- 
__Pascal Bourguignon__