At 1:08 pm +0100 28/9/99, Adrian Hey wrote:
>So, I guess the answer is.. Yes, we do need to let such operational
>issues muddy the waters. What worries me here is that there might be
>some unjustifiable assumptions about the nature of the machine which is
>performing those operations. In particular by talking about things
>like 'reduction order' and 'order of pattern matching' aren't we
>assuming a sequential machine.
Absolutely NOT (at least for pattern-matching, and note that Haskell is
non-strict rather
than normal-order!). Making Haskell sequential would have serious
implications on my research!!
This is the semantic distinction between sequentiality and serialism [*] --
serialism simply defines a final ordering of operations, whereas
sequentiality implies
a total ordering. It's entirely possible to have a parallel
implementation of a language
defining serial pattern matching [**], but in which the actual execution is
parallel.
The trick is not to be over-restrictive in defining the language semantics
(so a non-strict
semantics permits *some* parallel implementations). Shameless plug: the
forthcoming book that I edited
with Greg Michaelson ("Research Directions in Parallel Functional
Programming", Springer-Verlag)
tries hard to separate these high-level and behavioural semantics in a
parallel context.
Of course, depending on your perspective, a fully parallel semantics for
e.g. pattern matching may be better,
but it can make programs less intuitive or less compact. For example, given:
f 0 n = 1
f n 0 = 2
f m n = 3
What is f 0 0? What if I change the order of the rules? Do you really
want to have to write:
f m n | m == 0 && n != 0 = 1
| m != 0 && n == 0 = 2
| m != 0 && n != 0 = 3
Now you also have to check completeness of the rule set... What about
fully overlapping rules (if you extend the example to
3 arguments, there is NO correct sequential execution order, if _|_ can
occur in some position)? Do you want an equivalence with sequential 'if'?
What about 'otherwise' in guards/conditions if not? Shouldn't it be
possible to translate a single match into a series of pattern matches?
[I had some fun with a very sophisticated parallel pattern matching
language in the past! The problems are soluble,
but not necessarily in a way that most people think is nice.]
Standard disclaimers apply...
Regards,
Kevin
[*] Note that use of terminology does vary in the literature, since
there is some confusion about
these concepts! Many people say "sequential" when they mean
"serial", and there are
even some formal uses on these lines! Please accept my
definitions :-)
[**] or even I/O -- which is quite clever, but permissible in Haskell
1.4 for non-overlapping computations
[exceptions are the biggest problem, haven't checked the latest
definition carefully
enough to be 100% sure that this still works -- I hope it does]!
----------
Division of Computer Science, Tel: +44-1334 463241 (Direct)
School of Mathematical Fax: +44-1334 463278
and Computational Sciences, URL:
http://www.dcs.st-and.ac.uk/~kh/kh.html
University of St. Andrews, Fife, KY16 9SS.
