Haskell: Why was `par` defined the way it was?

Question

par is declared as:

par  :: a -> b -> b

Notice, that argument one is thrown away. In order to use par you need to play tricks like using the same expression multiple times.

If its purpose is to execute a and b in parallel, why wasn't it defined like this?:

par  :: (a, b) -> (a, b)

Taking a tuple of (unevaluated) expressions and returning the same expressions - while they are potentially being materialized on background threads.

It seems the latter model is simpler than the former. Why was the design chosen that way?

Northing

I find your version more difficult to think about. The pair you pass to par might be unevaluated. Who evaluates it and when? – Ethical

Answer 1

In the former, you can easily spark more than two computations,

c1 `par` c2 `par` c3 `par` c4 `pseq` something c1 c2 c3 c4

which would be rather cumbersome in the latter.

Voracity

The latter could be overloaded for up to 8 args and have a list version, too. – Northing

Notice, that argument one is thrown away which means only c4 from your example will survive (without further tricks). – Northing

How would you overload it? class par a where and instances for up to 8-tuples? Ugh. – Voracity

The trick is that you use the results of the sparked computations in the final value, which gets a pseq too. – Voracity

@Northing : haskell 'par' and 'pseq' features are tightly coupled to the evaluation model. You should have a look at the "lazy evaluation with sharing" model, as well as the garbage collection model. – Gillead

So I guess you could say that the Haskell compiler needs to recognize that the expression c1 is used multiple times and allocate a single "lazy evaluation slot" for both usages? If it didn't allocate one slot only, one copy would be calculated in parallel but thrown away. – Northing

Answer 2

The tupled version you suggest can be found as parTuple2 in Control.Parallel.Strategies, with the type:

evalTuple2 :: Strategy a -> Strategy b -> Strategy (a, b)

As for why par was designed that way, par is 'higher level', as chapter 24 of Real World Haskell discusses, where they parallelize a quicksort:

These changes to our code are remarkable for all the things we have not needed to say.

• How many cores to use.
• What threads do to communicate with each other.
• How to divide up work among the available cores.
• Which data are shared between threads, and which are private.
• How to determine when all the participants are finished.

In A Monad for Deterministic Parallelism, Marlow, Newton, and Peyton Jones write:

The par operator is an attractive language design because it capitalises on the overlap between lazy evaluation and futures. To implement lazy evaluation we must have a representation for expressions which are not yet evaluated but whose value may later be demanded; and similarly a future is a computation whose value is being evaluated in parallel and which we may wait for. Hence, par was conceived as a mechanism for annotating a lazy computation as being potentially profitable to evaluate in parallel, in effect turning a lazy computation into a future

Pendulous