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) Here you need BOTH type signatures, since otherwise the one stated for p is too general (needs polymorphic recursion). Maybe it's obvious from the two type variables that sharing will be lost-- but the example below only has one, and is still exponential time under Hugs (GHC optimises it to linear). fib2 n = fst (fib2' n) fib2' :: Num a => Integer -> (a,a) fib2' 0 = (0,1) fib2' n = (snd p,fst p+snd p) where p :: Num a => (a,a) p = fib2' (n-1) In this case, provided you write the type signature on fib2' (thus permitting polymorphic recursion), then the type signature I wrote on p is the one that would be inferred, were it not for the M-R--and thus this program risks running in exponential time. Same applies to fib' above: if you write the type signature on fib', then but for the M-R, the type signature on p is the one that would be inferred, and you get exponential time behaviour. 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? John
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. I still think removing the M-R and issuing a warning when there's a potential loss of sharing would be acceptable. -- Lennart
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
On Mon, 30 Jan 2006, John Hughes wrote:
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.
Insist the warnings be available, don't require them to be in the standard warning level? -- flippa@flippac.org The task of the academic is not to scale great intellectual mountains, but to flatten them.
Philippa Cowderoy wrote:
On Mon, 30 Jan 2006, John Hughes wrote:
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.
Insist the warnings be available, don't require them to be in the standard warning level?
But then beginners will, without warning, sometimes find their code running unreasonably slowly. That isn't, really, any better. Too many will just conclude "Haskell is unreasonably slow" and abandon it. John
On Mon, 30 Jan 2006, John Hughes wrote:
Insist the warnings be available, don't require them to be in the standard warning level?
But then beginners will, without warning, sometimes find their code running unreasonably slowly. That isn't, really, any better. Too many will just conclude "Haskell is unreasonably slow" and abandon it.
I can't speak for anyone else, but I certainly had a poke around the bit in the GHC docs on making stuff go faster (being not entirely clueless I found the bit about float not being specialised to be patronising - I happened to have audio in mind where float's appropriate and saves cache). This particular student was also happy to stop thinking about speed so much for once - and with a gamedev community background I'm more interested in it than most, who were happy with Java at a point when it was still much slower than C++. -- flippa@flippac.org Ivanova is always right. I will listen to Ivanova. I will not ignore Ivanova's recomendations. Ivanova is God. And, if this ever happens again, Ivanova will personally rip your lungs out!
Quoting John Hughes
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
lennart@augustsson.net writes:
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.
I can confirm that nhc98 (and hence yhc) still does not implement the M-R. I haven't noticed any particular performance problems in code compiled by nhc98 that were down to a consequent loss of sharing. (But I can't claim to have explicitly looked.) But as Lennart says, you do get occasional type errors which mean you need to restructure your code. Almost always, these are local bindings, e.g.: Context required in LHS pattern is an error emitted for code like: do (x,y) <- something complicated and numeric ... and the fix is do xy <- something complicated and numeric let x = fst xy y = snd xy ... As I recall, there were about 4-5 of these I needed to fix in the entire nofib suite. Regards, Malcolm
Quoting Malcolm Wallace
lennart@augustsson.net writes:
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.
I can confirm that nhc98 (and hence yhc) still does not implement the M-R. I haven't noticed any particular performance problems in code compiled by nhc98 that were down to a consequent loss of sharing. (But I can't claim to have explicitly looked.) But as Lennart says, you do get occasional type errors which mean you need to restructure your code. Almost always, these are local bindings, e.g.:
Context required in LHS pattern
is an error emitted for code like:
do (x,y) <- something complicated and numeric ...
and the fix is
do xy <- something complicated and numeric let x = fst xy y = snd xy ...
As I recall, there were about 4-5 of these I needed to fix in the entire nofib suite.
The changes I had to make were almost all simpler than that. I just had to add a few type signatures. (And thanks for supporting evidence from nhc. :) -- Lennart
participants (5)
-
John Hughes -
Lennart Augustsson -
lennart＠augustsson.net
-
Malcolm Wallace -
Philippa Cowderoy