Hello,
I'm obviously missing something - I wrote a very trivial function
called nsort that I was hoping would return a sorted list and make the
change permanent (i.e. a destrucvtive function). Here's the code with
some debugging output statements:
(defun nsort (lst fn)
(progn
(format t "lst is set to: ~A~%" lst) ;; print lst before the sort
(setf lst (sort lst fn)) ;; sort it
(format t "lst is set to: ~A~%" lst) ;; print lst after the sort
lst)) ;;
and return it
The function returns what I expect except the list I passed in does not
contain what I expect it to upon the function's return - Here's an
example:
CL-USER(17): (setf x '(5 4 3 2 1))
CL-USER(18): (nsort x #'<)
lst is set to: (5 4 3 2 1)
lst is set to: (1 2 3 4 5)
(1 2 3 4 5)
CL-USER(19): x
(5)
As you can see (5) is NOT the value I expected x to hold. Any insight
would be greatly appreciated!
Dave
"David N. Richards" <·········@earthlink.net> writes:
> Hello,
> I'm obviously missing something - I wrote a very trivial function
> called nsort that I was hoping would return a sorted list and make the
> change permanent (i.e. a destrucvtive function). Here's the code with
> some debugging output statements:
> (defun nsort (lst fn)
> (progn
> (format t "lst is set to: ~A~%" lst) ;; print lst before the sort
>
> (setf lst (sort lst fn)) ;; sort it
> (format t "lst is set to: ~A~%" lst) ;; print lst after the sort
>
> lst)) ;;
> and return it
>
> The function returns what I expect except the list I passed in does not
> contain what I expect it to upon the function's return - Here's an
> example:
>
>
> As you can see (5) is NOT the value I expected x to hold. Any insight
> would be greatly appreciated!
Let's go through this step by step:
[I changed the list to be 3 elements long so I could draw it easily]
> CL-USER(17): (setf x '(3 2 1))
Here's what you have now:
X ---+
|
V
+---+---+ +---+---+ +---+-----+
| 3 | *-->| 2 | *-->| 1 | nil |
+---+---+ +---+---+ +---+-----+
> CL-USER(18): (nsort x #'<)
> lst is set to: (3 2 1)
On entry to NSORT, you now have:
X ---+
|
V
+---+---+ +---+---+ +---+-----+
| 3 | *-->| 2 | *-->| 1 | nil |
+---+---+ +---+---+ +---+-----+
^
|
LST -+
NSORT calls SORT. The hyperspec has this (among other things) to say
about SORT:
sort and stable-sort destructively sort sequences according to the
order determined by the predicate function.
This means that the value you pass in to SORT should not be used
again, because SORT may or may not have altered the contents, and you
can't be sure of its coherency. You should not do:
(let ((foo (make-foo)))
(sort foo #'>)
(use-foo foo))
But rather:
(let ((foo (make-foo)))
(setf foo (sort foo #'>))
(use-foo foo))
> lst is set to: (1 2 3)
> (1 2 3)
> CL-USER(19): x
> (3)
After the call to SORT, you have:
X ---+
| +---------------+
V V |
+---+-----+ +---+---+ +---+-|-+
| 3 | nil | | 2 | * | | 1 | * |
+---+-----+ +---+-|-+ +---+---+
^ | ^
+-----------------+ |
LST -----------------------+
You can accomplish what you want to do with NSORT by doing
(setf foo (sort foo ...)), but you cannot write a function to do that.
You *could* write a macro that would do what you want:
(defmacro sort-and-set (sequence-var fn)
`(setf ,sequence-var (sort ,sequence-var ,fn)))
But I wouldn't. I like the explicitness of using SETF.
Also, NSORT is a bad name for what you wanted to do. SORT is already
NSORT -- the N prefix means that it destructively operates on its
argument(s), not that it performs variable-setting magic for you.
One last thing: you should not do (sort '(...) ...). Instead, use
(sort (list ...) ...). That quoted list is a constant, and you aren't
allowed to modify it. It will work sometimes, but it's non-standard,
and in compiled code the following could happen:
* (let ((a '(3 2 1))
(b '(3 2 1)))
(when (eq a b) (format t "They're EQ, alright~%"))
(setf a (sort a #'<))
(values a b))
They're EQ, alright
(1 2 3);
(3)
"David N. Richards" <·········@earthlink.net> wrote in message
······················@earthlink.net...
> Hello,
> I'm obviously missing something - I wrote a very trivial function
> called nsort that I was hoping would return a sorted list and make the
> change permanent (i.e. a destrucvtive function).
Usually what "destructive" means is that the function is *allowed* to modify
the list argument rather than it will do anything predictable to it. So the
normal way to use sort (which is a destructive function already) is (setf
my-list (sort my-list #'my-compare-func)).
> Here's the code with
> some debugging output statements:
> (defun nsort (lst fn)
> (progn
> (format t "lst is set to: ~A~%" lst) ;; print lst before the sort
>
> (setf lst (sort lst fn)) ;; sort it
> (format t "lst is set to: ~A~%" lst) ;; print lst after the sort
>
> lst)) ;;
> and return it
>
> The function returns what I expect except the list I passed in does not
You could get the functionality you want with a macro:
CL-USER 210 > (defmacro nsort (list pred)
`(setf ,list (sort ,list ,pred)))
NSORT
CL-USER 211 > (setf foo '(2 4 3 5))
(2 4 3 5)
CL-USER 212 > (nsort foo #'>)
(5 4 3 2)
CL-USER 213 > foo
(5 4 3 2)
but there are a lot of good reasons why this is not a good macro even if it
may fit your immediate needs.
Coby
--
(remove #\space "coby . beck @ opentechgroup . com")
"David N. Richards" <·········@earthlink.net> wrote in message
······················@earthlink.net...
> Hello,
> I'm obviously missing something - I wrote a very trivial function
> called nsort that I was hoping would return a sorted list and make the
> change permanent (i.e. a destrucvtive function).
Usually what "destructive" means is that the function is *allowed* to modify
the list argument rather than it will do anything predictable to it. So the
normal way to use sort (which is a destructive function already) is (setf
my-list (sort my-list #'my-compare-func)).
> Here's the code with
> some debugging output statements:
> (defun nsort (lst fn)
> (progn
> (format t "lst is set to: ~A~%" lst) ;; print lst before the sort
>
> (setf lst (sort lst fn)) ;; sort it
> (format t "lst is set to: ~A~%" lst) ;; print lst after the sort
>
> lst)) ;;
> and return it
>
> The function returns what I expect except the list I passed in does not
You could get the functionality you want with a macro:
CL-USER 210 > (defmacro nsort (list pred)
`(setf ,list (sort ,list ,pred)))
NSORT
CL-USER 211 > (setf foo '(2 4 3 5))
(2 4 3 5)
CL-USER 212 > (nsort foo #'>)
(5 4 3 2)
CL-USER 213 > foo
(5 4 3 2)
but there are a lot of good reasons why this is not a good macro even if it
may fit your immediate needs.
Coby
--
(remove #\space "coby . beck @ opentechgroup . com")
In article <·················@earthlink.net>, David N. Richards wrote:
>CL-USER(17): (setf x '(5 4 3 2 1))
>CL-USER(18): (nsort x #'<)
>lst is set to: (5 4 3 2 1)
>lst is set to: (1 2 3 4 5)
>(1 2 3 4 5)
>CL-USER(19): x
>(5)
>
>As you can see (5) is NOT the value I expected x to hold.
X initialy holds a reference to the first cons cell of the list '(5 4
3 2 1). The CAR of that cons cell contains 5, and the CDR contains a
reference to the next cons cell.
If you destructively rearrange the nodes of the list into a different
order, guess what: the variable X still holds a reference to the same
cons cell. This time that cons cell is at the end of the list; its CAR
is still 5, but its CDR is NIL. So it looks like the variable X contains
the list (5).
So the moral of the story is that variable X does not contain a list,
but only a reference to the first cell. If you stick to pure functional
programming, you can, for the most part, be oblivious to any reference
semantics in the connection between a symbol and a value. It simply looks
like the name X represents the given list. Under imperative programming,
the representational artifacts rear their ugly head, so to speak. It
then makes a difference how a variable is connected to an object, and
to what part of the object, or which version of an object. Surprising
things happen: you modify some object, and all variables that are really
references to that object, or to some substructure within that object,
suddenly change their values. It's no longer transparent whether you
are dealing with an original object or a copy of it.
"David N. Richards" <·········@earthlink.net> writes:
>
> Hello,
> I'm obviously missing something - I wrote a very trivial function
> called nsort that I was hoping would return a sorted list and make the
> change permanent (i.e. a destrucvtive function). Here's the code with
> some debugging output statements:
> (defun nsort (lst fn)
> (progn
> (format t "lst is set to: ~A~%" lst) ;; print lst before the sort
>
> (setf lst (sort lst fn)) ;; sort it
> (format t "lst is set to: ~A~%" lst) ;; print lst after the sort
>
> lst)) ;;
> and return it
>
> The function returns what I expect except the list I passed in does not
> contain what I expect it to upon the function's return - Here's an
> example:
>
> CL-USER(17): (setf x '(5 4 3 2 1))
> CL-USER(18): (nsort x #'<)
> lst is set to: (5 4 3 2 1)
> lst is set to: (1 2 3 4 5)
> (1 2 3 4 5)
> CL-USER(19): x
> (5)
>
> As you can see (5) is NOT the value I expected x to hold. Any insight
> would be greatly appreciated!
Common Lisp is not call-by-reference, it is call-by-identity.
SORT is permitted to re-use the conses that make up the backbone of
the list. A lexical variable in a calling function cannot have its
"value" modified by the callee, but it can have the structure of the
object whose identity it points to modified. In some implementations,
though it's not required by the spec, SORT called on a list held by
a variable will end up holding onto some cons in that list, but not
necessarily the first cons. In other implementations, the cars might be
shuffled and the cdr's left alone.
e.g., in LispWorks 4.1.20, I see this:
(let* ((x5 (cons 5 '()))
(x4 (cons 4 x5))
(x3 (cons 3 x4))
(x2 (cons 2 x3))
(x1 (cons 1 x2))
(x x1))
(labels ((print-item (item)
(cond ((not item) (write-string "()"))
((atom item) (prin1 item))
(t (let ((n (position item (list nil x1 x2 x3 x4 x5))))
(when n (format t "#~D=" n))
(write-string "( ")
(print-item (car item))
(write-string " . ")
(print-item (cdr item))
(write-string ") "))))
item))
(print-item x)
(terpri)
(print-item (sort x #'>))))
#1=( 1 . #2=( 2 . #3=( 3 . #4=( 4 . #5=( 5 . ()) ) ) ) )
#1=( 5 . #5=( 4 . #4=( 3 . #3=( 2 . #2=( 1 . ()) ) ) ) )
[Normally you could just set *print-circle* to see this kind of notation
used, but it doesn't use the same set of indexes in two unrelated calls
to PRINT, so the cons names get hard to compare]
As you can perhaps see here, LispWorks goes to some trouble here (at least
in this example) to assure that the resulting cons is set in the way you
seem to be expecting, but you can see by the cons order 1 5 4 3 2 that it
wasn't its first choice. I bet in your Lisp implementation you'll see:
#5=( 5 . #4=( 4 . #3=( 3 . #2=( 2 . #1=( 1 . ()) ) ) ) )
as the second printed line.
This would explain why you sort's caller's variable is set to (1) after,
since it continues to point to cons #1 throughout.
In article <·················@earthlink.net>,
"David N. Richards" <·········@earthlink.net> writes:
> Hello,
> I'm obviously missing something - I wrote a very trivial function
> called nsort that I was hoping would return a sorted list and make the
> change permanent (i.e. a destrucvtive function). Here's the code with
> some debugging output statements:
> (defun nsort (lst fn)
> (progn
> (format t "lst is set to: ~A~%" lst) ;; print lst before the sort
>
> (setf lst (sort lst fn)) ;; sort it
> (format t "lst is set to: ~A~%" lst) ;; print lst after the sort
>
> lst)) ;;
> and return it
>
> The function returns what I expect except the list I passed in does not
> contain what I expect it to upon the function's return - Here's an
> example:
>
> CL-USER(17): (setf x '(5 4 3 2 1))
> CL-USER(18): (nsort x #'<)
> lst is set to: (5 4 3 2 1)
> lst is set to: (1 2 3 4 5)
> (1 2 3 4 5)
> CL-USER(19): x
> (5)
>
> As you can see (5) is NOT the value I expected x to hold. Any insight
> would be greatly appreciated!
CL passes arguments by value, so using a destructive function with
argument x doesn't change the value used to pass the argument (i.e. x,
which is a pointer to the start of the list. otoh, it changes the
structure of the data accessed through the argument in whatever way
the function thinks is best. so after return anything that pointed
into the data structure wll still pint to something which basically is
undefined (as an exercise try to figure out from the result how your
sort was working). you will have to access the resulting structure
through the function value: replace
CL-USER(18): (nsort x #'<)
by
CL-USER(18): (setf x(nsort x #'<))
and you will get the expected result
hs
--
Lbh unir whfg ivbyngrq gur Qvtvgny Zvyraavhz Pbclevtug Npg ol oernxvat
gur cebgrpgvba bs pbclevtugrq zngrevny. Vs lbh ner abg n pvgvmra be
erfvqrag bs gur HFN, lbh evfx orvat vzcevfbarq naq uryq jvgubhg onvy
sbe hc gb gjb jrrxf hcba ragel gb gur HFN
(c) Copyright 2001 by Hartmann Schaffer (signature only)