1 -----------------------------------------------------------------------------
3 -- Module : Control.Parallel.Strategies
4 -- Copyright : (c) The University of Glasgow 2001
5 -- License : BSD-style (see the file libraries/base/LICENSE)
7 -- Maintainer : libraries@haskell.org
8 -- Stability : experimental
9 -- Portability : non-portable
11 -- Parallel strategy combinators. See
12 -- <http://www.macs.hw.ac.uk/~dsg/gph/papers/html/Strategies/strategies.html>
13 -- for more information.
16 -- Phil Trinder, Hans-Wolfgang Loidl, Kevin Hammond et al.
18 -----------------------------------------------------------------------------
19 module Control.Parallel.Strategies where
21 -- based on hslibs/concurrent/Strategies.lhs; see it for more detailed
24 import Control.Parallel as Parallel (par, pseq)
28 import Prelude hiding (seq)
29 import qualified Prelude (seq)
31 -- not a terribly portable way of getting at Ratio rep.
32 #ifdef __GLASGOW_HASKELL__
33 import GHC.Real (Ratio(..)) -- The basic defns for Ratio
37 import Hugs.Prelude(Ratio(..) )
41 import Ratio (Ratio(..) )
44 infixl 0 `using`,`demanding`,`sparking` -- weakest precedence!
46 infixr 2 >|| -- another name for par
47 infixr 3 >| -- another name for seq
48 infixl 6 $||, $| -- strategic function application (seq and par)
49 infixl 9 .|, .||, -|, -|| -- strategic (inverse) function composition
51 -- We need 'pseq', not the Prelude 'seq' here. See the documentation
52 -- with 'pseq' in Control.Parallel.
55 ------------------------------------------------------------------------------
56 -- * Strategy Type, Application and Semantics
57 ------------------------------------------------------------------------------
60 The basic combinators for strategies are 'par' and 'seq' but with types that
61 indicate that they only combine the results of a strategy application.
63 NB: This version can be used with Haskell 1.4 (GHC 2.05 and beyond), *but*
64 you won't get strategy checking on seq (only on par)!
66 The operators >| and >|| are alternative names for `seq` and `par`.
67 With the introduction of a Prelude function `seq` separating the Prelude
68 function from the Strategy function becomes a pain. The notation also matches
69 the notation for strategic function application.
74 -- | A strategy takes a value and returns a 'Done' value to indicate that
75 -- the specifed evaluation has been performed.
76 type Strategy a = a -> Done
79 -- | Evaluates the first argument before the second.
80 (>|) :: Done -> Done -> Done
84 -- | Evaluates the first argument in parallel with the second.
85 (>||) :: Done -> Done -> Done
90 -- | Takes a value and a strategy, and applies the strategy to the
91 -- value before returning the value. Used to express data-oriented
92 -- parallelism. @x \`using\` s@ is a projection on @x@, i.e. both:
94 -- [a retraction] @x \`using\` s@ ⊑ @x@
96 -- [idempotent] @(x \`using\` s) \`using\` s@ = @x \`using\` s@
98 using :: a -> Strategy a -> a
99 using x s = s x `seq` x
102 -- | Evaluates the second argument before the first.
103 -- Used to express control-oriented parallelism. The second
104 -- argument is usually a strategy application.
105 demanding :: a -> Done -> a
109 -- | Evaluates the second argument in parallel with the first.
110 -- Used to express control-oriented
111 -- parallelism. The second argument is usually a strategy application.
112 sparking :: a -> Done -> a
113 sparking = flip Parallel.par
114 -- Sparking should only be used
115 -- with a singleton sequence as it is not necessarily executed.
117 -- | A strategy corresponding to 'par':
118 -- @x \`par\` e@ = @e \`using\` sPar x@.
120 -- 'sPar' has been superceded by 'sparking'.
121 -- Replace @e \`using\` sPar x@ with @e \`sparking\` rwhnf x@.
122 sPar :: a -> Strategy b
123 sPar x y = x `par` ()
125 -- | A strategy corresponding to 'seq':
126 -- @x \`seq\` e@ = @e \`using\` sSeq x@.
128 -- 'sSeq' has been superceded by 'demanding'.
129 -- Replace @e \`using\` sSeq x@ with @e \`demanding\` rwhnf x@.
130 sSeq :: a -> Strategy b
131 sSeq x y = x `seq` ()
133 -----------------------------------------------------------------------------
134 -- * Basic Strategies
135 -----------------------------------------------------------------------------
137 -- | Performs /no/ evaluation of its argument.
141 -- | Reduces its argument to weak head normal form.
146 -- | Reduces its argument to (head) normal form.
148 -- Default method. Useful for base types. A specific method is necessay for
152 class (NFData a, Integral a) => NFDataIntegral a
153 class (NFData a, Ord a) => NFDataOrd a
155 ------------------------------------------------------------------------------
156 -- * Strategic Function Application
157 ------------------------------------------------------------------------------
161 handy when writing pipeline parallelism asa sequence of @$@, @$|@ and
162 @$||@'s. There is no need of naming intermediate values in this case. The
163 separation of algorithm from strategy is achieved by allowing strategies
164 only as second arguments to @$|@ and @$||@.
167 -- | Sequential function application. The argument is evaluated using
168 -- the given strategy before it is given to the function.
169 ($|) :: (a -> b) -> Strategy a -> a -> b
170 f $| s = \ x -> f x `demanding` s x
172 -- | Parallel function application. The argument is evaluated using
173 -- the given strategy, in parallel with the function application.
174 ($||) :: (a -> b) -> Strategy a -> a -> b
175 f $|| s = \ x -> f x `sparking` s x
177 -- | Sequential function composition. The result of
178 -- the second function is evaluated using the given strategy,
179 -- and then given to the first function.
180 (.|) :: (b -> c) -> Strategy b -> (a -> b) -> (a -> c)
181 (.|) f s g = \ x -> let gx = g x
182 in f gx `demanding` s gx
184 -- | Parallel function composition. The result of the second
185 -- function is evaluated using the given strategy,
186 -- in parallel with the application of the first function.
187 (.||) :: (b -> c) -> Strategy b -> (a -> b) -> (a -> c)
188 (.||) f s g = \ x -> let gx = g x
189 in f gx `sparking` s gx
191 -- | Sequential inverse function composition,
192 -- for those who read their programs from left to right.
193 -- The result of the first function is evaluated using the
194 -- given strategy, and then given to the second function.
195 (-|) :: (a -> b) -> Strategy b -> (b -> c) -> (a -> c)
196 (-|) f s g = \ x -> let fx = f x
197 in g fx `demanding` s fx
199 -- | Parallel inverse function composition,
200 -- for those who read their programs from left to right.
201 -- The result of the first function is evaluated using the
202 -- given strategy, in parallel with the application of the
204 (-||) :: (a -> b) -> Strategy b -> (b -> c) -> (a -> c)
205 (-||) f s g = \ x -> let fx = f x
206 in g fx `sparking` s fx
208 ------------------------------------------------------------------------------
209 -- Marking a Strategy
210 ------------------------------------------------------------------------------
215 Actually, @markStrat@ sticks a label @n@ into the sparkname field of the
216 thread executing strategy @s@. Together with a runtime-system that supports
217 propagation of sparknames to the children this means that this strategy and
218 all its children have the sparkname @n@ (if the static sparkname field in
219 the @parGlobal@ annotation contains the value 1). Note, that the @SN@ field
220 of starting the marked strategy itself contains the sparkname of the parent
221 thread. The END event contains @n@ as sparkname.
225 markStrat :: Int -> Strategy a -> Strategy a
226 markStrat n s x = unsafePerformPrimIO (
227 _casm_ ``%r = set_sparkname(CurrentTSO, %0);'' n `thenPrimIO` \ z ->
231 -----------------------------------------------------------------------------
232 -- Strategy Instances and Functions
233 -----------------------------------------------------------------------------
235 -----------------------------------------------------------------------------
237 -----------------------------------------------------------------------------
240 We currently support up to 9-tuples. If you need longer tuples you have to
241 add the instance explicitly to your program.
244 instance (NFData a, NFData b) => NFData (a,b) where
245 rnf (x,y) = rnf x `seq` rnf y
247 instance (NFData a, NFData b, NFData c) => NFData (a,b,c) where
248 rnf (x,y,z) = rnf x `seq` rnf y `seq` rnf z
250 instance (NFData a, NFData b, NFData c, NFData d) => NFData (a,b,c,d) where
251 rnf (x1,x2,x3,x4) = rnf x1 `seq`
256 instance (NFData a1, NFData a2, NFData a3, NFData a4, NFData a5) =>
257 NFData (a1, a2, a3, a4, a5) where
258 rnf (x1, x2, x3, x4, x5) =
265 instance (NFData a1, NFData a2, NFData a3, NFData a4, NFData a5, NFData a6) =>
266 NFData (a1, a2, a3, a4, a5, a6) where
267 rnf (x1, x2, x3, x4, x5, x6) =
275 instance (NFData a1, NFData a2, NFData a3, NFData a4, NFData a5, NFData a6, NFData a7) =>
276 NFData (a1, a2, a3, a4, a5, a6, a7) where
277 rnf (x1, x2, x3, x4, x5, x6, x7) =
286 instance (NFData a1, NFData a2, NFData a3, NFData a4, NFData a5, NFData a6, NFData a7, NFData a8) =>
287 NFData (a1, a2, a3, a4, a5, a6, a7, a8) where
288 rnf (x1, x2, x3, x4, x5, x6, x7, x8) =
298 instance (NFData a1, NFData a2, NFData a3, NFData a4, NFData a5, NFData a6, NFData a7, NFData a8, NFData a9) =>
299 NFData (a1, a2, a3, a4, a5, a6, a7, a8, a9) where
300 rnf (x1, x2, x3, x4, x5, x6, x7, x8, x9) =
311 -- | Apply two strategies to the elements of a pair sequentially
312 -- from left to right.
313 seqPair :: Strategy a -> Strategy b -> Strategy (a,b)
314 seqPair strata stratb (x,y) = strata x `seq` stratb y
316 -- | Apply two strategies to the elements of a pair in parallel.
317 parPair :: Strategy a -> Strategy b -> Strategy (a,b)
318 parPair strata stratb (x,y) = strata x `par` stratb y `par` ()
319 -- The reason for the last 'par' is so that the strategy terminates
320 -- quickly. This is important if the strategy is used as the 1st
323 -- | Apply three strategies to the elements of a triple in sequentially
324 -- from left to right.
325 seqTriple :: Strategy a -> Strategy b -> Strategy c -> Strategy (a,b,c)
326 seqTriple strata stratb stratc p@(x,y,z) =
331 -- | Apply three strategies to the elements of a triple in parallel.
332 parTriple :: Strategy a -> Strategy b -> Strategy c -> Strategy (a,b,c)
333 parTriple strata stratb stratc (x,y,z) =
340 Weak head normal form and normal form are identical for integers, so the
341 default rnf is sufficient.
344 instance NFData Integer
345 instance NFData Float
346 instance NFData Double
348 instance NFDataIntegral Int
349 instance NFDataOrd Int
351 --Rational and complex numbers.
353 instance (Integral a, NFData a) => NFData (Ratio a) where
354 rnf (x:%y) = rnf x `seq`
358 instance (RealFloat a, NFData a) => NFData (Complex a) where
359 rnf (x:+y) = rnf x `seq`
367 -----------------------------------------------------------------------------
369 ----------------------------------------------------------------------------
371 instance NFData a => NFData [a] where
373 rnf (x:xs) = rnf x `seq` rnf xs
375 ----------------------------------------------------------------------------
376 -- * Lists: Parallel Strategies
377 ----------------------------------------------------------------------------
379 -- | Applies a strategy to every element of a list in parallel.
380 parList :: Strategy a -> Strategy [a]
381 parList strat [] = ()
382 parList strat (x:xs) = strat x `par` (parList strat xs)
384 -- | Applies a strategy to the first @n@ elements of a list in parallel.
385 parListN :: (Integral b) => b -> Strategy a -> Strategy [a]
386 parListN n strat [] = ()
387 parListN 0 strat xs = ()
388 parListN n strat (x:xs) = strat x `par` (parListN (n-1) strat xs)
390 -- | Evaluates @n@ elements of the spine of the argument list and applies
391 -- the given strategy to the @n@th element (if there is one) in parallel with
392 -- the result. E.g. @parListNth 2 [e1, e2, e3]@ evaluates @e3@.
393 parListNth :: Int -> Strategy a -> Strategy [a]
394 parListNth n strat xs
396 | otherwise = strat (head rest) `par` ()
400 -- | Splits a list into chunks (sub-sequences) of length @n@,
401 -- and applies a strategy sequentially to the elements in each
402 -- chunk. The chunks are evaluated in parallel.
403 -- This is useful for increasing the grain size.
404 parListChunk :: Int -> Strategy a -> Strategy [a]
405 parListChunk n strat [] = ()
406 parListChunk n strat xs = seqListN n strat xs `par`
407 parListChunk n strat (drop n xs)
409 -- | Applies a function to each element of a list and
410 -- and evaluates the result list in parallel,
411 -- using the given strategy for each element.
412 parMap :: Strategy b -> (a -> b) -> [a] -> [b]
413 parMap strat f xs = map f xs `using` parList strat
415 -- | Uses 'parMap' to apply a list-valued function to each
416 -- element of a list in parallel, and concatenates the results.
417 parFlatMap :: Strategy [b] -> (a -> [b]) -> [a] -> [b]
418 parFlatMap strat f xs = concat (parMap strat f xs)
420 -- | Zips together two lists using a function,
421 -- and evaluates the result list in parallel.
422 parZipWith :: Strategy c -> (a -> b -> c) -> [a] -> [b] -> [c]
423 parZipWith strat z as bs =
424 zipWith z as bs `using` parList strat
426 ----------------------------------------------------------------------------
427 -- * Lists: Sequential Strategies
428 ----------------------------------------------------------------------------
430 -- | Sequentially applies a strategy to each element of a list.
431 seqList :: Strategy a -> Strategy [a]
432 seqList strat [] = ()
433 seqList strat (x:xs) = strat x `seq` (seqList strat xs)
435 -- | Sequentially applies a strategy to the first n elements of a list.
436 seqListN :: (Integral a) => a -> Strategy b -> Strategy [b]
437 seqListN n strat [] = ()
438 seqListN 0 strat xs = ()
439 seqListN n strat (x:xs) = strat x `seq` (seqListN (n-1) strat xs)
441 -- | Applies a strategy to the @n@th element of a list
442 -- (if there is one) before returning the result.
443 -- E.g. @seqListNth 2 [e1, e2, e3]@ evaluates @e3@.
444 seqListNth :: Int -> Strategy b -> Strategy [b]
445 seqListNth n strat xs
447 | otherwise = strat (head rest)
451 -- | Parallel n-buffer function added for the revised version of the strategies
452 -- paper. 'parBuffer' supersedes the older @fringeList@. It has the same
454 parBuffer :: Int -> Strategy a -> [a] -> [a]
456 return xs (start n xs)
458 return (x:xs) (y:ys) = (x:return xs ys) `sparking` s y
463 start n (y:ys) = start (n-1) ys `sparking` s y
466 'fringeList' implements a `rolling buffer' of length n, i.e.applies a
467 strategy to the nth element of list when the head is demanded. More
470 semantics: fringeList n s = id :: [b] -> [b]
471 dynamic behaviour: evalutates the nth element of the list when the
474 The idea is to provide a `rolling buffer' of length n.
475 fringeList :: (Integral a) => a -> Strategy b -> [b] -> [b]
476 fringeList n strat [] = []
477 fringeList n strat (r:rs) =
478 seqListNth n strat rs `par`
479 r:fringeList n strat rs
482 ------------------------------------------------------------------------------
484 ------------------------------------------------------------------------------
485 instance (Ix a, NFData a, NFData b) => NFData (Array a b) where
486 rnf x = rnf (bounds x) `seq` seqList rnf (elems x) `seq` ()
488 -- | Apply a strategy to all elements of an array sequentially.
489 seqArr :: (Ix b) => Strategy a -> Strategy (Array b a)
490 seqArr s arr = seqList s (elems arr)
492 -- | Apply a strategy to all elements of an array in parallel.
493 parArr :: (Ix b) => Strategy a -> Strategy (Array b a)
494 parArr s arr = parList s (elems arr)
496 -- | Associations maybe useful even without mentioning Arrays.
497 data Assoc a b = a := b deriving ()
499 instance (NFData a, NFData b) => NFData (Assoc a b) where
500 rnf (x := y) = rnf x `seq` rnf y `seq` ()
502 ------------------------------------------------------------------------------
503 -- * Some strategies specific for Lolita
504 ------------------------------------------------------------------------------
506 fstPairFstList :: (NFData a) => Strategy [(a,b)]
507 fstPairFstList = seqListN 1 (seqPair rwhnf r0)
509 -- Some HACKs for Lolita. AFAIK force is just another name for our rnf and
510 -- sforce is a shortcut (definition here is identical to the one in Force.lhs)
512 force :: (NFData a) => a -> a
513 sforce :: (NFData a) => a -> b -> b
516 sforce x y = force x `seq` y