How to watch out for the fact that NREVERSE may modify CARs instead

Question

http://www.aiai.ed.ac.uk/~jeff/lisp/cl-pitfalls states this as one of Common Lisp pitfalls

Destructive functions that you think would modify CDRs might modify CARs instead. (Eg, NREVERSE.)

I am not sure what precautions I am supposed to take. Usual precaution I can take from the fact that NREVERSE may modify CDRs is to use NREVERSE only when the list (the argument) does not share tail with any other lists that my variables may refer to later (except for the variable I save the return value to). What precaution I should take from the fact that NREVERSE may modify CARs? How is this something to watch out for?

Answer 1

Without any context this is very hard to understand.

Example:

(setq list1 (list 1 2 3 4))

We now have a list of four numbers. The variable list1 points to the first cons.

If we look at a destructive reverse we are talking about an operation which may alter the cons cells. There are different ways how this list can be reversed.

We could for example take the cons cells and reverse those. The first cons cell then is the last. The cdr of that cons cell then has to be changed into NIL.

CL-USER 52 > (setq list1 (list 1 2 3 4))
(1 2 3 4)

CL-USER 53 > (nreverse list1)
(4 3 2 1)

Now our variable list1 still points to the same cons cell, but its cdr has been changed:

CL-USER 54 > list1
(1)

To make sure that the variable points to a reversed list, the programmer then has the duty to update the variable and set it to the result of the nreverse operation. One may also be tempted to exploit the observable result that list1 points to the last cons.

Above is what a Lisp developer usually would expect. Most implementation of reverse seem to work that way. But it is not specified in the ANSI CL standard how nreverse has to be implemented.

So what would it mean to change the CARs instead?

Let's look at an alternative implementation of nreverse:

(defun nreverse1 (list)
  (loop for e across (reverse (coerce list 'vector))
        for a on list do
        (setf (car a) e))
  list)

Above function let's the chain of cons cells intact, but changes the car.

CL-USER 56 > (setq list1 (list 1 2 3 4))
(1 2 3 4)

Now let's use the new version, nreverse1.

CL-USER 57 > (nreverse1 list1)
(4 3 2 1)

CL-USER 58 > list1
(4 3 2 1)

Now you see the difference: list1 still points to the whole list.

Summary: one needs to be aware that there are different implementations of nreverse possible. Don't exploit the usual behavior, where a variable then will point to the last cons. Just use the result of nreverse and everything is fine.

Side note: where could the second version have been used?

Some Lisp implementations on Lisp Machines allowed a compact vector-like representation of lists. If on such a Lisp implementation one would nreverse such a list, the implementors could provide an efficient vector-like nreverse.