problem with delete
Roland Nilsson
I'm having a weird problem with (delete item list). Consider:
(setq foo '(1 2 3 4 5))
(when (my-test-for-deletion)
(delete 1 foo)
)
Ok, here delete should modify foo, so that
foo => (2 3 4 5)
Also, the delete clause should evaluate to this. For me, delete
*does* return this result, but it *does not* modify the list, i.e.
(delete 1 foo) => (2 3 4 5), but still
foo => (1 2 3 4 5)
For example, (setf foo (delete 1 foo)) does what's intended. It's
like delete is acting like remove, non-destructive, in this case.
I do not find this behaviour when doing delete at any other element
than the first in a list. I'm using an Allegro 5.0 SPARC system.
Thanks for any help,
Roland Nilsson
M.Sc. engineering student
Linkoeping Institute of Technology, Sweden
Espen Vestre
> Also, the delete clause should evaluate to this. For me, delete
> *does* return this result, but it *does not* modify the list, i.e.
the standard says that 'the result might or might not be identical to
sequence'. I.e. you're supposed to use the return value and *not*
use the parameter any more since it *may* have been destroyed.
--
(espen)
Raymond Wiker
> Hi you almigthy Lisp-gurus!
>
> I'm having a weird problem with (delete item list). Consider:
>
> (setq foo '(1 2 3 4 5))
> (when (my-test-for-deletion)
> (delete 1 foo)
> )
>
> Ok, here delete should modify foo, so that
>
> foo => (2 3 4 5)
>
> Also, the delete clause should evaluate to this. For me, delete
> *does* return this result, but it *does not* modify the list, i.e.
I think you've misunderstood what "destructive function"
means. delete is free to modify its (list) parameter, but is under no
obligation to do so. Further, even if it *does* modify its (list)
parameter, it is not certain that the parameter will have the same
value as the return result.
All this and more, at
http://www.xanalys.com/software_tools/reference/HyperSpec/Body/fun_removecm__elete-if-not.html
--
Raymond Wiker
Raymon...@fast.no
Frode Vatvedt Fjeld
> [...] For example, (setf foo (delete 1 foo)) does what's
> intended. It's like delete is acting like remove, non-destructive,
> in this case. I do not find this behaviour when doing delete at any
> other element than the first in a list. I'm using an Allegro 5.0
> SPARC system.
You are _supposed_ to do (setf foo (delete 1 foo)). Simply doing
(delete 1 foo) has an undefined result.
To understand this, note that DELETE is a function, and so takes
arguments by value. It does _not_ take a "place" as argument, like for
example the special form SETF does, and which would be required for
DELETE to have the semantics you mistakenly expect. If you draw a
diagram of cons-cells and try to manipulate the pointers according to
DELETE semantics, you'll see why.
This is a general rule that applies to most (or all?) destructive
functions: They should be called exactly the same way you would call
their non-destructive counterparts.
--
Frode Vatvedt Fjeld
Rainer Joswig
(Roland Nilsson) wrote:
> Hi you almigthy Lisp-gurus!
>
> I'm having a weird problem with (delete item list). Consider:
>
> (setq foo '(1 2 3 4 5))
> (when (my-test-for-deletion)
> (delete 1 foo)
> )
>
> Ok, here delete should modify foo, so that
>
> foo => (2 3 4 5)
>
> Also, the delete clause should evaluate to this. For me, delete
> *does* return this result, but it *does not* modify the list, i.e.
>
> (delete 1 foo) => (2 3 4 5), but still
> foo => (1 2 3 4 5)
>
> For example, (setf foo (delete 1 foo)) does what's intended. It's
> like delete is acting like remove, non-destructive, in this case.
> I do not find this behaviour when doing delete at any other element
> than the first in a list. I'm using an Allegro 5.0 SPARC system.
This is the usual way it works. You may want to consult
a text book. I don't know if it is in the FAQ.
Short explanation:
foo -> ( 1 . ( 2 . ( 3 . ( 4 . ( 5 . nil)))))
Now you call DELETE on 1 and the value of FOO.
This leads to:
(delete 1 '( 1 . ( 2 . ( 3 . ( 4 . ( 5 . nil))))))
Delete returns as a result:
( 2 . ( 3 . ( 4 . ( 5 . nil))))
DELETE never sees FOO, just the list. FOO is a variable
pointing to the first cons cell. DELETE can't modify
FOO in this case. So here the cons cell FOO
points to is unmodified. So, after a destructive operation
you may need to store the results in any variable
you want to change.
This is one of the popular pitfalls of lists in Common Lisp.
Paul Graham discusses this in "On Lisp" pages 30f.
His example is NREVERSE.
--
Rainer Joswig, Hamburg, Germany
Email: mailto:jos...@corporate-world.lisp.de
Web: http://corporate-world.lisp.de/
Erik Naggum
| I'm having a weird problem with (delete item list).
Nope. You're having a minor problem understanding how lists are
represented. You're also having a minor misunderstanding of what it
means for a Lisp function be destructive and have side effects.
delete is one of those functions that have side effects as a side
effect. Its main effect is to return a list as per specification.
(The streams functions have side effects as their main effect...)
| Consider:
|
| (setq foo '(1 2 3 4 5))
foo is a pointer to a cons cell containing 1 and a pointer to
a cons cell containing 2 and a pointer to
a cons cell containing 3 and a pointer to
a cons cell containing 4 and a pointer to
a cons cell containing 5 and nil.
| (when (my-test-for-deletion)
| (delete 1 foo))
|
| Ok, here delete should modify foo, so that
|
| foo => (2 3 4 5)
delete does not modify variables, _ever_. That would be the macro
setq/setf (or any of the other macros that use setq/setf).
delete modifies the structure of the internal pointers in the list
structure. Say you delete 3 from the list. foo is a pointer to
a cons cell containing 1 and a pointer to
a cons cell containing 2 and a pointer to
a cons cell containing 4 and a pointer to
a cons cell containing 5 and nil.
As a special case, if the first element of a list is to be deleted,
which pointer needs to be modified in order to reflect the missing
element? Hint: _not_ one of the poiners in the list structure.
| Also, the delete clause should evaluate to this. For me, delete
| *does* return this result, but it *does not* modify the list, i.e.
Bingo! Use the value it returns, then. Never use delete for its
side effect (unless you know exceptionally well what you're doing).
| (delete 1 foo) => (2 3 4 5), but still
| foo => (1 2 3 4 5)
Of course. foo points to the cons cell that contains 1 and a
pointer to the cons cell that contains 2 and ... For delete to work
the way you seem to want, it would have to rearrange the entire
top-level list structure.
| For example, (setf foo (delete 1 foo)) does what's intended. It's
| like delete is acting like remove, non-destructive, in this case.
Um, no. "Destructive" means that while building the result it is
free to reuse the resources that were used in one (or more) of the
arguments.
(let ((foo (list 1 2 3 4 5)))
(values (eq (cdr foo) (remove 1 foo))
(eq (cdr foo) (delete 1 foo))))
This should return as two values nil and t. Explain why.
Why don't you write your own delete function that behaves the way
you want, then try to understand how delete has been implemented,
and argue for both designs and implementations?
#:Erik
--
If this is not what you expected, please alter your expectations.
Erik Naggum
| You are _supposed_ to do (setf foo (delete 1 foo)). Simply doing
| (delete 1 foo) has an undefined result.
No, it is very well defined. It just isn't what some people expect.
| To understand this, note that DELETE is a function, and so takes
| arguments by value.
There is nothing wrong with a delete function that modifies the list
such that the variables keeps pointing to a list sans the first
element. (delete 1 (vector 1 2 3 4 5)) manages this, remember?
| This is a general rule that applies to most (or all?) destructive
| functions: They should be called exactly the same way you would call
| their non-destructive counterparts.
Good point. However, recall that they are allowed to nuke their
arguments, so if you got any of those (susceptible) arguments from
someone else and you haven't agreed on an object ownership protocol,
you'd better be careful not to alter somebody else's objects.
Frode Vatvedt Fjeld
> * Frode Vatvedt Fjeld <fro...@acm.org>
> | You are _supposed_ to do (setf foo (delete 1 foo)). Simply doing
> | (delete 1 foo) has an undefined result.
Erik Naggum <er...@naggum.net> writes:
> No, it is very well defined. It just isn't what some people expect.
Really? My understanding of the hyperspec is that DELETE may or may
not modify the list. So what is
(let ((list '(1 2 3 4)))
(delete 2 list)
list)
defined to return?
--
Frode Vatvedt Fjeld
Rainer Joswig
<fro...@acm.org> wrote:
First: '(1 2 3 4) is a constant list in code. It is
not allowed to modify it according to ANSI CL
(lookup the correct wording for that from
the Hyperspec). Use LIST to get a fresh list.
Then the above form returns (1 2 3 4) if
DELETE does not modify the list. It returns
(1 3 4) if it modifies the list.
It is well-defined in that it returns a list of these items
with the argument item removed. How that
list is constructed is not defined.
Duane Rettig
> * Frode Vatvedt Fjeld <fro...@acm.org>
> | You are _supposed_ to do (setf foo (delete 1 foo)). Simply doing
> | (delete 1 foo) has an undefined result.
>
> No, it is very well defined. It just isn't what some people expect.
I agree that this is very well defined, but it is also important not
to make an assumption about the implementation (note, Erik, that I am
not implying that you have made this assumption, but it is possible
that readers of your article may have made the assumption):
Given a list and an object that matches the first element in the list,
it is easy (but wrong) to assume that
(delete first-element list) ==> (cdr list).
A perverse implementation might, upon discovering that the match is in
the first element, store the second element into the first cons cell,
and point the cdr of the first cons cell to the third cell, thus
getting the specified effect for the return value _and_ the intuitive
side-effect (though the farther-reaching side-effects may be unintuitive
and surprising).
I was going to list the reasons why such an implementation would be so
perverse, but every example I think of is no worse for the first-element
case than for an nth-element case. Thus, I perform a hand-wave and
pronounce the above approach perverse simply for aesthetic reasons...
--
Duane Rettig Franz Inc. http://www.franz.com/ (www)
1995 University Ave Suite 275 Berkeley, CA 94704
Phone: (510) 548-3600; FAX: (510) 548-8253 du...@Franz.COM (internet)
Barry Margolin
Rainer Joswig <jos...@corporate-world.lisp.de> wrote:
>This is the usual way it works. You may want to consult
>a text book. I don't know if it is in the FAQ.
It definitely is -- it was one of the questions that prompted us to create
the FAQ in the first place (the other was regarding (read-from-string
some-string :start n)).
--
Barry Margolin, bar...@genuity.net
Genuity, Burlington, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
Barry Margolin
>
>> Erik Naggum <er...@naggum.net> writes:
>>
>> > * Frode Vatvedt Fjeld <fro...@acm.org>
>> > | You are _supposed_ to do (setf foo (delete 1 foo)). Simply doing
>> > | (delete 1 foo) has an undefined result.
>> >
>> > No, it is very well defined. It just isn't what some people expect.
>>
>
>I don't get this, please help me understand.. Do we agree that after
>the form (delete 1 foo) the exact list structure pointed to by foo is
>unknown, because the implementation may or may not destructively
>modify that list (in one of several possible ways)?
>
>Did you read my wording "undefined result" above to mean "the
>functional return value of the form"? In that case I would understand
>your comments, but I thought it should be quite clear from the context
>that "result" referred to the value of foo.
Actually, it's well defined that FOO's value is the same cons cell as it
was before the call. The DELETE function receives the cons as its
parameter, not the symbol FOO (if FOO is a local variable there often isn't
even a symbol involved at runtime -- the compiler will have translated FOO
into a stack location or something like that). It can make changes to the
car and/or cdr of that cell, or any of the cells in the chain, but it has
no access to the variable FOO itself.
All implementations of DELETE I've ever heard of work by relinking cdr's to
splice out the conses whose cars satisfy the test. If the first cons
matches, there's no cdr ahead of it to relink, since DELETE doesn't know
where the reference came from, so it just returns the cdr. This is why you
must use DELETE for value, not just for its side effects.
And even if DELETE worked by modifying car's instead of cdr's, you have to
deal with the limiting case where *all* the elements of the list satisfy
the test, so the result is NIL. In this case, no amount of cons cell
modification will produce the correct result.
Duane Rettig
> Duane Rettig <du...@franz.com> writes:
>
> > Erik Naggum <er...@naggum.net> writes:
> >
> > > * Frode Vatvedt Fjeld <fro...@acm.org>
> > > | You are _supposed_ to do (setf foo (delete 1 foo)). Simply doing
> > > | (delete 1 foo) has an undefined result.
> > >
> > > No, it is very well defined. It just isn't what some people expect.
> >
> > I agree that this is very well defined, [..]
>
> I don't get this, please help me understand.. Do we agree that after
> the form (delete 1 foo) the exact list structure pointed to by foo is
> unknown, because the implementation may or may not destructively
> modify that list (in one of several possible ways)?
No; it is a fact that the cons cell pointed to by foo after a delete
operation is the same one as before the operation. But because that
cons cell is part of the list that may be reused by the destructive
function, it is unknown what that cons cell actually has in it. That
is the essence of my previous argument.
> Did you read my wording "undefined result" above to mean "the
> functional return value of the form"? In that case I would understand
> your comments, but I thought it should be quite clear from the context
> that "result" referred to the value of foo.
No, It was quite clear.
Duane Rettig
> And even if DELETE worked by modifying car's instead of cdr's, you have to
> deal with the limiting case where *all* the elements of the list satisfy
> the test, so the result is NIL. In this case, no amount of cons cell
> modification will produce the correct result.
Now _that_ was the case I was looking for (but not thinking about it
thoroughly enough, didn't think of it while typing on-the-fly). Thanks!
This is the case that proves the "perversity" of the implementation that
tries to modify the car of the first cons cell to delete the first element.
Erik Naggum
| not modify the list. So what is
|
| (let ((list '(1 2 3 4)))
| (delete 2 list)
| list)
|
Apart from the undefined behavior of modifying a constant, of
course, the first cons cell of the original list. (You didn't
expect this. :)
Frode Vatvedt Fjeld
> Erik Naggum <er...@naggum.net> writes:
>
> > * Frode Vatvedt Fjeld <fro...@acm.org>
> > | You are _supposed_ to do (setf foo (delete 1 foo)). Simply doing
> > | (delete 1 foo) has an undefined result.
> >
> > No, it is very well defined. It just isn't what some people expect.
>
> I agree that this is very well defined, [..]
I don't get this, please help me understand.. Do we agree that after
the form (delete 1 foo) the exact list structure pointed to by foo is
unknown, because the implementation may or may not destructively
modify that list (in one of several possible ways)?
Did you read my wording "undefined result" above to mean "the
functional return value of the form"? In that case I would understand
your comments, but I thought it should be quite clear from the context
that "result" referred to the value of foo.
--
Frode Vatvedt Fjeld
Erik Naggum
| structure pointed to by foo is unknown, because the implementation
| may or may not destructively modify that list (in one of several
| possible ways)?
How could it be _unknown_? That would mean delete would have to do
some weird shit to the list structure while returning the well-
defined result.
What are you really getting at? This subthread got derailed because
you made a claim that is just plain wrong. Please ignore it, don't
try to defend it, and get back to your real issue.
Frode Vatvedt Fjeld
Erik Naggum writes:
> What are you really getting at? This subthread got derailed because
> you made a claim that is just plain wrong. Please ignore it, don't
> try to defend it, and get back to your real issue.
When I make what I considered to be a trivial statement, and a handful
of people claim it to be "just plain wrong", I have a hard time just
ignoring it. I wasn't defending anything. I was trying to understand
what you meant and hopefully learn something.
--
Frode Vatvedt Fjeld
David Bakhash
> In article <2h4s2vf...@dslab7.cs.uit.no>, Frode Vatvedt Fjeld
> <fro...@acm.org> wrote:
>
> > > * Frode Vatvedt Fjeld <fro...@acm.org>
> > > | You are _supposed_ to do (setf foo (delete 1 foo)). Simply doing
> > > | (delete 1 foo) has an undefined result.
> >
> > Erik Naggum <er...@naggum.net> writes:
> >
> > > No, it is very well defined. It just isn't what some people expect.
> >
> > Really? My understanding of the hyperspec is that DELETE may or may
> > not modify the list. So what is
> >
> > (let ((list '(1 2 3 4)))
> > (delete 2 list)
> > list)
>
> First: '(1 2 3 4) is a constant list in code. It is
> not allowed to modify it according to ANSI CL
> (lookup the correct wording for that from
> the Hyperspec). Use LIST to get a fresh list.
This is surprising. I never really knew that. In fact, I thought it
was implementation-defined. For example, the Hyperspec says, in
Section 3.1.2.1.3 Self-Evaluating Objects:
``The consequences are undefined if literal objects (including
self-evaluating objects) are destructively modified.''
I know that conses arn't typically self-evaluating, but I always
included them here. Anyway, now I know better. thanks for pointing
this out.
dave
Barry Margolin
David Bakhash <ca...@alum.mit.edu> wrote:
>Rainer Joswig <jos...@corporate-world.lisp.de> writes:
>> First: '(1 2 3 4) is a constant list in code. It is
>> not allowed to modify it according to ANSI CL
>> (lookup the correct wording for that from
>> the Hyperspec). Use LIST to get a fresh list.
>
>This is surprising. I never really knew that. In fact, I thought it
>was implementation-defined. For example, the Hyperspec says, in
>Section 3.1.2.1.3 Self-Evaluating Objects:
>
>``The consequences are undefined if literal objects (including
> self-evaluating objects) are destructively modified.''
>
>I know that conses arn't typically self-evaluating, but I always
>included them here.
Conses are definitely *not* self-evaluating. When you evaluate a CONS, it
performs (apply (fdefinition (car x)) (mapcar #'eval (cdr x))) (I'm
simplifying greatly: ignoring macros, special operators, and local
bindings, because they're irrelevant to this point).
But anything returned by a QUOTE form, including a cons, is a literal
object.
Hartmann Schaffer
>When I make what I considered to be a trivial statement, and a handful
>of people claim it to be "just plain wrong", I have a hard time just
>ignoring it. I wasn't defending anything. I was trying to understand
>what you meant and hopefully learn something.
pretty much every text on lisp has this short section that describes
with nice pictures how lists tend to be represented in memory. why
don't you look at it, draw your list just like those pictrures (with
foo pointing to that list) and figure out how a destructive delete
might work (and please remember that the delete function gets a copy
of foo, hence doesn't know where (and where else) this list might be
pointed to from). i am reasonably sure that once you have done this
you won't have to ask again.
hs
Erik Naggum
| What are you really getting at? This subthread got derailed because
| you made a claim that is just plain wrong. Please ignore it, don't
| try to defend it, and get back to your real issue.
* Frode Vatvedt Fjeld <fro...@acm.org>
| When I make what I considered to be a trivial statement, and a handful
| of people claim it to be "just plain wrong", I have a hard time just
| ignoring it. I wasn't defending anything. I was trying to understand
| what you meant and hopefully learn something.
The theory that you learn from doing something wrong and then being
corrected is not quite supported by the evidence: it has some very
restricted applications where it works well (such as in instruction
where you might have missed something and thus the range of what you
can reasonably do wrong is restricted), otherwise it doesn't work at
all (such as trial and error, where there is no restriction to what
you can do and how wrong it can be and why).
That's why it's much more important to answer the question "What
are/were you _really_ getting at?"
Thomas A. Russ
> (let ((foo (list 1 2 3 4 5)))
> (values (eq (cdr foo) (remove 1 foo))
> (eq (cdr foo) (delete 1 foo))))
>
> This should return as two values nil and t. Explain why.
Actually, it would seem to me that a conforming implementation could
return T and T for this example. There is no requirement that REMOVE
create a new list, just that it not modify the original list.
The hyperspec explicity says "The result of remove may share with
sequence". Of course the hyperspec also claims immediately before that
sentence "If any elements need to be removed, the result will be a
copy." In the case of all the removed elements being at the front of
the list that may not have really been the intention of the committee to
require a copy.
--
Thomas A. Russ, USC/Information Sciences Institute t...@isi.edu
Erik Naggum
| Actually, it would seem to me that a conforming implementation could
| return T and T for this example. There is no requirement that
| REMOVE create a new list, just that it not modify the original list.
Well, I asked you (or anyone) to explain why it _should_ return nil
and t, not whether it _could_ return something else.
| The hyperspec explicity says "The result of remove may share with
| sequence". Of course the hyperspec also claims immediately before
| that sentence "If any elements need to be removed, the result will
| be a copy." In the case of all the removed elements being at the
| front of the list that may not have really been the intention of the
| committee to require a copy.
Would you care to implement the remove that shares structure and
compare it with one that does not share structure? I think this
will be very illuminating.
Thomas A. Russ
> Would you care to implement the remove that shares structure and
> compare it with one that does not share structure? I think this
> will be very illuminating.
(defun sharing-remove (item list)
(setq list (loop for rest on list by #'cdr
unless (eq item (first rest))
return rest))
(loop with copy-end = 0
for rest on list by #'cdr
when (eq item (first rest))
;; ***
return (nconc (subseq list 0 copy-end)
(sharing-remove item rest))
else do (incf copy-end)
finally (return list)))
OK, here's the structure sharing remove for lists. I won't attempt it
for non-list sequences. The only nastiness is that anytime a copy needs
to be made, the copied part is traversed 3 times. (See ;; ***)
I suppose that I could write my own version of subseq that returned a
pointer to the last cons cell so that it could be destructively
modified. I don't feel up to that right now, but it would mean only
traversing the copied section 2 times instead of 3.
Anyway, here are some examples using ACL:
USER> (setq ll '(3 3 1 2 3 4 5 6 7))
(3 3 1 2 3 4 5 6 7)
USER> (remove 10 ll)
(3 3 1 2 3 4 5 6 7)
USER> (eq * ll)
NIL
USER> (sharing-remove 10 ll)
(3 3 1 2 3 4 5 6 7)
USER> (eq * ll)
T
USER> (sharing-remove 3 ll)
(1 2 4 5 6 7)
USER> (eq (cddr *) (nthcdr 5 ll))
T
Erik Naggum
| for non-list sequences. The only nastiness is that anytime a copy needs
| to be made, the copied part is traversed 3 times. (See ;; ***)
The non-sharing remove only copies the not-to-be-removed elements,
like, once:
(defun normal-remove (item list)
(loop for elt in list
unless (eq item elt)
collect elt))
Incidentally, since you're looking at sharing only some tail of the
list, you could reverse the list, scan for the first match, reverse
the part you had traversed, and copy the rest of the list, sans
matches. This would avoid any but the final copy. A deeply
recursive function could maintain a global variable that would allow
it to share structure on the way back.
All in all, I think the simplicity in implementation of a remove
that copies is much to be preferred over the speed penalty for the
version that tries to share. Another useful tidbit here is that if
you're using a generational garbage collector, mixing and matching
old and young generations usually has costs
Jason Kantz
(defun my-delete (item list)
(let ((l (remove-leading item list)))
(do* ((rest l (cdr rest)))
((endp rest) l)
(if (eq item (first (cdr rest)))
(setf (cdr rest) (remove-leading item (cdr rest)))))))
(defun remove-leading (item list)
(do ((rest list (cdr rest)))
((not (eq item (first rest))) rest)))
Barry Margolin
You're not checking for termination properly.
(my-delete nil anything) => infinite loop
(remove-leading nil nil) => infinite loop