gideon@cs.utexas.edu (Timothy Tin-Wai Chan) (04/25/91)
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!!!! */
}
barmar@think.com (Barry Margolin) (04/25/91)
In article <1351@ai.cs.utexas.edu> gideon@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. barmar@think.com {uunet,harvard}!think!barmar
iam@cs.Stanford.EDU (Ian Mason) (04/25/91)
"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-
bellman@lysator.liu.se (Thomas Bellman) (04/26/91)
In article <1991Apr25.052624.14541@Think.COM> Barry Margolin (barmar@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: Bellman@Lysator.LiU.Se ! WONDERFUL." -- Mae West
mkant@glinda.oz.cs.cmu.edu (Mark Kantrowitz) (04/27/91)
In article <595@lysator.liu.se> bellman@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
weinrich@clarity.Princeton.EDU (Tim Weinrich) (04/27/91)
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
HEP@smectos.gang.umass.edu (High Energy Physics Group) (05/02/91)
I have managed to get myself into trouble many times by using destructive operators. The following example is probably my favorite: <cl> (setf *ht* (make-hash-table :test #'equal)) #<EQUAL hash-table with 0 entries @ #x-ebca20e> <cl> (setf *x* '(3)) (3) <cl> (setf (gethash *x* *ht*) :hi-there) :hi-there <cl> (gethash '(3) *ht*) :hi-there t <cl> (setf (first *x*) 92) 92 <cl> (gethash '(3) *ht*) nil nil Sure, it's obvious in retrospect, but not at the time when I did this! --kleanthes