Re: bug in copy-list implementation

[osiris@cs.utexas.edu (Rob Browning)]

>I've been experimenting with the commands copy-list and copy-tree in a program
>I've been writing. I experienced a bug in that when using copy-list to make
>a copy of list that I was going to mutate, the program would mutate the
>original list too, but when I switched to copy-tree, the problem went away.
>
>(defun mutate (program)
>  (let ((prog-to-mutate (copy-list program)))
>     (mutate-loop prog-to-mutate)))
>
>where mutate-loop is a function that destructively modifies its argument.
>when it returned, it had also modified program, not just prog-to-mutate.
>
>However, when I switched to copy-tree, the problem was solved.

If I understand what you are doing, this behavior is normal, and correct,
not a bug.

According to Steele: "Only the top level of the list structure is copied;
that is, copy-list copies in the _cdr_ direction, but not in the _car_
direction."

This means that if you have a list like:

(setf list-1 '((a 1) (b 2) (c 3)))

and then you copy it like this:

(setf list-2 (copy-list list-1))

and then you destructively modify list-2 at any level other than the top
like this:

(setf (first (first list-2)) 'x)

you will be modifying both lists.

If you don't understand why, you should read up on list structure,
specifically the differece between the "backbone" (i.e. top-level) of a
list and it's "contents" so that you can see why if only the top level
(backbone) is copied, the two lists have to share pointers.

To see this realize that after the copy-list you end up with something in
the heap that looks sort of like the following (this is not strictly a
"correct" drawing, but it illustrates the point I think):

list-1 ---------------
         |     |     |
         |     |     |
         (a 1) (b 2) (c 3)
         |     |     |
         |     |     |
list-2 ---------------

So modifying the "a" through list-1 is the same as modifying it through list-2.

And indeed you are right, copy-tree works in your case, and is much closer
to what you really want as it recursively copies the list and any sublists.

Hope this helps,

--Rob.