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

[David Kastrup <dak@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