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