Side effects of `sort'

Side effects of `sort'

[Daniel Schoepe]

[-- Attachment #1: Type: text/plain, Size: 884 bytes --]

Hi,

according to describe-function, `sort' modifies its input list, but not
in any way that the programmer can rely on. (For example, '(2 1 3)
becomes '(2 3)). I assume the precise thing that ends up in the original
list is an implementation detail and being able to "destroy" the
original list has some performance benefits.

Personally, I find this behavior very surprising and think it would make
more sense to either set the input list to the final sorting result (in
addition to returning it) or not to modify the input. In the current
situation, one basically has to do something like (setq foo (sort foo))
anyway if one wants to continue using foo (or pass a copy of foo to sort
instead), which would no longer be necessary after this change (modulo
backwards compatibility).

Is there some rationale for sort working the way it does, that I am
missing here?

Cheers,
Daniel


[-- Attachment #2: Type: application/pgp-signature, Size: 835 bytes --]

Re: Side effects of `sort'

[Tassilo Horn]

Daniel Schoepe <daniel@schoepe.org> writes:

Hi Daniel,

> according to describe-function, `sort' modifies its input list, but
> not in any way that the programmer can rely on. (For example, '(2 1 3)
> becomes '(2 3)). I assume the precise thing that ends up in the
> original list is an implementation detail and being able to "destroy"
> the original list has some performance benefits.
>
> Personally, I find this behavior very surprising and think it would make
> more sense to either set the input list to the final sorting result (in
> addition to returning it) or not to modify the input.

That's the point of all destructive operations like sort, nconc,
nreverse and so forth.  The perform better, because they don't copy but
only rearrange pointers in their input, and you must always use the
return value.

In your example, foo points to the list (2 1 3), i.e., foo is a pointer
to the cons cell (2 . cdr).

  foo -> (2 . (1 . (3 . nil)))

2 is bigger than 1, so we can make the 1-cons-cdr point to the 2-cons,
and the 2-cons-cdr point to the cdr of the 1-cons.

  (1 . (2 . (3 . nil)))
       ^
       |
      foo

However, the variable foo still points to the original cons cell (2
. cdr).  See?

Bye,
Tassilo

Re: Side effects of `sort'

[Dave Abrahams]

on Thu Mar 01 2012, Daniel Schoepe <daniel-AT-schoepe.org> wrote:

> Hi,
>
> according to describe-function, `sort' modifies its input list, but not
> in any way that the programmer can rely on. (For example, '(2 1 3)
> becomes '(2 3)). I assume the precise thing that ends up in the original
> list is an implementation detail and being able to "destroy" the
> original list has some performance benefits.
>
> Personally, I find this behavior very surprising and think it would make
> more sense to either set the input list to the final sorting result (in
> addition to returning it) or not to modify the input. In the current
> situation, one basically has to do something like (setq foo (sort foo))
> anyway if one wants to continue using foo (or pass a copy of foo to sort
> instead), which would no longer be necessary after this change (modulo
> backwards compatibility).
>
> Is there some rationale for sort working the way it does, that I am
> missing here?

Lisp doesn't really have access to "the input list" in any real sense:

   (sort (identity x))

do you expect x to be rebound?

-- 
Dave Abrahams
BoostPro Computing
http://www.boostpro.com

Re: Side effects of `sort'

[Daniel Schoepe]

[-- Attachment #1: Type: text/plain, Size: 334 bytes --]

On Thu, 01 Mar 2012 16:04:19 -0500, Dave Abrahams <dave@boostpro.com> wrote:
> Lisp doesn't really have access to "the input list" in any real sense:

Oh, that's what I was missing: sort can't really do something like (setq
foo (sort foo)) by itself. I guess that renders my point moot.

Thanks for clearing that up.

Cheers,
Daniel


[-- Attachment #2: Type: application/pgp-signature, Size: 835 bytes --]

Re: Side effects of `sort'

[Stefan Monnier]

> Lisp doesn't really have access to "the input list" in any real sense:
>    (sort (identity x))
> do you expect x to be rebound?

It doesn't hav access to `x' but it has access to the list, obviously.
If the input is nil, the output is nil, and if the input is a cons, the
output could be the same cons.    It just means that `sort' would have
to fiddle not only with `cdr's but also with the `car's.
Not worth the trouble, tho.


        Stefan

Re: Side effects of `sort'

[Miles Bader]

Stefan Monnier <monnier@IRO.UMontreal.CA> writes:
> It just means that `sort' would have
> to fiddle not only with `cdr's but also with the `car's.
> Not worth the trouble, tho.

Also it would make sort inconsistent with other destructive list
operators, some of which _can't_ be "fixed".

A lisp programmer basically has to learn this pattern eventually.

-miles

-- 
Admiration, n. Our polite recognition of another's resemblance to ourselves.