compilation of pattern-matching?

[Simon Marlow]

Lennart Augustsson wrote:
> I find this "reordering" discussion somewhat nonsensical.
> Haskell specifies top-to-botton, left-to-right matching.
> This specifies exactly which tests that have to be made and in what order,
> and ghc does exactly those and in the correct order.
> 
> One can have a perception that when there are multiple arms in a case
> decided by a single test,
> then the first arm should somehow be reached quicker than the second one etc
> But that is something that the Haskell standard has never promised,
> nor has any compiler ever promised this.
> And to me such a perception is counter-intuitive; Haskell is about
> specifying functions abstractly so order should only matter when it's
> a matter of semantics.
> 
> On the other hand, adding some kind of pragma that indicates the
> likelyhood of a branch seems quite sensible to me.

I completely agree.  I think in an effort to be succinct I may have 
accidentally given the impression that I thought the ordering of case 
branches in Core mattered for some reason.  I don't think that at all, I 
was just trying to explain why it would be difficult to make ordering 
meaningful.

Cheers,
	Simon


>   -- Lennart
> 
> On Thu, Mar 26, 2009 at 9:09 AM, Simon Marlow <marlowsd at gmail.com> wrote:
>> Claus Reinke wrote:
>>
>>> Strange. I don't think it is my idea (older implementations
>>> used to work that way, and iirc, it also matches what Prolog
>>> systems used to do), and I didn't think it was anything but
>>> straightforward to avoid case transformations unless there
>>> is a clear benefit, so I doubt there is a useful paper in there
>>> (also, I can't afford to plan that far ahead atm).
>>> What is the benefit of changing the ordering (not just joining paths to
>>> avoid redundant tests, but actually modifying the order of tests, to sort by
>>> their order in the data type declaration)? Is there any documentation of
>>> these case transformations that I could look up?
>> It's not that GHC deliberately re-orders case alternatives, it's that it
>> doesn't deliberately not do it.
>>
>> That's quite an important difference.  To check whether case alternatives
>> ever get reordered, we'd have to look at the whole compiler.  It's a new
>> constraint on which transformations are valid, and global constraints should
>> not be added lightly.  I some kind of annotation is a much more promising
>> avenue to explore.
>>
>> Cheers,
>>        Simon
>>
>> _______________________________________________
>> Glasgow-haskell-users mailing list
>> Glasgow-haskell-users at haskell.org
>> http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
>>