2010 · 66 citations · 17 references
ComputingComputer EngineeringComputer ScienceCompilersParallel ComputingProgramming LanguagesData ParallelismData-flow AnalysisParallel Computer ArchitectureParallel Programming ModelsAbstractionCode ModularityCoordinationModularityMonadsParallel CompositionParallel Program SemanticsSpeculation
We present a complete redesign of evaluation strategies, a key abstraction for specifying pure, deterministic parallelism in Haskell. Our new formulation preserves the compositionality and modularity benefits of the original, while providing significant new benefits. First, we introduce an evaluation-order monad to provide clearer, more generic, and more efficient specification of parallel evaluation. Secondly, the new formulation resolves a subtle space management issue with the original strategies, allowing parallelism (sparks) to be preserved while reclaiming heap associated with superfluous parallelism. Related to this, the new formulation provides far better support for speculative parallelism as the garbage collector now prunes unneeded speculation. Finally, the new formulation provides improved compositionality: we can directly express parallelism embedded within lazy data structures, producing more compositional strategies, and our basic strategies are parametric in the coordination combinator, facilitating a richer set of parallelism combinators.
17
Programming parallel algorithms
Guy E. Blelloch · Communications of the ACM · 1996 · 454 citations · Full text
Applicative programming with effects
Conor McBride, Ross Paterson · Journal of Functional Programming · 2007 · 402 citations · Full text
Algorithm + strategy = parallelism
Phil Trinder, Kevin Hammond, Hans Loidl et al. · Journal of Functional Programming · 1998 · 246 citations
Manuel M. T. Chakravarty, Roman Leshchinskiy, Simon Peyton Jones et al. · 2007 · 199 citations