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
>>
>