Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!mailrus!purdue!decwrl!shelby!neon!michaelg
From: michaelg@Neon.Stanford.EDU (Michael Greenwald)
Newsgroups: comp.lang.lisp
Subject: Re: Are "destructive" functions really destructive?
Message-ID: <1989Nov29.212142.7735@Neon.Stanford.EDU>
Date: 29 Nov 89 21:21:42 GMT
References: <20991@mimsy.umd.edu> <1989Nov29.173139.26165@Neon.Stanford.EDU> <1989Nov29.191106.10329@cs.rochester.edu>
Sender: USENET News System <news@Neon.Stanford.EDU>
Distribution: usa
Organization: Computer Science Department, Stanford University
Lines: 52

koomen@cs.rochester.edu (Hans Koomen) writes:

>You don't need to walk down the entire list to knock off the last cons.  When
>deleting the first element of a 2+ element list, the Interlisp equivalent of
>Common Lisp delete, dremove, effectively does
>	(progn (rplaca x (cadr x)) (rplacd x (cddr x)))
>i.e., splices out the second cons after stuffing value of the second car into
>the first car.  No pathology required here to maintain eq-ness.

Some of the time.

The reason it's pathological was not because it has to walk down the
entire list (it has to do that anyway, to delete multiple copies of
item), but because the idea of implementing delete that way would only
make sense if you are trying to maintain EQness.  But >in general<
that can't work, because you won't win (as you mention) if the result
of an application of delete is NIL.  Therefore it's pathological to
try to make it work in only a subset of the cases.

It's also pathological because if you try to make delete "consistent"
about side-effecting, then I suppose one could argue that some
definition about the side-effect on sublists should be specified. But
I'm hard pressed to come up with one that would work.  (The Interlisp
definition you quote above certainly won't work, if you have two
people sharing list structure of x and (cdr x)).  Once properties like
that don't work, you might as well require people to only depend on
the value of delete, and not on side-effect.  To go to some lengths to
make a certain property hold (in only some of the cases) seems
pathological to me.  By calling delete instead of remove, you are
stating that you don't care to depend on side-effects (or the lack
thereof) to sequence.

(I must confess that I don't have a strict or well-defined definition
of "pathological", so if you are trying to make some point about, or
that depends upon, a precise definition of pathological, then I'm
probably wrong.)

In general, I think we both probably agree about the larger point:
DELETE can't preserve EQness by simply side-effecting SEQUENCE, and
you should always use the value of (DELETE ITEM SEQUENCE), rather than
depending on details of the implementation, or of your data, to
side-effect your SEQUENCE properly.

>The real problem lies in removing the first element of a 1-element list, 

Or all N elements of an N element list, '(a a a a a a a a).

>e.g.
>if x is bound to '(a) then (delete 'a x) returns nil, but there's no way for
>the delete function to know that its second argument, (a), was the binding of
>the variable x, and that x should be set to nil!
>--