From: Peter Seibel
Subject: destructive operators
Date: 
Message-ID: <m3r88gnz6h.fsf@javamonkey.com>
I had always understood that even with destructive operators it's good
form to save the return value. For example one should write:

  (setq x (nsubst 'z 'a x))

rather than just:

  (nsubst 'z 'a x)

However, some of the destructive operators (NSUBST being one) seem to
be documented in a particularly precise way: "The list structure of
tree is altered by destructively replacing with *new* each leaf of the
tree such that *old* and the leaf satisfy the test." Reading that, it
seems like I could use the second form above, since I know exactly
what's going to happen to my tree.

So, was my initial understanding wrong? Or is it just a style thing to
always reset the value you are changing because some destructive
operators really are destructive in the sense that they leave the
original data structure in shambles?

-Peter

-- 
Peter Seibel                                      ·····@javamonkey.com

  The intellectual level needed   for  system design is  in  general
  grossly  underestimated. I am  convinced  more than ever that this
  type of work is very difficult and that every effort to do it with
  other than the best people is doomed to either failure or moderate
  success at enormous expense. --Edsger Dijkstra

From: Kenny Tilton
Subject: Re: destructive operators
Date: 
Message-ID: <3E8F947F.3070508@nyc.rr.com>
Peter Seibel wrote:
> I had always understood that even with destructive operators it's good
> form to save the return value. For example one should write:
> 
>   (setq x (nsubst 'z 'a x))
> 
> rather than just:
> 
>   (nsubst 'z 'a x)
> 
> However, some of the destructive operators (NSUBST being one) seem to
> be documented in a particularly precise way: "The list structure of
> tree is altered by destructively replacing with *new* each leaf of the
> tree such that *old* and the leaf satisfy the test." Reading that, it
> seems like I could use the second form above, since I know exactly
> what's going to happen to my tree.

depends on the "tree":

(let ((tree 2))
   (list (nsubst 1 2 tree) tree))

=> (1 2)


-- 

  kenny tilton
  clinisys, inc
  http://www.tilton-technology.com/
  ---------------------------------------------------------------
"Everything is a cell." -- Alan Kay
From: Peter Seibel
Subject: Re: destructive operators
Date: 
Message-ID: <m3n0j4nx6t.fsf@javamonkey.com>
Kenny Tilton <·······@nyc.rr.com> writes:

> Peter Seibel wrote:
> > I had always understood that even with destructive operators it's good
> > form to save the return value. For example one should write:
> >   (setq x (nsubst 'z 'a x))
> 
> > rather than just:
> 
> >   (nsubst 'z 'a x)
> 
> > However, some of the destructive operators (NSUBST being one) seem to
> 
> > be documented in a particularly precise way: "The list structure of
> > tree is altered by destructively replacing with *new* each leaf of the
> > tree such that *old* and the leaf satisfy the test." Reading that, it
> > seems like I could use the second form above, since I know exactly
> > what's going to happen to my tree.
> 
> depends on the "tree":
> 
> (let ((tree 2))
>    (list (nsubst 1 2 tree) tree))
> 
> => (1 2)

Okay. So I'm convinced that my original sense was right--it's just
always a good idea to use the return value.

-Peter


-- 
Peter Seibel                                      ·····@javamonkey.com

  The intellectual level needed   for  system design is  in  general
  grossly  underestimated. I am  convinced  more than ever that this
  type of work is very difficult and that every effort to do it with
  other than the best people is doomed to either failure or moderate
  success at enormous expense. --Edsger Dijkstra
From: JP Massar
Subject: Re: destructive operators
Date: 
Message-ID: <3e9056cb.150314693@netnews.attbi.com>
On Sun, 06 Apr 2003 02:23:50 GMT, Peter Seibel <·····@javamonkey.com>
wrote:

>I had always understood that even with destructive operators it's good
>form to save the return value. For example one should write:
>
>  (setq x (nsubst 'z 'a x))
>
>rather than just:
>
>  (nsubst 'z 'a x)
>
>However, some of the destructive operators (NSUBST being one) seem to
>be documented in a particularly precise way: "The list structure of
>tree is altered by destructively replacing with *new* each leaf of the
>tree such that *old* and the leaf satisfy the test." Reading that, it
>seems like I could use the second form above, since I know exactly
>what's going to happen to my tree.
>
>So, was my initial understanding wrong? Or is it just a style thing to
>always reset the value you are changing because some destructive
>operators really are destructive in the sense that they leave the
>original data structure in shambles?
>
>-Peter
 
