This version hacked for use with GranSim (3.02) Phil Trinder October 2003 This module defines evaluation strategies for controlling the parallel evaluation of non-strict programs. They provide a clean separation between algorithmic and behavioural code. The functions described here, and their use is documented in "Algorithm + Strategy = Parallelism", P.W. Trinder, K. Hammond, H-W. Loidl, S.L. Peyton Jones In Journal of Functional Programming 8(1):23--60, January 1998. URL: http://www.cee.hw.ac.uk/~dsg/gph/papers/ps/strategies.ps.gz This module supports Haskell 1.2, Haskell 1.4 and Haskell98. The distinction is made based on the __HASKELL1__ CPP variable. Parts of the module could be rewritten using constructor classes. ----------------------------------------------------------------------------- The history of the Strategies module: Changelog: $Log: Strategies.lhs,v $ Revision 1.1.2.1 2001/05/01 20:46:20 hwloidl Updated Makefile common to separate .o and .hi files for Haskell 1.4 and 98 Revision 1.1 2000/01/14 13:34:32 hwloidl Module for specifying (parallel) behavioural code. Revision 1.9 1997/10/01 00:27:19 hwloidl Type of par and seq changed to Done -> Done -> Done with Done = () Works for Haskell 1.2 as well as Haskell 1.4 (checks the CPP variable __HASKELL1__ to distinguish setups). Fixed precedences for par and seq for Haskell 1.4 (stronger than using). New infix operators >| and >|| as aliases for par and seq as strategy combinators. Revision 1.8 1997/05/20 21:13:22 hwloidl Revised to use `demanding` and `sparking` (final JFP paper version) Revision 1.7 1997/04/02 21:26:21 hwloidl Minor changes in documentation, none in the code. revision 1.5 Version VII.1; Strategies96; Type: a -> () Minor changes to previous version. CPP flags now separate GUM from GranSim version. Infix declaration for `using` (important for e.g. quicksort where the old version puts parentheses in the wrong way). Moer instances for NFData and markStartegies (in GranSim setup only). revision 1.4 Version VII; Strategies96; Type: a -> () The type has changed again; with the old type it's not possible to describe all the strategies we want (for example seqPair r0 rnf which should not evaluate the first component of the pair at all). The () type acts as info that the strategy has been applied. The function `using` is used as inverse strategy application i.e. on top level we usually have something like res `using` strat where ... The markStrategy hack is included in this version: it attaches an Int value to the currently running strategy (this can be inherited by all sub-strats) It doesn't model the jumps between evaluating producer and consumer properly (for that something like cost centers would be necessary). revision 1.3 Version VI (V-based); Strategies95; Type: a -> a Now uses library modules like FiniteMap with strategies in there. CPP flags for using the same module with GUM and GranSim. A few new strategies. revision 1.2 Version V; Strategies95; Type: a -> a The type of Strategies has changed from a -> () to a -> a All strategies and instances of NFData have been redefined accordingly. This branch started off after discussions between PWT, SLPJ and HWL in mid Nov (start of development of the actual module: 10/1/96) revision 1.1 Initial revision ----------------------------------------------------------------------------- -- To use fakeinfo first replace all %%$ by \@ -- If you have fakeinfo makers in the file you need a slightly modified -- version of the lit-deatify script (called by lit2pgm). You get that -- version on Suns and Alphas in Glasgow by using -- \tr{lit2pgm -H "${HOME}/bin/`hw_os`"} -- in your Makefile ----------------------------------------------------------------------------- > module Strategies where > > import Parallel I lifted the precedence of @par@ and @seq@ by one level to make @using@ the combinator with the weakest precedence. Oooops, there seems to be a bug in ghc 0.29 prohibiting another infix declaration of @par@ and @seq@ despite renaming the imported versions. > infixr 0 `par` -- was: 0 > infixr 1 `seq` -- was: 1 > infixl 0 `using`,`demanding`,`sparking` -- weakest precedence! > infixr 2 >|| -- another name for par > infixr 3 >| -- another name for seq > infixl 6 $||, $| -- strategic function application (seq and par) > infixl 9 .|, .||, -|, -|| -- strategic (inverse) function composition > strategy_version = "$Revision: 1.1.2.1 $" > strategy_id = "$Id: Strategies.lhs,v 1.1.2.1 2001/05/01 20:46:20 hwloidl Exp $" ------------------------------------------------------------------------------ Strategy Type, Application and Semantics ------------------------------------------------------------------------------ > type Done = () > type Strategy a = a -> Done A strategy takes a value and returns a dummy `done' value to indicate that the specifed evaluation has been performed. The basic combinators for strategies are @par@ and @seq@ but with types that indicate that they only combine the results of a strategy application. NB: This version can be used with Haskell 1.4 (GHC 2.05 and beyond), *but* you won't get strategy checking on seq (only on par)! The infix fcts >| and >|| are alternative names for `seq` and `par`. With the introduction of a Prelude function `seq` separating the Prelude function from the Strategy function becomes a pain. The notation also matches the notation for strategic function application. <> par :: Done -> Done -> Done <> par = Parallel.par <> seq :: (Eval a) => a -> b -> b <> seq = Parallel.seq > using :: a -> Strategy a -> a > using x s = s x `seq` x using takes a strategy and a value, and applies the strategy to the value before returning the value. Used to express data-oriented parallelism x `using` s is a projection on x, i.e. both a retraction: x `using` s [ x - and idempotent: (x `using` s) `using` s = x `using` s demanding and sparking are used to express control-oriented parallelism. Their second argument is usually a sequence of strategy applications combined `par` and `seq`. Sparking should only be used with a singleton sequence as it is not necessarily excuted > demanding, sparking :: a -> Done -> a > demanding = flip seq > sparking = flip par sPar and sSeq have been superceded by sparking and demanding: replace e `using` sPar x with e `sparking` x e `using` sSeq x with e `demanding` x e `using` sPar x < <> sPar :: a -> Strategy b <> sPar x y = x `par` () < e `using` sSeq x < <> sSeq :: a -> Strategy b <> sSeq x y = x `seq` () ----------------------------------------------------------------------------- Basic Strategies ----------------------------------------------------------------------------- r0 performs *no* evaluation on its argument. > r0 :: Strategy a > r0 x = () rwhnf reduces its argument to weak head normal form. > rwhnf :: Eval a => Strategy a > rwhnf x = x `seq` () > class Eval a => NFData a where > -- rnf reduces its argument to (head) normal form > rnf :: Strategy a > -- Default method. Useful for base types. A specific method is necessay for > -- constructed types > rnf = rwhnf > > class (NFData a, Integral a) => NFDataIntegral a > class (NFData a, Ord a) => NFDataOrd a ------------------------------------------------------------------------------ Strategic Function Application ------------------------------------------------------------------------------ The two infix functions @$|@ and @$||@ perform sequential and parallel function application, respectively. They are parameterised with a strategy that is applied to the argument of the function application. This is very handy when writing pipeline parallelism as a sequence of @$@, @$|@ and @$||@'s. There is no need of naming intermediate values in this case. The separation of algorithm from strategy is achieved by allowing strategies only as second arguments to @$|@ and @$||@. > ($|), ($||) :: (a -> b) -> Strategy a -> a -> b <> f $| s = \ x -> f x `using` \ _ -> s x `seq` () <> f $|| s = \ x -> f x `using` \ _ -> s x `par` () > f $| s = \ x -> f x `demanding` s x > f $|| s = \ x -> f x `sparking` s x The same thing for function composition (.| and .||) and inverse function composition (-| and -||) for those who read their programs from left to right. > (.|), (.||) :: (b -> c) -> Strategy b -> (a -> b) -> (a -> c) > (-|), (-||) :: (a -> b) -> Strategy b -> (b -> c) -> (a -> c) > (.|) f s g = \ x -> let gx = g x > in f gx `demanding` s gx > (.||) f s g = \ x -> let gx = g x > in f gx `sparking` s gx > (-|) f s g = \ x -> let fx = f x > in g fx `demanding` s fx > (-||) f s g = \ x -> let fx = f x > in g fx `sparking` s fx ----------------------------------------------------------------------------- Strategy Instances and Functions ----------------------------------------------------------------------------- ----------------------------------------------------------------------------- Tuples ----------------------------------------------------------------------------- We currently support up to 9-tuples. If you need longer tuples you have to add the instance explicitly to your program. > instance (NFData a, NFData b) => NFData (a,b) where > rnf (x,y) = rnf x `seq` rnf y > instance (NFData a, NFData b, NFData c) => NFData (a,b,c) where > rnf (x,y,z) = rnf x `seq` rnf y `seq` rnf z > instance (NFData a, NFData b, NFData c, NFData d) => NFData (a,b,c,d) where > rnf (x1,x2,x3,x4) = rnf x1 `seq` > rnf x2 `seq` > rnf x3 `seq` > rnf x4 > -- code automatically inserted by `hwl-insert-NFData-n-tuple' > instance (NFData a1, NFData a2, NFData a3, NFData a4, NFData a5) => > NFData (a1, a2, a3, a4, a5) where > rnf (x1, x2, x3, x4, x5) = > rnf x1 `seq` > rnf x2 `seq` > rnf x3 `seq` > rnf x4 `seq` > rnf x5 > -- code automatically inserted by `hwl-insert-NFData-n-tuple' > instance (NFData a1, NFData a2, NFData a3, NFData a4, NFData a5, NFData a6) => > NFData (a1, a2, a3, a4, a5, a6) where > rnf (x1, x2, x3, x4, x5, x6) = > rnf x1 `seq` > rnf x2 `seq` > rnf x3 `seq` > rnf x4 `seq` > rnf x5 `seq` > rnf x6 > -- code automatically inserted by `hwl-insert-NFData-n-tuple' > instance (NFData a1, NFData a2, NFData a3, NFData a4, NFData a5, NFData a6, NFData a7) => > NFData (a1, a2, a3, a4, a5, a6, a7) where > rnf (x1, x2, x3, x4, x5, x6, x7) = > rnf x1 `seq` > rnf x2 `seq` > rnf x3 `seq` > rnf x4 `seq` > rnf x5 `seq` > rnf x6 `seq` > rnf x7 > -- code automatically inserted by `hwl-insert-NFData-n-tuple' > instance (NFData a1, NFData a2, NFData a3, NFData a4, NFData a5, NFData a6, NFData a7, NFData a8) => > NFData (a1, a2, a3, a4, a5, a6, a7, a8) where > rnf (x1, x2, x3, x4, x5, x6, x7, x8) = > rnf x1 `seq` > rnf x2 `seq` > rnf x3 `seq` > rnf x4 `seq` > rnf x5 `seq` > rnf x6 `seq` > rnf x7 `seq` > rnf x8 > -- code automatically inserted by `hwl-insert-NFData-n-tuple' > instance (NFData a1, NFData a2, NFData a3, NFData a4, NFData a5, NFData a6, NFData a7, NFData a8, NFData a9) => > NFData (a1, a2, a3, a4, a5, a6, a7, a8, a9) where > rnf (x1, x2, x3, x4, x5, x6, x7, x8, x9) = > rnf x1 `seq` > rnf x2 `seq` > rnf x3 `seq` > rnf x4 `seq` > rnf x5 `seq` > rnf x6 `seq` > rnf x7 `seq` > rnf x8 `seq` > rnf x9 > seqPair :: Strategy a -> Strategy b -> Strategy (a,b) > seqPair strata stratb (x,y) = strata x `seq` stratb y > parPair :: Strategy a -> Strategy b -> Strategy (a,b) > parPair strata stratb (x,y) = strata x `par` stratb y `par` () The reason for the second `par` is so that the strategy terminates quickly. This is important if the strategy is used as the 1st argument of a seq > seqTriple :: Strategy a -> Strategy b -> Strategy c -> Strategy (a,b,c) > seqTriple strata stratb stratc p@(x,y,z) = > strata x `seq` > stratb y `seq` > stratc z > parTriple :: Strategy a -> Strategy b -> Strategy c -> Strategy (a,b,c) > parTriple strata stratb stratc (x,y,z) = > strata x `par` > stratb y `par` > stratc z `par` > () ----------------------------------------------------------------------------- Numbers ----------------------------------------------------------------------------- Weak head normal form and normal form are identical for integers, so the default rnf is sufficient. > instance NFData Int > instance NFData Integer > instance NFData Float > instance NFData Double > instance NFDataIntegral Int > instance NFDataOrd Int Rational and complex numbers. ----------------------------------------------------------------------------- Characters ----------------------------------------------------------------------------- > instance NFData Char ----------------------------------------------------------------------------- Bools ----------------------------------------------------------------------------- > instance NFData Bool ----------------------------------------------------------------------------- Unit ----------------------------------------------------------------------------- > instance NFData () ----------------------------------------------------------------------------- Lists ---------------------------------------------------------------------------- > instance NFData a => NFData [a] where > rnf [] = () > rnf (x:xs) = rnf x `seq` rnf xs ---------------------------------------------------------------------------- Lists: Parallel Strategies ---------------------------------------------------------------------------- Applies a strategy to every element of a list in parallel > parList :: Strategy a -> Strategy [a] > parList strat [] = () > parList strat (x:xs) = strat x `par` (parList strat xs) Applies a strategy to the first n elements of a list in parallel > parListN :: (Integral b) => b -> Strategy a -> Strategy [a] > parListN n strat [] = () > parListN 0 strat xs = () > parListN n strat (x:xs) = strat x `par` (parListN (n-1) strat xs) Evaluates N elements of the spine of the argument list and applies `strat' to the Nth element (if there is one) in parallel with the result. e.g. parListNth 2 [e1, e2, e3] evaluates e2 > parListNth :: Int -> Strategy a -> Strategy [a] > parListNth n strat xs > | null rest = () > | otherwise = strat (head rest) `par` () > where > rest = drop n xs parListChunk sequentially applies a strategy to chunks (sub-sequences) of a list in parallel. Useful to increase grain size > parListChunk :: Int -> Strategy a -> Strategy [a] > parListChunk n strat [] = () > parListChunk n strat xs = seqListN n strat xs `par` > parListChunk n strat (drop n xs) parMap applies a function to each element of the argument list in parallel. The result of the function is evaluated using `strat' > parMap :: Strategy b -> (a -> b) -> [a] -> [b] > parMap strat f xs = map f xs `using` parList strat parFlatMap uses parMap to apply a list-valued function to each element of the argument list in parallel. The result of the function is evaluated using `strat' > parFlatMap :: Strategy [b] -> (a -> [b]) -> [a] -> [b] > parFlatMap strat f xs = concat (parMap strat f xs) parZipWith zips together two lists with a function z in parallel > parZipWith :: Strategy c -> (a -> b -> c) -> [a] -> [b] -> [c] > parZipWith strat z as bs = > zipWith z as bs `using` parList strat ---------------------------------------------------------------------------- Lists: Sequential Strategies ---------------------------------------------------------------------------- Sequentially applies a strategy to each element of a list > seqList :: Strategy a -> Strategy [a] > seqList strat [] = () > seqList strat (x:xs) = strat x `seq` (seqList strat xs) Sequentially applies a strategy to the first n elements of a list > seqListN :: (Integral a) => a -> Strategy b -> Strategy [b] > seqListN n strat [] = () > seqListN 0 strat xs = () > seqListN n strat (x:xs) = strat x `seq` (seqListN (n-1) strat xs) seqListNth applies a strategy to the Nth element of it's argument (if there is one) before returning the result. e.g. seqListNth 2 [e1, e2, e3] evaluates e2 > seqListNth :: Int -> Strategy b -> Strategy [b] > seqListNth n strat xs > | null rest = () > | otherwise = strat (head rest) > where > rest = drop n xs Parallel n-buffer function added for the revised version of the strategies paper. @parBuffer@ supersedes the older @fringeList@. It has the same semantics. > parBuffer :: Int -> Strategy a -> [a] -> [a] > parBuffer n s xs = > return xs (start n xs) > where > return (x:xs) (y:ys) = (x:return xs ys) `sparking` s y > return xs [] = xs > > start n [] = [] > start 0 ys = ys > start n (y:ys) = start (n-1) ys `sparking` s y fringeList implements a `rolling buffer' of length n, i.e.applies a strategy to the nth element of list when the head is demanded. More precisely: semantics: fringeList n s = id :: [b] -> [b] dynamic behaviour: evalutates the nth element of the list when the head is demanded. The idea is to provide a `rolling buffer' of length n. <> fringeList :: (Integral a) => a -> Strategy b -> [b] -> [b] <> fringeList n strat [] = [] <> fringeList n strat (r:rs) = <> seqListNth n strat rs `par` <> r:fringeList n strat rs