# [racket] streams, recursion and running out of memory

 From: Matthew Flatt (mflatt at cs.utah.edu) Date: Tue Feb 21 13:25:33 EST 2012 Previous message: [racket] streams, recursion and running out of memory Next message: [racket] streams, recursion and running out of memory Messages sorted by: [date] [thread] [subject] [author]

```I don't know the answer, but here's a piece of the puzzle that might be
relevant.

Try this alternate `make-coroutine':

(define (make-coroutine fn)
(let ([cont #f])
(λ ()
(call-with-continuation-prompt
(lambda ()
(if cont
(cont)
(fn (λ () (let/cc k
(set! cont k)
(abort-current-continuation
(default-continuation-prompt-tag)
void))))))))))

The difference between this one and the one on the web page is that it
uses a prompt to avoid capturing the continuation of the initial call
to a coroutine (i.e., it uses a delimited continuation for the
coroutine). For me, this variant makes `(prime-pi 500000)' work without
``(stream-ref prime-stream (inexact->exact (* 0.1 n)))'.

My guess is that avoiding capture of continuations converts O(N^2)
space usage into O(N) space for some N-deep forcing of streams. Using
`(stream-ref prime-stream (inexact->exact (* 0.1 n)))', meanwhile,
might similarly avoid an N-deep nesting at the point where O(N^2)
behavior would kick in.

I haven't studied the code enough to be certain that my explanation is
right, but when I see surprising space consumption with laziness and
undelimited continuations, my first guess is that undelimited
continuations are holding onto too much.

At Mon, 20 Feb 2012 17:19:02 -0800, Joe Gilray wrote:
> Hi,
>
> I created an infinite stream of primes (using this interesting article:
> http://matthias.benkard.de/journal/116)
>
> I tried to create a prime-pi function:
>
>   (define (prime-pi n)
>     (let loop-count ([candidate-stream prime-stream])
>       (if (> (stream-first candidate-stream) n)
>           0
>           (+ (loop-count (stream-rest candidate-stream)) 1))))
>
> (prime-pi 500000) grinds and runs out of memory
>
> But this little cludge makes it run just fine:
>
>   (define (prime-pi n)
>     (stream-ref prime-stream (inexact->exact (* 0.1 n)))  ; cludge added to
> get the stream to pre-create enough primes
>     (let loop-count ([candidate-stream prime-stream])
>       (if (> (stream-first candidate-stream) n)
>           0
>           (+ (loop-count (stream-rest candidate-stream)) 1))))
>
> What am I not understanding?
>
> Thanks,
> -Joe
> ____________________
>   Racket Users list:
>   http://lists.racket-lang.org/users

```

 Posted on the users mailing list. Previous message: [racket] streams, recursion and running out of memory Next message: [racket] streams, recursion and running out of memory Messages sorted by: [date] [thread] [subject] [author]