(setq x '(a b c d e))
(A B C D E)
 (delete 'a x)
(B C D E)
 x
(A B C D E)
From: Peter Seibel
Subject: Re: destructive operators
Date: 
Message-ID: <m31y0fo48l.fsf@javamonkey.com>
······@alum.mit.edu (JP Massar) writes:

> On Sun, 06 Apr 2003 02:23:50 GMT, Peter Seibel <·····@javamonkey.com>
> wrote:
> 
> >I had always understood that even with destructive operators it's good
> >form to save the return value. For example one should write:
> >
> >  (setq x (nsubst 'z 'a x))
> >
> >rather than just:
> >
> >  (nsubst 'z 'a x)
> >
> >However, some of the destructive operators (NSUBST being one) seem to
> >be documented in a particularly precise way: "The list structure of
> >tree is altered by destructively replacing with *new* each leaf of the
> >tree such that *old* and the leaf satisfy the test." Reading that, it
> >seems like I could use the second form above, since I know exactly
> >what's going to happen to my tree.
> >
> >So, was my initial understanding wrong? Or is it just a style thing to
> >always reset the value you are changing because some destructive
> >operators really are destructive in the sense that they leave the
> >original data structure in shambles?
> >
> >-Peter
>  
> (setq x '(a b c d e))
> (A B C D E)
>  (delete 'a x)
> (B C D E)
>  x
> (A B C D E)

Right. I get it that some destructive operators work this way. I was
just surprised that some others (such as nsubst) seemed to be
specified sufficiently precisely that one could depend on the side
effects. But Kenny convinced me that even the one I *thought* I
understood had edge cases that I missed. So I'm a believer now. ;-)
Always save the return value.

-Peter

-- 
Peter Seibel                                      ·····@javamonkey.com

  The intellectual level needed   for  system design is  in  general
  grossly  underestimated. I am  convinced  more than ever that this
  type of work is very difficult and that every effort to do it with
  other than the best people is doomed to either failure or moderate
  success at enormous expense. --Edsger Dijkstra
From: Kaz Kylheku
Subject: Re: destructive operators
Date: 
Message-ID: <cf333042.0304071100.7f809e6f@posting.google.com>
Peter Seibel <·····@javamonkey.com> wrote in message news:<··············@javamonkey.com>...
> I had always understood that even with destructive operators it's good
> form to save the return value. For example one should write:
> 
>   (setq x (nsubst 'z 'a x))
> 
> rather than just:
> 
>   (nsubst 'z 'a x)

It's not a matter of good form, but simple correctness. If the value
of x is going to be used, then it's necessary to rebind it to the
output of the destructive operation, if that operation may rearrange
the cons cells.

I think that in the case of NSUBST, I think you have nothing to worry
about.

> However, some of the destructive operators (NSUBST being one) seem to
> be documented in a particularly precise way: "The list structure of
> tree is altered by destructively replacing with *new* each leaf of the
> tree such that *old* and the leaf satisfy the test." Reading that, it
> seems like I could use the second form above, since I know exactly
> what's going to happen to my tree.

That's correct; the operation will only operate on CAR fields, and
only those which don't point to conses. So you know that the cons cell
backbone of the tree remains intact; you have just replaced some of
the decorations. Or so I think; I better check that HyperSpec to be
sure!

> So, was my initial understanding wrong? Or is it just a style thing to
> always reset the value you are changing because some destructive
> operators really are destructive in the sense that they leave the
> original data structure in shambles?

I would say that style is no subst-itute for proper understanding. ;)

You need to rebind the variable even if you are doing non-destructive
operations, simply because you need the variable to be the new object,
rather than the old:

   ;; wrong
   (append x y)

   ;; programmer intended:
   (setf y (append x y))

The mistake exists whether we use APPEND or NCONC; it's just that
NCONC also scrambles the list x which may or may not be a problem! In
this case, y is not affected by NCONC, because it's the rightmost
parameter; so its destructiveness is not the reason for doing the
SETF.

Since NCONC can clobber the list pointed to by X, any expressions
which depend on the value of X afterward may be incorrect. So if we
are going to add a setf to guard against this possibility, perhaps it
should be like this:

   (setf y (nconc x y))
   (setf x #:destroyed-junk)

Since Lisp doesn't provide us with a way to render a lexical variable
unbound, we bind it to a gensym. Hopefully, this gensym will trigger
an error when someone something accidentally tries to use the variable
as a proper list. In the case of a dynamic variable, we can use
mkunbound, so that any evaluation of it signals an error.

But even better than such devices is simply to write clear code which
makes them unnecessary by containing the effects of the destruction to
a small and easily understood region of computation, where by simple
inspection the programmer can prove to herself that it's right.
From: Peter Seibel
Subject: Re: destructive operators
Date: 
Message-ID: <m3he9acass.fsf@javamonkey.com>
···@ashi.footprints.net (Kaz Kylheku) writes:

> Peter Seibel <·····@javamonkey.com> wrote in message news:<··············@javamonkey.com>...
> > I had always understood that even with destructive operators it's good
> > form to save the return value. For example one should write:
> > 
> >   (setq x (nsubst 'z 'a x))
> > 
> > rather than just:
> > 
> >   (nsubst 'z 'a x)
> 
> It's not a matter of good form, but simple correctness. If the value
> of x is going to be used, then it's necessary to rebind it to the
> output of the destructive operation, if that operation may rearrange
> the cons cells.
> 
> I think that in the case of NSUBST, I think you have nothing to
> worry about.

As I thought. But as Kenny Tilton pointed out there is an edge case:

  (let ((tree 1)) (list (nsubst 2 1 tree) tree)) => (2 1)

-Peter

-- 
Peter Seibel                                      ·····@javamonkey.com

  The intellectual level needed   for  system design is  in  general
  grossly  underestimated. I am  convinced  more than ever that this
  type of work is very difficult and that every effort to do it with
  other than the best people is doomed to either failure or moderate
  success at enormous expense. --Edsger Dijkstra