Destructive sorting in lisp

Question

I'm reading Practical Common Lisp. In chapter 11, it says this about sorting:

Typically you won't care about the unsorted version of a sequence after you've sorted it, so it makes sense to allow SORT and STABLE-SORT to destroy the sequence in the course of sorting it. But it does mean you need to remember to write the following:

(setf my-sequence (sort my-sequence #'string<))

I tried the following code:

CL-USER> (defparameter *a* #( 8 4 3 9 5 9 2 3 9 2 9 4 3)) 
*A*            
CL-USER> *a*
#(8 4 3 9 5 9 2 3 9 2 9 4 3)                                     
CL-USER> (sort *a* #'<)
#(2 2 3 3 3 4 4 5 8 9 9 9 9)
CL-USER> *a*
#(2 2 3 3 3 4 4 5 8 9 9 9 9)

In this code we can see that the variable *a* has been changed by the sort function.

Then why do the book say that is necessary to do an assignment?

I'm using SBCL + Ubuntu 14.04 + Emacs + Slime

EDIT: Following the comment of @Sylwester I add the evaluation of *a* so it's clear that the value has been changed.

Answer 1

It's necessary to do the assignment if you want your variable to contain the proper value of the sorted sequence afterwards. If you don't care about that and only want the return value of sort, you don't need an assignment.

There are two reasons for this. First, an implementation is allowed to use non-destructive copying to implement destructive operations. Secondly, destructive operations on lists can permute the conses such that the value passed into the operation no longer points to the first cons of the sequence.

Here's an example of the second problem (run under SBCL):

(let ((xs (list 4 3 2 1)))
  (sort xs '<)
  xs)
=> (4)

If we add the assignment:

(let ((xs (list 4 3 2 1)))
  (setf xs (sort xs '<))
  xs)
=> (1 2 3 4)

Answer 2

The variable can't be changed by the sort function, since the sort function does not know about the variable at all.

All the sort function gets is a vector or a list, but not variables.

In Common Lisp the sort function can be destructive. When it gets a vector for sorting, it can return the same vector or a new one. This is up to the implementation. In one implementation it might return the same vector and in another one it may return a new one. But in any case they will be sorted.

If there is a variable, which points to a sequence and for which the author expects that it will after sorting point to a sorted sequence: set the variable to the result of the sort operation. Otherwise there might be cases, where after potentially destructive sorting, the variable won't point to the SORT result, but still to an unsorted, or otherwise changed, sequence. In case of the vector this CAN be the old and unsorted vector.

REMEMBER The only thing you can be sure: the SORT function returns a sorted sequence as its value.