Re: Stream-filter and space leaks

[Matthias Neubauer <neubauer@xxxxxxxxxxxxxxxxxxxxxxxxxx>]

Richard Kelsey <kelsey@xxxxxxx> writes:

>    From: sperber@xxxxxxxxxxxxxxxxxxxxxxxxxxx (Michael Sperber [Mr.  Preprocessor])
>    Date: Fri, 21 Feb 2003 11:04:03 +0100
> 
>    The code you posted seems to be essentially the definition of
>    DELAY/FORCE from Scheme 48.  However, Phil's old code does leak in
>    Scheme 48 and doesn't leak with the proposed fix.
> 
> Right.  I was mistaken about the source of the leak.  This time around
> I have actually tested the code.

I tested it, too. And I am totally confused now, because I still see
the space leak even *with* the proposed fix?!

I, for my part, downloaded the current reference implementation as
found on http://srfi.schemers.org/srfi-40/srfi-40.txt. The only thing
that I then changed was that I replaced the former version of
STREAM-FILTER by the one Phil posted last Thursday. When I load this
into my scsh (0.6.3) and evaluate

(stream-car (stream-filter (lambda (x) (zero? x)) (stream-from 1)))

the whole thing dies pretty soon ejecting a post-gc interrupt---i.e,
scsh seems to run out of memory.

Enlightened by Richard's last post I afterwards tried another setup: I
used the above implementation (i.e. the one with the _new_
implementation of STREAM-FILTER) but also replaced DELAY and FORCE by
Richard's non-reentrant versions. Unfortunately I *still* see the
space leak!

So I suspect that either I use a bogus version of scsh, or I use
completely different srfi implementation than you guys, or I am unable
to operate scsh, or I don't know what else ... :-)

Anyhow, I totally sympathize with Richard's approach. There should be
only one general stream transformer (like stream-unfoldn) that is
implemented in a space-safe way (if this is possible). Any other
stream procedure should then be implemented with that, and as a
consequence should also "work". For example, I'd like to be able to
define something like

(define (my-stream-filter pred? stream)
  (stream-unfoldn (lambda (stream)
                    (let ((results
		          (if (stream-null? stream)
			      (list '() '())
			      (let* ((head (stream-car stream))
			             (test (pred? head)))
			        (if test
			            (list (list head) #f)
			            (list #f (list head)))))))
                      (values (stream-cdr stream)
                              results)))
		  stream
		  2))

and this should work! If this is not possible, I think the whole
effort to make this srfi "space safe" should be abandoned completely.

The only thing I am not sure about is, if STREAM-UNFOLDN is the right
abstraction to transform streams (it looks a little bit too "heavy
weight" to me ...). Last summer I learned about another way to
transform streams: Richard Bird and Jeremy Gibbons proposed in [1,
page 26] a stream transformer "stream" that transforms one stream into
another by alternating between consuming and producing stream
elements. To my mind, this seems a little bit "simpler". In addition,
this function also has some nice properties; it allows you to "fuse"
unfolds with folds, which I think could be very neat, too. I just
tried to code it (I named it STREAM-TRANSFORM for now):

(define (stream-transform producer consumer state stream)

  (define (loop state stream)
    (if (null? (stream-value stream))
	(stream-value (stream-prepend (car (producer state)) stream-null))
	(if (null? (car (producer state)))
	    (loop (consumer (cdr (producer state))
			    (car (stream-value stream)))
		  (cdr (stream-value stream)))
	    (let ((res (producer state)))
	      (stream-value
	       (stream-prepend (car res)
			       (make-stream 
				(my-delay
				 (loop (consumer (cdr res)
						 (car (stream-value stream)))
				       (cdr (stream-value stream)))))))))))

  (make-stream
   (my-delay
     (loop state stream))))

(stream-define (stream-prepend l stream)
  (let inner-loop ((l l))
      (if (null? l)
	  stream
	  (stream-cons (car l)
		       (inner-loop (cdr l))))))

(define (stream-value s)
  (my-force (stream-promise s)))

With that, STREAM-FILTER is also very easy to define:

(define (my-stream-filter-2 pred? stream)
  (stream-transform (lambda (state)
		      (cons 
		       (if state
			   (list state)
			   '())
		       'foo))
		    (lambda (foo c)
		      (if (pred? c)
			  c
			  #f))
		    #f
		    stream))

Works, but is also not space-safe yet ...

Cheers,

Matthias

[1] http://www.cs.uu.nl/~johanj/afp/afp4/arith-4.pdf

-- 
Matthias Neubauer                                       |
Universität Freiburg, Institut für Informatik           | tel +49 761 203 8060
Georges-Köhler-Allee 79, 79110 Freiburg i. Br., Germany | fax +49 761 203 8052