Is that an NREVERSE bug? (SBCL)

[40hex]

My lisp book sez something along the lines of

Code: Select all

(defparameter x '(0 1 2 3))
(nreverse x)

Now x is '(3 2 1 0)

This works exactly as written above in CLISP.
It does not in SBCL, where the same NREVERSE
gives us '(0).

The return value is '(3 2 1 0), but that is not
enough, right? NREVERSE is supposed to be destructive,
although in such a way that the original list gets
reversed, not destroyed.

I get the style warning of "return value of NREVERSE shall not
be discarded" -- is that because NREVERSE does not work
as advertised? I edited the spots where I used NREVERSE
by (SETF X (REVERSE X)).

thx for attention

[nuntius]

Not an SBCL bug, just a common pitfall for users.

"nreverse might either create a new sequence, modify the argument sequence, or both."
http://www.lispworks.com/documentation/ ... revers.htm

Note the *might*. SBCL's warning is correct style. SBCL's behavior is conforming to the spec.

Note that printing (nreverse ...) will always show the right thing, since the return value is printed.
Thus it is all too easy for someone working through interactive examples in a book to miss this detail.

[edgar-rft]

It's only the return-value of NREVERSE that counts, the argument's value is allowed to be destructively modified into a complete mess:

NREVERSE sequence => reversed-sequence

For NREVERSE, [the original] sequence [argument] might be destroyed and re-used to produce the [reversed-sequence] result. ... Specifically, when [the original] sequence [argument] is a LIST, NREVERSE is permitted to SETF any part, CAR or CDR, of any CONS that is part of the LIST structure of [the original] sequence [argument].

[words in square brackes were added by edgar]

Destroying the value of the original argument allows implementations to use the fastest and most memory-efficient algorithm possible with no care to anything at all, except the return-value must be a valid reversed-sequence.

In practice this means:

Code: Select all

(defparameter x '(0 1 2 3))
(nreverse x)
x => <undefined>

This code might work by chance, but very often does not. The value of X after NREVERSE is undefined and therefore completely unreliable.

If you want to destructively reverse the list in X you need to write:

Code: Select all

(defparameter x '(0 1 2 3))
(setf x (nreverse x))
x => (3 2 1 0)

This code always works because the return-value of NREVERSE is stored back into the X variable.

The same is true for all other destructive Common Lisp operations.

- edgar

[edgar-rft]

The same explanation with some box-and-arrows artwork

The original list:

Code: Select all

       +-----+-----+     +-----+-----+     +-----+-----+     +-----+-----+
       |     |     |     |     |     |     |     |     |     |     |     |
 X --->|  0  |  *------->|  1  |  *------->|  2  |  *------->|  3  |  *------> NIL
       |     |     |     |     |     |     |     |     |     |     |     |
       +-----+-----+     +-----+-----+     +-----+-----+     +-----+-----+

The same list after being destructively modified by (nreverse x):

Code: Select all

                                                     return-value
                                                          |
       +-----+-----+     +-----+-----+     +-----+-----+  |  +-----+-----+
       |     |     |     |     |     |     |     |     |  |  |     |     |
 X --->|  0  |  *  |  ,->|  1  |  *  |  ,->|  2  |  *  |  '->|  3  |  *  |  ,->NIL
    ,->|     |  |  |  |  |     |  |  |  |  |     |  |  |     |     |  |  |  |
    |  +-----+--|--+  |  +-----+--|--+  |  +-----+--|--+     +-----+--|--+  |
    |           |     |           |     '-----------------------------'     |
    |           |     '-----------------------------'                       |
    '-----------------------------'                                         |
                '-----------------------------------------------------------'

I think you can see why SBCL returns (0). It's because X still points to the first CONS cell, while the return-value is not assigned to anything at all.

And here after the return-value has been assigned back to the X variable by (setf x (nreverse x)):

Code: Select all

    ,-----------------------------------------------------,
    |  +-----+-----+     +-----+-----+     +-----+-----+  |  +-----+-----+
    |  |     |     |     |     |     |     |     |     |  |  |     |     |
 X -'  |  0  |  *  |  ,->|  1  |  *  |  ,->|  2  |  *  |  '->|  3  |  *  |  ,->NIL
    ,->|     |  |  |  |  |     |  |  |  |  |     |  |  |     |     |  |  |  |
    |  +-----+--|--+  |  +-----+--|--+  |  +-----+--|--+     +-----+--|--+  |
    |           |     |           |     '-----------------------------'     |
    |           |     '-----------------------------'                       |
    '-----------------------------'                                         |
                '-----------------------------------------------------------'

- edgar

[edgar-rft]

Finally found it - Citation from the CLISP implementation notes Section 17.3 - Functions NREVERSE and NRECONC:

The result of NREVERSE [in CLISP] is always EQ to the argument ... NREVERSE on a LIST swaps the first and the last element and reverses the list chaining between them.

This explains why in CLISP NREVERSE reverses a list in-place, even without assigning the return-value back to the variable. But this is an implementation-specific behaviour that only works in CLISP but not necessarily in other Common Lisp implementations.

- edgar

[40hex]

Thanks a lot, nuntius and even more so edgar-rft for the elaborate box-drawings, because your explanations revealed an old misunderstanding of mine.

I never paid much attention to nreverse and wrongly believed that

recycling cons-cells = destructive = changes the value of referenced argument

Tried and trusted CLISP has left me in that believe for years. Yes, I did read the hyperspec entry on REVERSE and NREVERSE, but somehow could not make sense of "implementation-dependent" and ignored it, due to hypnotization. I thought that the very purpose of NREVERSE is to destroy the value of the referenced argument by reversing it, not just to save cons-cells. Now other N* operators make more sense as well. Thanks again, guys!

[edgar-rft]

The reason why destructive oprations can be dangerous is that if variables share list elements like in the following example:

Code: Select all

(defparameter x (list 0 1 2 3))
(defparameter y (cdr x))

x => (0 1 2 3)
y => (1 2 3)

The pointers of the CONS cells in memory look like this:

Code: Select all

 Y -------------------,
       +-----+-----+  |  +-----+-----+     +-----+-----+     +-----+-----+
       |     |     |  '->|     |     |     |     |     |     |     |     |
 X --->|  0  |  *------->|  1  |  *------->|  2  |  *------->|  3  |  *------> NIL
       |     |     |     |     |     |     |     |     |     |     |     |
       +-----+-----+     +-----+-----+     +-----+-----+     +-----+-----+

If you now (setf x (nreverse x)), what will be the value of Y afterwards?

Code: Select all

 Y -------------------, 
    ,-----------------------------------------------------,
    |  +-----+-----+  |  +-----+-----+     +-----+-----+  |  +-----+-----+
    |  |     |     |  '->|     |     |     |     |     |  |  |     |     |
 X -'  |  0  |  *  |  ,->|  1  |  *  |  ,->|  2  |  *  |  '->|  3  |  *  |  ,->NIL
    ,->|     |  |  |  |  |     |  |  |  |  |     |  |  |     |     |  |  |  |
    |  +-----+--|--+  |  +-----+--|--+  |  +-----+--|--+     +-----+--|--+  |
    |           |     |           |     '-----------------------------'     |
    |           |     '-----------------------------'                       |
    '-----------------------------'                                         |
                '-----------------------------------------------------------'

The answer is that X has been properly NREVERSEd, but Y now suddenly contains elements that it didn't contain before:

Code: Select all

x => (3 2 1 0)
y => (1 0)

In such cases either REVERSE instead of NREVERSE (where REVERSE makes a copy of the list), or COPY-LIST can be used like this:

Code: Select all

(defparameter x (list 0 1 2 3))
(defparameter y (cdr (copy-list x)))

CLISP History

In the very early days CLISP was developed to run the Maxima Computer Algebra System on standard home computers in a terminal window with a command history and cursor control. This was in the 1990s, when home computers had only a few megabytes of memory. Because Maxima makes heavy use of lists for math computations, it probably was most important not to waste memory for list operations. I'm no CLISP developer but I think this is one of the reasons for the unusual behaviour of NREVERSE in CLISP.

- edgar

[40hex]

Thanks for the box drawings, thanks for pointing the sneaky-mean trap.
This phenomenon bit me a few times in the my early lisp-days; today I nreverse responsibly (:

Another sneaky-mean destructive operator is MAPCAN in combination
with PUSHF. Paul Graham has a brief explanation in "ANSI Common Lisp".
Attention to detail required; good introductory Lisp books even more
required.