9e54bded3d071bfa92e2ee4d4e282ea928fc7ec2
[packages/old-locale.git] / Control / Parallel / Strategies.hs
1 -----------------------------------------------------------------------------
2 -- |
3 -- Module : Control.Parallel.Strategies
4 -- Copyright : (c) The University of Glasgow 2001
5 -- License : BSD-style (see the file libraries/base/LICENSE)
6 --
7 -- Maintainer : libraries@haskell.org
8 -- Stability : experimental
9 -- Portability : non-portable
10 --
11 -- Parallel strategy combinators. See
12 -- <http://www.macs.hw.ac.uk/~dsg/gph/papers/html/Strategies/strategies.html>
13 -- for more information.
14 --
15 -- Original authors:
16 -- Phil Trinder, Hans-Wolfgang Loidl, Kevin Hammond et al.
17 --
18 -----------------------------------------------------------------------------
19 module Control.Parallel.Strategies where
20
21 -- based on hslibs/concurrent/Strategies.lhs; see it for more detailed
22 -- code comments.
23
24 import Control.Parallel as Parallel (par, pseq)
25 import Data.Array
26 import Data.Complex
27
28 import Prelude hiding (seq)
29 import qualified Prelude (seq)
30
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
34 #endif
35
36 #ifdef __HUGS__
37 import Hugs.Prelude(Ratio(..) )
38 #endif
39
40 #ifdef __NHC__
41 import Ratio (Ratio(..) )
42 #endif
43
44 infixl 0 `using`,`demanding`,`sparking` -- weakest precedence!
45
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
50
51 -- We need 'pseq', not the Prelude 'seq' here. See the documentation
52 -- with 'pseq' in Control.Parallel.
53 seq = Parallel.pseq
54
55 ------------------------------------------------------------------------------
56 -- * Strategy Type, Application and Semantics
57 ------------------------------------------------------------------------------
58
59 {-
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.
62
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)!
65
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.
70 -}
71
72 type Done = ()
73
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
77
78
79 -- | Evaluates the first argument before the second.
80 (>|) :: Done -> Done -> Done
81 {-# INLINE (>|) #-}
82 (>|) = Prelude.seq
83
84 -- | Evaluates the first argument in parallel with the second.
85 (>||) :: Done -> Done -> Done
86 {-# INLINE (>||) #-}
87 (>||) = Parallel.par
88
89
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:
93 --
94 -- [a retraction] @x \`using\` s@ &#x2291; @x@
95 --
96 -- [idempotent] @(x \`using\` s) \`using\` s@ = @x \`using\` s@
97 --
98 using :: a -> Strategy a -> a
99 using x s = s x `seq` x
100
101
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
106 demanding = flip seq
107
108
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.
116
117 -- | A strategy corresponding to 'par':
118 -- @x \`par\` e@ = @e \`using\` sPar x@.
119 --
120 -- 'sPar' has been superceded by 'sparking'.
121 -- Replace @e \`using\` sPar x@ with @e \`sparking\` rwhnf x@.
122 {-# DEPRECATED sPar "Use sparking instead." #-}
123 sPar :: a -> Strategy b
124 sPar x y = x `par` ()
125
126 -- | A strategy corresponding to 'seq':
127 -- @x \`seq\` e@ = @e \`using\` sSeq x@.
128 --
129 -- 'sSeq' has been superceded by 'demanding'.
130 -- Replace @e \`using\` sSeq x@ with @e \`demanding\` rwhnf x@.
131 {-# DEPRECATED sSeq "Use demanding instead." #-}
132 sSeq :: a -> Strategy b
133 sSeq x y = x `seq` ()
134
135 -----------------------------------------------------------------------------
136 -- * Basic Strategies
137 -----------------------------------------------------------------------------
138
139 -- | Performs /no/ evaluation of its argument.
140 r0 :: Strategy a
141 r0 x = ()
142
143 -- | Reduces its argument to weak head normal form.
144 rwhnf :: Strategy a
145 rwhnf x = x `seq` ()
146
147 class NFData a where
148 -- | Reduces its argument to (head) normal form.
149 rnf :: Strategy a
150 -- Default method. Useful for base types. A specific method is necessay for
151 -- constructed types
152 rnf = rwhnf
153
154 class (NFData a, Integral a) => NFDataIntegral a
155 class (NFData a, Ord a) => NFDataOrd a
156
157 ------------------------------------------------------------------------------
158 -- * Strategic Function Application
159 ------------------------------------------------------------------------------
160
161 {-
162 These are very
163 handy when writing pipeline parallelism asa sequence of @$@, @$|@ and
164 @$||@'s. There is no need of naming intermediate values in this case. The
165 separation of algorithm from strategy is achieved by allowing strategies
166 only as second arguments to @$|@ and @$||@.
167 -}
168
169 -- | Sequential function application. The argument is evaluated using
170 -- the given strategy before it is given to the function.
171 ($|) :: (a -> b) -> Strategy a -> a -> b
172 f $| s = \ x -> f x `demanding` s x
173
174 -- | Parallel function application. The argument is evaluated using
175 -- the given strategy, in parallel with the function application.
176 ($||) :: (a -> b) -> Strategy a -> a -> b
177 f $|| s = \ x -> f x `sparking` s x
178
179 -- | Sequential function composition. The result of
180 -- the second function is evaluated using the given strategy,
181 -- and then given to the first function.
182 (.|) :: (b -> c) -> Strategy b -> (a -> b) -> (a -> c)
183 (.|) f s g = \ x -> let gx = g x
184 in f gx `demanding` s gx
185
186 -- | Parallel function composition. The result of the second
187 -- function is evaluated using the given strategy,
188 -- in parallel with the application of the first function.
189 (.||) :: (b -> c) -> Strategy b -> (a -> b) -> (a -> c)
190 (.||) f s g = \ x -> let gx = g x
191 in f gx `sparking` s gx
192
193 -- | Sequential inverse function composition,
194 -- for those who read their programs from left to right.
195 -- The result of the first function is evaluated using the
196 -- given strategy, and then given to the second function.
197 (-|) :: (a -> b) -> Strategy b -> (b -> c) -> (a -> c)
198 (-|) f s g = \ x -> let fx = f x
199 in g fx `demanding` s fx
200
201 -- | Parallel inverse function composition,
202 -- for those who read their programs from left to right.
203 -- The result of the first function is evaluated using the
204 -- given strategy, in parallel with the application of the
205 -- second function.
206 (-||) :: (a -> b) -> Strategy b -> (b -> c) -> (a -> c)
207 (-||) f s g = \ x -> let fx = f x
208 in g fx `sparking` s fx
209
210 ------------------------------------------------------------------------------
211 -- Marking a Strategy
212 ------------------------------------------------------------------------------
213
214 {-
215 Marking a strategy.
216
217 Actually, @markStrat@ sticks a label @n@ into the sparkname field of the
218 thread executing strategy @s@. Together with a runtime-system that supports
219 propagation of sparknames to the children this means that this strategy and
220 all its children have the sparkname @n@ (if the static sparkname field in
221 the @parGlobal@ annotation contains the value 1). Note, that the @SN@ field
222 of starting the marked strategy itself contains the sparkname of the parent
223 thread. The END event contains @n@ as sparkname.
224 -}
225
226 #if 0
227 markStrat :: Int -> Strategy a -> Strategy a
228 markStrat n s x = unsafePerformPrimIO (
229 _casm_ ``%r = set_sparkname(CurrentTSO, %0);'' n `thenPrimIO` \ z ->
230 returnPrimIO (s x))
231 #endif
232
233 -----------------------------------------------------------------------------
234 -- Strategy Instances and Functions
235 -----------------------------------------------------------------------------
236
237 -----------------------------------------------------------------------------
238 -- * Tuples
239 -----------------------------------------------------------------------------
240
241 {-
242 We currently support up to 9-tuples. If you need longer tuples you have to
243 add the instance explicitly to your program.
244 -}
245
246 instance (NFData a, NFData b) => NFData (a,b) where
247 rnf (x,y) = rnf x `seq` rnf y
248
249 instance (NFData a, NFData b, NFData c) => NFData (a,b,c) where
250 rnf (x,y,z) = rnf x `seq` rnf y `seq` rnf z
251
252 instance (NFData a, NFData b, NFData c, NFData d) => NFData (a,b,c,d) where
253 rnf (x1,x2,x3,x4) = rnf x1 `seq`
254 rnf x2 `seq`
255 rnf x3 `seq`
256 rnf x4
257
258 instance (NFData a1, NFData a2, NFData a3, NFData a4, NFData a5) =>
259 NFData (a1, a2, a3, a4, a5) where
260 rnf (x1, x2, x3, x4, x5) =
261 rnf x1 `seq`
262 rnf x2 `seq`
263 rnf x3 `seq`
264 rnf x4 `seq`
265 rnf x5
266
267 instance (NFData a1, NFData a2, NFData a3, NFData a4, NFData a5, NFData a6) =>
268 NFData (a1, a2, a3, a4, a5, a6) where
269 rnf (x1, x2, x3, x4, x5, x6) =
270 rnf x1 `seq`
271 rnf x2 `seq`
272 rnf x3 `seq`
273 rnf x4 `seq`
274 rnf x5 `seq`
275 rnf x6
276
277 instance (NFData a1, NFData a2, NFData a3, NFData a4, NFData a5, NFData a6, NFData a7) =>
278 NFData (a1, a2, a3, a4, a5, a6, a7) where
279 rnf (x1, x2, x3, x4, x5, x6, x7) =
280 rnf x1 `seq`
281 rnf x2 `seq`
282 rnf x3 `seq`
283 rnf x4 `seq`
284 rnf x5 `seq`
285 rnf x6 `seq`
286 rnf x7
287
288 instance (NFData a1, NFData a2, NFData a3, NFData a4, NFData a5, NFData a6, NFData a7, NFData a8) =>
289 NFData (a1, a2, a3, a4, a5, a6, a7, a8) where
290 rnf (x1, x2, x3, x4, x5, x6, x7, x8) =
291 rnf x1 `seq`
292 rnf x2 `seq`
293 rnf x3 `seq`
294 rnf x4 `seq`
295 rnf x5 `seq`
296 rnf x6 `seq`
297 rnf x7 `seq`
298 rnf x8
299
300 instance (NFData a1, NFData a2, NFData a3, NFData a4, NFData a5, NFData a6, NFData a7, NFData a8, NFData a9) =>
301 NFData (a1, a2, a3, a4, a5, a6, a7, a8, a9) where
302 rnf (x1, x2, x3, x4, x5, x6, x7, x8, x9) =
303 rnf x1 `seq`
304 rnf x2 `seq`
305 rnf x3 `seq`
306 rnf x4 `seq`
307 rnf x5 `seq`
308 rnf x6 `seq`
309 rnf x7 `seq`
310 rnf x8 `seq`
311 rnf x9
312
313 -- | Apply two strategies to the elements of a pair sequentially
314 -- from left to right.
315 seqPair :: Strategy a -> Strategy b -> Strategy (a,b)
316 seqPair strata stratb (x,y) = strata x `seq` stratb y
317
318 -- | Apply two strategies to the elements of a pair in parallel.
319 parPair :: Strategy a -> Strategy b -> Strategy (a,b)
320 parPair strata stratb (x,y) = strata x `par` stratb y `par` ()
321 -- The reason for the last 'par' is so that the strategy terminates
322 -- quickly. This is important if the strategy is used as the 1st
323 -- argument of a seq
324
325 -- | Apply three strategies to the elements of a triple in sequentially
326 -- from left to right.
327 seqTriple :: Strategy a -> Strategy b -> Strategy c -> Strategy (a,b,c)
328 seqTriple strata stratb stratc p@(x,y,z) =
329 strata x `seq`
330 stratb y `seq`
331 stratc z
332
333 -- | Apply three strategies to the elements of a triple in parallel.
334 parTriple :: Strategy a -> Strategy b -> Strategy c -> Strategy (a,b,c)
335 parTriple strata stratb stratc (x,y,z) =
336 strata x `par`
337 stratb y `par`
338 stratc z `par`
339 ()
340
341 {-
342 Weak head normal form and normal form are identical for integers, so the
343 default rnf is sufficient.
344 -}
345 instance NFData Int
346 instance NFData Integer
347 instance NFData Float
348 instance NFData Double
349
350 instance NFDataIntegral Int
351 instance NFDataOrd Int
352
353 --Rational and complex numbers.
354
355 instance (Integral a, NFData a) => NFData (Ratio a) where
356 rnf (x:%y) = rnf x `seq`
357 rnf y `seq`
358 ()
359
360 instance (RealFloat a, NFData a) => NFData (Complex a) where
361 rnf (x:+y) = rnf x `seq`
362 rnf y `seq`
363 ()
364
365 instance NFData Char
366 instance NFData Bool
367 instance NFData ()
368
369 -----------------------------------------------------------------------------
370 -- Lists
371 ----------------------------------------------------------------------------
372
373 instance NFData a => NFData [a] where
374 rnf [] = ()
375 rnf (x:xs) = rnf x `seq` rnf xs
376
377 ----------------------------------------------------------------------------
378 -- * Lists: Parallel Strategies
379 ----------------------------------------------------------------------------
380
381 -- | Applies a strategy to every element of a list in parallel.
382 parList :: Strategy a -> Strategy [a]
383 parList strat [] = ()
384 parList strat (x:xs) = strat x `par` (parList strat xs)
385
386 -- | Applies a strategy to the first @n@ elements of a list in parallel.
387 parListN :: (Integral b) => b -> Strategy a -> Strategy [a]
388 parListN n strat [] = ()
389 parListN 0 strat xs = ()
390 parListN n strat (x:xs) = strat x `par` (parListN (n-1) strat xs)
391
392 -- | Evaluates @n@ elements of the spine of the argument list and applies
393 -- the given strategy to the @n@th element (if there is one) in parallel with
394 -- the result. E.g. @parListNth 2 [e1, e2, e3]@ evaluates @e3@.
395 parListNth :: Int -> Strategy a -> Strategy [a]
396 parListNth n strat xs
397 | null rest = ()
398 | otherwise = strat (head rest) `par` ()
399 where
400 rest = drop n xs
401
402 -- | Splits a list into chunks (sub-sequences) of length @n@,
403 -- and applies a strategy sequentially to the elements in each
404 -- chunk. The chunks are evaluated in parallel.
405 -- This is useful for increasing the grain size.
406 parListChunk :: Int -> Strategy a -> Strategy [a]
407 parListChunk n strat [] = ()
408 parListChunk n strat xs = seqListN n strat xs `par`
409 parListChunk n strat (drop n xs)
410
411 -- | Applies a function to each element of a list and
412 -- and evaluates the result list in parallel,
413 -- using the given strategy for each element.
414 parMap :: Strategy b -> (a -> b) -> [a] -> [b]
415 parMap strat f xs = map f xs `using` parList strat
416
417 -- | Uses 'parMap' to apply a list-valued function to each
418 -- element of a list in parallel, and concatenates the results.
419 parFlatMap :: Strategy [b] -> (a -> [b]) -> [a] -> [b]
420 parFlatMap strat f xs = concat (parMap strat f xs)
421
422 -- | Zips together two lists using a function,
423 -- and evaluates the result list in parallel.
424 parZipWith :: Strategy c -> (a -> b -> c) -> [a] -> [b] -> [c]
425 parZipWith strat z as bs =
426 zipWith z as bs `using` parList strat
427
428 ----------------------------------------------------------------------------
429 -- * Lists: Sequential Strategies
430 ----------------------------------------------------------------------------
431
432 -- | Sequentially applies a strategy to each element of a list.
433 seqList :: Strategy a -> Strategy [a]
434 seqList strat [] = ()
435 seqList strat (x:xs) = strat x `seq` (seqList strat xs)
436
437 -- | Sequentially applies a strategy to the first n elements of a list.
438 seqListN :: (Integral a) => a -> Strategy b -> Strategy [b]
439 seqListN n strat [] = ()
440 seqListN 0 strat xs = ()
441 seqListN n strat (x:xs) = strat x `seq` (seqListN (n-1) strat xs)
442
443 -- | Applies a strategy to the @n@th element of a list
444 -- (if there is one) before returning the result.
445 -- E.g. @seqListNth 2 [e1, e2, e3]@ evaluates @e3@.
446 seqListNth :: Int -> Strategy b -> Strategy [b]
447 seqListNth n strat xs
448 | null rest = ()
449 | otherwise = strat (head rest)
450 where
451 rest = drop n xs
452
453 -- | Parallel n-buffer function added for the revised version of the strategies
454 -- paper. 'parBuffer' supersedes the older @fringeList@. It has the same
455 -- semantics.
456 parBuffer :: Int -> Strategy a -> [a] -> [a]
457 parBuffer n s xs =
458 return xs (start n xs)
459 where
460 return (x:xs) (y:ys) = (x:return xs ys) `sparking` s y
461 return xs [] = xs
462
463 start n [] = []
464 start 0 ys = ys
465 start n (y:ys) = start (n-1) ys `sparking` s y
466
467 {-
468 'fringeList' implements a `rolling buffer' of length n, i.e.applies a
469 strategy to the nth element of list when the head is demanded. More
470 precisely:
471
472 semantics: fringeList n s = id :: [b] -> [b]
473 dynamic behaviour: evalutates the nth element of the list when the
474 head is demanded.
475
476 The idea is to provide a `rolling buffer' of length n.
477 fringeList :: (Integral a) => a -> Strategy b -> [b] -> [b]
478 fringeList n strat [] = []
479 fringeList n strat (r:rs) =
480 seqListNth n strat rs `par`
481 r:fringeList n strat rs
482 -}
483
484 ------------------------------------------------------------------------------
485 -- * Arrays
486 ------------------------------------------------------------------------------
487 instance (Ix a, NFData a, NFData b) => NFData (Array a b) where
488 rnf x = rnf (bounds x) `seq` seqList rnf (elems x) `seq` ()
489
490 -- | Apply a strategy to all elements of an array sequentially.
491 seqArr :: (Ix b) => Strategy a -> Strategy (Array b a)
492 seqArr s arr = seqList s (elems arr)
493
494 -- | Apply a strategy to all elements of an array in parallel.
495 parArr :: (Ix b) => Strategy a -> Strategy (Array b a)
496 parArr s arr = parList s (elems arr)
497
498 -- | Associations maybe useful even without mentioning Arrays.
499 {-# DEPRECATED Assoc "Does not belong in Control.Parallel.Strategies" #-}
500 data Assoc a b = a := b deriving ()
501
502 instance (NFData a, NFData b) => NFData (Assoc a b) where
503 rnf (x := y) = rnf x `seq` rnf y `seq` ()
504
505 ------------------------------------------------------------------------------
506 -- * Some strategies specific for Lolita
507 ------------------------------------------------------------------------------
508
509 {-# DEPRECATED fstPairFstList "This was just an example. Write your own." #-}
510 fstPairFstList :: (NFData a) => Strategy [(a,b)]
511 fstPairFstList = seqListN 1 (seqPair rwhnf r0)
512
513 -- Some HACKs for Lolita. AFAIK force is just another name for our rnf and
514 -- sforce is a shortcut (definition here is identical to the one in Force.lhs)
515
516 {-# DEPRECATED force, sforce "Lolita-specific hacks." #-}
517 force :: (NFData a) => a -> a
518 sforce :: (NFData a) => a -> b -> b
519
520 force = id $| rnf
521 sforce x y = force x `seq` y