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 -- | Sequentially applies a strategy to chunks
401 -- (sub-sequences) of a list in parallel. Useful to increase grain size.
402 parListChunk :: Int -> Strategy a -> Strategy [a]
403 parListChunk n strat [] = ()
404 parListChunk n strat xs = seqListN n strat xs `par`
405 parListChunk n strat (drop n xs)
407 -- | Applies a function to each element of a list and
408 -- and evaluates the result list in parallel,
409 -- using the given strategy for each element.
410 parMap :: Strategy b -> (a -> b) -> [a] -> [b]
411 parMap strat f xs = map f xs `using` parList strat
413 -- | Uses 'parMap' to apply a list-valued function to each
414 -- element of a list in parallel, and concatenates the results.
415 parFlatMap :: Strategy [b] -> (a -> [b]) -> [a] -> [b]
416 parFlatMap strat f xs = concat (parMap strat f xs)
418 -- | Zips together two lists using a function,
419 -- and evaluates the result list in parallel.
420 parZipWith :: Strategy c -> (a -> b -> c) -> [a] -> [b] -> [c]
421 parZipWith strat z as bs =
422 zipWith z as bs `using` parList strat
424 ----------------------------------------------------------------------------
425 -- * Lists: Sequential Strategies
426 ----------------------------------------------------------------------------
428 -- | Sequentially applies a strategy to each element of a list.
429 seqList :: Strategy a -> Strategy [a]
430 seqList strat [] = ()
431 seqList strat (x:xs) = strat x `seq` (seqList strat xs)
433 -- | Sequentially applies a strategy to the first n elements of a list.
434 seqListN :: (Integral a) => a -> Strategy b -> Strategy [b]
435 seqListN n strat [] = ()
436 seqListN 0 strat xs = ()
437 seqListN n strat (x:xs) = strat x `seq` (seqListN (n-1) strat xs)
439 -- | Applies a strategy to the @n@th element of a list
440 -- (if there is one) before returning the result.
441 -- E.g. @seqListNth 2 [e1, e2, e3]@ evaluates @e3@.
442 seqListNth :: Int -> Strategy b -> Strategy [b]
443 seqListNth n strat xs
445 | otherwise = strat (head rest)
449 -- | Parallel n-buffer function added for the revised version of the strategies
450 -- paper. 'parBuffer' supersedes the older @fringeList@. It has the same
452 parBuffer :: Int -> Strategy a -> [a] -> [a]
454 return xs (start n xs)
456 return (x:xs) (y:ys) = (x:return xs ys) `sparking` s y
461 start n (y:ys) = start (n-1) ys `sparking` s y
464 'fringeList' implements a `rolling buffer' of length n, i.e.applies a
465 strategy to the nth element of list when the head is demanded. More
468 semantics: fringeList n s = id :: [b] -> [b]
469 dynamic behaviour: evalutates the nth element of the list when the
472 The idea is to provide a `rolling buffer' of length n.
473 fringeList :: (Integral a) => a -> Strategy b -> [b] -> [b]
474 fringeList n strat [] = []
475 fringeList n strat (r:rs) =
476 seqListNth n strat rs `par`
477 r:fringeList n strat rs
480 ------------------------------------------------------------------------------
482 ------------------------------------------------------------------------------
483 instance (Ix a, NFData a, NFData b) => NFData (Array a b) where
484 rnf x = rnf (bounds x) `seq` seqList rnf (elems x) `seq` ()
486 -- | Apply a strategy to all elements of an array sequentially.
487 seqArr :: (Ix b) => Strategy a -> Strategy (Array b a)
488 seqArr s arr = seqList s (elems arr)
490 -- | Apply a strategy to all elements of an array in parallel.
491 parArr :: (Ix b) => Strategy a -> Strategy (Array b a)
492 parArr s arr = parList s (elems arr)
494 -- | Associations maybe useful even without mentioning Arrays.
495 data Assoc a b = a := b deriving ()
497 instance (NFData a, NFData b) => NFData (Assoc a b) where
498 rnf (x := y) = rnf x `seq` rnf y `seq` ()
500 ------------------------------------------------------------------------------
501 -- * Some strategies specific for Lolita
502 ------------------------------------------------------------------------------
504 fstPairFstList :: (NFData a) => Strategy [(a,b)]
505 fstPairFstList = seqListN 1 (seqPair rwhnf r0)
507 -- Some HACKs for Lolita. AFAIK force is just another name for our rnf and
508 -- sforce is a shortcut (definition here is identical to the one in Force.lhs)
510 force :: (NFData a) => a -> a
511 sforce :: (NFData a) => a -> b -> b
514 sforce x y = force x `seq` y