bug#12314: 24.2.50; `add-to-history': use `setq' with `delete'

bug#12314: 24.2.50; `add-to-history': use `setq' with `delete'

[Drew Adams]

This line in `add-to-history':
 
(if history-delete-duplicates (delete newelt history))
 
should be this:
 
(if history-delete-duplicates (setq history (delete newelt history)))
 
(Or for more clarity, use `when' instead of `if'.)
 
I'm not 100% sure this is a problem, but it seems to be in a case I saw.
And there seems to be no reason not to set `history' to the `delete'
result here.

In GNU Emacs 24.2.50.1 (i386-mingw-nt5.1.2600)
 of 2012-08-26 on MARVIN
Bzr revision: 109788 dmantipov@yandex.ru-20120827041533-3cy7pdjdqz14o90c
Windowing system distributor `Microsoft Corp.', version 5.1.2600
Configured using:
 `configure --with-gcc (4.6) --no-opt --enable-checking --cflags
 -ID:/devel/emacs/libs/libXpm-3.5.8/include
 -ID:/devel/emacs/libs/libXpm-3.5.8/src
 -ID:/devel/emacs/libs/libpng-dev_1.4.3-1/include
 -ID:/devel/emacs/libs/zlib-dev_1.2.5-2/include
 -ID:/devel/emacs/libs/giflib-4.1.4-1/include
 -ID:/devel/emacs/libs/jpeg-6b-4/include
 -ID:/devel/emacs/libs/tiff-3.8.2-1/include
 -ID:/devel/emacs/libs/gnutls-3.0.9/include
 -ID:/devel/emacs/libs/libiconv-1.13.1-1-dev/include
 -ID:/devel/emacs/libs/libxml2-2.7.8/include/libxml2'
 

bug#12314: 24.2.50; `add-to-history': use `setq' with `delete'

[Chong Yidong]

"Drew Adams" <drew.adams@oracle.com> writes:

> This line in `add-to-history':
>  
> (if history-delete-duplicates (delete newelt history))
>  
> should be this:
>  
> (if history-delete-duplicates (setq history (delete newelt history)))

Fixed, thanks.

bug#12314: 24.2.50; `add-to-history': use `setq' with `delete'

[Eli Zaretskii]

> From: Chong Yidong <cyd@gnu.org>
> Date: Sat, 08 Sep 2012 22:32:13 +0800
> Cc: 12314@debbugs.gnu.org
> 
> "Drew Adams" <drew.adams@oracle.com> writes:
> 
> > This line in `add-to-history':
> >  
> > (if history-delete-duplicates (delete newelt history))
> >  
> > should be this:
> >  
> > (if history-delete-duplicates (setq history (delete newelt history)))
> 
> Fixed, thanks.

Does this mean the ELisp manual is in error?  It says:

 -- Function: delete object sequence
     If `sequence' is a list, this function destructively removes all
     elements `equal' to OBJECT from SEQUENCE.
     ...
     If `sequence' is a vector or string, `delete' returns a copy of
     `sequence' with all elements `equal' to `object' removed.

'history' is a list, isn't it?

bug#12314: 24.2.50; `add-to-history': use `setq' with `delete'

[Drew Adams]

> Does this mean the ELisp manual is in error?  It says:
> 
>  -- Function: delete object sequence
>      If `sequence' is a list, this function destructively removes all
>      elements `equal' to OBJECT from SEQUENCE.
>      ...
>      If `sequence' is a vector or string, `delete' returns a copy of
>      `sequence' with all elements `equal' to `object' removed.
> 
> 'history' is a list, isn't it?

Yes, it is a list.  What is your point/question?

