There's been a good deal of debate about parallel versus sequential
semantics on this list. As one of the pH (eager, parallel haskell)
implementors, I wanted to weigh in on a couple of issues, mostly
relating to eager versus lazy semantics.
Others have pointed out very nicely the distinction between parallel
semantics and a parallel implementation. In pH we perform
pattern-matching and boolean tests in a sequential fashion, even
though the items being tested are evaluated in parallel. Thus, we can
use a Haskell definition of or (||):
> True || _ = True
> False || True = True
> False || False = False
Again, note that because pH is eager the arguments are being evaluated
in parallel; only the final pattern matching is being done
sequentially (left to right).
Even this very slight loosening of Haskell semantics can cause
trouble, though. What is the value of the following expression when
xs==[]? How should it be implemented in an eager system?
null xs || head xs == 3 (A)
Clearly with lazy semantics this expression will be True; for eager
semantics our pattern matching again indicates a True result, but it's
less than clear what should become of the error produced by "head []".
Well, that's easy, you say, GHC allows us to catch errors; obviously
this is doable in other systems, and we can simply ignore bottom
values which are never referenced. But then what do we make of this
(again, xs==[])?
bottom _ = bottom ()
null xs || bottom () (B)
We might hope that (for example) the garbage collector will eventually
get rid of the nonterminating "bottom ()" computation, or that our
scheduler is fair, and that fairness will be enough for our system to
eventually eke out a meaningful result from the swath of useless
computations.
Note that the usual notion of parallel or gives us the most defined
possible semantics on both examples, and indeed would continue giving
a defined answer if the arguments were transposed (when haskell would
yield _|_ for both):
head xs == 3 || null xs (A')
bottom () || null xs (B')
Fundamentally, though, the semantic decisions we make have a strong
effect not only on the kind of programs we are able to write, but also
on the efficiency of our implementation:
* Adding eagerness requires a "parallel" execution model (even if the
parallelism is simulated by multitasking of some sort).
* Ignoring errors requires us to have a mechanism for catching and
recovering from those errors.
* Ignoring non-termination requires not only parallelism, but fair
scheduling---and a mechanism for killing parallel computations which
are no longer useful.
Often, these mechanisms are at odds with other aspects of our
implementation. For example, the programmer doesn't actually want a
parallel program to be fairly scheduled if resources are
limited---instead, work needed to obtain an answer should be performed
in preference to speculative computation. Indeed, it is my belief
that providing a fair schedule is fundamentally at odds with providing
an efficient schedule for Haskell programs.
For this reason, actual parallel implementations of Haskell invariably
_reduce_ the number of programs that will terminate with an answer.
Contrast this with Haskell + parallel or, which _increases_ the number
of programs which terminate with an answer. GpH (which is lazy and
explicitly parallel) requires the programmer to specify a parallel
evaluation strategy---only hand-scheduling seems to provide acceptable
performance. The chosen strategy may result in nontermination when
the original program produced an answer.
In pH, we deal with the matter by separating termination semantics
from value semantics. Our value domain still has a notion of
bottom---what does an erroneous or nonterminating computation return?
But we say that the meaning of a program fragment is always given
_modulo_error-free_termination_. For both the examples above, we
obtain the value "True" when xs==[]; however, both examples contain
computations which are either erroneous or non-terminating. Our
system (which does the scheduling for us in a hopefully efficient
manner) will print the error (A) or not terminate (B), and can choose
whether the result "True" happens to be returned as well. This choice
may vary from run to run, but the existence of an error (A) or
non-termination (B) will not.
Note that Id, the predecessor of pH, provided parallel and/or and
parallel pattern matching; however, program behavior was once again
defined modulo termination. This allowed pattern matching to
terminate quickly in some cases, but the "modulo termination" side
condition meant it didn't add measurable extra power, just a bit of
speed when one argument ran much faster than another.
-Jan-Willem Maessen
