At 8:02 pm +0100 28/9/99, Adrian Hey wrote:
>On Mon 27 Sep, Kevin Hammond wrote:
>> It's entirely possible to have a parallel
>> implementation of a language
>> defining serial pattern matching [**], but in which the actual execution is
>> parallel.
>
>Yes, I think I understand. You mean the implementation is parallel for
>efficiency reasons but it still behaves as if it were serial.
Yes, that's correct. The result is the same as with sequential execution
(including perhaps
_|_) but the evaluation order is different. This is also what allows
strictness analysis to
be exploited: strict arguments can be evaluated in any order, since they
will eventually be
required -- if they turn out to be undefined, then the entire computation
must be undefined.
>> 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?
>
>f 0 0 = 1
>
>> What if I change the order of the rules?
>
>You get a different function.
In Haskell, I do, but there are systems where this isn't the case!
>> 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
>
>No, I like the current rules for dealing with overlapping patterns just fine.
>But there's a difference between the rules used to disambiguate overlapping
>patterns in the 'syntactic sugar', (which are conceptually sequential,
>serial or whatever) and the semantics of the resulting case expressions
>(which really are serial).
Serial, but still not sequential! That is, they define an outcome but not
an order (unless
you're referring to the operational semantics of the STG machine). The
compiler will
rearrange the order of case-expressions if it's safe to do so, for example.
>By this I mean you could keep the current rules for disambiguation, but
>do the resulting un-abiguious pattern matching with something other than
>case expressions.
Or just reorder the case expressions (or do them in parallel) if you like,
and if it's safe.
>Current Haskell semantics specify that when reducing am expression of form..
> case e of ..
>e gets reduced. (The definition of seq relies on this if I remember).
>So, for example, the transformation..
> (case e of
> True -> e'
> False -> e') = e' is not allowed by Haskell semantics.
>So if e=_|_, case e of .. = _|_.
>
>So I don't understand how you can say 'Absolutely NOT'.
>Is the behaviour of && unspecified with Haskell as it is?
In a non-strict context, the *behaviour* is as you say below. In a strict
context,
it need not be (though the *value* will be the same!).
>I think it's..
> True && True = True
> True && False = False
> False && True = False
> False && False = False
> _|_ && True = _|_
> _|_ && False = _|_
> True && _|_ = _|_
> False && _|_ = False
> _|_ && _|_ = _|_
>
>So (a && b) = (b && a) is invalid
Not exactly: it's valid if and only if both a and b are needed (in which case
False && _|_ = _|_, so the asymmetry is eliminated)! This is the basis for
a number of theorems.
>wheras with what I called 'concurrent non-strict semantics' it should be..
> True && True = True
> True && False = False
> False && True = False
> False && False = False
> _|_ && True = _|_
> _|_ && False = False -- This is different
> True && _|_ = _|_
> False && _|_ = False
> _|_ && _|_ = _|_
I think this is called 'parallel and' in the literature? It's one of
several interesting ways to define the semantics of &&,
and is used in e.g. some logic languages.
The problem is (as I think Alexander has pointed out) that in Haskell you
can't tell
whether an expression will evaluate to _|_ without actually evaluating it
(at which point it's too
late, since _|_ is not necessarily a value that can be matched -- it might
be non-termination or
an unhandled exception, for example). If it's already evaluated, you're OK
of course (we use this trick in a paper that deals
with parallel databases -- a variant of Friedman and Wise 'if' -- bibtex
attached). A secondary problem is that
you lose the straightforward translation from pattern matching into
lambda-calculus.
The semantics of _|_ is fundamental to non-strict languages (and isn't just
operational!).
Best Wishes,
Kevin
@inproceedings{AHPT93,
author = "Akerholt, G. and Hammond, K. and Peyton~Jones, S.L. and
Trinder, P.W.",
title = "Processing Transactions on {GRIP}: a Parallel Graph Reducer",
booktitle = "Proceedings of {PARLE~'93} -- Parallel Architectures and
Reduction Languages Europe, M{\"{u}}nchen, Germany",
year = 1993,
publisher = "Springer-Verlag",
volume = "LNCS~694",
pages = "634--647"
}
----------
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.
