compilation of pattern-matching?

[Claus Reinke]

>So a first comment on this.  I spoke too soon, ghc clearly has a bug here.
>It shouldn't reorder those matches against literals like that.
>I suggest you report that bug, because, as you say, it violates the H98 report.

It would be nice if we could first reach a common understanding, so
that I can actually report the right problem, not just isolated symptoms.

>But I don't think that bug at all affects the function you had in your
>original email.

The argument goes like this:

- Haskell does prescribe the order in which patterns are matched
- Haskell does permit alternative implementations if they respect
    certain equations; in other words, there is a proof obligation
    associated with things like reordering patterns
- for types like 'data AB = A | B', we know that a successful match
    for 'A' implies a failing match for 'B', and vice-versa
- disregarding performance (which the language definition does
    not talk about), we therefore know that in 'case e of A->a;B->b',
    we don't need to match for both 'A' and 'B'; instead, we can 
    either match for 'A' and enter 'a' on success and 'b' on failure,
    or match for 'B' and enter 'b' on success and 'a' on failure
- another view of this is that 'not isB' is actually the same as 'isA',
    so we're matching for both in one test
- so, if we want to, we can fulfill the proof obligation involved 
    with reordering the patterns, or we can argue that by matching
    for 'B', we are actually matching for 'A' as well

So far, we have:

- pattern order does matter, by language definition
- GHC can nevertheless reorder patterns where it can prove 
    that this isn't observable

You are right that this doesn't help my performance argument,
as performance issues are outside the language definition (not
observable in the language definition sense). It was merely an 
answer to the vehement claims that pattern order is irrelevant.

And it has practical implications, too: the proof obligations are
getting harder to fulfill as pattern-match expressiveness improves.

For Haskell'98, we can't reorder: guards, overlapping patterns,
numeric literals, (others?). For GHC Haskell, we also can't reorder: 
view patterns, string literals (IsString/fromString), quasiquotes?, .. . 
And the list keeps growing, as DSL authors want IsBool/fromBool, 
container-library authors want IsList/fromList, etc. 

In other words, this

|It's not that GHC deliberately re-orders case alternatives, 
|it's that it doesn't deliberately not do it.

no longer is a safe default strategy (actually, it never was, as
the bug shows;-). Neither is sorting patterns by constructor tag,
as seems to happen on the way to Core.

GHC needs to consider every individual case before being lax 
about pattern order, and the result of that consideration might 
change over time: in Haskell'98, []/: patterns can be reordered 
for [a], in GHC Haskell, []/:. patterns can be reordered for [a], 
as long as a/=Char, in GHC Haskell with an IsList class, []/: 
patterns can not be reordered in general.

This is independent of performance considerations, just a
consequence of the language definition, and our abilities to
observe deviations from the prescribed sequential order.

Claus