The dreaded M-R
lennart at augustsson.net
lennart at augustsson.net
Mon Jan 30 09:20:49 EST 2006
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)
>>> 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.
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.
More information about the Haskell-prime