Subject: bug#17485: closed (Re: bug#17485: (srfi srfi-1) reduce-right does not scale, version 2.0.9)

From: [email-masked] (GNU bug Tracking System)
Date: Tue, 12 Jul 2016 07:09:02 +0000

Your bug report

#17485: (srfi srfi-1) reduce-right does not scale, version 2.0.9

which was filed against the guile package, has been closed.

The explanation is attached below, along with your original report.
If you require more details, please reply to [email-masked].

-- 
17485: http://debbugs.gnu.org/cgi/bugreport.cgi?bug=17485
GNU Bug Tracking System
Contact [email-masked] with problems

Subject: Re: bug#17485: (srfi srfi-1) reduce-right does not scale, version 2.0.9
From: Andy Wingo <[email-masked]>
To: David Kastrup <[email-masked]>
Cc: [email-masked]
Date: Tue, 12 Jul 2016 09:07:58 +0200
List-Id: <debbugs-submit.debbugs.gnu.org>

On Tue 21 Jun 2016 17:31, David Kastrup <[email-masked]> writes:

> Andy Wingo <[email-masked]> 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

Subject: (srfi srfi-1) reduce-right does not scale, version 2.0.9
From: David Kastrup <[email-masked]>
To: [email-masked]
Date: Tue, 13 May 2014 12:47:32 +0200
List-Id: <debbugs-submit.debbugs.gnu.org>

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