From: Wayne Folta
Subject: Are "destructive" functions really destructive?
Date:
Message-ID: <20991@mimsy.umd.edu>
I take it from the Common LISP Reference that functions marked "(destructive)"
are destructive in the sense that they *may be* destructive in some way.
Is it thus true that I cannot count on destructive behavior when I want it?
For example, if I want to delete something from a large datastructure, I
assume that I would use "delete":
(delete item huge-list :key #'my-key)
Or do I need to do:
(setq huge-list (delete item huge-list :key #'my-key))
In the Reference, it says, "..., or sequence may be unchanged and another
sequence returned.", which would seem to make "delete" different from "nconc"
in this respect. So destructiveness is an option for the convenience of LISP
implementation creators, not users?
Wayne Folta (·····@cs.umd.edu 128.8.128.8)
From: William J. Bouma
Subject: Re: Are "destructive" functions really destructive?
Date:
Message-ID: <8769@medusa.cs.purdue.edu>
In article <·····@mimsy.umd.edu> ·····@tove.umd.edu (Wayne Folta) writes:
>Is it thus true that I cannot count on destructive behavior when I want it?
>
>In the Reference, it says, "..., or sequence may be unchanged and another
>sequence returned.", which would seem to make "delete" different from "nconc"
>in this respect. So destructiveness is an option for the convenience of LISP
>implementation creators, not users?
Destructive operations are not really any easier to implement. Rather
they are faster and consume less memory than the identical but copying
operations. Thus they benefit the user.
Which reference are you quoting? It may be messed up! What good are
destructive operations if they aren't truely destructive? Even in
CLtL the wording is strange for this, "The argument SEQUENCE may be
destroyed and used to construct the result;" (pg. 254, delete). Why
does it say 'may' instead of 'will'? It could be just to account for
the case when no element is deleted.
Note that it is good practice to wrap your destructive operation
in a 'setf' anyway. It usually isn't too difficult and can keep you
from getting nailed by special cases you have overlooked. For instance
what if the element you are deleting is the first one in the list?
> (setq *b* '(a b c d))
(A B C D)
> (delete 'a *b*)
(B C D)
> *b*
(A B C D)
In this case, the resulting sequence is not EQ to the argument.
--
Bill <·····@cs.purdue.edu> || ...!purdue!bouma
·····@tove.umd.edu (Wayne Folta) writes:
>I take it from the Common LISP Reference that functions marked "(destructive)"
>are destructive in the sense that they *may be* destructive in some way.
>Is it thus true that I cannot count on destructive behavior when I want it?
Yes. (I assume you mean by "count on" .. "when I want it" that
identity of the argument would be preserved. It would be hard to
"count on" some internal detail not specified by the language
specification.)
>For example, if I want to delete something from a large datastructure, I
>assume that I would use "delete":
> (delete item huge-list :key #'my-key)
No.
>Or do I need to do:
> (setq huge-list (delete item huge-list :key #'my-key))
Yes.
>In the Reference, it says, "..., or sequence may be unchanged and another
>sequence returned.", which would seem to make "delete" different from "nconc"
>in this respect. So destructiveness is an option for the convenience of LISP
>implementation creators, not users?
No, this behavior is dictated by the semantics of delete. To wit,
(let ((x (copy-list '(a b c d e f))))
(setq y (delete 'a x)))
There is no reasonable way to destructively "modify" x so that delete
will work and you maitain EQness, since in this case DELETE == CDR.
In other words, you lose the first cons cell, and the rest of the list
is untouched.
(I'm ignoring the pathological implementation of altering the CAR of
every sublist, and knocking off the last cons.)
>Wayne Folta (·····@cs.umd.edu 128.8.128.8)
In article <······················@Neon.Stanford.EDU> ········@Neon.Stanford.EDU (Michael Greenwald) writes:
>·····@tove.umd.edu (Wayne Folta) writes:
>
>>I take it from the Common LISP Reference that functions marked "(destructive)"
>>are destructive in the sense that they *may be* destructive in some way.
>>Is it thus true that I cannot count on destructive behavior when I want it?
>
>Yes.
>>In the Reference, it says, "..., or sequence may be unchanged and another
>>sequence returned.", which would seem to make "delete" different from "nconc"
>>in this respect. So destructiveness is an option for the convenience of LISP
>>implementation creators, not users?
>
>No, this behavior is dictated by the semantics of delete. To wit,
>
>(let ((x (copy-list '(a b c d e f))))
> (setq y (delete 'a x)))
>
>There is no reasonable way to destructively "modify" x so that delete
>will work and you maitain EQness, since in this case DELETE == CDR.
There are unreasonable ways to do this, but michaelg correctly points
out that it's far more efficient to return the cdr of the original
list as the new sequence.
But consider the case of
(let ((x (copy-list '(a a a))))
(setq x (delete 'a x)))
Here, there's no way that (delete 'a x) could by itself modify the
variable x to be NIL because delete gets a copy of x's value, not of
x's location.
If delete's behavior really bothers you, you can construct a deletef
macro like:
(defmacro deletef (item place)
`(setf ,place (delete ,item ,place)))
Obviously this isn't completely equivalent to delete; caveat emptor
and all that.
Tim Moore ·····@cs.utah.edu {bellcore,hplabs}!utah-cs!moore
"Ah, youth. Ah, statute of limitations."
-John Waters
From: Dan Hoey
Subject: Re: Are "destructive" functions really destructive?
Date:
Message-ID: <372@ai.etl.army.mil>
In article <·····················@hellgate.utah.edu> ··················@cs.utah.edu (Tim Moore) writes:
...
>If delete's behavior really bothers you, you can construct a deletef
>macro like:
>
>(defmacro deletef (item place)
> `(setf ,place (delete ,item ,place)))
>
>Obviously this isn't completely equivalent to delete; caveat emptor
Perhaps something more like
(defmacro deletef (item place &rest delete-options &aux (itemv (gensym)))
(multiple-value-bind (vars vals store store-form access-form)
(get-setf-method place)
`(let* ((,itemv ,item)
,.(mapcar #'list vars vals)
(,(car store) (delete ,itemv ,access-form ,@delete-options)))
,store-form
,(car store))))
Dan
Michael Greenwald <········@Neon.Stanford.EDU> writes:
...
>(let ((x (copy-list '(a b c d e f))))
> (setq y (delete 'a x)))
>
>There is no reasonable way to destructively "modify" x so that delete
>will work and you maitain EQness, since in this case DELETE == CDR.
>In other words, you lose the first cons cell, and the rest of the list
>is untouched.
>
>(I'm ignoring the pathological implementation of altering the CAR of
>every sublist, and knocking off the last cons.)
>
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.
The real problem lies in removing the first element of a 1-element list, 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!
--
- - - /-/ a n s
······@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!
>--
In article <·····@mimsy.umd.edu> ·····@tove.umd.edu (Wayne Folta) writes:
>For example, if I want to delete something from a large datastructure, I
>assume that I would use "delete":
>
> (delete item huge-list :key #'my-key)
>
>Or do I need to do:
>
> (setq huge-list (delete item huge-list :key #'my-key))
Either one of these will work AS LONG AS THE DELETED ITEM WASN'T THE
FIRST ELEMENT OF THE LIST! You need to use the second version to deal
with the fact that using DELETE to remove the first element leaves the
rest of the list unchanged. Since the deleted element will not be
modified, it will still point to the rest of the list.
DELETE is a function. By the time it's called, the HUGE-LIST argument
has been evaluated to the first CONS in the list. DELETE can't do the
SETQ for you, since it doesn't know what variable to SETQ.
>
>So destructiveness is an option for the convenience of LISP
>implementation creators, not users?
>
On the contrary. Destructiveness saves the user a lot of extra
consing by reusing the same list. By and large, ease of
implementation was *not* a major consideration in the design of Common
Lisp. And it shows.
--
Hank Shiffman (415) 336-4658
Marketing Technical Specialist
Software Engineering Technologies ...!sun!shiffman
Sun Microsystems, Inc. ········@Sun.com
Zippy sez:
Do you have exactly what I want in a plaid poindexter bar bat??
·····@tove.umd.edu writes:
> [Concerning delete, is it destructive or what?] In the Reference, it says,
> "..., or sequence may be unchanged and another sequence returned.",
Although I'm not familiar with your reference, the problem may be a simple
misunderstanding. What can be said about value returned by delete after
removing 1 from the following list?
L --> (1 -2 3 -5 8 -13)
In this case, it appears reasonable for delete to simply return the cdr of L.
So, L (that is, the list referenced by L) is unchanged, and a list that is not
L (namely, L's cdr) is being returned.
Awkward? Naw. Ok, well, maaaybe. Happy Hunting, [Ag]
I'm well aware of this problem with "delete" (that you need to setq a
variable upon returning in case its the first element of a list) in
using Lisp. However, I don't understand why "delete" was not
implemented as a macro to make the semantics of its destructive
operation consistent. To have a function which applies to different
sequence types but performs differently for one implementation seems
bogus to me:
> (setq string "123")
"123"
> (setq list '(1 2 3))
'(1 2 3)
> (delete #\1 string)
"23"
> string
"23"
> (delete 1 list)
'(2 3)
> list
'(1 2 3)
It seems cleaner to have (delete item sequence) expand to something
like (no, this doesn't do all the proper checking):
`(if (listp ,sequence)
(setf ,sequence
(CL-delete ,item ,sequence)))
Where "CL-delete" would be the current CL delete function. Of course,
if the types are known at compile-time then we can even remove the
check. Is this a case where upward compatibility has ruined the
elegance of the language standard?
Karl B. Schwamb ·······@ics.uci.edu
Information and Computer Science
University of California, Irvine 92715
·······@ics.uci.edu (Karl Schwamb) writes:
>.... However, I don't understand why "delete" was not
>implemented as a macro to make the semantics of its destructive
>operation consistent. To have a function which applies to different
>sequence types but performs differently for one implementation seems
>bogus to me:
If you always use delete for value, rather than for effect, then it
always behaves consistently.
>It seems cleaner to have (delete item sequence) expand to something
>like (no, this doesn't do all the proper checking):
> `(if (listp ,sequence)
> (setf ,sequence
> (CL-delete ,item ,sequence)))
>Where "CL-delete" would be the current CL delete function.
By the way, your implementation doesn't work when sequence is the
result of function application. It is illegal to "apply" (if such
terminology is appropriate for a macro) SETF to something that isn't a
"place". Or is this one of the things you were referring to when you
said "this doesn't do all the proper checking"?
>Of course,
>if the types are known at compile-time then we can even remove the
>check. Is this a case where upward compatibility has ruined the
>elegance of the language standard?
I don't think so.
CL-delete doesn't side-effect the environment, while your macroized
delete does.
Yes, CL-delete does side-effect sequence (and if sequence is shared,
and isn't just an intermediate result, then the side-effect is visible
in the "environment"), but if delete is always used "functionally"
(for value) you can argue convincingly that cl-delete is cleaner than
your delete (if you subscribe to the notion, as many do, that
side-effects aren't particularly clean, and therefore should be
minimized).
Reasonable people might differ about whether CL-delete is cleaner than
your macroized delete (I strongly prefer CL-delete), but I don't think
this is "a case where upward compatibility has ruined the elegance of
the language standard"
In article <··············@paris.ics.uci.edu> ·······@ics.uci.edu (Karl Schwamb) writes:
>It seems cleaner to have (delete item sequence) expand to something
>like (no, this doesn't do all the proper checking):
> `(if (listp ,sequence)
> (setf ,sequence
> (CL-delete ,item ,sequence)))
Lisp is a *functional* programming language, and the above is contrary to
that philosophy.
For instance, what happens when sequence isn't a place that can be SETFed?
For instance, one might write code like:
(setq result (delete item (append foo bar baz)))
Or what if you didn't really need to store the result back into the
variable the list came from, e.g.
(let (other-list
(*list* (compute-the-list)))
(declare (special *list*))
<do stuff ...>
(setq other-list (delete item *list*))
<do more stuff ...>
)
If nothing in <do more stuff ...> references *list* then there is no need
to store the result back there, since the value will bt thrown away when
the LET returns. If *list* were a lexical variable then the compiler could
discover that the store is unnecessary using live variable analysis, but
since it's a special variable this is not always feasible.
If you want a DELETEF macro, create one. This would be just like the
distinction between 1+ and INCF. If you think DELETEF should have been
included in the standard language as INCF was, that's a completely
different issue. I suspect it wasn't because then the language would have
had to have SETF-like versions of all the destructive sequence operations.
Maclisp and Zetalisp, the primary influences on Common Lisp, had INCF, so
it was kept, but the CL designers apparently didn't want to throw in a
zillion new macros of that type.
Barry Margolin, Thinking Machines Corp.
······@think.com
{uunet,harvard}!think!barmar
In article <·····@mimsy.umd.edu> ·····@tove.umd.edu (Wayne Folta) writes:
>I take it from the Common LISP Reference that functions marked "(destructive)"
>are destructive in the sense that they *may be* destructive in some way.
>Is it thus true that I cannot count on destructive behavior when I want it?
ANSI CL is going to be a bit more clear about which destructive operations
can be "counted on" and which can't. For instance, NCONC will be specified
pretty fully (it RPLACD's the last cons in each non-null argument except
the last), as will NSUBSTITUTE (it RPLACA's or SETF-AREF's as appropriate).
The specifications of some others, such as DELETE and NREVERSE, will say
"may reuse any part of the sequence." We addressed these on a case-by-case
basis, trying to balance implementation flexibility against user needs and
expectations. NCONC is specified explicitly because it has a long history
and programmers have come to expect and rely upon its obvious
implementation; NSUBSTITUTE is specified explicitly because we couldn't
imagine an alternate implementation that would violate the requirement.
DELETE is flexible because its definition prevents it from always reusing
the input argument (e.g. if it has to delete all the elements of a list);
NREVERSE is flexible because there are a number of known implementations of
lists that have different optimal algorithms for reversing in place
(traditional lists are typically reversed by reordering the CDR chain,
cdr-coded lists are best reversed by replacing the CARs).
>So destructiveness is an option for the convenience of LISP
>implementation creators, not users?
In the more flexible cases, it is a way for the programmer to declare his
intentions (he doesn't care about the old structure), and thus permit the
implementation to try to optimize the operation.
Barry Margolin, Thinking Machines Corp.
······@think.com
{uunet,harvard}!think!barmar
In article <·····@news.Think.COM> ······@think.com writes:
>In the more flexible cases, it is a way for the programmer to declare his
>intentions (he doesn't care about the old structure), and thus permit the
>implementation to try to optimize the operation.
I note that it is okay for an implementation to have "destructive"
operations that actually don't modify their arguments's value. For
example, an implementation may have a concurrent garbage collector CPU
and have made other design choices such that destructive operations
are actually more expensive than copying the appropriate data. (Some
implementations of CDR-coding are almost like this.)
Strings (and general vectors as well, although I don't see the point
for them) can be implemented in many ways. In some cases, destructive
deletions can be made that return a new string object, but a pointer
to the original object (which is not eq to the new one) sees some of
the modifications.
The purpose of "destructive" operations is to allow the programmer to
say "do this fast, reusing whatever of the argument you want, and give
me the result" to the implementation. If that's not what you want to
do, don't use them. In particular, if you want a particular type of
reuse, and you want it to be portable, you have to write it yourself.
-andy
--
UUCP: {arpa gateways, sun, decwrl, uunet, rutgers}!neon.stanford.edu!andy
ARPA: ····@neon.stanford.edu
BELLNET: (415) 723-3088