I've been programming in LISP for quite some time, but I've always
gotten into buggy situations due to my misuse of destructive operations.
In fact, I can't even tell if I've used a destructive operation or not.
Does somebody have a general rule on how to watch out for misuse of
destructive operations? Or do you know of a reference to books talking
about destructive operations in LISP?
I'll appreciate any response in advance.
--
life () { /* My life: */
myself--; /* Let _myself_ decrease and */
Christ++; /* let _CHRIST_ increase!!!! */
}
In article <····@ai.cs.utexas.edu> ······@cs.utexas.edu (Timothy Tin-Wai Chan) writes:
> I've been programming in LISP for quite some time, but I've always
>gotten into buggy situations due to my misuse of destructive operations.
>In fact, I can't even tell if I've used a destructive operation or not.
In Common Lisp, the names of most destructive functions have the prefix "N"
(sorry, I don't recall the derivation of this). The exceptions I can think
of are SORT, DELETE and its variants (they are destructive versions of
REMOVE), RPLACA/D, and SETF of any list accessors.
>Does somebody have a general rule on how to watch out for misuse of
>destructive operations? Or do you know of a reference to books talking
>about destructive operations in LISP?
There are two common problems encountered when using destructive
operations.
1. Forgetting to store the result back. Even though the list is modified
in place, it is still necessary to store the result back into the original
location, e.g.
(setq foo (delete 'x foo))
This is necessary because X might be the first element of the list, so
DELETE could just return (CDR FOO), without actually modifying anything (it
can't store the result itself because of Lisp's call-by-value semantics).
If the original list was stored in multiple places, you may need to store
it back in all of them, e.g.
(setq bar foo)
...
(setq foo (delete 'x foo))
(setq bar foo)
2. Sharing structure that gets modified.
(setq bar (cdr foo))
...
(setq foo (sort foo #'<))
;;; now it's not safe to use BAR
It's generally best not to perform destructive operations on lists that are
shared in this way. You can use COPY-LIST or COPY-TREE, and then it will
be safe to modify the structure.
--
Barry Margolin, Thinking Machines Corp.
······@think.com
{uunet,harvard}!think!barmar
From: Thomas Bellman
Subject: Re: Destructive Operations
Date:
Message-ID: <595@lysator.liu.se>
In article <······················@Think.COM> Barry Margolin
(······@think.com) writes:
> 1. Forgetting to store the result back. Even though the list is modified
> in place, it is still necessary to store the result back into the original
> location, e.g.
> (setq foo (delete 'x foo))
> This is necessary because X might be the first element of the list, so
> DELETE could just return (CDR FOO), without actually modifying anything (it
> can't store the result itself because of Lisp's call-by-value semantics).
Well, I don't know very much about CommonLisp, but in good ol'
InterLISP, there was a function called DREMOVE, which did *not*
require the user to store the result back, *even* if it had to remove
the first element. It is easy to remove the first element of a list.
(DL REM1ST (L) (RPLACD (RPLACA L (CADR L)) (CDDR L)))
to speak InterLISP. (DL is the same as defun in CommonLisp.)
The only catch with DREMOVE was if the result was NIL. Then it
couldn't store the result back. If the result should be NIL, then
DREMOVE didn't modify the original list at all. (It returned NIL,
though.)
But then of course, there are some tricks you can use to make it
possible to turn a non-empty list into an empty list. You have to
have some structure around your lists, but that shouldn't be any
problem.
Personally, I like the TCONC type of lists, where you pass around a
cons cell whith the car pointing to the actual list, and the cdr
pointing to the last cons cell of the list. That way, it is very
cheap to add elements at the end of a list, and you can destructively
remove elements from the list. (It isn't inexpensive to remove the
last element of the list, but it is definitely possible to do "purely"
destructive functions. I know of no scheme where it is cheap for all
elements of the list.)
--
Thomas Bellman, Lysator Computer Club ! "Make Love - Nicht Wahr"
Linkoping University, Sweden ! "Too much of a good thing is
e-mail: ·······@Lysator.LiU.Se ! WONDERFUL." -- Mae West
From: Mark Kantrowitz
Subject: Re: Destructive Operations
Date:
Message-ID: <12814@pt.cs.cmu.edu>
In article <···@lysator.liu.se> ·······@lysator.liu.se (Thomas Bellman) writes:
>Well, I don't know very much about CommonLisp, but in good ol'
>InterLISP, there was a function called DREMOVE, which did *not*
>require the user to store the result back, *even* if it had to remove
>the first element. It is easy to remove the first element of a list.
If I remember correctly (it's been six or seven years since I used an
1108), the InterLisp-D functions DREMOVE and DISPLACE had problems if
the arguments shared list structure. This could lead to rather hideous
bugs. Imagine trying to debug code and running into a circular list in
the debugger.
--mark
"The semantics of Destructive Lisp" by yours truly
csli lecture notes #5, university of chicago press
talks about destructive operations in Lisp. a shortened version
appears in Science of Computer Programming 10 177-210 1988.
-iam-
One point I dont think anyone mentioned is that it is possible to
create self-modifying code in Lisp through perfectly innocent use of
destructive functions, as in:
(setq a '(some bogus list))
.
.
.
(rplaca a 'another)
Interestingly, this example is still self-modifying even if you use a
back-quote instead of a quote (at least in the implementations I have
used). The back-quoter is "intelligent" enough to act like a QUOTE
(rather than a LIST) if there is nothing in the list to be evaluated.
Twinerik