[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Stream-filter and space leaks

This page is part of the web mail archives of SRFI 40 from before July 7th, 2015. The new archives for SRFI 40 contain all messages, not just those from before July 7th, 2015.

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)

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-prepend (car res)
				 (loop (consumer (cdr res)
						 (car (stream-value stream)))
				       (cdr (stream-value stream)))))))))))

     (loop state stream))))

(stream-define (stream-prepend l stream)
  (let inner-loop ((l l))
      (if (null? l)
	  (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)
		       (if state
			   (list state)
		    (lambda (foo c)
		      (if (pred? c)

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



[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