From: dave yee
Subject: Kyoto Common LISP bug (SORT function)
Date:
Message-ID: <10988@cgl.ucsf.EDU>
I think i've found a bug in KCL (Kyoto Common LISP). I'd like to know if
(1) anyone has also seen/experienced this bug and
(2) if there is a fix. Should a fix exist, could you direct me to it?
We are running KCL on a SUN 3/280
The problem is with sort and stable-sort. Suppose
i have a structure of the following form:
(defstruct box
(item-code nil)
)
now, given a list of boxes, i would like to sort them by item-code number.
for example,
(setq sorted-boxes (sort unsorted-boxes #'< :key'box-item-code))
well, the function returns the correct value, BUT the original
list is not sorted, furthermore *elements of the list are missing*!!!
Now, i'm still a beginner, but if this is a feature of KCL i would
appreciate an explanation as to why. Oh, and i should add that i've
tested this using SUN Common LISP and the problem does *not* exist.
Any suggestions?
--
-dave:
ARPA: ···@cgl.ucsf.edu "Language is a
UUCP: ucbvax!ucsfcgl!yee Virus from
Bitnet: ···@ucsfcgl.BITNET Outer Space"
From: Dan Hoey
Subject: Re: Kyoto Common LISP bug (SORT function)
Date:
Message-ID: <116@ai.etl.army.mil>
In article <·····@cgl.ucsf.EDU> ···@cgl.ucsf.edu (dave yee) writes:
>I think i've found a bug in KCL (Kyoto Common LISP).
It's not a bug.
>Suppose i have a structure...
The presence of a structure is irrelevant.
> (setq sorted-boxes (sort unsorted-boxes #'< :key'box-item-code))
>well, the function returns the correct value, BUT the original
>list is not sorted, furthermore *elements of the list are missing*!!!
The definition of sort doesn't claim to sort the original list.
It might leave it sorted, but you can't count on it.
>Now, i'm still a beginner, but if this is a feature of KCL i would
>appreciate an explanation as to why.
During the course of any reasonably efficient sorting algorithm, we might
expect the sorted list to be formed, while the original list would not be
the sorted list. Typically it would be a tail of the sorted list. Since
it would take extra work to make the original list be the sorted list, KCL
does not waste time doing so.
> Oh, and i should add that i've
>tested this using SUN Common LISP and the problem does *not* exist.
Well, you haven't tested it with all possible lists. Many sorting algorithms
only exhibit the behavior on large lists.
>Any suggestions?
(when (setq sorted-boxes (sort (copy-list unsorted-boxes) #'<
:key 'box-item-code))
(setf (car unsorted-boxes) (car sorted-boxes)
(cdr unsorted-boxes) (cdr sorted-boxes)))
Dan
From: Tom "Hey Man" Hausmann
Subject: Re: Kyoto Common LISP bug (SORT function)
Date:
Message-ID: <4322@medusa.cs.purdue.edu>
In article <·····@cgl.ucsf.EDU>, ···@cgl.ucsf.edu (dave yee) writes:
> I think i've found a bug in KCL (Kyoto Common LISP). I'd like to know if
> (1) anyone has also seen/experienced this bug and
> (2) if there is a fix. Should a fix exist, could you direct me to it?
> We are running KCL on a SUN 3/280
> The problem is with sort and stable-sort. Suppose
> i have a structure of the following form:
> (defstruct box
> (item-code nil))
> now, given a list of boxes, i would like to sort them by item-code number.
> for example,
> (setq sorted-boxes (sort unsorted-boxes #'< :key'box-item-code))
> well, the function returns the correct value, BUT the original
> list is not sorted, furthermore *elements of the list are missing*!!!
> Now, i'm still a beginner, but if this is a feature of KCL i would
> appreciate an explanation as to why. Oh, and i should add that i've
> tested this using SUN Common LISP and the problem does *not* exist.
> Any suggestions?
> -dave:
In CLtL sort is *destructively* sorts a lists and retruns the sorted
list. Thus your problem is not a bug in KCL.
I have also experienced this when I ported someone else's code from
the Symbolics to KCL environment. The person assumed sort on the
Lispm would not destroy the list.
-Tom
-------------------------------------------------------------------------------
Tom Hausmann Dept. of Computer Sciences Purdue University
···@medusa.cs.purdue.edu | My ideas? There has never been an original
...!purdue!tlh | thought since Plato.
In article <·····@cgl.ucsf.EDU> ···@cgl.ucsf.edu (dave yee) writes:
>The problem is with sort and stable-sort. Suppose
>i have a structure of the following form:
>
>now, given a list of boxes, i would like to sort them by item-code number.
>for example,
>
> (setq sorted-boxes (sort unsorted-boxes #'< :key'box-item-code))
Sort and stable-sort are destructive of the original list. That's
mentioned in the first line of the description in Steele. Try
invoking sort on (copy-list unsorted-boxes) instead of unsorted-boxes.
----
Hank Shiffman (415) 336-4658
AI Product Marketing
Technical Specialist ········@Sun.COM
Sun Microsystems, Inc. ...!sun!shiffman
"Hanging its lawyers might not correct all of this country's woes but
it would be lots of fun and could do no harm to anyone."
- Robert Anson Heinlein quoting Samuel Langhorn Clemens