[darcs-users] Iteratees, streams, and mmap

Heinrich Apfelmus apfelmus at quantentunnel.de
Sat Dec 12 10:42:03 UTC 2009


Jason Dagit wrote:
> My next experiment will be to find ways to express "take this operation and
> apply it to a stream without letting the stream leak". One implication is
> that gzReadFilePS should not be used outside of a core set of modules which
> have been auideted to be resource concious.  Another implication is that we
> need to be really careful about wether or not we allow returning of
> sequences of patches.  Possibly, we need several foldl-like functions that
> open the stream internally.  For example, to process the pending maybe we
> should have:
> withPending :: (a -> Patch -> a) ->  IO a
> 
> And withPending would start the streaming and make sure that the stream
> cannot be visible as a data dependency outside of withPending.

Just a small comment on a potential flaw in this scheme and the
observation that even the rank-2 type trick from the  ST s  monad
wouldn't help.


Namely,  withPending  does not guarantee that the stream does not leak,
it only makes it more natural/convenient to formulate one's code so that
it doesn't leak. In particular, using  (:)  as argument pretty much
defeats the whole purpose:

   withPending (flip (:))

Fortunately, the type system can ensure that the patches don't leak.

   withPending :: (forall s. a -> Patch s -> a) -> IO a

Now,  a  may not mention  s  and the type checker will reject  flip (:)
 as argument. See also

  Oleg Kiselyov, Chung-chieh Shan.
  Lightweight Monadic Regions.
  http://www.cs.rutgers.edu/~ccshan/capability/region-io.pdf

for an elaboration of this technique.


However, the line between leaking and not leaking is very thin here. As
soon as we are given for example a function

   name :: Patch s -> String

that discards the  s , its results can "leak", in the sense that we
could now build a list of names

   foo :: IO [String]
   foo = withPending . flip $ (:) . name

Even worse, any type  a  that doesn't have O(1) space usage will "leak"

   bar :: IO [()]
   bar = withPending . flip $ const (() :)

In other words, exporting only a  foldl' -like interface does not really
prevent us from writing functions that have O(n) instead of O(1) space
usage. But trying to rectify that with the  forall s  trick is a doomed
idea, too.



Regards,
Heinrich Apfelmus

--
http://apfelmus.nfshost.com



More information about the darcs-users mailing list