[Haskell-cafe] Hughes' parallel annotations for fixing a space leak
apfelmus at quantentunnel.de
Wed Mar 31 15:51:53 EDT 2010
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.
Philip Wadler. Fixing some space leaks with a garbage collector.
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?
More information about the Haskell-Cafe