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

[David Kastrup <dak@gnu.org>]

Andy Wingo <wingo@pobox.com> writes:

> Hi,
>
> On Tue 13 May 2014 12:47, David Kastrup <dak@gnu.org> writes:
>
>> 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" ())'.
>
> On the 2.2 series this problem does not occur because there is no stack
> limit.  Mark if you would like to fix this on 2.0 in a different way, go
> ahead.  Otherwise we can close.
>
> I think on 2.0 that this might be an OK workaround:
>
>  (define (reduce-right f ridentity lst)
>    (reduce f ridentity (reverse lst)))
>
> Thoughts?

Traversing lst in reverse without additional O(n) storage would require
working on (reverse! lst), fixing up the list afterwards.  Using
reverse!  also has the advantage that the list? predicate check does not
require the turtle/hare traversal.

The downside, of course, is that for something like reduce-right,
temporary reversal of lst would be an unexpected side effect not working
well with multithreading or read-only memory.

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.

I don't like that then both reduce and reverse check for listness.  But
that's a different topic.

-- 
David Kastrup