[Haskell-cafe] Re: [darcs-users] Iteratees, streams, and mmap

Heinrich Apfelmus apfelmus at quantentunnel.de
Sun Dec 13 06:47:01 EST 2009


Jason Dagit wrote:
>>> 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.
>
> [...]
>
> Heinrich Apfelmus wrote:
>>
>> 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.
> 
> I realize it's not perfect, but the problem we have now is that it's too
> easy to write things that have dismal space usage.  If we can't force proper
> space usage, how can we make it more natural to have bounded space?  Or at
> least a good approximation.
> 
> It seems that:
>  * foldl'-style helps
>  * rank-n can help
>  * no approach I've seen *forces* the behavior we want
>  * existing code and bug reports demonstrate we need to improve the
> situation

Yep, I agree completely; except for the rank-n (rank-2) trick where I'm
more pessimistic.


I think rank-2 works fine for things like ensuring that file handles are
closed properly. But for the purpose of ensuring O(1) space usage, I
think that

    withPending . flip $ const (() :)

demonstrates that rank-2 is not worth the complexity they bring. Still,
the idea of tracking resource usage in the type system is attractive.


> I'm open to suggestions on how to ensure the code has the space behavior I
> want.

I've got another, unfinished idea:

>> 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:
> 
> Right.  And the iteratee library points out that your iteratees have to be
> well-behaved (I think there they say "bounded").  I'm well aware of this
> issue and thanks for pointing it out for others who are reading along.

How about tracking the requirement of "bounded" in the type system? In
particular, I'm thinking of a type class

    class NFData a => Small a

where the idea is that all types that can be stored in constant space
are members of this class. For example, we have

    instance Small ()
    instance Small Int
    instance Small Char
    instance (Small a, Small b) => Small (a,b)
    instance (Small a, Small b) => Small (Either a b)

but recursive types like  [a]  or  String  are not allowed to be members.

Then,

    withPending :: Small a => (a -> Patch -> a) -> IO a

which is based on the function

    foldlSmall :: Small b => (b -> a -> b) -> b -> [a] -> b
    foldlSmall f b []     =
    foldlSmall f b (x:xs) = foldlSmall f b' xs
        where b' = rnf (f b x)

is pretty much guaranteed to run in O(1) space. Well, that depends on  f
, but the point is it's not  foldlSmall  who introduces the space leak,
it's the argument that takes all the blame.


> In other words, the human effort to make the code behave how we want is
> currently too high and that's the issue I want to address.  I don't know how
> we could make it impossible to have space leaks, although that would be
> interesting.

I opine that aiming for the latter (making space leaks impossible) while
experimenting brings you closer to the actual goal (making them easy to
avoid) when it comes to putting these experiments into practice. But
that's just me.



Regards,
Heinrich Apfelmus

--
http://apfelmus.nfshost.com



More information about the Haskell-Cafe mailing list