Hi,
At the risk of being ridiculed, can anyone explain the following
behaviour with SBCL:
--
(defparameter *a* '(#(2 4) #(7 4) #(18 2) #(2 10) #(89 83) #(34 2)))
(defun dist (a b)
(let ((x (- (elt b 0) (elt a 0)))
(y (- (elt b 1) (elt a 1))))
(+ (* x x) (* y y))))
(defun tst (x xs)
(sort xs #'(lambda (a b) (< (dist a x) (dist b x)))))
(format t "~a~%" (tst #(4 3) *a*))
(format t "~a~%" (tst #(18 12) *a*))
(format t "~a~%" (tst #(5 2) *a*))
--
SBCL 1.0.22 gives:
(#(2 4) #(7 4) #(2 10) #(18 2) #(34 2) #(89 83))
(#(18 2) #(7 4) #(2 10) #(2 4) #(34 2) #(89 83))
(#(2 4) #(34 2) #(89 83))
CLISP 2.43, LispWorks Personal both give (as I would expect):
(#(2 4) #(7 4) #(2 10) #(18 2) #(34 2) #(89 83))
(#(18 2) #(7 4) #(2 10) #(2 4) #(34 2) #(89 83))
(#(7 4) #(2 4) #(2 10) #(18 2) #(34 2) #(89 83))
I am assuming that its something to do with my naive predicate to
destructive 'sort', but I am new to all this...
Apologies if it's blindingly obvious.
On Jul 20, 3:15 pm, b23 <·······@tyldd.com> wrote:
> Hi,
>
> At the risk of being ridiculed, can anyone explain the following
> behaviour with SBCL:
>
> --
> (defparameter *a* '(#(2 4) #(7 4) #(18 2) #(2 10) #(89 83) #(34 2)))
>
> (defun dist (a b)
> (let ((x (- (elt b 0) (elt a 0)))
> (y (- (elt b 1) (elt a 1))))
> (+ (* x x) (* y y))))
>
> (defun tst (x xs)
> (sort xs #'(lambda (a b) (< (dist a x) (dist b x)))))
>
> (format t "~a~%" (tst #(4 3) *a*))
> (format t "~a~%" (tst #(18 12) *a*))
> (format t "~a~%" (tst #(5 2) *a*))
>
> --
>
> SBCL 1.0.22 gives:
>
> (#(2 4) #(7 4) #(2 10) #(18 2) #(34 2) #(89 83))
> (#(18 2) #(7 4) #(2 10) #(2 4) #(34 2) #(89 83))
> (#(2 4) #(34 2) #(89 83))
>
> CLISP 2.43, LispWorks Personal both give (as I would expect):
>
> (#(2 4) #(7 4) #(2 10) #(18 2) #(34 2) #(89 83))
> (#(18 2) #(7 4) #(2 10) #(2 4) #(34 2) #(89 83))
> (#(7 4) #(2 4) #(2 10) #(18 2) #(34 2) #(89 83))
>
> I am assuming that its something to do with my naive predicate to
> destructive 'sort', but I am new to all this...
> Apologies if it's blindingly obvious.
The predicate is not the problem, sort is (and in particular the fact
it's a destructive operation). You are modifying the list pointed by
*a* while sorting it. This is bad, also because in your example *a*
refers to a quoted list which is a literal value, and modifying a
literal value is undefined behaviour. One solution is to (sort (copy-
list ...) ...).
hth,
Alessio
On Jul 20, 2:23 pm, Alessio Stalla <·············@gmail.com> wrote:
> On Jul 20, 3:15 pm, b23 <·······@tyldd.com> wrote:
>
>
>
>
>
> > Hi,
>
> > At the risk of being ridiculed, can anyone explain the following
> > behaviour with SBCL:
>
> > --
> > (defparameter *a* '(#(2 4) #(7 4) #(18 2) #(2 10) #(89 83) #(34 2)))
>
> > (defun dist (a b)
> > (let ((x (- (elt b 0) (elt a 0)))
> > (y (- (elt b 1) (elt a 1))))
> > (+ (* x x) (* y y))))
>
> > (defun tst (x xs)
> > (sort xs #'(lambda (a b) (< (dist a x) (dist b x)))))
>
> > (format t "~a~%" (tst #(4 3) *a*))
> > (format t "~a~%" (tst #(18 12) *a*))
> > (format t "~a~%" (tst #(5 2) *a*))
>
> > --
>
> > SBCL 1.0.22 gives:
>
> > (#(2 4) #(7 4) #(2 10) #(18 2) #(34 2) #(89 83))
> > (#(18 2) #(7 4) #(2 10) #(2 4) #(34 2) #(89 83))
> > (#(2 4) #(34 2) #(89 83))
>
> > CLISP 2.43, LispWorks Personal both give (as I would expect):
>
> > (#(2 4) #(7 4) #(2 10) #(18 2) #(34 2) #(89 83))
> > (#(18 2) #(7 4) #(2 10) #(2 4) #(34 2) #(89 83))
> > (#(7 4) #(2 4) #(2 10) #(18 2) #(34 2) #(89 83))
>
> > I am assuming that its something to do with my naive predicate to
> > destructive 'sort', but I am new to all this...
> > Apologies if it's blindingly obvious.
>
> The predicate is not the problem, sort is (and in particular the fact
> it's a destructive operation). You are modifying the list pointed by
> *a* while sorting it. This is bad, also because in your example *a*
> refers to a quoted list which is a literal value, and modifying a
> literal value is undefined behaviour. One solution is to (sort (copy-
> list ...) ...).
>
> hth,
> Alessio
Thanks - that's great. The phrase 'undefined behaviour' is what I was
looking for.
b23 wrote:
[snip]
> (defun tst (x xs)
> (sort xs #'(lambda (a b) (< (dist a x) (dist b x)))))
[snip]
> SBCL 1.0.22 gives:
>
> (#(2 4) #(7 4) #(2 10) #(18 2) #(34 2) #(89 83))
> (#(18 2) #(7 4) #(2 10) #(2 4) #(34 2) #(89 83))
> (#(2 4) #(34 2) #(89 83))
>
> CLISP 2.43, LispWorks Personal both give (as I would expect):
>
> (#(2 4) #(7 4) #(2 10) #(18 2) #(34 2) #(89 83))
> (#(18 2) #(7 4) #(2 10) #(2 4) #(34 2) #(89 83))
> (#(7 4) #(2 4) #(2 10) #(18 2) #(34 2) #(89 83))
>
> I am assuming that its something to do with my naive predicate to
> destructive 'sort', but I am new to all this...
Well, you hit the nail on the head in recognizing that you're getting
behavior that you weren't expecting as a result of your SORTing. If you
modify the format statements a little bit to output the value of *a*
after calling tst, you can observe what's happening to its value:
CL-USER> (defparameter *a* '(#(2 4) #(7 4) #(18 2) #(2 10) #(89 83)
#(34 2)))
*A*
;; define dist and tst...
CL-USER> (progn
(format t "~a~%~a~%~%" (tst #(4 3) *a*) *a*)
(format t "~a~%~a~%~%" (tst #(18 12) *a*) *a*)
(format t "~a~%~a~%~%" (tst #(5 2) *a*) *a*))
(#(2 4) #(7 4) #(2 10) #(18 2) #(34 2) #(89 83)) ; result of tst
(#(2 4) #(7 4) #(2 10) #(18 2) #(34 2) #(89 83)) ; value of *a*
(#(18 2) #(7 4) #(2 10) #(2 4) #(34 2) #(89 83)) ; result of tst
(#(2 4) #(34 2) #(89 83)) ; value of *a*
(#(2 4) #(34 2) #(89 83)) ; result of tst
(#(2 4) #(34 2) #(89 83)) ; value of *a*
NIL
SORT is allowed to modify the list structure of a list passed to it.
Specifically, SORT is allowed modify the CAR and CDR of any CONS in the
structure of the list [1, and follow the link about NREVERSE]. If want
to ensure that SORT isn't going to modify a value that you care about,
pass in a copy of the value instead. For instance, if you define tst by:
CL-USER>
(defun tst (x xs)
(sort (copy-seq xs) ; copy the sequence with COPY-SEQ
#'(lambda (a b) (< (dist a x) (dist b x)))))
STYLE-WARNING: redefining TST in DEFUN
TST
(and reset the value of *a* as well), the format trio from above outputs:
CL-USER> (progn
(format t "~a~%~a~%~%" (tst #(4 3) *a*) *a*)
(format t "~a~%~a~%~%" (tst #(18 12) *a*) *a*)
(format t "~a~%~a~%~%" (tst #(5 2) *a*) *a*))
(#(2 4) #(7 4) #(2 10) #(18 2) #(34 2) #(89 83))
(#(2 4) #(7 4) #(18 2) #(2 10) #(89 83) #(34 2))
(#(18 2) #(7 4) #(2 10) #(2 4) #(34 2) #(89 83))
(#(2 4) #(7 4) #(18 2) #(2 10) #(89 83) #(34 2))
(#(7 4) #(2 4) #(2 10) #(18 2) #(34 2) #(89 83))
(#(2 4) #(7 4) #(18 2) #(2 10) #(89 83) #(34 2))
NIL
which is what you wanted, I think. If you never need to modify *a*,
you're all set now.
However, if you may ever modify *a*, don't define its value with a
quoted literal (i.e., in (defparameter *a* '(...))). Defined like that,
the value is constant, and the result of trying to modify it is
undefined. If you plan to modify the structure of *a*, do
CL-USER> (defparameter *a* (list #(2 4) #(7 4) #(18 2) #(2 10) #(89 83)
#(34 2)))
*A*
or if you might modify the contents of those vectors too, something like
CL-USER> (defparameter *a*
(mapcar #'(lambda (points)
(apply 'vector points))
'((2 4) (7 4) (18 2) (2 10) (89 83) (34 2))))
*A*
//JT
[1] http://www.lispworks.com/documentation/HyperSpec/Body/f_sort_.htm
On Jul 20, 2:46 pm, Joshua Taylor <······@cs.rpi.edu> wrote:
> b23 wrote:
>
> [snip]
>
>
>
>
>
> > (defun tst (x xs)
> > (sort xs #'(lambda (a b) (< (dist a x) (dist b x)))))
> [snip]
> > SBCL 1.0.22 gives:
>
> > (#(2 4) #(7 4) #(2 10) #(18 2) #(34 2) #(89 83))
> > (#(18 2) #(7 4) #(2 10) #(2 4) #(34 2) #(89 83))
> > (#(2 4) #(34 2) #(89 83))
>
> > CLISP 2.43, LispWorks Personal both give (as I would expect):
>
> > (#(2 4) #(7 4) #(2 10) #(18 2) #(34 2) #(89 83))
> > (#(18 2) #(7 4) #(2 10) #(2 4) #(34 2) #(89 83))
> > (#(7 4) #(2 4) #(2 10) #(18 2) #(34 2) #(89 83))
>
> > I am assuming that its something to do with my naive predicate to
> > destructive 'sort', but I am new to all this...
>
> Well, you hit the nail on the head in recognizing that you're getting
> behavior that you weren't expecting as a result of your SORTing. If you
> modify the format statements a little bit to output the value of *a*
> after calling tst, you can observe what's happening to its value:
>
> CL-USER> (defparameter *a* '(#(2 4) #(7 4) #(18 2) #(2 10) #(89 83)
> #(34 2)))
> *A*
>
> ;; define dist and tst...
>
> CL-USER> (progn
> (format t "~a~%~a~%~%" (tst #(4 3) *a*) *a*)
> (format t "~a~%~a~%~%" (tst #(18 12) *a*) *a*)
> (format t "~a~%~a~%~%" (tst #(5 2) *a*) *a*))
> (#(2 4) #(7 4) #(2 10) #(18 2) #(34 2) #(89 83)) ; result of tst
> (#(2 4) #(7 4) #(2 10) #(18 2) #(34 2) #(89 83)) ; value of *a*
>
> (#(18 2) #(7 4) #(2 10) #(2 4) #(34 2) #(89 83)) ; result of tst
> (#(2 4) #(34 2) #(89 83)) ; value of *a*
>
> (#(2 4) #(34 2) #(89 83)) ; result of tst
> (#(2 4) #(34 2) #(89 83)) ; value of *a*
>
> NIL
>
> SORT is allowed to modify the list structure of a list passed to it.
> Specifically, SORT is allowed modify the CAR and CDR of any CONS in the
> structure of the list [1, and follow the link about NREVERSE]. If want
> to ensure that SORT isn't going to modify a value that you care about,
> pass in a copy of the value instead. For instance, if you define tst by:
>
> CL-USER>
> (defun tst (x xs)
> (sort (copy-seq xs) ; copy the sequence with COPY-SEQ
> #'(lambda (a b) (< (dist a x) (dist b x)))))
> STYLE-WARNING: redefining TST in DEFUN
> TST
>
> (and reset the value of *a* as well), the format trio from above outputs:
>
> CL-USER> (progn
> (format t "~a~%~a~%~%" (tst #(4 3) *a*) *a*)
> (format t "~a~%~a~%~%" (tst #(18 12) *a*) *a*)
> (format t "~a~%~a~%~%" (tst #(5 2) *a*) *a*))
> (#(2 4) #(7 4) #(2 10) #(18 2) #(34 2) #(89 83))
> (#(2 4) #(7 4) #(18 2) #(2 10) #(89 83) #(34 2))
>
> (#(18 2) #(7 4) #(2 10) #(2 4) #(34 2) #(89 83))
> (#(2 4) #(7 4) #(18 2) #(2 10) #(89 83) #(34 2))
>
> (#(7 4) #(2 4) #(2 10) #(18 2) #(34 2) #(89 83))
> (#(2 4) #(7 4) #(18 2) #(2 10) #(89 83) #(34 2))
>
> NIL
>
> which is what you wanted, I think. If you never need to modify *a*,
> you're all set now.
>
> However, if you may ever modify *a*, don't define its value with a
> quoted literal (i.e., in (defparameter *a* '(...))). Defined like that,
> the value is constant, and the result of trying to modify it is
> undefined. If you plan to modify the structure of *a*, do
>
> CL-USER> (defparameter *a* (list #(2 4) #(7 4) #(18 2) #(2 10) #(89 83)
> #(34 2)))
> *A*
>
> or if you might modify the contents of those vectors too, something like
>
> CL-USER> (defparameter *a*
> (mapcar #'(lambda (points)
> (apply 'vector points))
> '((2 4) (7 4) (18 2) (2 10) (89 83) (34 2))))
> *A*
>
> //JT
>
> [1]http://www.lispworks.com/documentation/HyperSpec/Body/f_sort_.htm
It all makes sense now - following the link to 'nreverse' helped.
RTFM, I guess. Thanks, all - I suspected it was 'sort' - and I can now
understand why, and also why Seibel recommends "[Y]ou should always do
something with the return value of these functions (such as assign it
to a variable or pass it to another function), and, two, unless you're
done with the object you're passing to the destructive function, you
should pass a copy instead". From this discussion it looks like the
best solution is 'just don't do it that way.' I had modified
everything to use 'copy-seq' before posting anyhow.
Thanks again, helpful people.
In article <············@news.eternal-september.org>,
Joshua Taylor <······@cs.rpi.edu> wrote:
> SORT is allowed to modify the list structure of a list passed to it.
This is one of the many ways that the standard conspires to confuse
newbies. SORT really ought to be called NSORT to alert people to the
fact that it is (potentially) destructive. The Right Fix IMHO is:
(defun nsort (...) (sort ...))
(shadow 'sort)
(defun sort (...) (nsort (copy-seq ...) ..))
rg