Basic questions about elisp

Basic questions about elisp

[Francis Moreau]

Hello,

I'm trying to learn elisp and have a couple of basic questions.

I'm iterating over a list using dotimes, but in the body of dotimes,
the list can mutate. For example I have:

  (dolist (elt lst)
    ;; some codes
    (nconc lst '(2)))

This adds/appends a new element to 'lst' list. It looks like 'dotimes'
doesn't like it.

So I eventually wrote it like this

    (setq i 0)
    (while (< i (length lst))
          ;; some codes
          (x-nconc lst '(2))))
      (setq i (1+ i)))

which is a bit ugly, is there another way to do that ?

I also need to iterate over elements of a vector.  I basically use a
'while' loop as above. Is there any helper to do that, I looked at
"(elisp) Sequences Arrays Vectors" but found nothing appropriate.

And finally, is it the good place to ask such questions about elisp ?

Thanks

Re: Basic questions about elisp

[Lennart Borgman]

On Thu, Nov 5, 2009 at 12:13 PM, Francis Moreau <francis.moro@gmail.com> wrote:
> Hello,
>
> I'm trying to learn elisp and have a couple of basic questions.
>
> I'm iterating over a list using dotimes, but in the body of dotimes,
> the list can mutate. For example I have:
>
>  (dolist (elt lst)
>    ;; some codes
>    (nconc lst '(2)))
>
> This adds/appends a new element to 'lst' list. It looks like 'dotimes'
> doesn't like it.
>
> So I eventually wrote it like this
>
>    (setq i 0)
>    (while (< i (length lst))
>          ;; some codes
>          (x-nconc lst '(2))))
>      (setq i (1+ i)))
>
> which is a bit ugly, is there another way to do that ?

It is much easier to answer if you define exactly what you want to do
when lst grows.

Re: Basic questions about elisp

[Francis Moreau]

On Nov 5, 12:50 pm, Lennart Borgman <lennart.borg...@gmail.com> wrote:
> On Thu, Nov 5, 2009 at 12:13 PM, Francis Moreau <francis.m...@gmail.com> wrote:
> > Hello,
>
> > I'm trying to learn elisp and have a couple of basic questions.
>
> > I'm iterating over a list using dotimes, but in the body of dotimes,
> > the list can mutate. For example I have:
>
> >  (dolist (elt lst)
> >    ;; some codes
> >    (nconc lst '(2)))
>
> > This adds/appends a new element to 'lst' list. It looks like 'dotimes'
> > doesn't like it.
>
> > So I eventually wrote it like this
>
> >    (setq i 0)
> >    (while (< i (length lst))
> >          ;; some codes
> >          (x-nconc lst '(2))))
> >      (setq i (1+ i)))
>
> > which is a bit ugly, is there another way to do that ?
>
> It is much easier to answer if you define exactly what you want to do
> when lst grows.

I'd like to iterate over all elements of the list even if the element
are appended during the loop execution.

For example if the list is (1 2) before entering in the loop and then
during the first iteration the code append '3' to the list so it
becomes (1 2 3), I'd like the loop to iterate over the '3' element as
well. 'dotimes' doesn't seem to do that.

I noticed that I used 'x-nconc' without giving its definition: it is
something I wrote for my own need: it's the same as 'nconc' except if
the list given in parameter is nil then 'x-nconc' creates a new list
and assigns it to its first parameter.

I did the following macro to do that, although I'm not sure it's the
good thing to do:

  (defmacro x-nconc (l e)
    `(if (null ,l) (setq ,l ,e) (nconc ,l ,e)))

Thanks

Re: Basic questions about elisp

[Lennart Borgman]

On Thu, Nov 5, 2009 at 1:07 PM, Francis Moreau <francis.moro@gmail.com> wrote:
> On Nov 5, 12:50 pm, Lennart Borgman <lennart.borg...@gmail.com> wrote:
>> On Thu, Nov 5, 2009 at 12:13 PM, Francis Moreau <francis.m...@gmail.com> wrote:
>> > Hello,
>>
>> > I'm trying to learn elisp and have a couple of basic questions.
>>
>> > I'm iterating over a list using dotimes, but in the body of dotimes,
>> > the list can mutate. For example I have:
>>
>> >  (dolist (elt lst)
>> >    ;; some codes
>> >    (nconc lst '(2)))
>>
>> > This adds/appends a new element to 'lst' list. It looks like 'dotimes'
>> > doesn't like it.
>>
>> > So I eventually wrote it like this
>>
>> >    (setq i 0)
>> >    (while (< i (length lst))
>> >          ;; some codes
>> >          (x-nconc lst '(2))))
>> >      (setq i (1+ i)))
>>
>> > which is a bit ugly, is there another way to do that ?
>>
>> It is much easier to answer if you define exactly what you want to do
>> when lst grows.
>
> I'd like to iterate over all elements of the list even if the element
> are appended during the loop execution.
>
> For example if the list is (1 2) before entering in the loop and then
> during the first iteration the code append '3' to the list so it
> becomes (1 2 3), I'd like the loop to iterate over the '3' element as
> well. 'dotimes' doesn't seem to do that.


Can't you just add the new elements to the end of the list and in each
iteration check if there are anything left in the tail to handle?

Re: Basic questions about elisp

[tomas]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On Thu, Nov 05, 2009 at 03:13:32AM -0800, Francis Moreau wrote:
> Hello,
> 
> I'm trying to learn elisp and have a couple of basic questions.
> 
> I'm iterating over a list using dotimes, but in the body of dotimes,
> the list can mutate. For example I have:
> 
>   (dolist (elt lst)
>     ;; some codes
>     (nconc lst '(2)))
> 
> This adds/appends a new element to 'lst' list. It looks like 'dotimes'
> doesn't like it.
> 
> So I eventually wrote it like this
> 
>     (setq i 0)
>     (while (< i (length lst))
>           ;; some codes
>           (x-nconc lst '(2))))
>       (setq i (1+ i)))
> 
> which is a bit ugly, is there another way to do that ?

What about:

  (let ((l lst))
    (while l
      (do-something-with (car l))
      (setq l (cdr l))))

This should be fine as long as you only append to lst. Dragons might
emerge whenever you do more drastic things to it ;-)

(and you would have to re-think things when Emacs Lisp becomes
multi-threaded. It might work then and it might not).

Regards
- -- tomás

> And finally, is it the good place to ask such questions about elisp ?

I'd think so, yes

Regards
- -- tomás
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)

iD8DBQFK8svUBcgs9XrR2kYRAth8AJwN4fyTcKzMZ4kdHKXuuwlmPcJ0RgCggIXe
ZTA5JsD54pM81Ur1HehQw38=
=fNST
-----END PGP SIGNATURE-----

Re: Basic questions about elisp

[David Kastrup]

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

> On Nov 5, 12:50 pm, Lennart Borgman <lennart.borg...@gmail.com> wrote:
>> On Thu, Nov 5, 2009 at 12:13 PM, Francis Moreau <francis.m...@gmail.com> wrote:
>> > I'm iterating over a list using dotimes, but in the body of dotimes,
>> > the list can mutate. For example I have:
>>
>> >  (dolist (elt lst)
>> >    ;; some codes
>> >    (nconc lst '(2)))
>>
>> > This adds/appends a new element to 'lst' list. It looks like 'dotimes'
>> > doesn't like it.

dolist.

>>
>> > So I eventually wrote it like this
>>
>> >    (setq i 0)
>> >    (while (< i (length lst))
>> >          ;; some codes
>> >          (x-nconc lst '(2))))
>> >      (setq i (1+ i)))
>>
>> > which is a bit ugly,

This looks like you would use (elt lst i) inside of the loop, quite a
bad idea since you get quadratic behavior.

> I'd like to iterate over all elements of the list even if the element
> are appended during the loop execution.
>
> For example if the list is (1 2) before entering in the loop and then
> during the first iteration the code append '3' to the list so it
> becomes (1 2 3), I'd like the loop to iterate over the '3' element as
> well. 'dotimes' doesn't seem to do that.

dolist

> I noticed that I used 'x-nconc' without giving its definition: it is
> something I wrote for my own need: it's the same as 'nconc' except if
> the list given in parameter is nil then 'x-nconc' creates a new list
> and assigns it to its first parameter.
>
> I did the following macro to do that, although I'm not sure it's the
> good thing to do:
>
>   (defmacro x-nconc (l e)
>     `(if (null ,l) (setq ,l ,e) (nconc ,l ,e)))

Actually, that's pretty stupid since it is exactly the same as
(defmacro (l e) `(setq ,l (nconc ,l ,e)))

It is less obscure to use nconc in the same manner as append, namely
using the return value (and accepting the side-effect for efficiency's
sake).  And then you don't need your personal macro and get more
readable code.

The usual iteration would be something like

(while lst
  <do something with (car lst)>
  <maybe append something to lst>
  (setq lst (cdr lst)))

If you really want efficiency, you'll not append something to lst in
order to avoid quadratic behavior.  Then you'd rather do something like

(let ((iter lst) app)
  (while
    (progn
       (while iter
          <do something with (car iter)>
          <maybe (push something app)>
          (setq lst (cdr lst)))
        app)
     (setq iter (nreverse app) app nil)))

Note that this does not change the original list at all.  If that's not
what is desired, you can write the last setq as

(setq iter (nreverse app) lst (nconc lst iter) app nil)

This still is suboptimal since the nconc will repeatedly traverse the
same elements.  Better solutions will track the additions also by just
pushing them, and do the concatenation as the very last step.

-- 
David Kastrup

Re: Basic questions about elisp

[Francis Moreau]

On Nov 5, 1:59 pm, David Kastrup <d...@gnu.org> wrote:
> Francis Moreau <francis.m...@gmail.com> writes:
>
> >   (defmacro x-nconc (l e)
> >     `(if (null ,l) (setq ,l ,e) (nconc ,l ,e)))
>
> Actually, that's pretty stupid

thanks

> since it is exactly the same as
> (defmacro (l e) `(setq ,l (nconc ,l ,e)))
>
> It is less obscure to use nconc in the same manner as append, namely
> using the return value (and accepting the side-effect for efficiency's
> sake).  And then you don't need your personal macro and get more
> readable code.

yes, I actually missed the use of the return value.

>
> The usual iteration would be something like
>
> (while lst
>   <do something with (car lst)>
>   <maybe append something to lst>
>   (setq lst (cdr lst)))
>
> If you really want efficiency, you'll not append something to lst in
> order to avoid quadratic behavior.  Then you'd rather do something like
>
> (let ((iter lst) app)
>   (while
>     (progn
>        (while iter
>           <do something with (car iter)>
>           <maybe (push something app)>
>           (setq lst (cdr lst)))
>         app)
>      (setq iter (nreverse app) app nil)))
>

hmm, it's probably my lack of elisp usage/knowledge, but it's terribly
hard to read for something really simple to achieve...

BTW, is '(setq lst (cdr lst)))' correct ?

> Note that this does not change the original list at all.  If that's not
> what is desired, you can write the last setq as
>
> (setq iter (nreverse app) lst (nconc lst iter) app nil)
>
> This still is suboptimal since the nconc will repeatedly traverse the
> same elements.

Lists are really implemented as simply linked list ?

Thanks

Re: Basic questions about elisp

[Francis Moreau]

On Nov 5, 1:57 pm, to...@tuxteam.de wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
>
>
> On Thu, Nov 05, 2009 at 03:13:32AM -0800, Francis Moreau wrote:
> > Hello,
>
> > I'm trying to learn elisp and have a couple of basic questions.
>
> > I'm iterating over a list using dotimes, but in the body of dotimes,
> > the list can mutate. For example I have:
>
> >   (dolist (elt lst)
> >     ;; some codes
> >     (nconc lst '(2)))
>
> > This adds/appends a new element to 'lst' list. It looks like 'dotimes'
> > doesn't like it.
>
> > So I eventually wrote it like this
>
> >     (setq i 0)
> >     (while (< i (length lst))
> >           ;; some codes
> >           (x-nconc lst '(2))))
> >       (setq i (1+ i)))
>
> > which is a bit ugly, is there another way to do that ?
>
> What about:
>
>   (let ((l lst))
>     (while l
>       (do-something-with (car l))
>       (setq l (cdr l))))
>

looks better but as David pointed out, appending something to a list
is quite expensive.

> This should be fine as long as you only append to lst. Dragons might
> emerge whenever you do more drastic things to it ;-)
>
> (and you would have to re-think things when Emacs Lisp becomes
> multi-threaded. It might work then and it might not).
>

Is this going to happen ?

Thanks

Re: Basic questions about elisp

[Pascal J. Bourguignon]

Francis Moreau <francis.moro@gmail.com> writes:
>> This still is suboptimal since the nconc will repeatedly traverse the
>> same elements.
>
> Lists are really implemented as simply linked list ?

Not all lists, but lisp lists yes.

-- 
__Pascal Bourguignon__

Re: Basic questions about elisp

[Pascal J. Bourguignon]

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

> Hello,
>
> I'm trying to learn elisp and have a couple of basic questions.
>
> I'm iterating over a list using dotimes, but in the body of dotimes,
                                  dolist                      dolist

> the list can mutate. For example I have:
>
>   (dolist (elt lst)
>     ;; some codes
>     (nconc lst '(2)))

This is an infinite loop.  It will break when the program runs out of
memory.


> This adds/appends a new element to 'lst' list. It looks like 'dotimes'
                                                                dolist
> doesn't like it.

If you are not careful, you won't be able to program...


> I also need to iterate over elements of a vector.  I basically use a
> 'while' loop as above. Is there any helper to do that, I looked at
> "(elisp) Sequences Arrays Vectors" but found nothing appropriate.

(require 'cl)
(loop for element in list       do (something element))
(loop for element across vector do (something element))


> And finally, is it the good place to ask such questions about elisp ?

Yes, it's right here.

-- 
__Pascal Bourguignon__

Re: Basic questions about elisp

[Pascal J. Bourguignon]

Francis Moreau <francis.moro@gmail.com> writes:
> I did the following macro to do that, although I'm not sure it's the
> good thing to do:
>
>   (defmacro x-nconc (l e)
>     `(if (null ,l) (setq ,l ,e) (nconc ,l ,e)))

It's ok, but it works only on variables.  If you want your macro to
work on places too, you could use setf instead of setq (actually, you
could always use setf instead of setq):

(require 'cl)

(defmacro* nconcf (place expression &environment environment)
  (destructuring-bind (vars vals store-vars writer-form reader-form)
       (get-setf-method place environment)
    (when (rest store-vars) (error "Cannot expand %S" place))
    `(let ,(mapcar* (function list) vars vals)
       (let ((,(first store-vars) ,reader-form))
         (setq ,(first store-vars) (nconc ,(first store-vars) ,expression))
         ,writer-form))))


(let ((a (make-vector 3 '()))
      (i 0))
 (nconcf (aref a (incf i)) '(x))
 (nconcf (aref a (decf i)) '(y))
 (nconcf (aref a (incf i)) '(x))
 a)
--> [(y) (x x) nil]

-- 
__Pascal Bourguignon__

Re: Basic questions about elisp

[David Kastrup]

pjb@informatimago.com (Pascal J. Bourguignon) writes:

> Francis Moreau <francis.moro@gmail.com> writes:
>
>> Hello,
>>
>> I'm trying to learn elisp and have a couple of basic questions.
>>
>> I'm iterating over a list using dotimes, but in the body of dotimes,
>                                   dolist                      dolist
>
>> the list can mutate. For example I have:
>>
>>   (dolist (elt lst)
>>     ;; some codes
>>     (nconc lst '(2)))
>
> This is an infinite loop.  It will break when the program runs out of
> memory.

It was oversimplified.  But it violates one basic principle of
programming:

Only ever use destructive list operators like nconc on lists that have
been consed together _entirely_ under your control.

In this particular case, the cons '(2) has been consed together under
control of the Lisp reader.  The second time this code gets executed,
the cons is destroyed.

For example, the code

(let ((lst (list 1 2 3)))
  (dotimes (i 2 lst) (nconc lst '(2))))

never finishes.  After 2 iterations, you get a circular list which hangs
the third nconc.

-- 
David Kastrup

Re: Basic questions about elisp

[Barry Margolin]

In article <87iqdpdog1.fsf@galatea.local>,
 pjb@informatimago.com (Pascal J. Bourguignon) wrote:

> Francis Moreau <francis.moro@gmail.com> writes:
> 
> > Hello,
> >
> > I'm trying to learn elisp and have a couple of basic questions.
> >
> > I'm iterating over a list using dotimes, but in the body of dotimes,
>                                   dolist                      dolist
> 
> > the list can mutate. For example I have:
> >
> >   (dolist (elt lst)
> >     ;; some codes
> >     (nconc lst '(2)))
> 
> This is an infinite loop.  It will break when the program runs out of
> memory.

It also modifies a literal, which modifies the function itself 
(resulting in a circular list of (2 2 2 2 ...)).  Change that nconc to:

(nconc lst (list 2))

to avoid that.

> 
> 
> > This adds/appends a new element to 'lst' list. It looks like 'dotimes'
>                                                                 dolist
> > doesn't like it.
> 
> If you are not careful, you won't be able to program...
> 
> 
> > I also need to iterate over elements of a vector.  I basically use a
> > 'while' loop as above. Is there any helper to do that, I looked at
> > "(elisp) Sequences Arrays Vectors" but found nothing appropriate.
> 
> (require 'cl)
> (loop for element in list       do (something element))
> (loop for element across vector do (something element))
> 
> 
> > And finally, is it the good place to ask such questions about elisp ?
> 
> Yes, it's right here.

-- 
Barry Margolin, barmar@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
*** PLEASE don't copy me on replies, I'll read them in the group ***

Re: Basic questions about elisp

[Francis Moreau]

On 5 nov, 16:06, David Kastrup <d...@gnu.org> wrote:
> p...@informatimago.com (Pascal J. Bourguignon) writes:
>
>
>
> > Francis Moreau <francis.m...@gmail.com> writes:
>
> >> Hello,
>
> >> I'm trying to learn elisp and have a couple of basic questions.
>
> >> I'm iterating over a list using dotimes, but in the body of dotimes,
> >                                   dolist                      dolist
>
> >> the list can mutate. For example I have:
>
> >>   (dolist (elt lst)
> >>     ;; some codes
> >>     (nconc lst '(2)))
>
> > This is an infinite loop.  It will break when the program runs out of
> > memory.
>
> It was oversimplified.  But it violates one basic principle of
> programming:

Basic principle of _elisp_ programming, I asssume...

>
> Only ever use destructive list operators like nconc on lists that have
> been consed together _entirely_ under your control.
>
> In this particular case, the cons '(2) has been consed together under
> control of the Lisp reader.  The second time this code gets executed,
> the cons is destroyed.

eh ?

When I wrote '(2), I suppose the elisp interpreter to create a new
list. And doing (nconc lst '(2)), I assume that this new list is now
referenced by 'lst', hence can't be destroyed.

I initialy thought that this didn't work, but after retrying it, I got
the correct result:

(let ((lst (list 1 2 3)))
  (dolist (elt lst)
    (when (eq elt 1)
      (nconc lst '(4))))
  lst)

which evalutes to "(1 2 3 4)"

Re: Basic questions about elisp

[David Kastrup]

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

> On 5 nov, 16:06, David Kastrup <d...@gnu.org> wrote:
>> p...@informatimago.com (Pascal J. Bourguignon) writes:
>>
>>
>>
>> > Francis Moreau <francis.m...@gmail.com> writes:
>>
>> >> Hello,
>>
>> >> I'm trying to learn elisp and have a couple of basic questions.
>>
>> >> I'm iterating over a list using dotimes, but in the body of dotimes,
>> >                                   dolist                      dolist
>>
>> >> the list can mutate. For example I have:
>>
>> >>   (dolist (elt lst)
>> >>     ;; some codes
>> >>     (nconc lst '(2)))
>>
>> > This is an infinite loop.  It will break when the program runs out of
>> > memory.
>>
>> It was oversimplified.  But it violates one basic principle of
>> programming:
>
> Basic principle of _elisp_ programming, I asssume...

Of Lisp programming.

>> Only ever use destructive list operators like nconc on lists that
>> have been consed together _entirely_ under your control.
>>
>> In this particular case, the cons '(2) has been consed together under
>> control of the Lisp reader.  The second time this code gets executed,
>> the cons is destroyed.
>
> eh ?

Did you try my example?

> When I wrote '(2), I suppose the elisp interpreter to create a new
> list.

It does so, but at read time.  Not execution time.

> And doing (nconc lst '(2)), I assume that this new list is now
> referenced by 'lst', hence can't be destroyed.

Garbage collection is the least of your problems.

> I initialy thought that this didn't work, but after retrying it, I got
> the correct result:
>
> (let ((lst (list 1 2 3)))
>   (dolist (elt lst)
>     (when (eq elt 1)
>       (nconc lst '(4))))
>   lst)
>
> which evalutes to "(1 2 3 4)"

And

(let ((lst (list 1 2 3)))
   (dolist (elt lst)
     (when (< elt 3)
       (nconc lst '(4))))
   lst)

just crashes.


-- 
David Kastrup

Re: Basic questions about elisp

[Francis Moreau]

David Kastrup <dak@gnu.org> writes:

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

[...]

>>
>> Basic principle of _elisp_ programming, I asssume...
>
> Of Lisp programming.
>
>>> Only ever use destructive list operators like nconc on lists that
>>> have been consed together _entirely_ under your control.
>>>
>>> In this particular case, the cons '(2) has been consed together under
>>> control of the Lisp reader.  The second time this code gets executed,
>>> the cons is destroyed.
>>
>> eh ?
>
> Did you try my example?

nope I was a bit confused by what you wrote and your example was using
'dotimes'.

>
>
>> 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 ?

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.

>
> And
>
> (let ((lst (list 1 2 3)))
>    (dolist (elt lst)
>      (when (< elt 3)
>        (nconc lst '(4))))
>    lst)
>
> just crashes.

OK.

-- 
Francis

Re: Basic questions about elisp

[Pascal J. Bourguignon]

Francis Moreau <francis.moro@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...  


(Note however that if you need a different kind of list, you can
always implement your own abstract data type in any way you like.)

-- 
__Pascal Bourguignon__

Re: Basic questions about elisp

[Francis Moreau]

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.

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__

Re: Basic questions about elisp

[tomas]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On Sat, Nov 07, 2009 at 06:49:52AM -0800, Francis Moreau wrote:
> On 6 nov, 22:18, p...@informatimago.com (Pascal J. Bourguignon) wrote:
> > Francis Moreau <francis.m...@gmail.com> writes:

[...]

> > > 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.

There's no "one data structure fits all" philosophy here. Use list for
"list things" and arrays for "array things". Nowadays all Lisps have
some form or other of array.

And still, lists are among the strongest points of Lisp. They are
simple and flexible, they are the representation of Lisp programs. They
are the reason why Lisp programmers are writing programs that write
programs ever since ~50 years ago.

If a list doesn't fit your bill, by all means: use defstruct, use
arrays, use hashes. But (as Pascal pointed out), sometimes lists fit a
bill quite unexpectedly, if you are willing to think flexibly (e.g. push
new elements at the head instead of append, etc).

Ah, btw. Some Lisp implementations optimize runs of lists as arrays
behind the scenes (search for "cdr compression"). But you still get this
nice, simple and expressive programming interface.

Regards
- -- tomás
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)

iD8DBQFK9pNqBcgs9XrR2kYRArYpAJ9/CnR5m6JBknoM3FcDVMrlqyDBygCfeKVh
2QyoTVHjkwWxtb/Uu8Abj1o=
=Zmom
-----END PGP SIGNATURE-----

Re: Basic questions about elisp

[Francis Moreau]

pjb@informatimago.com (Pascal J. Bourguignon) writes:

> Francis Moreau <francis.moro@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.
>

Sorry for being blind but I can't find the revelant section.

Could you give me a pointer ?

-- 
Francis

Re: Basic questions about elisp

[tomas]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On Sun, Nov 08, 2009 at 04:18:41PM +0100, Francis Moreau wrote:
> pjb@informatimago.com (Pascal J. Bourguignon) writes:

[...]

> > Yes.
> >
> 
> Sorry for being blind but I can't find the revelant section.
> 
> Could you give me a pointer ?

Start here:

  9. Evaluation
 19. Reading and Prinitng Lisp Objects

(they are cross-linked, as one might expect). Have fun.

(Note: on second-reading, I notice that one might read sarcasm into
this. ot the least. I know that I had lots of fun grasping those
things).

Regards
- -- tomás
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)

iD8DBQFK9vjGBcgs9XrR2kYRAlpHAJ9aTrcvKC8foksbMHgXXxcOYjWUCQCeJOAk
Ep5EpqcZJ/dKahSaq15AGtE=
=UPnI
-----END PGP SIGNATURE-----

Re: Basic questions about elisp

[Pascal J. Bourguignon]

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

> pjb@informatimago.com (Pascal J. Bourguignon) writes:
>
>> Francis Moreau <francis.moro@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.
>>
>
> Sorry for being blind but I can't find the revelant section.
>
> Could you give me a pointer ?

Well, there are several places where it's covered, but here is one
where it's explicitely explained:


(info "(elisp)Rearrangement")


 -- Function: nconc &rest lists

     [...]

     A common pitfall is to use a quoted constant list as a non-last
     argument to `nconc'.  If you do this, your program will change
     each time you run it!  Here is what happens:

          (defun add-foo (x)            ; We want this function to add
            (nconc '(foo) x))           ;   `foo' to the front of its arg.

          (symbol-function 'add-foo)
               => (lambda (x) (nconc (quote (foo)) x))

          (setq xx (add-foo '(1 2)))    ; It seems to work.
               => (foo 1 2)
          (setq xy (add-foo '(3 4)))    ; What happened?
               => (foo 1 2 3 4)
          (eq xx xy)
               => t

          (symbol-function 'add-foo)
               => (lambda (x) (nconc (quote (foo 1 2 3 4) x)))



Of course, it could be infered from:
C-h f quote RET
or:
(info "(elisp)Quoting")


-- 
__Pascal Bourguignon__

Re: Basic questions about elisp

[Francis Moreau]

tomas@tuxteam.de writes:

> On Sat, Nov 07, 2009 at 06:49:52AM -0800, Francis Moreau wrote:
>> On 6 nov, 22:18, p...@informatimago.com (Pascal J. Bourguignon) wrote:
>> > Francis Moreau <francis.m...@gmail.com> writes:
>
> [...]
>
>> > > 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.
>
> There's no "one data structure fits all" philosophy here. Use list for
> "list things" and arrays for "array things". Nowadays all Lisps have
> some form or other of array.
>
> And still, lists are among the strongest points of Lisp. They are
> simple and flexible, they are the representation of Lisp programs. They
> are the reason why Lisp programmers are writing programs that write
> programs ever since ~50 years ago.
>
> If a list doesn't fit your bill, by all means: use defstruct, use
> arrays, use hashes. But (as Pascal pointed out), sometimes lists fit a
> bill quite unexpectedly, if you are willing to think flexibly (e.g. push
> new elements at the head instead of append, etc).

yeah, optimized push/pop operations of lists is a bit unusual for me,
it's actually like using stack instead of lists. Specially since the
first code I tried to write with elisp was a sort algo where order
matters and first parsed elements need to be the first ones in the list.

Thanks
-- 
Francis

Re: Basic questions about elisp

[Francis Moreau]

pjb@informatimago.com (Pascal J. Bourguignon) writes:

> Francis Moreau <francis.moro@gmail.com> writes:
>
>> pjb@informatimago.com (Pascal J. Bourguignon) writes:
>>
>>> Francis Moreau <francis.moro@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.
>>>
>>
>> Sorry for being blind but I can't find the revelant section.
>>
>> Could you give me a pointer ?
>
> Well, there are several places where it's covered, but here is one
> where it's explicitely explained:
>
>
> (info "(elisp)Rearrangement")
>
>
>  -- Function: nconc &rest lists
>
>      [...]
>
>      A common pitfall is to use a quoted constant list as a non-last
>      argument to `nconc'.  If you do this, your program will change
>      each time you run it!  Here is what happens:
>
>           (defun add-foo (x)            ; We want this function to add
>             (nconc '(foo) x))           ;   `foo' to the front of its arg.
>
>           (symbol-function 'add-foo)
>                => (lambda (x) (nconc (quote (foo)) x))
>
>           (setq xx (add-foo '(1 2)))    ; It seems to work.
>                => (foo 1 2)
>           (setq xy (add-foo '(3 4)))    ; What happened?
>                => (foo 1 2 3 4)
>           (eq xx xy)
>                => t
>
>           (symbol-function 'add-foo)
>                => (lambda (x) (nconc (quote (foo 1 2 3 4) x)))

ok that tells: "don't do that !" but it doesn't tell why not...

>
> Of course, it could be infered from:
> C-h f quote RET
> or:
> (info "(elisp)Quoting")

There's nothing here about a cons built by the Lisp Reader.

Thanks
-- 
Francis

Re: Basic questions about elisp

[Joost Kremers]

Francis Moreau wrote:
> pjb@informatimago.com (Pascal J. Bourguignon) writes:
>> Well, there are several places where it's covered, but here is one
>> where it's explicitely explained:
>>
>> (info "(elisp)Rearrangement")
[...]
>
> ok that tells: "don't do that !" but it doesn't tell why not...

just imagine a list as an object living somewhere in the memory of your
computer. then try to figure out which list gets *modified* by the call to
nconc, keeping in mind that nconc does *not* copy its arguments before doing its
job.


-- 
Joost Kremers                                      joostkremers@yahoo.com
Selbst in die Unterwelt dringt durch Spalten Licht
EN:SiS(9)

Re: Basic questions about elisp

[Francis Moreau]

On Nov 10, 1:11 pm, Joost Kremers <joostkrem...@yahoo.com> wrote:
> Francis Moreau wrote:
> > p...@informatimago.com (Pascal J. Bourguignon) writes:
> >> Well, there are several places where it's covered, but here is one
> >> where it's explicitely explained:
>
> >> (info "(elisp)Rearrangement")
> [...]
>
> > ok that tells: "don't do that !" but it doesn't tell why not...
>
> just imagine a list as an object living somewhere in the memory of your
> computer. then try to figure out which list gets *modified* by the call to
> nconc, keeping in mind that nconc does *not* copy its arguments before doing its
> job.
>

I don't really want to imagine some scenarios when reading this kind
of documentation.

BTW, the documentation is actually taking about the non-last argument,
however I was using a constant list for the last argument. So it
wouldn't apply in my case...

Thanks

Re: Basic questions about elisp

[David Kastrup]

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

> On Nov 10, 1:11 pm, Joost Kremers <joostkrem...@yahoo.com> wrote:
>> Francis Moreau wrote:
>> > p...@informatimago.com (Pascal J. Bourguignon) writes:
>> >> Well, there are several places where it's covered, but here is one
>> >> where it's explicitely explained:
>>
>> >> (info "(elisp)Rearrangement")
>> [...]
>>
>> > ok that tells: "don't do that !" but it doesn't tell why not...
>>
>> just imagine a list as an object living somewhere in the memory of
>> your computer. then try to figure out which list gets *modified* by
>> the call to nconc, keeping in mind that nconc does *not* copy its
>> arguments before doing its job.
>
> I don't really want to imagine some scenarios when reading this kind
> of documentation.
>
> BTW, the documentation is actually taking about the non-last argument,
> however I was using a constant list for the last argument. So it
> wouldn't apply in my case...

In the second iteration, your constant list has become part of the first
argument.

-- 
David Kastrup