Keep reading the same section of the manual (section for `delete'):

  ;; If you want to change `l' reliably,
  ;; write `(setq l (delete '(2) l))'.

There is more explanation higher up in the same node, under `delq':

 Don't assume that a variable
 which formerly held the argument LIST now has fewer elements,
 or that it still holds the original list!  Instead, save the
 result of `delq' and use that.  Most often we store the result
 back into the variable that held the original list:

     (setq flowers (delq 'rose flowers))

I would imagine that you already know this, so I'm likely missing something in
your question.  But if you don't already know this, or if you knew it but forgot
it, there's no harm/shame in that.  Does this help, or were you referring to
something else?

bug#12314: 24.2.50; `add-to-history': use `setq' with `delete'

[Eli Zaretskii]

> From: "Drew Adams" <drew.adams@oracle.com>
> Cc: <12314@debbugs.gnu.org>
> Date: Sat, 8 Sep 2012 07:57:12 -0700
> 
> > Does this mean the ELisp manual is in error?  It says:
> > 
> >  -- Function: delete object sequence
> >      If `sequence' is a list, this function destructively removes all
> >      elements `equal' to OBJECT from SEQUENCE.
> >      ...
> >      If `sequence' is a vector or string, `delete' returns a copy of
> >      `sequence' with all elements `equal' to `object' removed.
> > 
> > 'history' is a list, isn't it?
> 
> Yes, it is a list.  What is your point/question?

That for a list, assigning the result is not necessary.  At least
that's my interpretation of what the manual says.

> Keep reading the same section of the manual (section for `delete'):
> 
>   ;; If you want to change `l' reliably,
>   ;; write `(setq l (delete '(2) l))'.

My interpretation of "reliably" here is "without assuming that l is a
list".  Is that a wrong interpretation?

> There is more explanation higher up in the same node, under `delq':

'delq' is not identical to 'delete', so assumptions that somethiong
described there is pertinent to 'delete' are unsafe.  And how should
the reader know that she needs to read something under 'delq' to fully
understand what 'delete' does, anyway?

> I would imagine that you already know this, so I'm likely missing something in
> your question.

I'm not sure who is missing what.  All I'm saying is that the manual
seems to suggest that an explicit assignment is unnecessary, and yet
Chong did exactly that.  If just "(delete 'foo bar)", with 'bar' a
list, is sometimes not enough, the manual should say when.  And if it
is enough, why should we make the change in add-to-history?

IOW, it sounds like some kind of black magic is going on under the
hood, but the manual is too shy to talk about it.  It shouldn't; doing
so could easily spread confusion.  I'm not sure the code in question
was written as it was due to that confusion.

bug#12314: 24.2.50; `add-to-history': use `setq' with `delete'

[Drew Adams]

> That for a list, assigning the result is not necessary.  At least
> that's my interpretation of what the manual says.

No, that is incorrect.  This is an old Lisp gotcha.  It is one reason people
often advise Lisp newbies not to start out by using destructive operations.
They can be quite confusing, and you can run into trouble far from where a
problem/bug is introduced.

> > Keep reading the same section of the manual (section for `delete'):
> > 
> >   ;; If you want to change `l' reliably,
> >   ;; write `(setq l (delete '(2) l))'.
> 
> My interpretation of "reliably" here is "without assuming that l is a
> list".  Is that a wrong interpretation?

Yes, it is wrong.

> > There is more explanation higher up in the same node, under `delq':
> 
> 'delq' is not identical to 'delete', so assumptions that somethiong
> described there is pertinent to 'delete' are unsafe.  And how should
> the reader know that she needs to read something under 'delq' to fully
> understand what 'delete' does, anyway?

The doc for `delete' sends you to the doc for `delq', where there is a good
step-by-step illustration.  The only difference between `delq' and `delete' is
comparison by `eq' vs by `equal'.

This is in fact a general thing for Lisp functions that are destructive of list
structure.

The manual describes it for `delq':

 When `delq' deletes elements from the front of the list, it
 does so simply by advancing down the list and returning a
 sublist that starts after those elements:

     (delq 'a '(a b c)) == (cdr '(a b c))

The point is not to confuse the _side effect_ of an operation (so-called
"function") such as `delete' with its _return value_.

The list targeted by the function might or might not be modified.  The return
value has the correct contents in all cases, and that is why you should
generally set your variable to the return value, if you want that variable to
reflect the result of the operation.

The list structure is one thing.  Your variable pointing to some list structure
is another thing.  If you want the variable to reflect the changed structure
(list contents) in all cases, then set the variable value to the function's
return value.

In short, to reflect the _result_ of the operation, you need to set the variable
to the returned result.  Otherwise, it will not necessarily point to a list that
has the correct contents.

> I'm not sure who is missing what.  All I'm saying is that the manual
> seems to suggest that an explicit assignment is unnecessary, and yet
> Chong did exactly that.  If just "(delete 'foo bar)", with 'bar' a
> list, is sometimes not enough, the manual should say when.  And if it
> is enough, why should we make the change in add-to-history?

It is not enough, if you need the variable to reflect the updated list contents.
It's about using the return value of the function vs depending on the "function"
only for its side effect (i.e., not caring about what the variable points to
after the operation).

If we cared only about a particular list structure and not some variable that
might point to it, then we might not bother to update the variable by setting it
to the returned value.

> IOW, it sounds like some kind of black magic is going on under the
> hood, but the manual is too shy to talk about it.  It shouldn't; doing
> so could easily spread confusion.  I'm not sure the code in question
> was written as it was due to that confusion.

It's not black magic, but it is about list structure and Lisp not being a
(purely) functional language.

Perhaps the node `Modifying Lists' should go into a little more detail about
this; dunno.  `delq' or `delete' is a great way to illustrate it, and we
currently do that (for `delq').  Perhaps we should be more explicit about other
list-modifying (i.e. destructive) operations having the same behavior, and
generally advise setting any variable you care about to the returned value of
the function.

bug#12314: 24.2.50; `add-to-history': use `setq' with `delete'

[Eli Zaretskii]

> From: "Drew Adams" <drew.adams@oracle.com>
> Cc: <cyd@gnu.org>, <12314@debbugs.gnu.org>
> Date: Sat, 8 Sep 2012 08:48:53 -0700
> 
> > I'm not sure who is missing what.  All I'm saying is that the manual
> > seems to suggest that an explicit assignment is unnecessary, and yet
> > Chong did exactly that.  If just "(delete 'foo bar)", with 'bar' a
> > list, is sometimes not enough, the manual should say when.  And if it
> > is enough, why should we make the change in add-to-history?
> 
> It is not enough, if you need the variable to reflect the updated list contents.

Then the manual should be corrected to state that much more explicitly
than it does now.  Perhaps it shouldn't even talk about destructive
removal, as that will surely spread confusion.  For me "destructive"
means "in-place", and no amount of describing how 'delete' works
internally will ever be able to countermand that.  Besides, if all I
need is a quick reminder about the semantics, I'm unlikely to read all
the verbiage, let alone go up to read more under 'delq'.  So the most
important facts should be right there at the beginning, not hidden
away under "note that" etc.

bug#12314: 24.2.50; `add-to-history': use `setq' with `delete'

[Andreas Schwab]

Eli Zaretskii <eliz@gnu.org> writes:

> Then the manual should be corrected to state that much more explicitly
> than it does now.  Perhaps it shouldn't even talk about destructive
> removal, as that will surely spread confusion.  For me "destructive"
> means "in-place", and no amount of describing how 'delete' works
> internally will ever be able to countermand that.

Even if the element is not the first one, you always have to think about
other references that may exist to the cons that is removed.

Andreas.

-- 
Andreas Schwab, schwab@linux-m68k.org
GPG Key fingerprint = 58CA 54C7 6D53 942B 1756  01D3 44D5 214B 8276 4ED5
"And now for something completely different."

bug#12314: 24.2.50; `add-to-history': use `setq' with `delete'

[Eli Zaretskii]

> From: Andreas Schwab <schwab@linux-m68k.org>
> Cc: Drew Adams <drew.adams@oracle.com>,  12314@debbugs.gnu.org,  cyd@gnu.org
> Date: Sat, 08 Sep 2012 18:19:58 +0200
> 
> Eli Zaretskii <eliz@gnu.org> writes:
> 
> > Then the manual should be corrected to state that much more explicitly
> > than it does now.  Perhaps it shouldn't even talk about destructive
> > removal, as that will surely spread confusion.  For me "destructive"
> > means "in-place", and no amount of describing how 'delete' works
> > internally will ever be able to countermand that.
> 
> Even if the element is not the first one, you always have to think about
> other references that may exist to the cons that is removed.

Sorry, I'm not sure how this is related.  Please elaborate.

bug#12314: 24.2.50; `add-to-history': use `setq' with `delete'

[Lars Ingebrigtsen]

Eli Zaretskii <eliz@gnu.org> writes:

> Sorry, I'm not sure how this is related.  Please elaborate.

`delete' may modify the list, so other references into the list may get
surprising results after you've modified it.

The current doc string is kinda obscure, though.  It stars with

---
Delete by side effect any occurrences of ELT as a member of SEQ.
---

which is like "err".

Perhaps something like

Delete any occurrences of ELT from SEQ.  This operation may
destructively modify SEQ.  See `remove' for a non-destructive version.

would be more readable.

-- 
(domestic pets only, the antidote for overdose, milk.)
  http://lars.ingebrigtsen.no  *  Lars Magne Ingebrigtsen

bug#12314: 24.2.50; `add-to-history': use `setq' with `delete'

[Drew Adams]

> > Even if the element is not the first one, you always have 
> > to think about other references that may exist to the
> > cons that is removed.
> 
> Sorry, I'm not sure how this is related.  Please elaborate.

(Think pointers.)  A variable stays pointed to the same cons cell - these
operations do not change that.  But they can change the relations among cons
cells: which of them point to which others.

(setq a  '(1 2 3 4))
(setq b  (cddr a))

a => (1 2 3 4)
b => (3 4)

(delq 4 b)

a => (1 2 3)
b => (3)

The value of variable `a' was changed by changing the value of `b', because `b'
points to a cons cell that is used in the list structure pointed to by `a'.

bug#12314: 24.2.50; `add-to-history': use `setq' with `delete'

[Andreas Schwab]

Eli Zaretskii <eliz@gnu.org> writes:

>> From: Andreas Schwab <schwab@linux-m68k.org>
>> Cc: Drew Adams <drew.adams@oracle.com>,  12314@debbugs.gnu.org,  cyd@gnu.org
>> Date: Sat, 08 Sep 2012 18:19:58 +0200
>> 
>> Eli Zaretskii <eliz@gnu.org> writes:
>> 
>> > Then the manual should be corrected to state that much more explicitly
>> > than it does now.  Perhaps it shouldn't even talk about destructive
>> > removal, as that will surely spread confusion.  For me "destructive"
>> > means "in-place", and no amount of describing how 'delete' works
>> > internally will ever be able to countermand that.
>> 
>> Even if the element is not the first one, you always have to think about
>> other references that may exist to the cons that is removed.
>
> Sorry, I'm not sure how this is related.  Please elaborate.

It's just a special case of this general behaviour.

Andreas.

-- 
Andreas Schwab, schwab@linux-m68k.org
GPG Key fingerprint = 58CA 54C7 6D53 942B 1756  01D3 44D5 214B 8276 4ED5
"And now for something completely different."

bug#12314: 24.2.50; `add-to-history': use `setq' with `delete'

[Drew Adams]

> > Then the manual should be corrected to state that much more 
> > explicitly than it does now.  Perhaps it shouldn't even talk
> > about destructive removal, as that will surely spread
> > confusion.  For me "destructive" means "in-place", and no
> > amount of describing how 'delete' works internally will ever
> > be able to countermand that.
> 
> Even if the element is not the first one, you always have to 
> think about other references that may exist to the cons that
> is removed.

Exactly.  That too merits an explicit mention.  That is an even more insidious
source of hard-to-find bugs.

There is no harm in driving this point home, even at the risk of some
repetition.  Destructive operations should not be used without extra care.  It
is a gotcha that newbies sometimes learn the hard way.

In particular, thinking that such operations are only about performance, and
understanding that they can be more performant, newbies sometimes start using
them right off the bat (premature optimization).  And because the gotchas only
surface in some situations, they don't necessarily notice problems right away.

IIRC, the Common Lisp manual was pretty good at essentially warning readers not
to use destructive operations unless they really understand them well.  I don't
recall just what was said, though.

A simple guideline to set your variable to the list returned by such an
operation will go a long way, I think.  But we should of course explain why
also.

bug#12314: 24.2.50; `add-to-history': use `setq' with `delete'

[Drew Adams]

> > It is not enough, if you need the variable to reflect the 
> > updated list contents.
> 
> Then the manual should be corrected to state that much more explicitly
> than it does now.  Perhaps it shouldn't even talk about destructive
> removal, as that will surely spread confusion.  For me "destructive"
> means "in-place", and no amount of describing how 'delete' works
> internally will ever be able to countermand that.  Besides, if all I
> need is a quick reminder about the semantics, I'm unlikely to read all
> the verbiage, let alone go up to read more under 'delq'.  So the most
> important facts should be right there at the beginning, not hidden
> away under "note that" etc.

Go for it.  I suggest mentioning something like this in node `Modifying Lists'
(and then cross-ref'ing that node from other nodes about functions that are
destructive of list structure):

Typically, you want a variable whose value is a list to reflect the result of
any destructive operation on that list.  To achieve that, set the variable value
to the value returned by that operation.

The reason for this is that operations that modify list structure do not also
update any variables that might point to such structure.  They are concerned
only with changing list structure.

Then give the `delq' example as an illustration of this.  Point out why  the
variable's value no longer reflects the updated list content.  (Perhaps even use
a cons-cell diagram to illustrate.)

  When `delq' deletes elements from the front of the list, it
  does so simply by advancing down the list and returning a
  sublist that starts after those elements:

     (setq sample-list '(a b c (4)))
          => (a b c (4))

     (delq 'a sample-list) => (b c (4))
     sample-list           => (a b c (4))

Mention explicitly that the same thing is involved with *ALL* list-modification
operations.  The only things guaranteed by such operations are (a) the
modification of the list structure takes place as advertised, and (b) the return
value reflects the modified list structure correctly.

So if you want a variable to reflect the list correctly as modified then set its
value to the return value of the modification function.

bug#12314: 24.2.50; `add-to-history': use `setq' with `delete'

[Eli Zaretskii]

> From: "Drew Adams" <drew.adams@oracle.com>
> Cc: <cyd@gnu.org>, <12314@debbugs.gnu.org>
> Date: Sat, 8 Sep 2012 09:25:08 -0700
> 
> Go for it.  I suggest mentioning something like this in node `Modifying Lists'
> (and then cross-ref'ing that node from other nodes about functions that are
> destructive of list structure):

Why is it even necessary to talk about destructive modifications, if
we are to advise to assign the result anyway?

bug#12314: 24.2.50; `add-to-history': use `setq' with `delete'

[Drew Adams]

> Why is it even necessary to talk about destructive modifications, if
> we are to advise to assign the result anyway?

Not sure I understand the question.  It is because these operations can be
destructive of list structure that we advise that.

These operations are not concerned with any variables, period - they act only on
list structure.

If you have variables that point to some list structure that you modify somehow,
then it is up to you to ensure that the variables point to what you want them to
point to after such modification.

It all depends on what you want/need.

(This is a bit like using pointers.  A variable points to a particular cons
cell.  Modifying one or more cons cells in a chain might or might not change
that particular cons cell or cells that its cdr points to.  The variable
continues to point to the same cons cell, but that cell might not still reflect
the "list" that you expect it to reflect.)

bug#12314: 24.2.50; `add-to-history': use `setq' with `delete'

[Eli Zaretskii]

> From: "Drew Adams" <drew.adams@oracle.com>
> Cc: <cyd@gnu.org>, <12314@debbugs.gnu.org>
> Date: Sat, 8 Sep 2012 09:42:59 -0700
> 
> > Why is it even necessary to talk about destructive modifications, if
> > we are to advise to assign the result anyway?
> 
> Not sure I understand the question.  It is because these operations can be
> destructive of list structure that we advise that.

If you need to forget about the old value and assign the new one
returned by 'delete', why does it matter that the modification was
destructive?  That pertains to the old value that you need to toss
anyway.

> If you have variables that point to some list structure that you modify somehow,
> then it is up to you to ensure that the variables point to what you want them to
> point to after such modification.

Variables that point to that list structure will point to something
whose value is unpredictable, a.k.a. "garbage".  It is enough to say
that the old value is garbage and shouldn't be used, IMO.

> It all depends on what you want/need.

You can never want/need the old value, because you cannot predict what
it will be.

bug#12314: 24.2.50; `add-to-history': use `setq' with `delete'

[Drew Adams]

> > > Why is it even necessary to talk about destructive 
> > > modifications, if we are to advise to assign the result anyway?
> > 
> > Not sure I understand the question.  It is because these 
> > operations can be destructive of list structure that we advise that.
> 
> If you need to forget about the old value and assign the new one
> returned by 'delete', why does it matter that the modification was
> destructive?  That pertains to the old value that you need to toss
> anyway.

Perhaps we are miscommunicating.

That general advice about assigning the variable is only a general guideline; it
is not absolute.  You will NOT always want to assign the variable to the return
value.  It all depends on what you want/need.

The doc about these operations needs to describe what they do, and what they do
is typically destructive; that is, they typically modify list structure.

The bit about variables here is only a heads-up about a classic gotcha, nothing
more.  It is because we often have variables that are assigned/bound to the list
structure that we might be modifying that we should BE AWARE that these
operations do NOT do ANYTHING wrt variables.  

All they do is modify list structure.  We typically give them access to the list
structure via the values of variables.  But the operations have nothing to do
with the variables themselves - they are completely unaware of the existence of
any variables.

Hence, IF you want your variable, and not just some particular list structure,
to always be updated to reflect your modification, then that is a separate step
that you must perform after modification: assign the variable to the resulting
list structure that you want.

This is not so obvious to newbies, just as fiddling with pointers is not obvious
to a newbie to a language that has pointers.

A function such as `add-to-history' or `add-to-list' is something quite
different.  Those functions act on a VARIABLE, whose value is a list.  IOW, they
are aware of the existence of a certain variable - they are passed the SYMBOL as
argument, not just its value, and they make sure that the variable gets updated.

The modification functions that operate only on lists have no awareness of any
variables.  They are not passed a variable as argument.  Their job is simply to
return a list value, possibly (typically) modifying existing list structure in
the process.

> > If you have variables that point to some list structure 
> > that you modify somehow, then it is up to you to ensure that
> > the variables point to what you want them to point to after
> > such modification.
> 
> Variables that point to that list structure will point to something
> whose value is unpredictable, a.k.a. "garbage".  It is enough to say
> that the old value is garbage and shouldn't be used, IMO.

No.  It all depends.  Lisp programs that use list modification do so sometimes
for performance in calculating the new list, but more often they do so in order
to take advantage of SHARING list structure.

(This too is something not so obvious to newbies - they can get the impression
that these operations are mainly about saving cycles in calculating the return
value.)

For such programs - which are IMO the typical and the strongest (most important)
uses of list modification, what you call garbage is anything but.

Consider the example I gave before:

(setq a  '(1 2 3 4))
(setq b  (cddr a))

a => (1 2 3 4)
b => (3 4)

(delq 4 b)

a => (1 2 3)
b => (3)

The fact that modifying the list pointed to by `b' also modifies the list
pointed to by `a' is an advantage for certain kinds of programs.  Without a
separate `setq' operation, the variables point to the same cons cells they
pointed to at the outset.  And in some cases that is exactly what you want: you
want to remove the last link in the list that is shared by `a' and `b'.

List structure can be shared among multiple variables, so that changes to the
structure are seen by more than one - perhaps all.  Each variable provides a
different view of parts or all of the list structure.

> > It all depends on what you want/need.
> 
> You can never want/need the old value, because you cannot predict what
> it will be.

Not so.  If you know `a' and `b' before the operation then you know them
afterward as well.

What `a' and `b' here do NOT care about is `4' or the cons that contains `4' in
its car.  To THEM it is now garbage - it is no longer part of the lists THEY
point to.  But some other variable, `c', might well care about (point to) that
particular cons.  E.g.,

(setq a  '(1 2 3 4))
(setq b  (cddr a))
(setq c  (cdr b))

Here, `c' points to the last cons cell in `a' and `b'.  After the `delq'
operation, that cons cell is no longer part of the lists pointed to by `a' and
`b'.  But it is still pointed to by `c'.

And in such programs it can also be the case that what is garbage to `a' and `b'
now will later be important to them.  IOW, these 3 lists/views might well be
logically related and dynamically change in related ways.  

Removing the sublist `c' from `a' and `b' might be a temporary operation - that
sublist might be added back later.  And when it is added back it might no longer
contain `4' - it might then be (42 19 "hike").  You get the point.

It is probably easier to see all of this by looking at `setcar' and `setcdr'.
For `delq' we do not necessarily want/need to expose exactly how the
implementation works, other than to say what it does in general and point out
that it might NOT modify any existing list structure in some cases.  But for
`setcar' and `setcdr' the behavior is transparent and simple.  They always
modify list structure, and in simple ways.

Think of variables whose values are cons cells as pointers.  List modification
can move such pointers around.  In the above case, the pointer from the cdr of
the first cons of `b' to its second cons is changed to point to nil.  That's
all.  And `b' is a sublist of `a', so now `a's value reflects the structure
change also.

That can be a very handy thing.  Certain kinds of programs take advantage of
this sharing.  Others - most - do not.

bug#12314: 24.2.50; `add-to-history': use `setq' with `delete'

[Eli Zaretskii]

> From: "Drew Adams" <drew.adams@oracle.com>
> Cc: <cyd@gnu.org>, <12314@debbugs.gnu.org>
> Date: Sat, 8 Sep 2012 15:26:04 -0700
> 
> > > > Why is it even necessary to talk about destructive 
> > > > modifications, if we are to advise to assign the result anyway?
> > > 
> > > Not sure I understand the question.  It is because these 
> > > operations can be destructive of list structure that we advise that.
> > 
> > If you need to forget about the old value and assign the new one
> > returned by 'delete', why does it matter that the modification was
> > destructive?  That pertains to the old value that you need to toss
> > anyway.
> 
> Perhaps we are miscommunicating.
> 
> That general advice about assigning the variable is only a general guideline; it
> is not absolute.  You will NOT always want to assign the variable to the return
> value.  It all depends on what you want/need.

Please describe the situations with using 'delete' when the old value
will be wanted.  (Please try to do that succinctly, because I get lost
in your longish deliberations.)

> The doc about these operations needs to describe what they do, and what they do
> is typically destructive; that is, they typically modify list structure.
> 
> The bit about variables here is only a heads-up about a classic gotcha, nothing
> more.  It is because we often have variables that are assigned/bound to the list
> structure that we might be modifying that we should BE AWARE that these
> operations do NOT do ANYTHING wrt variables.  

Being aware doesn't solve problems.  To write reliable code, one needs
to always do certain things.  My understanding is that one must always
assign the new value, because the old one is unpredictable in general.

> > > If you have variables that point to some list structure 
> > > that you modify somehow, then it is up to you to ensure that
> > > the variables point to what you want them to point to after
> > > such modification.
> > 
> > Variables that point to that list structure will point to something
> > whose value is unpredictable, a.k.a. "garbage".  It is enough to say
> > that the old value is garbage and shouldn't be used, IMO.
> 
> No.  It all depends.  Lisp programs that use list modification do so sometimes
> for performance in calculating the new list, but more often they do so in order
> to take advantage of SHARING list structure.
> 
> (This too is something not so obvious to newbies - they can get the impression
> that these operations are mainly about saving cycles in calculating the return
> value.)

But the manual should cater first and foremost to newbies.  The rest
will get the point when they read the detailed description of how the
list is modified.

> (setq a  '(1 2 3 4))
> (setq b  (cddr a))
> 
> a => (1 2 3 4)
> b => (3 4)
> 
> (delq 4 b)
> 
> a => (1 2 3)
> b => (3)
> 
> The fact that modifying the list pointed to by `b' also modifies the list
> pointed to by `a' is an advantage for certain kinds of programs.  Without a
> separate `setq' operation, the variables point to the same cons cells they
> pointed to at the outset.  And in some cases that is exactly what you want: you
> want to remove the last link in the list that is shared by `a' and `b'.

I fail to see the utility of this.  Building code that relies on
internal implementation details is never a good idea.  But that's me;
please don't bother to argue.

bug#12314: 24.2.50; `add-to-history': use `setq' with `delete'

[Drew Adams]

> > The fact that modifying the list pointed to by `b' also 
> > modifies the list pointed to by `a' is an advantage for
> > certain kinds of programs.
> 
> I fail to see the utility of this.  Building code that relies on
> internal implementation details is never a good idea.  But that's me;
> please don't bother to argue.

Intentional list modification is not an implementation detail.  That is, it
concerns the implementation of your program, of course, but not the
implementation of Lisp itself.  You have to know what a given Lisp operation
does (side effects) and what it returns, but not how it is implemented.

My description of this area apparently did not help you.
Perhaps someone else can do better.

You might start here: (elisp) `Modifying Lists'.
You might search there for "share|sharing".

You might also google for, say, "lisp sharing list structure modification".
Looking at some of the hits, I think several should be helpful.

Here's one that might be another place to start:
http://en.wikipedia.org/wiki/Lisp_(programming_language)#Shared_structure

Perhaps you can imagine a complex program with a humongous graph structure
(already you see some sharing), which is dynamically modified.  Imagine
different views (e.g., variables) into various parts of that structure.  This
kind of Lisp program is not uncommon in some applications.  (The same could be
done using Java or C or whatever, but Lisp is good for doing things with lists.)

Lisp is not a purely functional language.  You need not like that, and you are
not forced to use `setf' etc. when programming in Lisp.  But such operations are
a part of Lisp, and they are used by some Lisp programs.  They are not a
mistake, but it is possible to make mistakes when using them.

bug#12314: 24.2.50; `add-to-history': use `setq' with `delete'

[Chong Yidong]

Eli Zaretskii <eliz@gnu.org> writes:

> But the manual should cater first and foremost to newbies.  The rest
> will get the point when they read the detailed description of how the
> list is modified.

I modified the manual to hopefully make the situation clearer.  In
particular, the descriptions of delq and delete explicitly say that you
typically ought to use the return value.

The docstrings are harder, since they should be succinct.  Here is what
I suggest; WDYT?


(delq ELT LIST)

Delete by side effect occurrences of ELT as a member of LIST.
Comparison is done with `eq'.  Return the resulting list.

More precisely, this function skips any occurrences of ELT at the
front of LIST, then removes occurrences of ELT from the remaining
sublist by modifying the list structure, then returns the resulting
sublist.

Therefore, write `(setq foo (delq element foo))' to be sure of
changing the value of `foo'.


(delete ELT SEQ)

Delete occurrence of ELT as a member of SEQ.
SEQ must be a sequence (i.e. a list, a vector, or a string).
Comparison is done with `equal'.  Return the resulting sequence.

If SEQ is a list, this behaves like `delq', except that it compares
with `equal' instead of `eq'.  In particular, it may remove elements
by altering the list structure.

If SEQ is not a list, deletion is not a side effect; this function
creates and returns a new sequence.

Therefore, write `(setq foo (delete element foo))'
to be sure of changing the value of `foo'.

bug#12314: 24.2.50; `add-to-history': use `setq' with `delete'

[Eli Zaretskii]

> From: Chong Yidong <cyd@gnu.org>
> Cc: Drew Adams <drew.adams@oracle.com>,  12314@debbugs.gnu.org
> Date: Sun, 09 Sep 2012 15:53:34 +0800
> 
> Eli Zaretskii <eliz@gnu.org> writes:
> 
> > But the manual should cater first and foremost to newbies.  The rest
> > will get the point when they read the detailed description of how the
> > list is modified.
> 
> I modified the manual to hopefully make the situation clearer.  In
> particular, the descriptions of delq and delete explicitly say that you
> typically ought to use the return value.

Thanks, the text is much better now.  I still think the "destructive
modification" part should be retired to later in the description,
perhaps as notes, because it invokes mental models that get in the way
of interpreting the text correctly.  But I won't fight over it.

> The docstrings are harder, since they should be succinct.  Here is what
> I suggest; WDYT?
> 
> 
> (delq ELT LIST)
> 
> Delete by side effect occurrences of ELT as a member of LIST.
> Comparison is done with `eq'.  Return the resulting list.
> 
> More precisely, this function skips any occurrences of ELT at the
> front of LIST, then removes occurrences of ELT from the remaining
> sublist by modifying the list structure, then returns the resulting
> sublist.
> 
> Therefore, write `(setq foo (delq element foo))' to be sure of
> changing the value of `foo'.

I would remove the "by side effect" part, as it doesn't really add
anything of importance, and OTOH runs a real risk of confusing the
reader.  Otherwise, I think this is fine.  Thanks.

> (delete ELT SEQ)
> 
> Delete occurrence of ELT as a member of SEQ.
> SEQ must be a sequence (i.e. a list, a vector, or a string).
> Comparison is done with `equal'.  Return the resulting sequence.
> 
> If SEQ is a list, this behaves like `delq', except that it compares
> with `equal' instead of `eq'.  In particular, it may remove elements
> by altering the list structure.
> 
> If SEQ is not a list, deletion is not a side effect; this function
> creates and returns a new sequence.
> 
> Therefore, write `(setq foo (delete element foo))'
> to be sure of changing the value of `foo'.

This is also OK, except that I'd prefer an explicit description to a
reference to 'delq' in the second paragraph.  The corresponding text
in the doc string of 'delq' is short enough, so there are no real
savings in the reference, while the disadvantage of having to consult
another doc string is real.

bug#12314: 24.2.50; `add-to-history': use `setq' with `delete'

[Wolfgang Jenkner]

On Sun, Sep 09 2012, Drew Adams wrote:

>> Variables that point to that list structure will point to something
>> whose value is unpredictable, a.k.a. "garbage".  It is enough to say
>> that the old value is garbage and shouldn't be used, IMO.
>
> No.  It all depends.  Lisp programs that use list modification do so sometimes
> for performance in calculating the new list, but more often they do so in order
> to take advantage of SHARING list structure.
>
> Consider the example I gave before:
>
> (setq a  '(1 2 3 4))
> (setq b  (cddr a))
>
> a => (1 2 3 4)
> b => (3 4)
>
> (delq 4 b)
>
> a => (1 2 3)
> b => (3)

Though using `delete' and friends this way would have unpredictable
results in ANSI Common Lisp[1] or Scheme (delete! in srfi1[2]), hence
may be regarded as questionable programming style in Emacs Lisp as well,
which I understand is Eli's point.

The following should work in both CL (except for the missing DEFVARs)
and Emacs Lisp, but sort of defeats the point about easy sharing ;-)

(setq a (list 1 2 3 4))
(setq b (cddr a))
(setf (cddr a) (setq b (delete 4 b)))

[1] http://www.lispworks.com/documentation/HyperSpec/Body/f_rm_rm.htm#delete
    http://www.lispworks.com/documentation/HyperSpec/Issues/iss293_w.htm

[2] http://srfi.schemers.org/srfi-1/srfi-1.html#LinearUpdateProcedures

Wolfgang

bug#12314: 24.2.50; `add-to-history': use `setq' with `delete'

[Stefan Monnier]

>> > Why is it even necessary to talk about destructive modifications, if
>> > we are to advise to assign the result anyway?
>> Not sure I understand the question.  It is because these operations can be
>> destructive of list structure that we advise that.
> If you need to forget about the old value and assign the new one
> returned by 'delete', why does it matter that the modification was
> destructive?

Because it avoids memory allocation.  I.e. 99% of the uses of
delete/delq/nconc are simple optimizations.


        Stefan

bug#12314: 24.2.50; `add-to-history': use `setq' with `delete'

[Eli Zaretskii]

> From: Stefan Monnier <monnier@iro.umontreal.ca>
> Cc: Drew Adams <drew.adams@oracle.com>,  12314@debbugs.gnu.org,  cyd@gnu.org
> Date: Sat, 08 Sep 2012 19:11:50 -0400
> 
> >> > Why is it even necessary to talk about destructive modifications, if
> >> > we are to advise to assign the result anyway?
> >> Not sure I understand the question.  It is because these operations can be
> >> destructive of list structure that we advise that.
> > If you need to forget about the old value and assign the new one
> > returned by 'delete', why does it matter that the modification was
> > destructive?
> 
> Because it avoids memory allocation.  I.e. 99% of the uses of
> delete/delq/nconc are simple optimizations.

I meant "why does it matter FOR THE USER that the modification was
destructive?"  Users don't care about optimizations, they only care
about performance.

bug#12314: 24.2.50; `add-to-history': use `setq' with `delete'

[Stefan Monnier]

>> Because it avoids memory allocation.  I.e. 99% of the uses of
>> delete/delq/nconc are simple optimizations.
> I meant "why does it matter FOR THE USER that the modification was
> destructive?"  Users don't care about optimizations, they only care
> about performance.

Because this optimization improves performance,


        Stefan

bug#12314: 24.2.50; `add-to-history': use `setq' with `delete'

[Eli Zaretskii]

> From: Stefan Monnier <monnier@iro.umontreal.ca>
> Cc: drew.adams@oracle.com,  12314@debbugs.gnu.org,  cyd@gnu.org
> Date: Sun, 09 Sep 2012 10:44:01 -0400
> 
> >> Because it avoids memory allocation.  I.e. 99% of the uses of
> >> delete/delq/nconc are simple optimizations.
> > I meant "why does it matter FOR THE USER that the modification was
> > destructive?"  Users don't care about optimizations, they only care
> > about performance.
> 
> Because this optimization improves performance,

But this optimization was already done.  We don't tell users in the
manuals about each and every optimization we do to improve
performance, do we?

bug#12314: 24.2.50; `add-to-history': use `setq' with `delete'

[Drew Adams]

> > >> Because it avoids memory allocation.  I.e. 99% of the uses of
> > >> delete/delq/nconc are simple optimizations.
> > >
> > > I meant "why does it matter FOR THE USER that the modification was
> > > destructive?"  Users don't care about optimizations, they 
> > > only care about performance.
> > 
> > Because this optimization improves performance,
> 
> But this optimization was already done.

??

> We don't tell users in the manuals about each and every
> optimization we do to improve performance, do we?

Eli, at the risk of butting in, I respectfully suggest that you might not be
reading about this topic well enough or perhaps not thinking enough about it.
The replies to you are now repetitive because there is not much more that can be
said in response.

Stefan is making the point that when programmers use `delete' or `delq' or
`nconc' they often do so to improve the performance of their code.  Which is
true.

We document what these functions do, including the fact that because of what
they do they can often improve performance.  And we mention caveats that users
of such functions need to be aware of.

This is not about any optimization that "we" do in implementing Emacs, i.e.,
something that Emacs does in its implementation, under the covers.

This is about an intentional optimization that some Lisp programmers sometimes
use in their own code.  You can use destructive operations like `delete' to
improve performance, but if you do so then you should be aware of some possible
pitfalls.  That's all.

bug#12314: 24.2.50; `add-to-history': use `setq' with `delete'

[Eli Zaretskii]

> From: "Drew Adams" <drew.adams@oracle.com>
> Cc: <12314@debbugs.gnu.org>, <cyd@gnu.org>
> Date: Sun, 9 Sep 2012 10:35:21 -0700
> 
> Eli, at the risk of butting in, I respectfully suggest that you might not be
> reading about this topic well enough or perhaps not thinking enough about it.

How is this remark helpful?

> Stefan is making the point that when programmers use `delete' or `delq' or
> `nconc' they often do so to improve the performance of their code.  Which is
> true.

This is an entirely different issue.  "Destructive modification" does
not imply the optimization you (and evidently Stefan) are alluding to,
at least not universally so, nor a possibility to piggy-back that to
optimize application code.  It just means that the original object is
modified (a.k.a. "destroyed") in the process.

bug#12314: 24.2.50; `add-to-history': use `setq' with `delete'

[Drew Adams]

> > Eli, at the risk of butting in, I respectfully suggest that 
> > you might not be reading about this topic well enough or
> > perhaps not thinking enough about it.
> 
> How is this remark helpful?

I am sincerely _trying_ to help you.  I've tried to explain and give examples.
I've pointed you to other explanations on line and elsewhere in the Elisp
manual.  And I've suggested that you take a bit more time to study and think
about what you've read.  And I would add, perhaps experiment.

If my attempts to help do not help you or you do not appreciate them, sorry.

This is really not that big a deal.  Ask around.  This is a common question and
lots of people have explained it in various ways.  Take your pick.

> > Stefan is making the point that when programmers use 
> > `delete' or `delq' or `nconc' they often do so to improve
> > the performance of their code.  Which is true.
> 
> This is an entirely different issue.  "Destructive modification" does
> not imply the optimization you (and evidently Stefan) are alluding to,
> at least not universally so, nor a possibility to piggy-back that to
> optimize application code.  It just means that the original object is
> modified (a.k.a. "destroyed") in the process.

To quote a famous person (you), I give up.  I sincerely hope someone else helps
you find what you're looking for.  If not, maybe you will reread the thread or
the manual at a later date and you will find it yourself.  Sometimes that's all
it takes for things to become clear.

bug#12314: 24.2.50; `add-to-history': use `setq' with `delete'

[Stefan Monnier]

>> > I meant "why does it matter FOR THE USER that the modification was
>> > destructive?"  Users don't care about optimizations, they only care
>> > about performance.
>> Because this optimization improves performance,
> But this optimization was already done.  We don't tell users in the
> manuals about each and every optimization we do to improve
> performance, do we?

I don't understand the question: the user of delete/delq/nconc (the one
reading their docstring or their texinfo doc) is the person
reading/writing the code, and the optimization is the act of choosing
delete over remove or delq over remq or nconc over append, which is
exactly what the reader will want to know, I think.


        Stefan

bug#12314: 24.2.50; `add-to-history': use `setq' with `delete'

[Eli Zaretskii]

> From: Stefan Monnier <monnier@iro.umontreal.ca>
> Cc: drew.adams@oracle.com,  12314@debbugs.gnu.org,  cyd@gnu.org
> Date: Sun, 09 Sep 2012 17:37:53 -0400
> 
> >> > I meant "why does it matter FOR THE USER that the modification was
> >> > destructive?"  Users don't care about optimizations, they only care
> >> > about performance.
> >> Because this optimization improves performance,
> > But this optimization was already done.  We don't tell users in the
> > manuals about each and every optimization we do to improve
> > performance, do we?
> 
> I don't understand the question: the user of delete/delq/nconc (the one
> reading their docstring or their texinfo doc) is the person
> reading/writing the code, and the optimization is the act of choosing
> delete over remove or delq over remq or nconc over append, which is
> exactly what the reader will want to know, I think.

See my other message: I think we are talking about 2 different
things.  My gripe was only about using the term "destructive
modification", which muddies the waters without gaining anything.

bug#12314: 24.2.50; `add-to-history': use `setq' with `delete'

[Stefan Monnier]

> See my other message: I think we are talking about 2 different
> things.  My gripe was only about using the term "destructive
> modification", which muddies the waters without gaining anything.

I don't know, to me "destructive modification" sounds like a very clear
term explaining the general kind of danger we're up against (the kind
that's summarized in Scheme by adding a "!" at the end of the
identifier).


        Stefan

bug#12314: 24.2.50; `add-to-history': use `setq' with `delete'

[Stefan Monnier]

>> See my other message: I think we are talking about 2 different
>> things.  My gripe was only about using the term "destructive
>> modification", which muddies the waters without gaining anything.
> I don't know, to me "destructive modification" sounds like a very clear
> term explaining the general kind of danger we're up against (the kind
> that's summarized in Scheme by adding a "!" at the end of the
> identifier).

This said, we could use some other "equivalent" term, such as "side
effect", "imperative", "impure", ...


        Stefan

bug#12314: 24.2.50; `add-to-history': use `setq' with `delete'

[Drew Adams]

> > My gripe was only about using the term "destructive
> > modification", which muddies the waters without gaining anything.
> 
> I don't know, to me "destructive modification" sounds like a 
> very clear term explaining the general kind of danger we're up
> against (the kind that's summarized in Scheme by adding a "!" at
> the end of the identifier).

The term itself does not _explain_ the danger, but it does suggest some danger.

Strictly speaking, "destructive modification" is redundant - all modification
replaces one state by another: it destroys an old state and creates a new one.

But Lisp being entre deux chaises (functional, imperative/procedural), and given
the existence of similar-sounding Lisp functions such as `remove' and `delete',
it is worth emphasizing the difference (for the doc of both `remove' and
`delete').

For the non-modifying one, we point out explicitly that it is "non-destructive".
For the modifying one, we point out explicitly that it modifies something, as a
side effect, and we (conventionally, in Lisp jargon) call it "destructive".

It's about the doc being not only correct but also more helpful.  Sometimes a
bit of redundancy has pedagogical merit.  Sometimes redundancy is just noise to
wade through.  Here, specifically because of the "danger"/gotchas, it does not
hurt to add "destructive", IMO.

It is really the names of "non-destructive" functions such as `append' and
`remove' that are misleading.  They necessitate our taking pains to explain that
no real modification takes place.  Names that better suggest the declarative
nature of such functions might be, say, `concatenation' and `all-but' (or
`removed').

Names such as `append' and `remove' do not describe the result value of the
function.  Instead, they describe a modifying operation that might have nothing
to do with the actual implementation (which is not so important here anyway),
and they take emphasis away from what is important for a pure function: the
return value.

But such procedurally oriented naming is pretty common/traditional, even for
applicative languages.  And it tends toward shorter, simpler names.

bug#12314: 24.2.50; `add-to-history': use `setq' with `delete'

[Eli Zaretskii]

> From: Stefan Monnier <monnier@iro.umontreal.ca>
> Cc: drew.adams@oracle.com,  12314@debbugs.gnu.org,  cyd@gnu.org
> Date: Mon, 10 Sep 2012 08:59:26 -0400
> 
> > See my other message: I think we are talking about 2 different
> > things.  My gripe was only about using the term "destructive
> > modification", which muddies the waters without gaining anything.
> 
> I don't know, to me "destructive modification" sounds like a very clear
> term explaining the general kind of danger we're up against (the kind
> that's summarized in Scheme by adding a "!" at the end of the
> identifier).

Alas, the manual itself gives no basis for such an interpretation.  It
says (in two different places):

  You can modify the CAR and CDR contents of a cons cell with the
  primitives `setcar' and `setcdr'.  We call these "destructive"
  operations because they change existing list structure.

  Here are some functions that rearrange lists "destructively" by
  modifying the CDRs of their component cons cells.  We call these
  functions "destructive" because they chew up the original lists passed
  to them as arguments, relinking their cons cells to form a new list that
  is the returned value.

The only danger I glean from these is the "danger" of assigning any
meaning to the original list.

bug#12314: 24.2.50; `add-to-history': use `setq' with `delete'

[Dmitry Gutov]

Chong Yidong <cyd@gnu.org> writes:

 > Eli Zaretskii <eliz@gnu.org> writes:
 >
 >> But the manual should cater first and foremost to newbies.  The rest
 >> will get the point when they read the detailed description of how the
 >> list is modified.
 >
 > I modified the manual to hopefully make the situation clearer.  In
 > particular, the descriptions of delq and delete explicitly say that you
 > typically ought to use the return value.
 >
 > The docstrings are harder, since they should be succinct.  Here is what
 > I suggest; WDYT?
 >
 >
 > (delq ELT LIST)
 >
 > ...
 >
 > Therefore, write `(setq foo (delq element foo))' to be sure of
 > changing the value of `foo'.

I think the last sentence could be better: (a) the value of foo won't
necessarily change, even if we do (setq ...), (b) our goal is for foo to
have the correct value, some not changed one. How about this?

Therefore, write `(setq foo (delq element foo))' to make sure that
`foo' points to the result.