[debbugs-tracker] bug#17485: closed ((srfi srfi-1) reduce-right does not scale, version 2.0.9)

[GNU bug Tracking System]

Your message dated Tue, 12 Jul 2016 09:07:58 +0200
with message-id <address@hidden>
and subject line Re: bug#17485: (srfi srfi-1) reduce-right does not scale, 
version 2.0.9
has caused the debbugs.gnu.org bug report #17485,
regarding (srfi srfi-1) reduce-right does not scale, version 2.0.9
to be marked as done.

(If you believe you have received this mail in error, please contact
address@hidden)


-- 
17485: http://debbugs.gnu.org/cgi/bugreport.cgi?bug=17485
GNU Bug Tracking System
Contact address@hidden with problems
> --- Begin Message ---
>
>
>
> Subject: 
>
> (srfi srfi-1) reduce-right does not scale, version 2.0.9
>
>
>
>
> Date: 
>
> Tue, 13 May 2014 12:47:32 +0200
>
>
>
>
> The following code results in an error:
>
> (use-modules (srfi srfi-1))
> (reduce-right + 0 (make-list 10000 1))
>
> Backtrace:
> In srfi/srfi-1.scm:
>  379: 19 [recur (1 1 1 1 1 1 1 1 1 ...) (1 1 1 1 1 1 1 1 1 ...)]
>  379: 18 [recur (1 1 1 1 1 1 1 1 1 ...) (1 1 1 1 1 1 1 1 1 ...)]
>  379: 17 [recur (1 1 1 1 1 1 1 1 1 ...) (1 1 1 1 1 1 1 1 1 ...)]
>  379: 16 [recur (1 1 1 1 1 1 1 1 1 ...) (1 1 1 1 1 1 1 1 1 ...)]
>  379: 15 [recur (1 1 1 1 1 1 1 1 1 ...) (1 1 1 1 1 1 1 1 1 ...)]
>  379: 14 [recur (1 1 1 1 1 1 1 1 1 ...) (1 1 1 1 1 1 1 1 1 ...)]
>  379: 13 [recur (1 1 1 1 1 1 1 1 1 ...) (1 1 1 1 1 1 1 1 1 ...)]
>  379: 12 [recur (1 1 1 1 1 1 1 1 1 ...) (1 1 1 1 1 1 1 1 1 ...)]
>  379: 11 [recur (1 1 1 1 1 1 1 1 1 ...) (1 1 1 1 1 1 1 1 1 ...)]
>  379: 10 [recur (1 1 1 1 1 1 1 1 1 ...) (1 1 1 1 1 1 1 1 1 ...)]
>  379: 9 [recur (1 1 1 1 1 1 1 1 1 ...) (1 1 1 1 1 1 1 1 1 ...)]
>  379: 8 [recur (1 1 1 1 1 1 1 1 1 ...) (1 1 1 1 1 1 1 1 1 ...)]
>  379: 7 [recur (1 1 1 1 1 1 1 1 1 ...) (1 1 1 1 1 1 1 1 1 ...)]
>  379: 6 [recur (1 1 1 1 1 1 1 1 1 ...) (1 1 1 1 1 1 1 1 1 ...)]
>  379: 5 [recur (1 1 1 1 1 1 1 1 1 ...) (1 1 1 1 1 1 1 1 1 ...)]
>  379: 4 [recur (1 1 1 1 1 1 1 1 1 ...) (1 1 1 1 1 1 1 1 1 ...)]
>  379: 3 [recur (1 1 1 1 1 1 1 1 1 ...) (1 1 1 1 1 1 1 1 1 ...)]
>  379: 2 [recur (1 1 1 1 1 1 1 1 1 ...) (1 1 1 1 1 1 1 1 1 ...)]
>  379: 1 [recur (1 1 1 1 1 1 1 1 1 ...) (1 1 1 1 1 1 1 1 1 ...)]
>  379: 0 [recur (1 1 1 1 1 1 1 1 1 ...) (1 1 1 1 1 1 1 1 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" ())'.
>
> This is for Guile version 2.0.9 as distributed by Ubuntu 14.04.
>
> Somewhat surprisingly, fold-right does not suffer from the same error.
>
> Surprisingly because the definition of reduce-right is
>
> (define (reduce-right f ridentity lst)
>   "`reduce-right' is a variant of `fold-right', where the first call to
> F is on two elements from LST, rather than one element and a given
> initial value.  If LST is empty, RIDENTITY is returned.  If LST
> has just one element then that's the return value."
>   (check-arg procedure? f reduce)
>   (if (null? lst)
>       ridentity
>       (fold-right f (last lst) (drop-right lst 1))))
>
> 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)))
>         '())))
>
> 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.
>
> -- 
> David Kastrup
>
>
>
> --- End Message ---
> --- Begin Message ---
>
>
>
> Subject: 
>
> Re: bug#17485: (srfi srfi-1) reduce-right does not scale, version 2.0.9
>
>
>
>
> Date: 
>
> Tue, 12 Jul 2016 09:07:58 +0200
>
>
>
>
> User-agent: 
>
> Gnus/5.13 (Gnus v5.13) Emacs/24.5 (gnu/linux)
>
>
>
>
> On Tue 21 Jun 2016 17:31, David Kastrup <address@hidden> writes:
>
> > Andy Wingo <address@hidden> writes:
> >
> >> I think on 2.0 that this might be an OK workaround:
> >>
> >>  (define (reduce-right f ridentity lst)
> >>    (reduce f ridentity (reverse lst)))
> >
> > So if we don't store the inverse list in-space, it needs to be either a
> > copy in heap (reverse) or stack (recursion).  Stack allocation is likely
> > cheaper in execution time (though the total memory cost depends on the
> > stack frame size taken per call).  The limited stack size on 2.0 does
> > not seem like a good fit, however.  Which makes your workaround seem
> > like the best option.
>
> Applied this fix to stable-2.0.  Thanks for the report.
>
> Andy
>
>
> --- End Message ---