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