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

Re: Stream-filter and space leaks



Richard Kelsey <kelsey@xxxxxxx> writes:

> Our different experiences may be based on differences between the 0.57 and
> the Scheme 48 version underlying Scsh 0.6.3.  I don't know which version
> that is.

Well, that's what I already feared. To me, this means either that my
scsh is somehow "buggy" or that we still don't have a portable,
non-leaking implementation of STREAM-FILTER.

>    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 ...).
> 
> It certainly isn't a polished result.  Most of the goofiness comes from
> wanting to be able to convert N input streams into M output streams.

Yes, this really looks like the reason why I had that impression.

> It might be simpler to have three functions that handle N->1, 1->1, and
> 1->N conversions.  Perhaps having all four would be the most useful thing
> to do.

To me, this sounds like the way to go. And I would go even
further. The primitives STREAM-UNFOLD (->1), STREAM-ZIP (N->1),
STREAM-UNZIP (N->1) and a "really nice" STREAM-TRANSFORM (1->1) should
be enough to express all the other "thingies" we now have in this
srfi.

> It's a bit hard to tell what your stream-transform is doing.  Can you 
> explain it?  Or give a type?

Sure. I should have already done this in the first place. My
STREAM-TRANSFORM is one possiblity to define such a 1->1-conversion
function (though I can't tell you for sure if it is really the one
we'll want to have in the end ... :-)

     (stream-transform producer consumer state stream) -> stream-2

     STREAM-TRANSFORM takes 
       a PRODUCER : s -> (values (list b) s)  function,
       a CONSUMER : s a -> s   function,
       an initial seed STATE : s, and
       an input STREAM : (stream a) as arguments. 
       From that, it produces an output STREAM-2 : (stream b) as
       result.

     STREAM-TRANSFORM first applies the PRODUCER function to the
     inital STATE. The result is the beginning of the new stream,
     given as (list b), and a successor state STATE-1.

     In case the input stream is empty, the result is just the list
     returned from the PRODUCER.

     In case the input stream is not empty, we split away its head
     element. The CONSUMER function then consumes the head element
     using STATE-1 and produces a new state STATE-2. The resulting
     stream begins with the list return from the PRODUCER and
     continues with the transformation of rest of the input stream
     initialized with the new state STATE-2.

Maybe it also helps to give another example: STREAM-MERGE coded using
STREAM-TRANSFORM.

     (define (stream-merge lt? stream-1 stream-2)
       (let ((stream-zipped (stream-zip stream-1 stream-2)))
         (stream-transform (lambda (list-of-two)
                             (values list-of-two #f)
                           (lambda (state-2 list-of-two-elements)
                             (let ((first (car list-of-two))
                                   (second (cadr list-of-two)))
                               (if (lt? first second)
                                   list-of-two
                                   (list second first))))
                           '()
                           stream-zipped))))

Here, we first zip the two streams together to one stream carrying
lists of two elements. After that, we transform the stream of lists to
the merged stream. The producer function does not do much; it just
passes on the two next elements given as its input state. The input
state on the other hand comes from the consumer function. It takes the
next two elements of the input stream, puts them in the right order,
and passes them on as new state.

As I already briefly mentioned, STREAM-TRANSFORM can also be used to
fuse STREAM-FOLD-LEFT and STREAM-UNFOLD. After Bird and Gibbons,

   (STREAM-UNFOLD f (STREAM-FOLD-LEFT g z s))

can be rewritten to

   (STREAM-TRANSFORM (lambda (s) (STREAM-UNFOLD f s)) g z s

which usually has much better space properties.

-Matthias

-- 
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