RE: stream operations unnecessarily hold on to the original stream

Jacob Jozef Sat, 11 Feb 2023 12:51:19 -0800

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,

Including greeting to Philip Bewig with whom I have had very pleasant discussions in the past.

From: Arthur A. Gleckler
Sent: 08 February 2023 20:03
To: Sorawee Porncharoenwase; Phil Bewig
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)

RE: stream operations unnecessarily hold on to the original stream

Reply via email to