GHC provides two functions for controlling parallel execution, through the `Parallel' interface:
interface Parallel where infixr 0 `par` infixr 1 `seq` par :: a -> b -> b seq :: a -> b -> b
The expression `(x `par` y)' sparks the evaluation of `x' (to weak head normal form) and returns `y'. Sparks are queued for execution in FIFO order, but are not executed immediately. At the next heap allocation, the currently executing thread will yield control to the scheduler, and the scheduler will start a new thread (until reaching the active thread limit) for each spark which has not already been evaluated to WHNF.
The expression `(x `seq` y)' evaluates `x' to weak head normal form and then returns `y'. The `seq' primitive can be used to force evaluation of an expression beyond WHNF, or to impose a desired execution sequence for the evaluation of an expression.
For example, consider the following parallel version of our old nemesis, `nfib':
import Parallel nfib :: Int -> Int nfib n | n <= 1 = 1 | otherwise = par n1 (seq n2 (n1 + n2 + 1)) where n1 = nfib (n-1) n2 = nfib (n-2)
For values of `n' greater than 1, we use `par' to spark a thread to evaluate `nfib (n-1)', and then we use `seq' to force the parent thread to evaluate `nfib (n-2)' before going on to add together these two subexpressions. In this divide-and-conquer approach, we only spark a new thread for one branch of the computation (leaving the parent to evaluate the other branch). Also, we must use `seq' to ensure that the parent will evaluate `n2' before `n1' in the expression `(n1 + n2 + 1)'. It is not sufficient to reorder the expression as `(n2 + n1 + 1)', because the compiler may not generate code to evaluate the addends from left to right.