[racket] streams, recursion and running out of memory

Hi Matthew,

Thanks for your help.  I really can't even pretend to understand the
make-coroutine code but this is what I'm seeing:

Original make-coroutine, without stream-ref pre-call => out of memory (1GB)
when running (prime-pi 500000)
Original make-coroutine, with stream-ref pre-call => runs (prime-pi 500000)
in about .4 sec
Alternate make-coroutine, with or without stream-ref pre-call => runs
(prime-pi 500000) in about 28 sec

All runs from "clean" state.

-joe

On Tue, Feb 21, 2012 at 10:25 AM, Matthew Flatt <mflatt at cs.utah.edu> wrote:

> 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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20120221/016695ae/attachment.html>