yee@cgl.ucsf.edu (dave yee) (06/11/88)
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: yee@cgl.ucsf.edu "Language is a UUCP: ucbvax!ucsfcgl!yee Virus from Bitnet: yee@ucsfcgl.BITNET Outer Space"
hoey@ai.etl.army.mil (Dan Hoey) (06/11/88)
In article <10988@cgl.ucsf.EDU> yee@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
tlh@cs.purdue.EDU (Tom "Hey Man" Hausmann) (06/11/88)
In article <10988@cgl.ucsf.EDU>, yee@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 tlh@medusa.cs.purdue.edu | My ideas? There has never been an original ...!purdue!tlh | thought since Plato.
shiffman%basselope@Sun.COM (Hank Shiffman) (06/11/88)
In article <10988@cgl.ucsf.EDU> yee@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 shiffman@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