Another java.lang.StackOverflowError

[Wen-Chun Ni <wcn at tbcommerce dot com>]

I was trying to generalize foldl to something accepting a sequence.
The original looks like

(define (foldl op init lst)
  (let loop ((init init)
             (lst lst))
    (if (null? lst)
        init
        (loop (op init (car lst)) (cdr lst)))))

while the new one looks like

(define (foldl-seq op init-proc seq-producer)
  (let loop ((initial init-proc))
    (let ((data (seq-producer)))
      (if (null? data)
          (initial)
          (loop (lambda () (op (initial) data)))))) )

or directly use `do':

(define (foldl-seq op init-proc seq-producer)
  (do ((data (seq-producer) (seq-producer))
       (initial init-proc (lambda () (op (initial) data))))
      ((null? data) (initial))))



Suppose we use a trivial function (mk-list n) to produce a list
of length n, then the first one works in

 (foldl + 0 (mk-list n))

for n less than or equal to 2000000. Beyond that, it gives OutOfMemoryError.

However, 

 (foldl-seq + (lambda () 0) (mk-list-seq n))

throws StackOverflowError before n <= 100000.

In general, I can't write iterative code without hitting this kind of
problem, unless I use full-tailcalls (which might be too slow).
Is there any way I can comfortably deal with this kind of problems?

Thanks a lot!


Wen-Chun Ni


APPENDIX: rest of my testing code

(define (mk-list n)
  (let loop ((result '())
             (cnt 0))
    (if (>= cnt n)
        result ;; no reverse for testing
        (loop (cons cnt result) (+ cnt 1)))))

(define (mk-list-seq n)
  (let ((cnt 0))
    (lambda ()
      (if (>= cnt n)
          '()
          (let ((m cnt))
            (set! cnt (+ 1 cnt))
            m)))))