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?

Hulbard

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.

Velleman

I +1'd your answer because I like the detailed approach you took, but I'm not sure if you answered the OP's question, which is how to deal with the fact that both car and cdr are potentially mutated when calling nreverse. – Delladelle

@Chris Jester-Young: there is no need to deal with it. Just don't exploit a particular side effect of a particular implementation. Just use the returned result of nreverse. – Velleman

I agree, if the list you're passing in has no aliases. Otherwise, you run into all sorts of trouble. Scheme, in particular, has lots of list procedures that return shared-tail results, which are a form of aliasing. For example, the result of append and append! (nconc) shares tail with the last list given, so calling reverse! (nreverse) on that could be problematic (if the list with the tail-sharing is being used elsewhere). – Delladelle

@Chris Jester-Young: sure, nreverse in general can have observable side effects which can lead to problems. The point here is that these side effects can be different than expected, since a relatively rare implementation variant of nreverse could be used. – Velleman

@Chris Jester-Young: nreverse in Common Lisp is not required to be non-consing. CLHS: nreverse might either create a new sequence, modify the argument sequence, or both. Creating a new sequence would be consing. It's just that we expect in any self-respecting implementation that there is some advantage in using nreverse over reverse. – Velleman

Right, in fact I nuked my last comment because I reread CLHS and it was too late to edit the comment. :-) (For the record for others reading this, the remainder of the comment read: True, the actual side effects may indeed be different from what's expected (in Scheme, in particular, implementations are allowed to implement reverse! as reverse, especially for implementations like Racket where conses are immutable; so using the return value is a must).) – Delladelle

Answer 2

In any case, be it CAR or CDR of cons cell modified, you shouldn't use NREVERSE if any cons cell (including first cons cell) of passed list may be shared with another list. Use REVERSE instead.

BTW, clisp indeed modifies CARs:

> (let ((a (list 1 2 3 4 5 6 7 8 9 0)))
     (nreverse a)
     a)
(0 9 8 7 6 5 4 3 2 1)

Thrill