b52f6aa25394eba7dffb5393a7649e532ecdd375
[packages/random.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/core/LICENSE)
6 --
7 -- Maintainer : libraries@haskell.org
8 -- Stability : experimental
9 -- Portability : non-portable
10 --
11 -- Parallel strategy combinators
12 --
13 -----------------------------------------------------------------------------
14
15 {-
16 Time-stamp: <Wed Mar 21 2001 00:45:34 Stardate: [-30]6360.15 hwloidl>
17 $Id: Strategies.hs,v 1.3 2002/04/26 13:34:06 simonmar Exp $
18
19 This module defines parallel strategy combinators
20
21 Phil Trinder, Hans-Wolfgang Loidl, Kevin Hammond et al.
22
23 Based on Version VII (1/5/96) `Strategies96' of type a -> ()
24
25 Author: $Author: simonmar $
26 Date: $Date: 2002/04/26 13:34:06 $
27 Revision: $Revision: 1.3 $
28 Source: $Source: /srv/cvs/cvs.haskell.org/fptools/libraries/base/Control/Parallel/Strategies.hs,v $
29 State: $State: Exp $
30
31 This module defines evaluation strategies for controlling the parallel
32 evaluation of non-strict programs. They provide a clean separation between
33 algorithmic and behavioural code.
34
35 The functions described here, and their use is documented in
36
37 "Algorithm + Strategy = Parallelism",
38 P.W. Trinder, K. Hammond, H-W. Loidl, S.L. Peyton Jones
39 In Journal of Functional Programming 8(1):23--60, January 1998.
40 URL: http://www.cee.hw.ac.uk/~dsg/gph/papers/ps/strategies.ps.gz
41
42 This module supports Haskell 1.2, Haskell 1.4 and Haskell98.
43 The distinction is made based on the __HASKELL1__ CPP variable.
44 Parts of the module could be rewritten using constructor classes.
45
46 -----------------------------------------------------------------------------
47 The history of the Strategies module:
48
49 Changelog:
50 $Log: Strategies.hs,v $
51 Revision 1.3 2002/04/26 13:34:06 simonmar
52 Remove \$Id\$ from all files: it isn't particularly useful (see
53 previous discussion on cvs-ghc@haskell.org), and it confuses Haddock.
54
55 Revision 1.2 2002/04/24 16:31:39 simonmar
56 Add the single character '|' to the header comment of each module so
57 that Haddock will parse it as the module documentation.
58
59 Revision 1.1 2001/06/28 14:15:02 simonmar
60 First cut of the Haskell Core Libraries
61 =======================================
62
63 NOTE: it's not meant to be a working snapshot. The code is just here
64 to look at and so the NHC/Hugs guys can start playing around with it.
65
66 There is no build system. For GHC, the libraries tree is intended to
67 be grafted onto an existing fptools/ tree, and the Makefile in
68 libraries/core is a quick hack for that setup. This won't work at the
69 moment without the other changes needed in fptools/ghc, which I
70 haven't committed because they'll cause breakage. However, with the
71 changes required these sources build a working Prelude and libraries.
72
73 The layout mostly follows the one we agreed on, with one or two minor
74 changes; in particular the Data/Array layout probably isn't final
75 (there are several choices here).
76
77 The document is in libraries/core/doc as promised.
78
79 The cbits stuff is just a copy of ghc/lib/std/cbits and has
80 GHC-specific stuff in it. We should really separate the
81 compiler-specific C support from any compiler-independent C support
82 there might be.
83
84 Don't pay too much attention to the portability or stability status
85 indicated in the header of each source file at the moment - I haven't
86 gone through to make sure they're all consistent and make sense.
87
88 I'm using non-literate source outside of GHC/. Hope that's ok with
89 everyone.
90
91 We need to discuss how the build system is going to work...
92
93 Revision 1.3 2001/03/22 03:51:12 hwloidl
94 -*- outline -*-
95 Time-stamp: <Thu Mar 22 2001 03:50:16 Stardate: [-30]6365.79 hwloidl>
96
97 This commit covers changes in GHC to get GUM (way=mp) and GUM/GdH (way=md)
98 working. It is a merge of my working version of GUM, based on GHC 4.06,
99 with GHC 4.11. Almost all changes are in the RTS (see below).
100
101 GUM is reasonably stable, we used the 4.06 version in large-ish programs for
102 recent papers. Couple of things I want to change, but nothing urgent.
103 GUM/GdH has just been merged and needs more testing. Hope to do that in the
104 next weeks. It works in our working build but needs tweaking to run.
105 GranSim doesn't work yet (*sigh*). Most of the code should be in, but needs
106 more debugging.
107
108 ToDo: I still want to make the following minor modifications before the release
109 - Better wrapper skript for parallel execution [ghc/compiler/main]
110 - Update parallel docu: started on it but it's minimal [ghc/docs/users_guide]
111 - Clean up [nofib/parallel]: it's a real mess right now (*sigh*)
112 - Update visualisation tools (minor things only IIRC) [ghc/utils/parallel]
113 - Add a Klingon-English glossary
114
115 * RTS:
116
117 Almost all changes are restricted to ghc/rts/parallel and should not
118 interfere with the rest. I only comment on changes outside the parallel
119 dir:
120
121 - Several changes in Schedule.c (scheduling loop; createThreads etc);
122 should only affect parallel code
123 - Added ghc/rts/hooks/ShutdownEachPEHook.c
124 - ghc/rts/Linker.[ch]: GUM doesn't know about Stable Names (ifdefs)!!
125 - StgMiscClosures.h: END_TSO_QUEUE etc now defined here (from StgMiscClosures.hc)
126 END_ECAF_LIST was missing a leading stg_
127 - SchedAPI.h: taskStart now defined in here; it's only a wrapper around
128 scheduleThread now, but might use some init, shutdown later
129 - RtsAPI.h: I have nuked the def of rts_evalNothing
130
131 * Compiler:
132
133 - ghc/compiler/main/DriverState.hs
134 added PVM-ish flags to the parallel way
135 added new ways for parallel ticky profiling and distributed exec
136
137 - ghc/compiler/main/DriverPipeline.hs
138 added a fct run_phase_MoveBinary which is called with way=mp after linking;
139 it moves the bin file into a PVM dir and produces a wrapper script for
140 parallel execution
141 maybe cleaner to add a MoveBinary phase in DriverPhases.hs but this way
142 it's less intrusive and MoveBinary makes probably only sense for mp anyway
143
144 * Nofib:
145
146 - nofib/spectral/Makefile, nofib/real/Makefile, ghc/tests/programs/Makefile:
147 modified to skip some tests if HWL_NOFIB_HACK is set; only tmp to record
148 which test prgs cause problems in my working build right now
149
150 Revision 1.2 2000/11/18 02:13:11 hwloidl
151 Now provides explicit def of seq (rather than just re-exporting).
152 Required by the current version of the compiler.
153
154 Revision 1.1 2000/01/14 13:34:32 hwloidl
155 Module for specifying (parallel) behavioural code.
156
157 Revision 1.9 1997/10/01 00:27:19 hwloidl
158 Type of par and seq changed to Done -> Done -> Done with Done = ()
159 Works for Haskell 1.2 as well as Haskell 1.4 (checks the CPP variable
160 __HASKELL1__ to distinguish setups).
161 Fixed precedences for par and seq for Haskell 1.4 (stronger than using).
162 New infix operators >| and >|| as aliases for par and seq as strategy
163 combinators.
164
165 Revision 1.8 1997/05/20 21:13:22 hwloidl
166 Revised to use `demanding` and `sparking` (final JFP paper version)
167
168 Revision 1.7 1997/04/02 21:26:21 hwloidl
169 Minor changes in documentation, none in the code.
170
171
172 revision 1.5
173 Version VII.1; Strategies96; Type: a -> ()
174 Minor changes to previous version.
175 CPP flags now separate GUM from GranSim version.
176 Infix declaration for `using` (important for e.g. quicksort where the old
177 version puts parentheses in the wrong way).
178 Moer instances for NFData and markStartegies (in GranSim setup only).
179
180 revision 1.4
181 Version VII; Strategies96; Type: a -> ()
182 The type has changed again; with the old type it's not possible to describe
183 all the strategies we want (for example seqPair r0 rnf which should not
184 evaluate the first component of the pair at all). The () type acts as info
185 that the strategy has been applied.
186 The function `using` is used as inverse strategy application i.e.
187 on top level we usually have something like res `using` strat where ...
188 The markStrategy hack is included in this version: it attaches an Int value
189 to the currently running strategy (this can be inherited by all sub-strats)
190 It doesn't model the jumps between evaluating producer and consumer properly
191 (for that something like cost centers would be necessary).
192
193 revision 1.3
194 Version VI (V-based); Strategies95; Type: a -> a
195 Now uses library modules like FiniteMap with strategies in there.
196 CPP flags for using the same module with GUM and GranSim.
197 A few new strategies.
198
199 revision 1.2
200 Version V; Strategies95; Type: a -> a
201 The type of Strategies has changed from a -> () to a -> a
202 All strategies and instances of NFData have been redefined accordingly.
203 This branch started off after discussions between PWT, SLPJ and HWL in
204 mid Nov (start of development of the actual module: 10/1/96)
205
206 revision 1.1 Initial revision
207 -----------------------------------------------------------------------------
208 -- To use fakeinfo first replace all %%$ by \@
209 -- If you have fakeinfo makers in the file you need a slightly modified
210 -- version of the lit-deatify script (called by lit2pgm). You get that
211 -- version on Suns and Alphas in Glasgow by using
212 -- \tr{lit2pgm -H "${HOME}/bin/`hw_os`"}
213 -- in your Makefile
214 -----------------------------------------------------------------------------
215
216 --@node Evaluation Strategies, , ,
217 --@chapter Evaluation Strategies
218
219 --@menu
220 --* Imports and infix declarations::
221 --* Strategy Type and Application::
222 --* Basic Strategies::
223 --* Strategic Function Application::
224 --* Marking a Strategy::
225 --* Strategy Instances::
226 --* Lolita-specific Strategies::
227 --@end menu
228
229 --@node Imports and infix declarations, Strategy Type and Application, Evaluation Strategies, Evaluation Strategies
230 --@section Imports and infix declarations
231
232 > module Strategies(
233 >#if (__HASKELL1__>=4)
234 > module Strategies,
235 > module Parallel
236 >#else
237 > Strategies..
238 >#endif
239 > ) where
240 >
241 >#if defined(GRAN) && !(__HASKELL1__>=4)
242 > import PreludeGlaST -- only needed for markStrat
243 >#endif
244 >#if (__HASKELL1__>=4)
245
246 <> import Prelude hiding (seq)
247 <> import qualified Parallel
248
249 > import Parallel
250
251 >#else
252 > import Parallel renaming (par to par_from_Parallel, seq to seq_from_Parallel)
253 >#endif
254
255 >#if (__HASKELL1__>=4)
256 > import Ix
257 > import Array
258 >#endif
259
260 >#if defined(PAR_GRAN_LIST)
261 > import QSort -- tmp (only for parGranList)
262 >#endif
263
264 I lifted the precedence of @par@ and @seq@ by one level to make @using@ the
265 combinator with the weakest precedence.
266 Oooops, there seems to be a bug in ghc 0.29 prohibiting another infix
267 declaration of @par@ and @seq@ despite renaming the imported versions.
268
269 >#if (__HASKELL1__>=4)
270
271 <> infixr 2 `par` -- was: 0
272 <> infixr 3 `seq` -- was: 1
273
274 >#else
275 > infixr 0 `par` -- was: 0
276 > infixr 1 `seq` -- was: 1
277 >#endif
278
279 > infixl 0 `using`,`demanding`,`sparking` -- weakest precedence!
280
281 > infixr 2 >|| -- another name for par
282 > infixr 3 >| -- another name for seq
283 > infixl 6 $||, $| -- strategic function application (seq and par)
284 > infixl 9 .|, .||, -|, -|| -- strategic (inverse) function composition
285
286 > strategy_version = "$Revision: 1.3 $"
287 > strategy_id = "$Id: Strategies.hs,v 1.3 2002/04/26 13:34:06 simonmar Exp $"
288
289 ------------------------------------------------------------------------------
290 Strategy Type, Application and Semantics
291 ------------------------------------------------------------------------------
292 --@node Strategy Type and Application, Basic Strategies, Imports and infix declarations, Evaluation Strategies
293 --@section Strategy Type and Application
294
295 --@cindex Strategy
296
297 > type Done = ()
298 > type Strategy a = a -> Done
299
300 A strategy takes a value and returns a dummy `done' value to indicate that
301 the specifed evaluation has been performed.
302
303 The basic combinators for strategies are @par@ and @seq@ but with types that
304 indicate that they only combine the results of a strategy application.
305
306 NB: This version can be used with Haskell 1.4 (GHC 2.05 and beyond), *but*
307 you won't get strategy checking on seq (only on par)!
308
309 The infix fcts >| and >|| are alternative names for `seq` and `par`.
310 With the introduction of a Prelude function `seq` separating the Prelude
311 function from the Strategy function becomes a pain. The notation also matches
312 the notation for strategic function application.
313
314 --@cindex par
315 --@cindex seq
316 --@cindex >|
317 --@cindex >||
318
319 >#if (__HASKELL1__>=4)
320
321 par and seq have the same types as before; >| and >|| are more specific
322 and can only be used when composing strategies.
323
324 <> par :: Done -> Done -> Done
325 <> par = Parallel.par
326 <> seq :: a -> b -> b -- that's the real type of seq defined in Prelude
327 <> seq = Parallel.seq
328
329 > (>|), (>||) :: Done -> Done -> Done
330 > {-# INLINE (>|) #-}
331 > {-# INLINE (>||) #-}
332 > (>|) = Prelude.seq
333 > (>||) = Parallel.par
334 >#else
335 > par, seq, (>|), (>||) :: Done -> Done -> Done
336 > par = par_from_Parallel
337 > seq = seq_from_Parallel
338 > {-# INLINE (>|) #-}
339 > {-# INLINE (>||) #-}
340 > (>|) = seq
341 > (>||) = par
342 >#endif
343
344 --@cindex using
345
346 > using :: a -> Strategy a -> a
347 >#if (__HASKELL1__>=4)
348 > using x s = s x `seq` x
349 >#else
350 > using x s = s x `seq_from_Parallel` x
351 >#endif
352
353 using takes a strategy and a value, and applies the strategy to the
354 value before returning the value. Used to express data-oriented parallelism
355
356 x `using` s is a projection on x, i.e. both
357
358 a retraction: x `using` s [ x
359 -
360 and idempotent: (x `using` s) `using` s = x `using` s
361
362 demanding and sparking are used to express control-oriented
363 parallelism. Their second argument is usually a sequence of strategy
364 applications combined `par` and `seq`. Sparking should only be used
365 with a singleton sequence as it is not necessarily excuted
366
367 --@cindex demanding
368 --@cindex sparking
369
370 > demanding, sparking :: a -> Done -> a
371 >#if (__HASKELL1__>=4)
372 > demanding = flip Parallel.seq
373 > sparking = flip Parallel.par
374 >#else
375 > demanding = flip seq_from_Parallel
376 > sparking = flip par_from_Parallel
377 >#endif
378
379 sPar and sSeq have been superceded by sparking and demanding: replace
380 e `using` sPar x with e `sparking` x
381 e `using` sSeq x with e `demanding` x
382
383 <sPar is a strategy corresponding to par. i.e. x `par` e <=> e `using` sPar x
384 <
385 <> sPar :: a -> Strategy b
386 <> sPar x y = x `par` ()
387 <
388 <sSeq is a strategy corresponding to seq. i.e. x `seq` e <=> e `using` sSeq x
389 <
390 <> sSeq :: a -> Strategy b
391 <> sSeq x y = x `seq` ()
392
393 -----------------------------------------------------------------------------
394 Basic Strategies
395 -----------------------------------------------------------------------------
396 --@node Basic Strategies, Strategic Function Application, Strategy Type and Application, Evaluation Strategies
397 --@section Basic Strategies
398
399 r0 performs *no* evaluation on its argument.
400
401 --@cindex r0
402
403 > r0 :: Strategy a
404 > r0 x = ()
405
406 rwhnf reduces its argument to weak head normal form.
407
408 --@cindex rwhnf
409 --@cindex rnf
410 --@cindex NFData
411
412 >#if defined(__HASKELL98__)
413 > rwhnf :: Strategy a
414 > rwhnf x = x `seq` ()
415 >#elif (__HASKELL1__==4)
416 > rwhnf :: Eval a => Strategy a
417 > rwhnf x = x `seq` ()
418 >#else
419 > rwhnf :: Strategy a
420 > rwhnf x = x `seq_from_Parallel` ()
421 >#endif
422
423 >#if defined(__HASKELL98__)
424 > class NFData a where
425 >#elif (__HASKELL1__>=4)
426 > class Eval a => NFData a where
427 >#else
428 > class NFData a where
429 >#endif
430 > -- rnf reduces its argument to (head) normal form
431 > rnf :: Strategy a
432 > -- Default method. Useful for base types. A specific method is necessay for
433 > -- constructed types
434 > rnf = rwhnf
435 >
436 > class (NFData a, Integral a) => NFDataIntegral a
437 > class (NFData a, Ord a) => NFDataOrd a
438
439 ------------------------------------------------------------------------------
440 Strategic Function Application
441 ------------------------------------------------------------------------------
442 --@node Strategic Function Application, Marking a Strategy, Basic Strategies, Evaluation Strategies
443 --@section Strategic Function Application
444
445 The two infix functions @$|@ and @$||@ perform sequential and parallel
446 function application, respectively. They are parameterised with a strategy
447 that is applied to the argument of the function application. This is very
448 handy when writing pipeline parallelism as a sequence of @$@, @$|@ and
449 @$||@'s. There is no need of naming intermediate values in this case. The
450 separation of algorithm from strategy is achieved by allowing strategies
451 only as second arguments to @$|@ and @$||@.
452
453 --@cindex $|
454 --@cindex $||
455
456 > ($|), ($||) :: (a -> b) -> Strategy a -> a -> b
457
458 <> f $| s = \ x -> f x `using` \ _ -> s x `seq` ()
459 <> f $|| s = \ x -> f x `using` \ _ -> s x `par` ()
460
461 > f $| s = \ x -> f x `demanding` s x
462 > f $|| s = \ x -> f x `sparking` s x
463
464 The same thing for function composition (.| and .||) and inverse function
465 composition (-| and -||) for those who read their programs from left to
466 right.
467
468 --@cindex .|
469 --@cindex .||
470 --@cindex -|
471 --@cindex -||
472
473 > (.|), (.||) :: (b -> c) -> Strategy b -> (a -> b) -> (a -> c)
474 > (-|), (-||) :: (a -> b) -> Strategy b -> (b -> c) -> (a -> c)
475
476 > (.|) f s g = \ x -> let gx = g x
477 > in f gx `demanding` s gx
478 > (.||) f s g = \ x -> let gx = g x
479 > in f gx `sparking` s gx
480
481 > (-|) f s g = \ x -> let fx = f x
482 > in g fx `demanding` s fx
483 > (-||) f s g = \ x -> let fx = f x
484 > in g fx `sparking` s fx
485
486 ------------------------------------------------------------------------------
487 Marking a Strategy
488 ------------------------------------------------------------------------------
489 --@node Marking a Strategy, Strategy Instances, Strategic Function Application, Evaluation Strategies
490 --@section Marking a Strategy
491
492 Marking a strategy.
493
494 Actually, @markStrat@ sticks a label @n@ into the sparkname field of the
495 thread executing strategy @s@. Together with a runtime-system that supports
496 propagation of sparknames to the children this means that this strategy and
497 all its children have the sparkname @n@ (if the static sparkname field in
498 the @parGlobal@ annotation contains the value 1). Note, that the @SN@ field
499 of starting the marked strategy itself contains the sparkname of the parent
500 thread. The END event contains @n@ as sparkname.
501
502 --@cindex markStrat
503
504 >#if defined(GRAN) && !(__HASKELL1__>=4)
505 > markStrat :: Int -> Strategy a -> Strategy a
506 > markStrat n s x = unsafePerformPrimIO (
507 > _casm_ ``%r = set_sparkname(CurrentTSO, %0);'' n `thenPrimIO` \ z ->
508 > returnPrimIO (s x))
509 >#endif
510
511 -----------------------------------------------------------------------------
512 Strategy Instances and Functions
513 -----------------------------------------------------------------------------
514 --@node Strategy Instances, Lolita-specific Strategies, Marking a Strategy, Evaluation Strategies
515 --@section Strategy Instances
516 -----------------------------------------------------------------------------
517 Tuples
518 -----------------------------------------------------------------------------
519 --@menu
520 --* Tuples::
521 --* Numbers::
522 --* Characters::
523 --* Booleans::
524 --* Unit::
525 --* Lists::
526 --* Arrays::
527 --@end menu
528
529 --@node Tuples, Numbers, Strategy Instances, Strategy Instances
530 --@subsection Tuples
531
532 We currently support up to 9-tuples. If you need longer tuples you have to
533 add the instance explicitly to your program.
534
535 > instance (NFData a, NFData b) => NFData (a,b) where
536 > rnf (x,y) = rnf x `seq` rnf y
537
538 > instance (NFData a, NFData b, NFData c) => NFData (a,b,c) where
539 > rnf (x,y,z) = rnf x `seq` rnf y `seq` rnf z
540
541 > instance (NFData a, NFData b, NFData c, NFData d) => NFData (a,b,c,d) where
542 > rnf (x1,x2,x3,x4) = rnf x1 `seq`
543 > rnf x2 `seq`
544 > rnf x3 `seq`
545 > rnf x4
546
547 > -- code automatically inserted by `hwl-insert-NFData-n-tuple'
548 > instance (NFData a1, NFData a2, NFData a3, NFData a4, NFData a5) =>
549 > NFData (a1, a2, a3, a4, a5) where
550 > rnf (x1, x2, x3, x4, x5) =
551 > rnf x1 `seq`
552 > rnf x2 `seq`
553 > rnf x3 `seq`
554 > rnf x4 `seq`
555 > rnf x5
556
557 > -- code automatically inserted by `hwl-insert-NFData-n-tuple'
558 > instance (NFData a1, NFData a2, NFData a3, NFData a4, NFData a5, NFData a6) =>
559 > NFData (a1, a2, a3, a4, a5, a6) where
560 > rnf (x1, x2, x3, x4, x5, x6) =
561 > rnf x1 `seq`
562 > rnf x2 `seq`
563 > rnf x3 `seq`
564 > rnf x4 `seq`
565 > rnf x5 `seq`
566 > rnf x6
567
568 > -- code automatically inserted by `hwl-insert-NFData-n-tuple'
569 > instance (NFData a1, NFData a2, NFData a3, NFData a4, NFData a5, NFData a6, NFData a7) =>
570 > NFData (a1, a2, a3, a4, a5, a6, a7) where
571 > rnf (x1, x2, x3, x4, x5, x6, x7) =
572 > rnf x1 `seq`
573 > rnf x2 `seq`
574 > rnf x3 `seq`
575 > rnf x4 `seq`
576 > rnf x5 `seq`
577 > rnf x6 `seq`
578 > rnf x7
579
580 > -- code automatically inserted by `hwl-insert-NFData-n-tuple'
581 > instance (NFData a1, NFData a2, NFData a3, NFData a4, NFData a5, NFData a6, NFData a7, NFData a8) =>
582 > NFData (a1, a2, a3, a4, a5, a6, a7, a8) where
583 > rnf (x1, x2, x3, x4, x5, x6, x7, x8) =
584 > rnf x1 `seq`
585 > rnf x2 `seq`
586 > rnf x3 `seq`
587 > rnf x4 `seq`
588 > rnf x5 `seq`
589 > rnf x6 `seq`
590 > rnf x7 `seq`
591 > rnf x8
592
593 > -- code automatically inserted by `hwl-insert-NFData-n-tuple'
594 > instance (NFData a1, NFData a2, NFData a3, NFData a4, NFData a5, NFData a6, NFData a7, NFData a8, NFData a9) =>
595 > NFData (a1, a2, a3, a4, a5, a6, a7, a8, a9) where
596 > rnf (x1, x2, x3, x4, x5, x6, x7, x8, x9) =
597 > rnf x1 `seq`
598 > rnf x2 `seq`
599 > rnf x3 `seq`
600 > rnf x4 `seq`
601 > rnf x5 `seq`
602 > rnf x6 `seq`
603 > rnf x7 `seq`
604 > rnf x8 `seq`
605 > rnf x9
606
607 --@cindex seqPair
608
609 > seqPair :: Strategy a -> Strategy b -> Strategy (a,b)
610 > seqPair strata stratb (x,y) = strata x `seq` stratb y
611
612 --@cindex parPair
613
614 > parPair :: Strategy a -> Strategy b -> Strategy (a,b)
615 > parPair strata stratb (x,y) = strata x `par` stratb y `par` ()
616
617 The reason for the second `par` is so that the strategy terminates
618 quickly. This is important if the strategy is used as the 1st argument of a seq
619
620 --@cindex seqTriple
621
622 > seqTriple :: Strategy a -> Strategy b -> Strategy c -> Strategy (a,b,c)
623 > seqTriple strata stratb stratc p@(x,y,z) =
624 > strata x `seq`
625 > stratb y `seq`
626 > stratc z
627
628 --@cindex parTriple
629
630 > parTriple :: Strategy a -> Strategy b -> Strategy c -> Strategy (a,b,c)
631 > parTriple strata stratb stratc (x,y,z) =
632 > strata x `par`
633 > stratb y `par`
634 > stratc z `par`
635 > ()
636
637 -----------------------------------------------------------------------------
638 Numbers
639 -----------------------------------------------------------------------------
640 --@node Numbers, Characters, Tuples, Strategy Instances
641 --@subsection Numbers
642
643 Weak head normal form and normal form are identical for integers, so the
644 default rnf is sufficient.
645
646 > instance NFData Int
647 > instance NFData Integer
648 > instance NFData Float
649 > instance NFData Double
650
651 > instance NFDataIntegral Int
652 > instance NFDataOrd Int
653
654 Rational and complex numbers.
655
656 >#if !(__HASKELL1__>=4)
657 > instance (NFData a) => NFData (Ratio a) where
658 > rnf (x:%y) = rnf x `seq`
659 > rnf y `seq`
660 > ()
661
662 > instance (NFData a) => NFData (Complex a) where
663 > rnf (x:+y) = rnf x `seq`
664 > rnf y `seq`
665 > ()
666 >#endif
667
668 -----------------------------------------------------------------------------
669 Characters
670 -----------------------------------------------------------------------------
671 --@node Characters, Booleans, Numbers, Strategy Instances
672 --@subsection Characters
673
674 > instance NFData Char
675
676 -----------------------------------------------------------------------------
677 Bools
678 -----------------------------------------------------------------------------
679 --@node Booleans, Unit, Characters, Strategy Instances
680 --@subsection Booleans
681
682 > instance NFData Bool
683
684 -----------------------------------------------------------------------------
685 Unit
686 -----------------------------------------------------------------------------
687 --@node Unit, Lists, Booleans, Strategy Instances
688 --@subsection Unit
689
690 > instance NFData ()
691
692 -----------------------------------------------------------------------------
693 Lists
694 ----------------------------------------------------------------------------
695 --@node Lists, Arrays, Unit, Strategy Instances
696 --@subsection Lists
697
698 > instance NFData a => NFData [a] where
699 > rnf [] = ()
700 > rnf (x:xs) = rnf x `seq` rnf xs
701
702 --@menu
703 --* Parallel Strategies for Lists::
704 --* Sequential Strategies for Lists::
705 --@end menu
706
707 ----------------------------------------------------------------------------
708 Lists: Parallel Strategies
709 ----------------------------------------------------------------------------
710 --@node Parallel Strategies for Lists, Sequential Strategies for Lists, Lists, Lists
711 --@subsubsection Parallel Strategies for Lists
712
713 Applies a strategy to every element of a list in parallel
714
715 --@cindex parList
716
717 > parList :: Strategy a -> Strategy [a]
718 > parList strat [] = ()
719 > parList strat (x:xs) = strat x `par` (parList strat xs)
720
721 Applies a strategy to the first n elements of a list in parallel
722
723 --@cindex parListN
724
725 > parListN :: (Integral b) => b -> Strategy a -> Strategy [a]
726 > parListN n strat [] = ()
727 > parListN 0 strat xs = ()
728 > parListN n strat (x:xs) = strat x `par` (parListN (n-1) strat xs)
729
730 Evaluates N elements of the spine of the argument list and applies
731 `strat' to the Nth element (if there is one) in parallel with the
732 result. e.g. parListNth 2 [e1, e2, e3] evaluates e2
733
734 --@cindex parListNth
735
736 > parListNth :: Int -> Strategy a -> Strategy [a]
737 > parListNth n strat xs
738 > | null rest = ()
739 > | otherwise = strat (head rest) `par` ()
740 > where
741 > rest = drop n xs
742
743 parListChunk sequentially applies a strategy to chunks
744 (sub-sequences) of a list in parallel. Useful to increase grain size
745
746 --@cindex parListChunk
747
748 > parListChunk :: Int -> Strategy a -> Strategy [a]
749 > parListChunk n strat [] = ()
750 > parListChunk n strat xs = seqListN n strat xs `par`
751 > parListChunk n strat (drop n xs)
752
753 parMap applies a function to each element of the argument list in
754 parallel. The result of the function is evaluated using `strat'
755
756 --@cindex parMap
757
758 > parMap :: Strategy b -> (a -> b) -> [a] -> [b]
759 > parMap strat f xs = map f xs `using` parList strat
760
761 parFlatMap uses parMap to apply a list-valued function to each
762 element of the argument list in parallel. The result of the function
763 is evaluated using `strat'
764
765 --@cindex parFlatMap
766
767 > parFlatMap :: Strategy [b] -> (a -> [b]) -> [a] -> [b]
768 > parFlatMap strat f xs = concat (parMap strat f xs)
769
770 parZipWith zips together two lists with a function z in parallel
771
772 --@cindex parZipWith
773
774 > parZipWith :: Strategy c -> (a -> b -> c) -> [a] -> [b] -> [c]
775 > parZipWith strat z as bs =
776 > zipWith z as bs `using` parList strat
777
778 ----------------------------------------------------------------------------
779 Lists: Sequential Strategies
780 ----------------------------------------------------------------------------
781 --@node Sequential Strategies for Lists, , Parallel Strategies for Lists, Lists
782 --@subsubsection Sequential Strategies for Lists
783
784 Sequentially applies a strategy to each element of a list
785
786 --@cindex seqList
787
788 > seqList :: Strategy a -> Strategy [a]
789 > seqList strat [] = ()
790 > seqList strat (x:xs) = strat x `seq` (seqList strat xs)
791
792 Sequentially applies a strategy to the first n elements of a list
793
794 --@cindex seqListN
795
796 > seqListN :: (Integral a) => a -> Strategy b -> Strategy [b]
797 > seqListN n strat [] = ()
798 > seqListN 0 strat xs = ()
799 > seqListN n strat (x:xs) = strat x `seq` (seqListN (n-1) strat xs)
800
801 seqListNth applies a strategy to the Nth element of it's argument
802 (if there is one) before returning the result. e.g. seqListNth 2 [e1,
803 e2, e3] evaluates e2
804
805 --@cindex seqListNth
806
807 >#if (__HASKELL1__>=4)
808 > seqListNth :: Int -> Strategy b -> Strategy [b]
809 >#else
810 > seqListNth :: (Integral a) => a -> Strategy b -> Strategy [b]
811 >#endif
812 > seqListNth n strat xs
813 > | null rest = ()
814 > | otherwise = strat (head rest)
815 > where
816 > rest = drop n xs
817
818 Parallel n-buffer function added for the revised version of the strategies
819 paper. @parBuffer@ supersedes the older @fringeList@. It has the same
820 semantics.
821
822 --@cindex parBuffer
823
824 > parBuffer :: Int -> Strategy a -> [a] -> [a]
825 > parBuffer n s xs =
826 > return xs (start n xs)
827 > where
828 > return (x:xs) (y:ys) = (x:return xs ys) `sparking` s y
829 > return xs [] = xs
830 >
831 > start n [] = []
832 > start 0 ys = ys
833 > start n (y:ys) = start (n-1) ys `sparking` s y
834
835 fringeList implements a `rolling buffer' of length n, i.e.applies a
836 strategy to the nth element of list when the head is demanded. More
837 precisely:
838
839 semantics: fringeList n s = id :: [b] -> [b]
840 dynamic behaviour: evalutates the nth element of the list when the
841 head is demanded.
842
843 The idea is to provide a `rolling buffer' of length n.
844
845 --@cindex fringeList
846
847 <> fringeList :: (Integral a) => a -> Strategy b -> [b] -> [b]
848 <> fringeList n strat [] = []
849 <> fringeList n strat (r:rs) =
850 <> seqListNth n strat rs `par`
851 <> r:fringeList n strat rs
852
853 ------------------------------------------------------------------------------
854 Arrays
855 ------------------------------------------------------------------------------
856 --@node Arrays, , Lists, Strategy Instances
857 --@subsection Arrays
858
859 > instance (Ix a, NFData a, NFData b) => NFData (Array a b) where
860 > rnf x = rnf (bounds x) `seq` seqList rnf (elems x) `seq` ()
861
862 Apply a strategy to all elements of an array in parallel. This can be done
863 either in sequentially or in parallel (same as with lists, really).
864
865 > seqArr :: (Ix b) => Strategy a -> Strategy (Array b a)
866 > seqArr s arr = seqList s (elems arr)
867
868 > parArr :: (Ix b) => Strategy a -> Strategy (Array b a)
869 > parArr s arr = parList s (elems arr)
870
871 Associations maybe useful even withou mentioning Arrays.
872
873 See: .../lib/prelude/TyArrays.hs:
874 data Assoc a b = a := b deriving ()
875
876 >#if (__HASKELL1__<4)
877 > instance (NFData a, NFData b) => NFData (Assoc a b) where
878 > rnf (x := y) = rnf x `seq` rnf y `seq` ()
879 >#endif
880
881 ------------------------------------------------------------------------------
882 Some strategies specific for Lolita
883 ------------------------------------------------------------------------------
884 --@node Lolita-specific Strategies, Index, Strategy Instances, Evaluation Strategies
885 --@section Lolita-specific Strategies
886
887 The following is useful in mergePenGroups
888
889 --@cindex fstPairFstList
890
891 > fstPairFstList :: (NFData a) => Strategy [(a,b)]
892 > fstPairFstList = seqListN 1 (seqPair rwhnf r0)
893
894 Some HACKs for Lolita. AFAIK force is just another name for our rnf and
895 sforce is a shortcut (definition here is identical to the one in Force.lhs)
896
897 > force :: (NFData a) => a -> a
898 > sforce :: (NFData a) => a -> b -> b
899
900 Same as definition below
901
902 <> force x = rnf x `seq` x
903
904 > force = id $| rnf
905 >#if (__HASKELL1__>=4)
906 > sforce x y = force x `seq` y
907 >#else
908 > sforce x y = force x `seq_from_Parallel` y
909 >#endif
910
911 --@node Bowing-alg specific strategies
912 --@section Bowing-alg specific strategies
913
914 NB: this strategy currently needs the quicksort implementation from the hbc syslib
915
916 >#if defined(PAR_GRAN_LIST)
917 > parGranList :: Strategy a -> (a -> Int) -> [a] -> Strategy [a]
918 > parGranList s gran_estim l_in = \ l_out ->
919 > parListByIdx s l_out $
920 > sortedIdx gran_list (sortLe ( \ (i,_) (j,_) -> i>j) gran_list)
921 > where -- spark list elems of l in the order specified by (i:idxs)
922 > parListByIdx s l [] = ()
923 > parListByIdx s l (i:idxs) = parListByIdx s l idxs `sparking` s (l!!i)
924 > -- get the index of y in the list
925 > idx y [] = error "idx: x not in l"
926 > idx y ((x,_):xs) | y==x = 0
927 > | otherwise = (idx y xs)+1
928 > -- the `schedule' for sparking: list of indices of sorted input list
929 > sortedIdx l idxs = [ idx x l | (x,_) <- idxs ]
930 > -- add granularity info to elems of the input list
931 > gran_list = map (\ l -> (gran_estim l, l)) l_in
932 >#endif
933
934 --@node Index, , Lolita-specific Strategies, Evaluation Strategies
935 --@section Index
936
937 --@index
938 --* $|:: @cindex\s-+$|
939 --* $||:: @cindex\s-+$||
940 --* -|:: @cindex\s-+-|
941 --* -||:: @cindex\s-+-||
942 --* .|:: @cindex\s-+.|
943 --* .||:: @cindex\s-+.||
944 --* NFData:: @cindex\s-+NFData
945 --* Strategy:: @cindex\s-+Strategy
946 --* demanding:: @cindex\s-+demanding
947 --* fringeList:: @cindex\s-+fringeList
948 --* fstPairFstList:: @cindex\s-+fstPairFstList
949 --* markStrat:: @cindex\s-+markStrat
950 --* parBuffer:: @cindex\s-+parBuffer
951 --* parFlatMap:: @cindex\s-+parFlatMap
952 --* parList:: @cindex\s-+parList
953 --* parListChunk:: @cindex\s-+parListChunk
954 --* parListN:: @cindex\s-+parListN
955 --* parListNth:: @cindex\s-+parListNth
956 --* parMap:: @cindex\s-+parMap
957 --* parPair:: @cindex\s-+parPair
958 --* parTriple:: @cindex\s-+parTriple
959 --* parZipWith:: @cindex\s-+parZipWith
960 --* r0:: @cindex\s-+r0
961 --* rnf:: @cindex\s-+rnf
962 --* rwhnf:: @cindex\s-+rwhnf
963 --* seqList:: @cindex\s-+seqList
964 --* seqListN:: @cindex\s-+seqListN
965 --* seqListNth:: @cindex\s-+seqListNth
966 --* seqPair:: @cindex\s-+seqPair
967 --* seqTriple:: @cindex\s-+seqTriple
968 --* sparking:: @cindex\s-+sparking
969 --* using:: @cindex\s-+using
970 --@end index