[racket] streams, recursion and running out of memory
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