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