[Haskell-cafe] Google Summer of Code - Lock-free data structures

[Heinrich Apfelmus]

Ben wrote:
> perhaps it is too late to suggest things for GSOC --
> 
> but stephen tetley on a different thread pointed at aaron turon's
> work, which there's a very interesting new concurrency framework he
> calls "reagents" which seems to give the best of all worlds : it is
> declarative and compositional like STM, but gives performance akin to
> hand-coded lock-free data structures.  he seems to have straddled the
> duality of isolation vs message-passing nicely, and can subsume
> things like actors and the join calculus.
> 
> http://www.ccs.neu.edu/home/turon/reagents.pdf
> 
> he has a BSD licensed library in scala at
> 
> https://github.com/aturon/ChemistrySet
> 
> if someone doesn't want to pick this up for GSOC i might have a hand
> at implementing it myself.

That looks great! While I didn't take the time to understand the 
concurrency model in detail, the overall idea is to use arrows that can 
be run atomically

    runAtomically :: Reagent a b -> (a -> IO b)

This is very similar to STM: combining computations within the 
monad/arrow is atomic while combining computations "outside" the 
monad/arrow can interleave them.

    runAtomically (f . g)              -- atomic
    runAtomically f . runAtomically g  -- interleaving


Actually, it turns out that the  Reagent  arrow is also a monad, but the 
author seems to claim that the "static" arrow style enables certain 
optimizations. I haven't checked his model in detail to see whether this 
is really the case and how exactly it differs from STM, but we know that 
situations like this happen for parser combinators. Maybe it's enough to 
recast reagents as an applicative functor?

To summarize: the way I understand it is that it's apparently possible 
to improve the STM monad by turning it into an arrow. (I refer to "STM" 
in a very liberal sense here: whether memory is transactional or not is 
unimportant, the only thing that matters is a computation that composes 
atomically.)


Best regards,
Heinrich Apfelmus

--
http://apfelmus.nfshost.com