Andy Wingo <wi...@pobox.com> writes: > Hi, > > On Tue 13 May 2014 12:47, David Kastrup <d...@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