|Eval is a Monad that makes it easier to define parallel strategies|
|a function that embodies a parallel evaluation strategy. The function traverses (parts of) its argument, evaluating subexpressions in parallel or in sequence|
|sparks its argument (for evaluation in parallel)|
|evaluates its argument to weak head normal form|
|evaluates the entire structure of its argument, reducing it to normal form, before returning the argument itself. It is provided by the Control.DeepSeq module|
Simon Marlow's book, Concurrent and Parallel Programming in Haskell, is outstanding and covers a multitude of concepts. It is also very much accessible for even the newest Haskell programmer. It is highly recommended and available in PDF or online for free.
Parallel vs Concurrent
Simon Marlow puts it best:
A parallel program is one that uses a multiplicity of computational hardware (e.g., several processor cores) to perform a computation more quickly. The aim is to arrive at the answer earlier, by delegating different parts of the computation to different processors that execute at the same time.
By contrast, concurrency is a program-structuring technique in which there are multiple threads of control. Conceptually, the threads of control execute “at the same time”; that is, the user sees their effects interleaved. Whether they actually execute at the same time or not is an implementation detail; a concurrent program can execute on a single processor through interleaved execution or on multiple physical processors.
Weak Head Normal Form
It's important to be aware of how lazy-evaluation works. The first section of this chapter will give a strong introduction into WHNF and how this relates to parallel and concurrent programming.
Parallelism in Haskell can be expressed using the
Eval Monad from
Control.Parallel.Strategies, using the
rseq functions (among others).
f1 :: [Int] f1 = [1..100000000] f2 :: [Int] f2 = [1..200000000] main = runEval $ do a <- rpar (f1) -- this'll take a while... b <- rpar (f2) -- this'll take a while and then some... return (a,b)
main above will execute and "return" immediately, while the two values,
b are computed in the background through
Note: ensure you compile with
-threaded for parallel execution to occur.
rpar :: Strategy a executes the given strategy (recall:
type Strategy a = a -> Eval a) in parallel:
import Control.Concurrent import Control.DeepSeq import Control.Parallel.Strategies import Data.List.Ordered main = loop where loop = do putStrLn "Enter a number" n <- getLine let lim = read n :: Int hf = quot lim 2 result = runEval $ do -- we split the computation in half, so we can concurrently calculate primes as <- rpar (force (primesBtwn 2 hf)) bs <- rpar (force (primesBtwn (hf + 1) lim)) return (as ++ bs) forkIO $ putStrLn ("\nPrimes are: " ++ (show result) ++ " for " ++ n ++ "\n") loop -- Compute primes between two integers -- Deliberately inefficient for demonstration purposes primesBtwn n m = eratos [n..m] where eratos  =  eratos (p:xs) = p : eratos (xs `minus` [p, p+p..])
Running this will demonstrate the concurrent behaviour:
Enter a number 12 Enter a number Primes are: [2,3,5,7,8,9,10,11,12] for 12 100 Enter a number Primes are: [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100] for 100 200000000 Enter a number -- waiting for 200000000 200 Enter a number Primes are: [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116,117,118,119,120,121,122,123,124,125,126,127,128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,144,145,146,147,148,149,150,151,152,153,154,155,156,157,158,159,160,161,162,163,164,165,166,167,168,169,170,171,172,173,174,175,176,177,178,179,180,181,182,183,184,185,186,187,188,189,190,191,192,193,194,195,196,197,198,199,200] for 200 -- still waiting for 200000000
We can use
rseq :: Strategy a to force an argument to Weak Head Normal Form:
f1 :: [Int] f1 = [1..100000000] f2 :: [Int] f2 = [1..200000000] main = runEval $ do a <- rpar (f1) -- this'll take a while... b <- rpar (f2) -- this'll take a while and then some... rseq a return (a,b)
This subtly changes the semantics of the
rpar example; whereas the latter would return immediately whilst computing the values in the background, this example will wait until
a can be evaluated to WHNF.