Why doesn't Simon Marlow use 'force' in this example?

Learn
#1

I’m reading through Parallel and Concurrent Programming in Haskell and I find it super interesting (and practical). On page 32, he says:

[…] for example, to evaluate the pair (fib 35, fib 36) in parallel, we could write:
runEval (parPair (fib 35, fib 36))

In this case, parPair is implemented as such:

parPair :: Strategy (a, b)
parPair (a, b) = do
  a' <- rpar a
  b' <- rpar b
  return (a', b')

Notice that there is no force in the definition. Why doesn’t that lead to a very little amount of parallelism? On page 22 he even notes that “Not evaluating deeply enough is a common mistake when using rpar […]”.

#2

I don’t know the full context, but fib 35 and fib 36 are not deep structures, so presumably they don’t have to be forced deeply.

#3

I thought WHNF of fib 35 would only be evaluated to something like fib 34 + fib 33 in parallel and then evaluate the rest sequentially, but I might have to read up on what exactly a structure being deep means!

#4

The weak head normal form of types like Integer (and other primitive number types) is the same as the full normal form. So even if you just evaluate those to WHNF you will still fully evaluate them.

Examples of cases where WHNF differs from NF are function types and data structures like lists, maps, tuples, and most algebraic data types in general (with the exception of enumeration-like ADTs). As a concrete example take a tuple of two numbers:

(0 + 1, 1 + 1)

This is already in WHNF, which is more easily seen if we remove some syntactic sugar:

(,) (0 + 1) (1 + 1)

Note that the constructor (,) is in head position so the arguments don’t get evaluated further.

While the NF is:

(1, 2)
-- or without sugar
(,) 1 2
1 Like
#5

Yeah, that makes sense. I hadn’t recognized the correlation between WHNF and the constructor in head position! So… is fib 35 going to be fully evaluated because its type is Int?

#6

Almost, it’s type is actually Integer, which is the arbitrary precision variant, but that has the same property, namely that it has no constructors, or you could theoretically see each integer as its own constructor. So the only constructor that can be in head position is the fully evaluated integer itself. In the intermediate steps there is always a function (not a constructor!) at the head position, e.g. (+) in your example:

(+) (fib 34) (fib 33)
2 Likes
#7

Oh, right right right! Thanks for emphasizing function vs. constructor! This goes very much hand in hand with the wiki:

An expression is in weak head normal form (WHNF), if it is either:

  • a constructor (eventually applied to arguments)
  • a built-in function applied to too few arguments
  • or a lambda abstraction

Thanks for your explanation!

1 Like