GNU bug report logs - #17485
(srfi srfi-1) reduce-right does not scale, version 2.0.9

Previous Next

Full log

Message #8 received at 17485 <at> debbugs.gnu.org (full text, mbox):

From: Mark H Weaver <mhw <at> netris.org>
To: David Kastrup <dak <at> gnu.org>
Cc: 17485 <at> debbugs.gnu.org
Subject: Re: bug#17485: (srfi srfi-1) reduce-right does not scale,
 version 2.0.9
Date: Sun, 01 Jun 2014 19:41:41 -0400

David Kastrup <dak <at> gnu.org> writes:

> The following code results in an error:
>
> (use-modules (srfi srfi-1))
> (reduce-right + 0 (make-list 10000 1))

[...]

> srfi/srfi-1.scm:379:31: In procedure recur:
> srfi/srfi-1.scm:379:31: Throw to key `vm-error' with args `(vm-run "VM: Stack overflow" ())'.

Yes, this should be fixed.

> It turns out that the call of drop-right is responsible here:
>
> (define (drop-right lis k)
>   (let recur ((lag lis) (lead (drop lis k)))
>     (if (pair? lead)
>         (cons (car lag) (recur (cdr lag) (cdr lead)))
>         '())))

Thanks for tracking this down.

> For all the cleverness involved here, one has to run through the whole
> list anyway.  It makes no real sense to do this in this manner.  The
> motivation may be to have a warm cache when k is small, but the result
> is self-defeating because of VM stack buildup.
>
> (define (drop-right lis k)
>     (drop lis (- (length lis) k)))
>
> should be all that is needed.

That won't be sufficient.  SRFI-1 specifies that 'drop-right' works for
dotted lists, i.e. finite non-nil-terminated lists, whereas 'length'
accepts only proper lists.

It includes these examples:

  (drop-right '(1 2 3 . d) 2) => (1)
  (drop-right '(1 2 3 . d) 0) => (1 2 3)

See <http://srfi.schemers.org/srfi-1/srfi-1.html>.

Would you like to propose another fix?

    Thanks,
      Mark

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.