Bug in SRFI-95 sample implementation of sorted?
Sudarshan S Chawathe
(07 Mar 2020 21:23 UTC)
|
Re: Bug in SRFI-95 sample implementation of sorted?
Arthur A. Gleckler
(07 Mar 2020 21:29 UTC)
|
Re: Bug in SRFI-95 sample implementation of sorted? Aubrey Jaffer (08 Mar 2020 00:17 UTC)
|
Re: Bug in SRFI-95 sample implementation of sorted?
Arthur A. Gleckler
(08 Mar 2020 00:29 UTC)
|
Re: Bug in SRFI-95 sample implementation of sorted?
John Cowan
(07 Mar 2020 22:30 UTC)
|
Re: Bug in SRFI-95 sample implementation of sorted? Aubrey Jaffer 08 Mar 2020 00:17 UTC
"Arthur A. Gleckler" <xxxxxx@speechcode.com> writes: | [1:text/plain Hide] > | Thank you very much for the bug report. I've added Aubrey Jaffer, author | of SRFI 95, to the conversation. > | Aubrey, would you mind taking a look at this bug report and fix? Yes, it is a bug. The proposed fix includes: (less? last nxt last); but less? is only required to accept two arguments. Here is the fix I am applying to SLIB: --- sort.scm.~1.16.~ 2011-12-23 00:24:37.000000000 -0500 +++ sort.scm 2020-03-07 19:13:48.994605516 -0500 @@ -33,7 +33,7 @@ (last (key (array-ref seq dimax)))) (or (negative? idx) (let ((nxt (key (array-ref seq idx)))) - (and (less? nxt last) + (and (not (less? last nxt)) (loop (+ -1 idx) nxt)))))))) ((null? (cdr seq)) #t) (else | Sudarshan, I'll wait up to a week for Aubrey to reply. If he doesn't, I'll | contact you again so that we can review and apply the fix. > | Thanks to you both. > | On Sat, Mar 7, 2020 at 1:23 PM Sudarshan S Chawathe <xxxxxx@eip10.org> wrote: > >> There seems to be a bug in the SRFI-95 sample implementation of the >> sorted? procedure when given a vector argument with duplicates. >> >> The sample run below illustrates the problem and suggests a simple fix >> as well. (The sorted? procedure definition is verbatim from the >> sample implementation.) >> >> I apologize for the hackish definitions of some of the dependencies, >> but I don't think they change the behavior in the illustrated case. (I >> had some dependency trouble getting the official SLIB installed on my >> machine.) >> >> I believe this bug also exists in the current SLIB (slib-3b6). >> >> $ cat w.scm >> (import (scheme base) >> (scheme write)) >> >> (define array? vector?) >> >> (define array-ref vector-ref) >> >> (define (array-dimensions arr) >> (list (vector-length arr))) >> >> (define identity values) >> >> (define (sorted? seq less? . opt-key) >> (define key (if (null? opt-key) identity (car opt-key))) >> (cond ((null? seq) #t) >> ((array? seq) >> (let ((dimax (+ -1 (car (array-dimensions seq))))) >> (or (<= dimax 1) >> (let loop ((idx (+ -1 dimax)) >> (last (key (array-ref seq dimax)))) >> (or (negative? idx) >> (let ((nxt (key (array-ref seq idx)))) >> (and (less? nxt last) >> (loop (+ -1 idx) nxt)))))))) >> ((null? (cdr seq)) #t) >> (else >> (let loop ((last (key (car seq))) >> (next (cdr seq))) >> (or (null? next) >> (let ((nxt (key (car next)))) >> (and (not (less? nxt last)) >> (loop nxt (cdr next))))))))) >> >> (write (sorted? '(1 2 2 3) <)) >> (newline) >> (write (sorted? #(1 2 2 3) <)) >> (newline) >> $ chibi-scheme w.scm >> #t >> #f >> $ diff -u w.scm w2.scm >> --- w.scm 2020-03-07 16:02:00.395402293 -0500 >> +++ w2.scm 2020-03-07 16:02:00.395402293 -0500 >> @@ -20,7 +20,7 @@ >> (last (key (array-ref seq dimax)))) >> (or (negative? idx) >> (let ((nxt (key (array-ref seq idx)))) >> - (and (less? nxt last) >> + (and (not (less? last nxt last)) >> (loop (+ -1 idx) nxt)))))))) >> ((null? (cdr seq)) #t) >> (else >> $ chibi-scheme w2.scm >> #t >> #t >> $ >> >> Regards, >> >> -chaw >> >