[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