The dreaded M-R

[lennart at augustsson.net]

Quoting John Hughes <rjmh at cs.chalmers.se>:

> Lennart Augustsson wrote:
>
>> John Hughes wrote:
>>
>>> An example where loss of sharing leads to exponential time:
>>>
>>> fib n = fst (fib' n)
>>>
>>> fib' :: (Num a, Num b) => Integer -> (a,b)
>>> fib' 0 = (0,1)
>>> fib' n = (snd p,fst p+snd p)
>>>  where
>>>    p :: (Num a, Num b) => (a,b)
>>>    p = fib' (n-1)
>>>
>>> It would be undesirable for adding a type signature to a function 
>>> (such as fib'
>>> above) to risk making its performance exponentially worse, because of
>>> consequential loss of sharing in a binding somewhere else. Wouldn't it?
>>
>>
>> I don't agree in this case.  You are asking for something rather strange
>> when you put that type signature on fib'.  I also noticed that to give
>> a "convincing" example you picked something with polyporphic recursion.
>> P-R wasn't in Haskell at the time the M-R was added (if memory serves
>> me).  So there must be other examples.
>
> True. I don't remember my original example.
>
>>
>> I still think removing the M-R and issuing a warning when there's a
>> potential loss of sharing would be acceptable.
>>
>>
> Wouldn't there be quite a lot of warnings?
>
> I really think we have to remember beginners' problems here. I know 
> noone reading this discussion is
> one, but without beginners, there will be no growth in the Haskell 
> community. If we did as you suggest,
> then beginners would be confronted by yet another kind of 
> incomprehensible message--and I fear it
> would be hard to report that x=e risks evaluating e many times, in a 
> way that would be viewed as positive
> by someone still trying to understand how Haskell works at all.
>
> John
>

I am thinking of the beginner.  I would hate to explain what the
difference between '=' and ':=' is and when to use one or the other.
I think that's a wart as ugly as the M-R.

As for there being many warnings, we don't really know, do we?
I'm only suggesting a warning when there's a potential loss of
sharing, not in general.  In my experience it's very rare to
have the M-R kick in at the top level; it's almost always in
local definitions.  And for local definitions you can see all uses
of a binding and handle it accordingly.  Local bindings are very
rarely used polymorphically.

Nhc didn't use to implement the M-R (maybe it does now).  When
porting code to nhc this caused a few code changes.  Perhaps
10 lines out of 10000 when I tried the Bluespec compiler.  So
my gut feeling is that the M-R is a rare beast in practise.

    -- Lennart