[project @ 1996-07-25 21:02:03 by partain]
[nofib.git] / parallel / NESL / StrategiesV.lhs
1 Time-stamp: <Fri Jul 12 1996 16:41:04 Stardate: [-31]7798.26 hwloidl>
2
3 This file should serve as a replacement for Force.lhs.
4 It uses strategies instead of a class of forcing functions.
5 Phil's current working copy of the strategies module is:
6 /local/grasp_tmp5/trinder/tests/SUN4/parallel/ParallelStrategiesV.hs
7
8 ---------------------------------------------------------------------------
9
10   This Module Defines the parallel strategy combinators
11
12         Phil Trinder 10/1/96                             
13
14 *********************** parallelStrategies *************************
15
16 Version V, with `type Strategy a : a -> a'
17
18 > module Strategies (Strategies.., Parallel..)  where
19 >
20 >#if defined(GRAN)
21 > import PreludeGlaST                        -- only needed for markStrat
22 >#endif
23 > import Parallel
24
25 ------------------------------------------------------------------------------
26                         Strategy Type
27 ------------------------------------------------------------------------------
28
29 N.B. This may be rewritten to use constructor classes when
30 they become available in Haskell 1.3 
31
32 > type Strategy a = a -> a
33
34 A strategy function, s, guarantees to return the same argument value, but
35 may perform some evaluation on it. i.e. s applied to some argument a
36 is less defined than a:
37
38 s a [ a
39     -
40
41 More formally, a strategy s is a projection, i.e. both 
42
43   a retraction: s [ id
44                   -
45   and idempotent: s o s = s
46
47 ------------------------------------------------------------------------------
48                         Basic Strategies
49 ------------------------------------------------------------------------------
50
51 note that
52
53 seq, par :: a -> Strategy b
54
55 @rnf@ performs *no* evaluation on it's argument 
56
57 > r0 :: Strategy a 
58 > r0 x = x
59
60 @rwhnf@ reduces it's argument to weak head normal form 
61
62 > rwhnf :: Strategy a 
63 > rwhnf x = x `seq` x  
64
65 > class NFData a where
66 >   rnf :: Strategy a
67 >   rnf = rwhnf
68
69 @rnf@ evaluates it's argument to normal form. Its default method is reducing
70 to weak head normal form. This is useful for base types. 
71 A specific method is necessay for constructed types.
72
73 > class (NFData a, Integral a) => NFDataIntegral a
74 > class (NFData a, Ord a) => NFDataOrd a
75
76 ------------------------------------------------------------------------------
77                         Using & Marking a Strategy
78 ------------------------------------------------------------------------------
79
80 Strategy application
81
82 > using :: a -> Strategy a -> a
83 > using x s = s x -- `seq` x
84
85 >#if defined(GRAN)
86
87 Marking a strategy.
88
89 Actually, @markStrat@  sticks a label @n@  into the sparkname  field of the
90 thread executing strategy @s@. Together with a runtime-system that supports
91 propagation of sparknames to the children this means that this strategy and
92 all its children have  the sparkname @n@ (if the  static sparkname field in
93 the @parGlobal@ annotation contains the value 1). Note, that the @SN@ field
94 of starting the marked strategy itself contains the sparkname of the parent
95 thread. The END event contains @n@ as sparkname.
96
97 > markStrat :: Int -> Strategy a -> Strategy a 
98 > markStrat n s x = unsafePerformPrimIO (
99 >     _casm_ ``%r = set_sparkname(CurrentTSO, %0);'' n `thenPrimIO` \ z ->
100 >     returnPrimIO (s x))
101 >#endif  /* GRAN */
102
103 ------------------------------------------------------------------------------
104                         Strategy Instances
105 ------------------------------------------------------------------------------
106                         Lists
107 ------------------------------------------------------------------------------
108
109 N.B. These functions traverse their result, but do *not* construct
110 a new version 
111
112 > instance NFData a => NFData [a] where
113 >  rnf nil@[] = nil
114 >  rnf xs@(x:rest) = rnf x `seq` 
115 >                    rnf rest `seq` 
116 >                    xs
117
118 > {-#SPECIALISE instance NFData [Char]#-}
119 > {-#SPECIALISE instance NFData [Int]#-}
120 > {-#SPECIALISE instance NFData [[Char]]#-}
121 > {-#SPECIALISE instance NFData [[Int]]#-}
122
123 ------------------------------------------------------------------------------
124                         Tuples
125 ------------------------------------------------------------------------------
126
127 > instance (NFData a, NFData b) => NFData (a,b) where
128 >   rnf p@(x,y) = rnf x `seq` 
129 >                 rnf y `seq`
130 >                 p
131 >
132 > instance (NFData a, NFData b, NFData c) => NFData (a,b,c) where
133 >   rnf t@(x,y,z) = rnf x `seq` 
134 >                   rnf y `seq` 
135 >                   rnf z `seq` 
136 >                   t
137
138 ------------------------------------------------------------------------------
139                         Numbers
140 ------------------------------------------------------------------------------
141
142 Weak head normal form and normal form are identical for
143 enumerations like integers
144
145 > instance NFData Int 
146 > instance NFData Integer
147 > instance NFData Float
148 > instance NFData Double
149
150 > instance NFDataIntegral Int
151 > instance NFDataOrd Int
152
153 > instance (NFData a) => NFData (Ratio a) where
154 >   rnf p@(x:%y) = rnf x `seq` 
155 >                  rnf y `seq`
156 >                  p
157 >
158 > instance (NFData a) => NFData (Complex a) where
159 >   rnf p@(x:+y) = rnf x `seq` 
160 >                  rnf y `seq`
161 >                  p
162 >
163
164 ------------------------------------------------------------------------------
165                         Other basic types
166 ------------------------------------------------------------------------------
167
168 > instance NFData Char
169 > instance NFData Bool
170
171 ------------------------------------------------------------------------------
172                         Useful functions using Strategies
173 ------------------------------------------------------------------------------
174                         Lists - Parallel
175 ------------------------------------------------------------------------------
176
177 Applies a strategy to each element in a list in parallel
178
179 > parList :: Strategy a -> Strategy [a]
180 > parList strat nil@[]     = nil
181 > parList strat xs@(x:rest) = strat x `par` 
182 >                             (parList strat rest) `seq`
183 >                             xs
184
185 Applies a strategy to the first  n elements of a list  in parallel
186
187 > parListN :: (Integral b) => b -> Strategy a -> Strategy [a]
188 > parListN n strat nil@[]      = nil
189 > parListN 0 strat xs          = xs
190 > parListN n strat xs@(x:rest) = strat x `par` 
191 >                                (parListN (n-1) strat rest) `seq`
192 >                                xs
193
194 Evaluates just the Nth element of it's argument list (if there is
195 one) in parallel with the result. e.g. parListNth 2 [e1, e2, e3]
196 evaluates e2 
197
198 > parListNth :: Int -> Strategy a -> Strategy [a]
199 > parListNth n strat xs
200 >   | length (take n xs) >= n  = strat (xs !! (n-1)) `par` xs
201 >   | otherwise                = xs
202
203 parListChunk sequentially applies a strategy to chunks (sub-sequences) 
204 of a list in parallel. Useful to increase grain size.
205
206 > parListChunk :: (Integral b) => b -> Strategy a -> Strategy [a]
207 > parListChunk n strat [] = []
208 > parListChunk n strat xs = seqListN n strat xs `par` 
209 >                           parListChunk n strat (drop n xs) `par`
210 >                           xs
211
212 parMap semantics:  maps f over the list xs.
213 dynamic behaviour: evaluates each element of the result in parallel, to
214                       the degree specified by the strategy parameter, strat.
215
216 > parMap :: Strategy b -> (a -> b) -> [a] -> [b]
217 > parMap strat f xs     = strategy (map f xs)
218 >                         where
219 >                           strategy = parList strat 
220
221 > parFlatMap :: Strategy [b] -> (a -> [b]) -> [a] -> [b]
222 > parFlatMap strat f xs = concat (parMap strat f xs)
223
224 ------------------------------------------------------------------------------
225                 Lists - Sequential
226 ------------------------------------------------------------------------------
227
228 Sequentially applies a strategy to each element of a list
229
230 > seqList :: Strategy a -> Strategy [a]
231 > seqList strat nil@[]      = nil
232 > seqList strat xs@(x:rest) = strat x `seq` 
233 >                             (seqList strat rest) `seq`
234 >                             xs
235
236 Sequentially applies a strategy to the first  n elements of a list. e.g.
237 seqListN 2 [e1, e2, e3] evaluates e1 and e2
238
239 > seqListN :: (Integral b) => b -> Strategy a -> Strategy [a]
240 > seqListN n strat nil@[]      = nil
241 > seqListN 0 strat xs          = xs
242 > seqListN n strat xs@(x:rest) = strat x `seq` 
243 >                                (seqListN (n-1) strat rest) `seq`
244 >                                xs
245
246 Applies a strategy to the Nth element of it's argument (if there is
247 one) before returning the result. e.g. seqListNth 2 [e1, e2, e3]
248 evaluates e2
249
250 > seqListNth n strat xs 
251 >  | length (take n xs) >= n  = strat (xs !! (n-1)) `seq` xs
252 >  | otherwise                = xs
253
254 Implements a `rolling buffer' of length n, i.e.applies a strategy
255 to the nth element of list when the head is demanded.
256
257 > fringeList :: Int -> Strategy b -> Strategy [b] 
258 > fringeList n strat [] = []
259 > fringeList n strat (r:rs) = 
260 >   seqListNth (n-1) strat rs `par`
261 >   r:fringeList n strat rs
262
263 ------------------------------------------------------------------------------
264                         Tuples
265 ------------------------------------------------------------------------------
266
267 Applies a strategy to both elements of a pair in parallel. The reason for the
268 second `par` is so that the strategy terminates quickly. This is
269 important if the strategy is used as the 1st argument of a seq
270
271 > parPair :: Strategy a -> Strategy b -> Strategy (a,b)
272 > parPair strata stratb p@(x,y) = strata x `par` 
273 >                                 stratb y `par` 
274 >                                 p
275
276 Sequentially applies a strategy to both elements of a pair.
277
278 > seqPair :: Strategy a -> Strategy b -> Strategy (a,b)
279 > seqPair strata stratb p@(x,y) = strata x `seq` 
280 >                                 stratb y `seq`
281 >                                 p
282
283 The above doesn't work if one strategy is r0 (seq is strict in its first arg). A more expensive but correct version is:
284
285 % new_seqPair :: Strategy a -> Strategy b -> Strategy (a,b)
286 % new_seqPair strata stratb p@(x,y) = let 
287 %                                       x' = strata x
288 %                                       y' = stratb y 
289 %                                     in
290 %                                     (x',y') `seq` p
291
292 The same for triples:
293
294 > parTriple :: Strategy a -> Strategy b -> Strategy c -> Strategy (a,b,c)
295 > parTriple strata stratb stratc p@(x,y,z) = strata x `par` 
296 >                                          stratb y `par` 
297 >                                          stratc z `par` 
298 >                                          p
299
300 > seqTriple :: Strategy a -> Strategy b -> Strategy c -> Strategy (a,b,c)
301 > seqTriple strata stratb stratc p@(x,y,z) = strata x `seq` 
302 >                                            stratb y `seq`
303 >                                            stratc z `seq`
304 >                                            p
305
306 ------------------------------------------------------------------------------
307                         Arrays
308 ------------------------------------------------------------------------------
309
310 > instance (NFData a, Ix a, NFData b) => NFData (Array a b) where
311 >   rnf a = rnf (bounds a) `seq` foldr seq () (elems a) `seq` a
312
313 Associations maybe useful even withou mentioning Arrays.
314
315 See: .../lib/prelude/TyArrays.hs:
316 data  Assoc a b =  a := b  deriving ()
317
318 > instance (NFData a, NFData b) => NFData (Assoc a b) where
319 >   rnf a@(x := y) = rnf x `seq` rnf y `seq` a
320
321 ------------------------------------------------------------------------------
322                         Some strategies specific for Lolita     
323 ------------------------------------------------------------------------------
324
325 The following is useful in mergePenGroups
326
327 > fstPairFstList = seqListN 1 (seqPair rwhnf r0)
328
329 Some HACKs for Lolita. AFAIK force is just another name for our rnf and
330 sforce is a shortcut (definition here is identical to the one in Force.lhs)
331
332 > force :: (NFData a) => Strategy a
333 > force = rnf
334 > sforce x y = force x `seq` y
335