Discussion:
what exactly does UNION return?
(too old to reply)
Andrei Zorine
2020-05-07 21:44:30 UTC
Permalink
Gentlemen,
I see the following behaviour:

CL-USER> (let ((A\\B (list 1 3)) (AB (list 4 2)))
(union A\\B AB) (print AB))

(4 2)
(4 2)
CL-USER> (let ((A\\B (list 1 3)) (AB (list 4 2)))
(sort (union A\\B AB) #'<) (print AB))

(2 3 4)

So, why does SORTing spoil the list stored in AB?

Sincerely yours,
Andrei Zorine
Andrei Zorine
2020-05-07 21:56:44 UTC
Permalink
An addition:
this test was run in SBCL. In CLISP the two inputs return two-elements lists as epected. Is it an SBCL issue?
Post by Andrei Zorine
Gentlemen,
CL-USER> (let ((A\\B (list 1 3)) (AB (list 4 2)))
(union A\\B AB) (print AB))
(4 2)
(4 2)
CL-USER> (let ((A\\B (list 1 3)) (AB (list 4 2)))
(sort (union A\\B AB) #'<) (print AB))
(2 3 4)
So, why does SORTing spoil the list stored in AB?
Sincerely yours,
Andrei Zorine
Piotr Chamera
2020-05-07 23:30:42 UTC
Permalink
Post by Andrei Zorine
Gentlemen,
CL-USER> (let ((A\\B (list 1 3)) (AB (list 4 2)))
(union A\\B AB) (print AB))
(4 2)
(4 2)
CL-USER> (let ((A\\B (list 1 3)) (AB (list 4 2)))
(sort (union A\\B AB) #'<) (print AB))
(2 3 4)
So, why does SORTing spoil the list stored in AB?
Sincerely yours,
Andrei Zorine
In CCL result is „(4)” :)

List returned by union shares some structure with its arguments
and when You destructively sort it it has implementation dependent
effect.

You can copy list before sorting:

(let ((A\\B (list 1 3)) (AB (list 4 2)))
(sort (copy-list (union A\\B AB)) #'<) (print AB))
Jocelyn Fréchot
2020-05-07 22:49:37 UTC
Permalink
List returned by union shares some structure with its arguments [..]
List returned by UNION doesn’t have to but may share. Hence
the different behaviour between SBCL and CLISP.

The trick is that the HyperSpec doesn’t say UNION returns a *fresh*
list. And that is... tricky.
--
Jocelyn Fréchot
Kaz Kylheku
2020-05-08 14:47:05 UTC
Permalink
Post by Andrei Zorine
Gentlemen,
CL-USER> (let ((A\\B (list 1 3)) (AB (list 4 2)))
(union A\\B AB) (print AB))
(4 2)
(4 2)
CL-USER> (let ((A\\B (list 1 3)) (AB (list 4 2)))
(sort (union A\\B AB) #'<) (print AB))
(2 3 4)
So, why does SORTing spoil the list stored in AB?
The Common Lisp SORT is defined in a way that permits it to be performed
in-place: the sorted list can be made out of pieces of the input list
even if that requires changing the contents of those pieces.

The UNION function isn't permitted to change its inputs, but it can
still return an object that is made out pieces of the input,
if doing so doesn't involve modifying the pieces.

So what is happening is that (union A\\B AB), though pure, is returning
an object that shares structure with the original AB.

When the result of UNION is passed to SORT, the destructive operatinos
inside that function are affecting the original AB.

We can obtain a pure sort by wrapping sort with a function
which ensures that SORT is given freshly allocated data that doesn't
share structure with anything in any other scope:

(defun pure-sort (sequence predicate &key key)
(sort (copy-seq sequence) predicate :key key))
--
TXR Programming Lanuage: http://nongnu.org/txr
Music DIY Mailing List: http://www.kylheku.com/diy
ADA MP-1 Mailing List: http://www.kylheku.com/mp1
Nelson Alexandra
2020-05-11 12:30:43 UTC
Permalink
Post by Kaz Kylheku
[...]
We can obtain a pure sort by wrapping sort with a function
which ensures that SORT is given freshly allocated data that doesn't
(defun pure-sort (sequence predicate &key key)
(sort (copy-seq sequence) predicate :key key))
The package rutils [1] contains safe-sort that seems to address this
problem.

rutils.sequence defines:

(defun safe-sort (sequence predicate &rest args &key key)
"The destructuve nature of SORT triggers many obscure bugs.
This function is a thin wrapper over SORT that enqures
that an input SEQUENCE is copied."
(declare (ignorable key))
(apply 'sort (copy-seq sequence) predicate args))

Some notes:

1. Norvig [2] hints that APPLY might exceed call-arguments-limit. But
that isn't a problem here, is it?

2. I get a
"STYLE-WARNING: The return value of STABLE-SORT-LIST should not be
discarded."
in sbcl when using safe-sort on the OP's example

(let ((A\\B (list 1 3)) (AB (list 4 2)))
(safe-sort (union A\\B AB) #'<) (print AB)).

I don't get that warning with pure-sort.

Is there a significant difference between the apply (safe-sort) and
no-apply (pure-sort) version?

[1] https://github.com/vseloved/rutils/blob/master/docs/tutorial.md
[2] http://norvig.com/luv-slides.ps
Jocelyn Fréchot
2020-05-11 13:15:02 UTC
Permalink
Post by Nelson Alexandra
2. I get a
"STYLE-WARNING: The return value of STABLE-SORT-LIST should not be
discarded."
in sbcl when using safe-sort on the OP's example
(let ((A\\B (list 1 3)) (AB (list 4 2)))
(safe-sort (union A\\B AB) #'<) (print AB)).
I don't get that warning with pure-sort.
Is there a significant difference between the apply (safe-sort) and
no-apply (pure-sort) version?
I guess you get this warning because SAFE-SORT is declared as inline
(top of the file).
--
Jocelyn Fréchot
Loading...