Destructive side effect of the union operator

Interesting destructive side effect of the union operator. 
It actually only shows after a sort is done on the union. 
Bruno

CL-USER 125 : 3 > (setf x '(1 2 3 4))
(1 2 3 4)

CL-USER 126 : 3 > (setf y '(5 6 7 8))
(5 6 7 8)

CL-USER 127 : 3 > (setf w (append x y))
(1 2 3 4 5 6 7 8)

CL-USER 128 : 3 > (setf z (union x y))
(8 7 6 5 1 2 3 4)

CL-USER 129 : 3 > x
(1 2 3 4)

CL-USER 130 : 3 > (sort w #'>)
(8 7 6 5 4 3 2 1)

CL-USER 131 : 3 > x
(1 2 3 4)

CL-USER 132 : 3 > (sort z #'>)
(8 7 6 5 4 3 2 1)

CL-USER 133 : 3 > x
(1)

CL-USER 134 : 3 > y
(4 3 2 1)

_______________________________________________
Lisp Hug - the mailing list for LispWorks users
lisp-hug@lispworks.com
http://www.lispworks.com/support/lisp-hug.html

Re: Destructive side effect of the union operator

> On 26 Jun 2014, at 21:38, Bruno Emond <brunoemond@fastmail.fm> wrote:
> 
> Interesting destructive side effect of the union operator.

No.  The return value of UNION may share structure with its arguments.  SORT is destructive, and may therefore modify that structure.

_______________________________________________
Lisp Hug - the mailing list for LispWorks users
lisp-hug@lispworks.com
http://www.lispworks.com/support/lisp-hug.html

Re: Destructive side effect of the union operator

Bruno Emond <brunoemond@fastmail.fm> writes:

> Interesting destructive side effect of the union operator. 
> It actually only shows after a sort is done on the union. 
> Bruno
>
> CL-USER 125 : 3 > (setf x '(1 2 3 4))
> (1 2 3 4)
>
> CL-USER 126 : 3 > (setf y '(5 6 7 8))
> (5 6 7 8)
>
> CL-USER 127 : 3 > (setf w (append x y))
> (1 2 3 4 5 6 7 8)
>
> CL-USER 128 : 3 > (setf z (union x y))
> (8 7 6 5 1 2 3 4)
>
> CL-USER 129 : 3 > x
> (1 2 3 4)

So far, so good.  Conforming code above.


> CL-USER 130 : 3 > (sort w #'>)
> (8 7 6 5 4 3 2 1)

This call to SORT is not conforming, because W contains literal data.




UNION is NOT DESTRUCTIVE.
NUNION is NON-consing, and therefore MAY HAVE TO BE destructive.

Compare:

[pjb@kuiper :0.0 ~]$ clall -r '(let ((a (list 1 3 5)) (b (list 2 4 6))) (values (NUNION a b) a b))'

Armed Bear Common Lisp         --> (5 3 1 2 4 6), (1 2 4 6), (2 4 6)
Clozure Common Lisp            --> (5 3 1 2 4 6), (1 2 4 6), (2 4 6)
CLISP                          --> (1 3 5 2 4 6), (1 3 5 2 4 6), (2 4 6)
CMU Common Lisp                --> (5 3 1 2 4 6), (1 2 4 6), (2 4 6)
ECL                            --> (1 3 5 2 4 6), (1 3 5 2 4 6), (2 4 6)
SBCL                           --> (5 3 1 2 4 6), (1 2 4 6), (2 4 6)

[pjb@kuiper :0.0 ~]$ clall -r '(let ((a (list 1 3 5)) (b (list 2 4 6))) (values (UNION a b) a b))'

Armed Bear Common Lisp         --> (5 3 1 2 4 6), (1 3 5), (2 4 6)
Clozure Common Lisp            --> (5 3 1 2 4 6), (1 3 5), (2 4 6)
CLISP                          --> (1 3 5 2 4 6), (1 3 5), (2 4 6)
CMU Common Lisp                --> (5 3 1 2 4 6), (1 3 5), (2 4 6)
ECL                            --> (1 3 5 2 4 6), (1 3 5), (2 4 6)
SBCL                           --> (5 3 1 2 4 6), (1 3 5), (2 4 6)



Of course, if NUNION doesn't have to be destructive, then it is not
(there's no point in doing useless work):

[pjb@kuiper :0.0 ~]$ clall -r '(setf *print-circle* t)' '(let ((a (list 1 3 5)) (b (list 1 3 5))) (list (nunion a b) a b))'

Armed Bear Common Lisp         --> T
Armed Bear Common Lisp         --> (#1=(1 3 5) (1 3 5) #1#)
Clozure Common Lisp            --> T
Clozure Common Lisp            --> (#1=(1 3 5) (1 3 5) #1#)
CLISP                          --> T
CLISP                          --> (#1=(1 3 5) (1 3 5) #1#)
CMU Common Lisp                --> T
CMU Common Lisp                --> (#1=(1 3 5) (1 3 5) #1#)
ECL                            --> T
ECL                            --> (#1=(1 3 5) (1 3 5) #1#)
SBCL                           --> T
SBCL                           --> (#1=(1 3 5) (1 3 5) #1#)


-- 
__Pascal Bourguignon__
http://www.informatimago.com/
"Le mercure monte ?  C'est le moment d'acheter !"

_______________________________________________
Lisp Hug - the mailing list for LispWorks users
lisp-hug@lispworks.com
http://www.lispworks.com/support/lisp-hug.html

Re: Destructive side effect of the union operator

On Thu, 26 Jun 2014 16:38:50 -0400
Bruno Emond <brunoemond@fastmail.fm> wrote:

> 
> Interesting destructive side effect of the union operator. 
> It actually only shows after a sort is done on the union. 
> Bruno
> 
> CL-USER 125 : 3 > (setf x '(1 2 3 4))
> (1 2 3 4)
> 
> CL-USER 126 : 3 > (setf y '(5 6 7 8))
> (5 6 7 8)
> 
> CL-USER 127 : 3 > (setf w (append x y))
> (1 2 3 4 5 6 7 8)
> 
> CL-USER 128 : 3 > (setf z (union x y))
> (8 7 6 5 1 2 3 4)
> 
> CL-USER 129 : 3 > x
> (1 2 3 4)
> 
> CL-USER 130 : 3 > (sort w #'>)
> (8 7 6 5 4 3 2 1)
> 
> CL-USER 131 : 3 > x
> (1 2 3 4)
> 
> CL-USER 132 : 3 > (sort z #'>)
> (8 7 6 5 4 3 2 1)
> 
> CL-USER 133 : 3 > x
> (1)
> 
> CL-USER 134 : 3 > y
> (4 3 2 1)
My only response is "Ouch!"

Sincerely
-- 
Dr Sian Mountbatten
http://www.poenikatu.co.uk/
Associate member of the FSF no. 10888
Asocia membro de la Libera Programara Fonduso n-ro 10888

_______________________________________________
Lisp Hug - the mailing list for LispWorks users
lisp-hug@lispworks.com
http://www.lispworks.com/support/lisp-hug.html

Re: Destructive side effect of the union operator

SETF'ing an undeclared variable is unspecifiied behavior, but was
being pointed out is that literal data was being modified. It was
literal data because you QUOTE'ed it.  So

(let ((a '(2 3 4 5 1)))
  (sort a '<))

is a problem, too.  From the HyperSpec

>>>
4.1.2 Literal expressions

… As noted in section 3.4, it is an error to alter a constant (i.e.
the value of a literal expression) using a mutation procedure like
set-car! or string-set!.
<<<


On Fri, Jun 27, 2014 at 8:51 AM, Bruno Emond <brunoemond@fastmail.fm> wrote:
>
> Yes I checked the Lisp specs, and no reference is made to destructive side effects of union.
> My mistake.
>
> Sorry for my ignorance, but what would be conforming code?
> I guess  I do not see the subtlety in assigning a value to z with a setf compared to a let* operator (beside the scope of the variable).
>
> Bruno
>
> On 2014-06-27, at 07:16 , Tim Bradshaw wrote:
>
>> On 27 Jun 2014, at 01:49, Pascal J. Bourguignon <pjb@informatimago.com> wrote:
>>
>>> his call to SORT is not conforming, because W contains literal data.
>>
>> This is correct, of course (and an important point), but the effect happens even in conforming code:
>>
>> (let* ((x (list 1 2 3 4))
>>       (y (list 5))
>>       (z (union y x)))
>>  (values (sort z #'<) x y)))
>>
>> or even using the canonical non-destructive function
>>
>> (let* ((x (list 1 2 3 4))
>>       (y 5)
>>       (z (cons y x)))
>>  (values (sort z #'<) x y))
>>
>> I know you know this, but OP may not.
>>
>
>
> _______________________________________________
> Lisp Hug - the mailing list for LispWorks users
> lisp-hug@lispworks.com
> http://www.lispworks.com/support/lisp-hug.html
>



-- 
Joshua Taylor, http://www.cs.rpi.edu/~tayloj/

_______________________________________________
Lisp Hug - the mailing list for LispWorks users
lisp-hug@lispworks.com
http://www.lispworks.com/support/lisp-hug.html

Re: Destructive side effect of the union operator

On Fri, Jun 27, 2014 at 8:56 AM, Joshua TAYLOR <joshuaaaron@gmail.com> wrote:
> SETF'ing an undeclared variable is unspecifiied behavior, but was
> being pointed out is that literal data was being modified. It was
> literal data because you QUOTE'ed it.  So
>
> (let ((a '(2 3 4 5 1)))
>   (sort a '<))
>
> is a problem, too.  From the HyperSpec
>
>>>>
> 4.1.2 Literal expressions
>
> … As noted in section 3.4, it is an error to alter a constant (i.e.
> the value of a literal expression) using a mutation procedure like
> set-car! or string-set!.
> <<<

Ooops, that was a quote about Scheme. For Common Lisp, it's in the doc
for QUOTE:

The consequences are undefined if literal objects (including quoted
objects) are destructively modified.
http://www.lispworks.com/documentation/HyperSpec/Body/s_quote.htm


>
>
> On Fri, Jun 27, 2014 at 8:51 AM, Bruno Emond <brunoemond@fastmail.fm> wrote:
>>
>> Yes I checked the Lisp specs, and no reference is made to destructive side effects of union.
>> My mistake.
>>
>> Sorry for my ignorance, but what would be conforming code?
>> I guess  I do not see the subtlety in assigning a value to z with a setf compared to a let* operator (beside the scope of the variable).
>>
>> Bruno
>>
>> On 2014-06-27, at 07:16 , Tim Bradshaw wrote:
>>
>>> On 27 Jun 2014, at 01:49, Pascal J. Bourguignon <pjb@informatimago.com> wrote:
>>>
>>>> his call to SORT is not conforming, because W contains literal data.
>>>
>>> This is correct, of course (and an important point), but the effect happens even in conforming code:
>>>
>>> (let* ((x (list 1 2 3 4))
>>>       (y (list 5))
>>>       (z (union y x)))
>>>  (values (sort z #'<) x y)))
>>>
>>> or even using the canonical non-destructive function
>>>
>>> (let* ((x (list 1 2 3 4))
>>>       (y 5)
>>>       (z (cons y x)))
>>>  (values (sort z #'<) x y))
>>>
>>> I know you know this, but OP may not.
>>>
>>
>>
>> _______________________________________________
>> Lisp Hug - the mailing list for LispWorks users
>> lisp-hug@lispworks.com
>> http://www.lispworks.com/support/lisp-hug.html
>>
>
>
>
> --
> Joshua Taylor, http://www.cs.rpi.edu/~tayloj/



-- 
Joshua Taylor, http://www.cs.rpi.edu/~tayloj/

_______________________________________________
Lisp Hug - the mailing list for LispWorks users
lisp-hug@lispworks.com
http://www.lispworks.com/support/lisp-hug.html

Re: Destructive side effect of the union operator

Tim Bradshaw <tfb@tfeb.org> writes:

> On 27 Jun 2014, at 01:49, Pascal J. Bourguignon <pjb@informatimago.com> wrote:
>
>> his call to SORT is not conforming, because W contains literal data.
>
> This is correct, of course (and an important point), but the effect happens even in conforming code:
>
> (let* ((x (list 1 2 3 4))
>        (y (list 5))
>        (z (union y x)))
>   (values (sort z #'<) x y)))
>
> or even using the canonical non-destructive function
>
> (let* ((x (list 1 2 3 4))
>        (y 5)
>        (z (cons y x)))
>   (values (sort z #'<) x y))
>
> I know you know this, but OP may not.

Those calls to SORT are still non-conforming, because you're using the
values of X and Y after.  Each implementation may implement
destructiveness in SORT in a different way, therefore you get different
modifications in the object bound to X and in the object bound to Y, in
different implementations (which is the definition of non-conforming).

If SORT was specified to destroy its argument the same way in all
implementations, those calls would be conforming (you could count on
those modifications of X and Y), but this is not the case.

If you wrote: 

 (let* ((x (list 1 2 3 4))
        (y (list 5))
        (z (union y x)))
   (sort z #'<))

then this would be conforming, because you'd not be leaking any
non-conforming side effect.

The non-conformance is in _depending_ on results that may differ in
different implementations.

The Common Lisp language has operators that have side effects.  When
those side effects are specified and implemented the same in all
implementations, you can use them portably.  When they are not specified
(but allowed) and therefore differ in different implementations, then
you should avoid those side effects, either by not producing them, or by
avoiding using the objects that have been thusly modified.  Otherwise
you will get different results in different implementations, and this is
what we call non-conforming.

 (let* ((x (list 1 2 3 4))
        (y 5)
        (z (cons y x)))
   (values (sort (copy-seq z) #'<) x y))
 --> (1 2 3 4 5), (1 2 3 4), 5

is conforming.

-- 
__Pascal Bourguignon__
http://www.informatimago.com/
"Le mercure monte ?  C'est le moment d'acheter !"

_______________________________________________
Lisp Hug - the mailing list for LispWorks users
lisp-hug@lispworks.com
http://www.lispworks.com/support/lisp-hug.html

Re: Destructive side effect of the union operator

Bruno Emond <brunoemond@fastmail.fm> writes:

> Yes I checked the Lisp specs, and no reference is made to destructive side effects of union. 
> My mistake.
>
> Sorry for my ignorance, but what would be conforming code? 

Both:

 (let* ((x (list 1 2 3 4))
       (y 5)
       (z (union #|or cons|# y x)))
   (sort z #'<))


 (let* ((x (list 1 2 3 4))
       (y 5)
       (z (union #|or cons|# y x)))
  (values (sort (copy-seq z) #'<) x y))

would be conforming.  They both would always produce the same results on
all conforming CL implementation.

The former one by not leaking unspecified side effects, the later by
ensuring that no unspecified side effect occurs.

-- 
__Pascal Bourguignon__
http://www.informatimago.com/
"Le mercure monte ?  C'est le moment d'acheter !"

_______________________________________________
Lisp Hug - the mailing list for LispWorks users
lisp-hug@lispworks.com
http://www.lispworks.com/support/lisp-hug.html