Hi Jos,
While it’s true that I used Racket, the above report is observed from a
faithful implementation of the SRFI. I didn’t use racket/stream, but rather
ran the reference implementation of the SRFI. I also tried it in Guile and
it has the same problem.
scheme@(guile-user)> (use-modules (srfi srfi-41))
scheme@(guile-user)> (define (times3 n)
(define st
(stream-filter
(lambda (x)
(zero? (modulo x n)))
(stream-from 0)))
(stream-ref st 3)
(stream-ref st 3))
scheme@(guile-user)> (times3 100000000) ;; observe the memory increase
in task manager / htop / whatnot
You are welcome to try it in other implementations too. The problem I
identified above should be universal.
Best,
Sorawee (Oak)
On Sat, Feb 11, 2023 at 12:50 PM Jacob Jozef <[email protected]> wrote:
> May be Philip Bewig has seen the discussion, but I won’t blame him if he
> does not want to take part in it. I think SRFI41 has been maltreated in
> Racket. Unifying streams with lists is a bad idea, I think. A stream is not
> a list an a list is not a stream. Like a vector is not a list and
> reversely. If we want syntax for to accept streams as lists and reversely,
> ok, but please maintain the original ideas about streams as described by
> Philip Bewig in his SRFI41.
>
>
>
> Jos,
>
>
>
> PS
>
> Including greeting to Philip Bewig with whom I have had very pleasant
> discussions in the past.
>
>
>
>
>
>
>
> *From: *Arthur A. Gleckler <[email protected]>
> *Sent: *08 February 2023 20:03
> *To: *Sorawee Porncharoenwase <[email protected]>; Phil Bewig
> <[email protected]>
> *Cc: *[email protected]
> *Subject: *Re: stream operations unnecessarily hold on to the original
> stream
>
>
>
> Thanks, Sorawee, for the feedback. I'm CC-ing Philip Bewig, the author of
> the SRFI, who is still on the mailing list but might not have seen this yet.
>
>
>
> Philip, what do you think?
>
>
>
>
>
> On Tue, Feb 7, 2023 at 7:56 AM Sorawee Porncharoenwase <
> [email protected]> wrote:
>
> Hi everyone,
>
>
>
> I'm new to the SRFI discussion, so my apologies if I do anything wrong.
>
>
>
> SRFI-41 discusses the times3 example, noting that it should take constant
> space.
>
>
>
> But the following modified times3 example uses linear space:
>
>
>
> (define (times3 n)
> (define st
> (stream-filter
> (lambda (x)
> (zero? (modulo x n)))
> (stream-from 0)))
> (stream-ref st 3)
> (stream-ref st 3))
>
>
>
> The issue, as I understand it, is that `stream-filter` holds on to the
> original stream, particularly in stream-cons:
>
>
>
> (define (stream-filter pred? strm)
> (define stream-filter
> (stream-lambda (strm)
> (cond ((stream-null? strm) stream-null)
> ((pred? (stream-car strm))
> (stream-cons (stream-car strm) (stream-filter (stream-cdr
> strm))))
> (else (stream-filter (stream-cdr strm))))))
> (cond ((not (procedure? pred?)) (error 'stream-filter "non-procedural
> argument"))
> ((not (stream? strm)) (error 'stream-filter "non-stream
> argument"))
>
> (else (stream-filter strm))))
>
>
>
> If I'm not mistaken, one way to fix the issue is to do stream-car outside
> stream-cons. This happens to be fine because stream-filter already needs to
> determine the value of (pred? (stream-car strm)) before, so calling
> (stream-car strm) again is fine. I call this new implementation
> stream-filter*:
>
>
>
> (define (stream-filter* pred? strm)
> (define stream-filter
> (stream-lambda (strm)
> (cond ((stream-null? strm) stream-null)
> ((pred? (stream-car strm))
> (let ((v (stream-car strm)))
> (stream-cons v (stream-filter (stream-cdr strm)))))
> (else (stream-filter (stream-cdr strm))))))
> (cond ((not (procedure? pred?)) (error 'stream-filter "non-procedural
> argument"))
> ((not (stream? strm)) (error 'stream-filter "non-stream
> argument"))
> (else (stream-filter strm))))
>
>
>
> But the same pitfall applies to other operations, like stream-map, too.
> Unlike stream-filter, there is no reason to force the car of a stream
> early. That is to say, I don't expect anything to be displayed in the
> following program:
>
>
>
> (define st (stream-cons (begin (display "a") 1) stream-null))
> (define st* (stream-map (lambda (x) (+ x 1)) st))
> (stream-cdr st*)
>
>
>
> which is unfortunate, because it means the strategy for stream-filter
> can't be applied to stream-map.
>
>
>
> One possibility to really fix this issue is to provide stream-force and a
> new operation stream-car*, which is just like stream-car, but does not
> stream-force the resulting value.
>
>
>
> (define (stream-car* strm)
> (cond ((not (stream? strm)) (error 'stream-car* "non-stream"))
> ((stream-null? strm) (error 'stream-car* "null stream"))
> (else (stream-kar (stream-force strm)))))
>
>
>
> Then the new implementation, which I call stream-map*, can be implemented
> as follows:
>
>
>
> (define (stream-map* proc . strms)
> (define stream-map
> (stream-lambda (strms)
> (if (exists stream-null? strms)
> stream-null
> (let ((cars (map stream-car* strms)))
> (stream-cons (apply proc (map stream-force cars))
> (stream-map (map stream-cdr strms)))))))
> (cond ((not (procedure? proc)) (error 'stream-map "non-procedural
> argument"))
> ((null? strms) (error 'stream-map "no stream arguments"))
> ((exists (lambda (x) (not (stream? x))) strms)
> (error 'stream-map "non-stream argument"))
> (else (stream-map strms))))
>
>
>
> Does this sound right?
>
>
>
> Best,
>
> Sorawee (Oak)
>
>
>
