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