DELETE is destructive -- but not always?

Question

I'm a little confused about Common Lisp's destructive DELETE function. It seems to work as expected, except for if the item is the first item on the list:

CL-USER> (defvar *test* (list 1 2 3))
*TEST*
CL-USER> (delete 1 *test*)
(2 3)
CL-USER> *test*
(1 2 3)
CL-USER> (delete 2 *test*)
(1 3)
CL-USER> *test*
(1 3)

Geelong

Answer 1

"Destructive" does not mean "operates in place". It means that the structure of the value operated on might be modified in some arbitrary and often undefined way. This can in some instances, implementations and cases have an effect as if it was "in place". This can generally not be relied upon, however.

If you use a destructive operator, you are telling the compiler that you are not interested in the previous value of the variable after the operation is complete. You should assume that that value is garbled beyond recognition afterwards and not use it anymore. Instead, you should use the return value of the operation.

(let ((a (list 1 2 3)))
  (let ((b (delete 2 a)))
    (frob b))
  a)

=> You were eaten by a grue.

If you are unsure of the safety of destructive operations, use their non-destructive counterparts (remove in this case).

(let ((a (list 1 2 3)))
  (let ((b (remove 2 a)))
    (frob b))
  a)

=> (1 2 3)

If you really want to modify the contents of a variable, set them to the return value of the operation:

(let ((a (list 1 2 3)))
  (setf a (delete 2 a))
  a)

=> (1 3)

Kataway

Well, not so much "previous value of the variable" as "structure of the value that at least this variable holds". Sharing structure is not uncommon, after all. – Parament

And it's not restricted to the "value of [a] variable". You could do, e.g., (delete 1 (rest some-list)). It just needs a list as an argument; it's not a macro, and doesn't need a place. – Ides

@Geelong Do note that the results in the first case aren't quite as unpredictable as "you were eaten by a grue." While the car and cdr of any cons cell in the list can be modified, they're still going to be cons cells. In the first case, a will always be a cons cell after calling (delete 2 a), even if it's car and cdr are different afterwards. Even more importantly, it will still be the same cons cell that it was before. E.g., see this code sample. – Ides

Answer 2

Keep in mind that DELETE is supposed to work on the list, and not on a variable. DELETE gets passed the list (a pointer to the first cons) and not the variable.

Since delete does not have access to the variable *test*, it can't change it. 'It' here means its bindings. *test* will point to the same cons cell as before. The only thing that can be changed is the contents of the cons cell or the contents of other cons cells the first cons cell is pointing to.

One thing is sure, no matter what DELETE does, *test* will always point to the same cons cell.

What follows from that? If you want to have *test* point to the result of the delete operation, then you explicitly have to say so:

(setq *test* (delete 1 *test*))

Whiggism

Answer 3

DELETE works by changing the CDR of the previous cons cell of the list to point to the one past the element(s) being deleted. But if you're deleting the first element of the list, there is no previous cons cell to modify.

Although this implementation isn't actually specified by the language standard, it's the way practically every implementation works.

Since there's no previous cons cell to modify when deleting the first element of the list, it simply returns the second cons cell. So even though DELETE is permitted to modify the list, you still must assign the result to your variable to handle this case. Also, it should be emphasized that destructive behavior is only allowed by the standard, not required. So there's a remote possibility that some implementation might not implement it destructively at all, and you must allow for that as well.

And even if DELETE worked by modifying CARs instead of CDRs, there's still a case that it can't do destructively: deleting all the elements of a list, e.g.

(setq *test* (list 'a 'a))
(delete 'a *test*)

This results in an empty list, i.e. NIL. But *test* still contains the cons cell that was the head of the original list, and there's no way for DELETE to change that. So you must do:

(setq *test* (delete 'a *test*))

to set *test* to NIL.

Milicent