[Haskell-cafe] Hughes' parallel annotations for fixing a space leak

Heinrich Apfelmus apfelmus at quantentunnel.de
Wed Mar 31 15:51:53 EDT 2010


Dear haskell-cafe,

I've been thinking about space leaks lately. In particular, I've been
studying the tricky example with pairs

    break []     = ([],[])
    break (x:xs) = if x == '\n' then ([],xs) else (x:ys,zs)
        where (ys,zs) = break xs

which was discussed in the papers

    Jan Sparud. Fixing some space leaks without a garbage collector.
    http://bit.ly/cOxcVJ

    Philip Wadler. Fixing some space leaks with a garbage collector.
    http://homepages.inf.ed.ac.uk/wadler/topics/garbage-collection.html

As I understand it, GHC implements the technique from Sparud's paper, so
this is a solved problem. (It will only kick in when compiled with
optimization, though, so -O0 will make the above leak in GHC 6.10.4 if I
checked that correctly.)


Now, I'm wondering about alternative solutions. Wadler mentions some
sort of parallel combinators

    break xs = (PAR before '\n' ys, PAR after '\n' zs)
        where (ys,zs) = SYNCLIST xs

which were introduced by John Hughes in his Phd thesis from 1983. They
are intriguing! Unfortunately, I haven't been able to procure a copy of
Hughes' thesis, either electronic or in paper. :( Can anyone help? Are
there any other resources about this parallel approach?



Regards,
Heinrich Apfelmus

--
http://apfelmus.nfshost.com



More information about the Haskell-Cafe mailing list