Understanding Eval Monad's `rpar`

Question

Looking at the following example from Parallel and Concurrent Programming in Haskell:

main = do
  [n] <- getArgs
  let test = [test1,test2,test3,test4] !! (read n - 1) 
  t0 <- getCurrentTime
  r <- evaluate (runEval test)
  printTimeSince t0
  print r
  printTimeSince t0


test1 = do
  x <- rpar (fib 36)
  y <- rpar (fib 35)
  return (x,y)

The book shows its compilation:

 $ ghc -O2 rpar.hs -threaded

And then running the above test:

$ ./rpar 1 +RTS -N2
time: 0.00s
(24157817,14930352)
time: 0.83s

If I understand correctly, the Eval Monad (using rpar) results in both fib 36 and fib 35 being computed in parallel.

Does the actual work, i.e. computing the function fib ... occur when calling (runEval test)? Or perhaps evaluate ... is required? Or, finally, perhaps it gets computed when calling print r to evaluate it entirely?

It's not clear to me when the actual work gets performed for rpar.

Answer 1

Here's my guess, but I can't seem to replicate this on my laptop, too many imports I'd have to get from cabal.

test1 = do
  x <- rpar (fib 36)
  y <- rpar (fib 35)
  return (x,y)

In this, you spark the evaluation of (fib 36) and (fib 35) in parallel, but you don't wait for them - you just return (x,y) immediately, while x and y are still evaluating. Then, we you get to print r, you are forced to wait until x and y finish evaluating.

In theory, the following code should force test1 to wait until x and y have finished evaluating before returning them.

test1 = do
  x <- rpar (fib 36)
  y <- rpar (fib 35)
  rseq x
  rseq y
  return (x,y)

Then, running this should give you approximately

$ ./rpar 1 +RTS -N2
time: 0.83s
(24157817,14930352)
time: 0.83s

hopefully...

EDIT

Finally got back to my machine, replicated the condition, and my suggested code gives the expected result. However, the OP raises another good question: if evaluate only evaluates to the WHNF, why does it even end up doing work before print is called?

The answer is in the monad definition of Control.Parallel.Strategies - in other words, it isn't evaluate that pushes the evaluation of x and y, but runEval. The Eval monad is strict in the first argument: in x >>= f it will evaluate x (please check out this question before continuing). Then, de-sugaring test1 gives:

test1 = (rpar (fib 36)) >>= (\x -> 
        (rpar (fib 35)) >>= (\y ->
        (rseq x)        >>= (\_ ->
        (rseq y)        >>= (\_ ->
        return (x,y)))))

Then, since rpar only "sparks" evaluation, it uses par (which begins the evaluation of the first argument but immediately returns the second) and immediately returns Done, however, rseq (like seq, but strict only in the first argument) does not return Done until its argument is actually evaluated (to WHNF). Hence, without the rseq calls, you have know that x and y have begun to be evaluated but no assurance that they have finished, but with those calls, you know both x and y are also evaluated before return is called on them.