Hello

While playing with streams, I think I've noticed that the stream "head" is not garbage collected while traversing the stream even if it is not referenced by user data structures anymore.

There also seems to be a (independent?) problem releasing memory when streams are long (thus recursion is deep). I'm getting out of memory errors when "there shouldn't be", and need to run (##gc) manually to be able to continue calculations (entering ,c in the debugger resumes calculation correctly): it looks like gambit is starting to fill up all available memory if the recursion depth is bigger than something between 20000 and 35000.

The two issues happen in both interpreted and compiled code.

$ ulimit -S -v 300000 $ gsc

; (compile-file "test.scm") (load "test") (test 35000)

repeat the test call several times, it will give *** ERROR IN ##bignum.make -- Heap overflow after about 10 invocations. Same thing with

(test-2 35000)

This can be repeated "forever" without hitting out of memory errors:

(test 20000)

or this

(test-2 20000)

(There are two implementations of stream-take below (one commented out), choosing the other one doesn't change the situation.)

This is with Gambit Version 4.0 beta 14 on Debian ppc. With beta 15 on Debian x86, the out of memory situation already happens with a test argument of 25000.

What I'm especially wondering is this: the output list from take only needs about 600000 bytes. So if the stream would be deallocated while stream-take is still walking it, much longer streams should be possible (at least 10 times longer). Do you have an explanation or a solution?

Thanks Christian.

;; test.scm

(declare (block) (standard-bindings) (extended-bindings) )

;; stream library

(define *stream-strict* #f) (set! *stream-strict* #t)

(define @force ##force) (define @promise? ##promise?) (define @car ##car) (define @cdr ##cdr) (define @pair? ##pair?) (define @null? ##null?)

(define (stream-force strm) (if (@promise? strm) (@force strm) (if *stream-strict* (error "not a stream: expected promise, got:" strm) strm)))

(define stream-car (lambda (strm) (let ((p (stream-force strm))) (if (@pair? p) (@car p) (error "stream-car: not a pair:" p))))) (define stream-cdr (lambda (strm) (let ((p (stream-force strm))) (if (@pair? p) (@cdr p) (error "stream-cdr: not a pair:" p)))))

(define (null-stream? strm) (let ((l (stream-force strm))) (cond ((##pair? l) #f) ((##null? l) #t) (else (error "null-stream?: argument out of domain:" l)))))

; (define (stream-take strm k) ;; returns a list, not a stream. ; (if (and (##fixnum? k) (##fixnum.>= k 0)) ; (if (##fixnum.= k 0) ; '() ; (or (and (not (null-stream? strm)) ; (let ((res (cons (stream-car strm) '()))) ; (let iter ((res-tail res) ; (strm (stream-cdr strm)) ; (k (##fixnum.- k 1))) ; (if (##fixnum.zero? k) res ; (let ((p (stream-force strm))) ; (and (##pair? p) ; (let ((res-next (##cons (##car p) '()))) ; (##set-cdr! res-tail res-next) ; (iter res-next ; (##cdr p) ; (##fixnum.- k 1))))))))) ; (error "stream-take: stream too short"))) ; (error "stream-take: k is not a positive fixnum:" k)))

(define (stream-take strm k) ;; returns a list, not a stream. (if (and (##fixnum? k) (##fixnum.>= k 0)) (let recur ((strm strm) (k k)) (if (##fixnum.zero? k) '() (let ((p (stream-force strm))) (if (##pair? p) (##cons (##car p) (recur (##cdr p) (##fixnum.- k 1))) (error "stream-take: stream too short"))))) (error "stream-take: k is not a positive fixnum:" k)))

(define-macro (scons a r) `(delay (cons ,a ,r)))

;; the actual program

(define (fib-stream) (letrec ((strm (scons 0 (scons 1 (let recur ((2behind (let ((s strm)) ;(set! strm #f); make gc possible? no, doesn't help. s))) (delay (let ((a (stream-car 2behind)) (r (stream-cdr 2behind)) ) (cons (+ a (stream-car r)) (recur r))))))))) strm))

(define (fib-stream-2) ;; (misses the first two values of the fib series) (let recur ((pprev 0) (prev 1)) (delay (let ((cur (+ prev pprev))) (cons cur (recur prev cur))))))

(define t #f)

(define (test n) (time (set! t (stream-take (fib-stream) n))))

(define (test-2 n) (time (set! t (stream-take (fib-stream-2) n))))

;;end