Is that an NREVERSE bug? (SBCL)

Discussion of Common Lisp
Post Reply
40hex
Posts: 3
Joined: Wed Sep 02, 2015 12:00 pm

Is that an NREVERSE bug? (SBCL)

Post by 40hex » Wed Sep 02, 2015 12:10 pm

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
Posts: 538
Joined: Sat Aug 09, 2008 10:44 am
Location: Newton, MA

Re: Is that an NREVERSE bug? (SBCL)

Post by nuntius » Wed Sep 02, 2015 2:57 pm

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
Posts: 226
Joined: Fri Aug 06, 2010 6:34 am
Location: Germany

Re: Is that an NREVERSE bug? (SBCL)

Post by edgar-rft » Wed Sep 02, 2015 8:41 pm

It's only the return-value of NREVERSE that counts, the argument's value is allowed to be destructively modified into a complete mess:
CLHS NREVERSE wrote:
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
Posts: 226
Joined: Fri Aug 06, 2010 6:34 am
Location: Germany

Re: Is that an NREVERSE bug? (SBCL)

Post by edgar-rft » Thu Sep 03, 2015 2:48 am

The same explanation with some box-and-arrows artwork :P

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
Last edited by edgar-rft on Thu Sep 03, 2015 5:12 am, edited 1 time in total.

edgar-rft
Posts: 226
Joined: Fri Aug 06, 2010 6:34 am
Location: Germany

Re: Is that an NREVERSE bug? (SBCL)

Post by edgar-rft » Thu Sep 03, 2015 3:15 am

Finally found it - Citation from the CLISP implementation notes Section 17.3 - Functions NREVERSE and NRECONC:
CLISP ImpNotes, Section 17.3. wrote: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
Posts: 3
Joined: Wed Sep 02, 2015 12:00 pm

Re: Is that an NREVERSE bug? (SBCL)

Post by 40hex » Thu Sep 03, 2015 3:04 pm

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
Posts: 226
Joined: Fri Aug 06, 2010 6:34 am
Location: Germany

Re: Is that an NREVERSE bug? (SBCL)

Post by edgar-rft » Fri Sep 04, 2015 8:26 am

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
Posts: 3
Joined: Wed Sep 02, 2015 12:00 pm

Re: Is that an NREVERSE bug? (SBCL)

Post by 40hex » Tue Sep 08, 2015 11:42 am

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.

Post Reply