[MLton-user] Re: Stream Fusion

[Vesa Karvonen]

On 4/29/07, Vesa Karvonen <vesa.a.j.k at gmail.com> wrote:
> AFAICT, a drawback of the technique, that I did not see mentioned in the
> paper, is a potential for space leaks.  Consider a stream expression of
> the form:
>
>   (map f s1) @ s2
>
> Due to the non-recursive implementation of @ (append) the space taken by f
> may not be reclaimed until after the entire stream has been discarded
> (modulo exceedingly clever compiler optimizations).  This concern should
> also apply to the Haskell version even with the "unstream . streamFn
> . stream" wrapping (which, AFAICT, effectively memoizes streams) used to
> implement list functions in terms of streams.

I've thought about this a little more and realized a couple of things.
First of all, the space leak of append described above can be fixed.  Here
is one way:

   fun concat ss = let
      exception St of 'a t List.t
   in
      T (St ss,
         fn St []            => DONE
          | St (T (s, g)::r) => (case g s
                                  of DONE        => SKIP (St r)
                                   | SKIP s      => SKIP (St (T (s, g)::r))
                                   | GIVE (a, s) => GIVE (a, St (T (s, g)::r)))
          | _                => fail "impossible")
   end

   fun a @ b = concat [a, b]

This fixes the space leak, because the step function of the first stream
becomes garbage as soon as the stream is exhausted.  However, this has the
disadvantage that the step functions are now more difficult to dispatch to
statically.  So, either you get a space leak or forget about the fusion in
the case of append.

-Vesa Karvonen