I have read in the History of Haskell, that originally 'seq' should be a method of a type class, that can be automatically derived by a 'deriving' clause. It was also mentioned that this clean solution was dropped because of particular experiences with developing a parser. However the arguments appeared to me, like these were problems of debugging. I think that hacks are ok for debugging, such as dynamically finding a Show method for a message for 'error', although no Show constraint was given in the type signature. But I think that hacks are not ok for regular programming. In the History of Haskell it is told that the hack of making 'seq' not a member of a type class leads to invalid fusion optimization. While it is not possible to get rid of 'seq' anymore, wouldn't it be feasible to define a new type class with a new 'seq' - maybe just a new module, from where I can import the new 'seq' instead of the one from Prelude? This would also allow us to handle cases like this one: When I have a datatype like data T = A | B | C and I use 'seq' for it a lot, and once I have to switch to data T = Cons Int S data S = A | B | C and I like that 'seq' on T is strict both on Cons and on the constructors of S, this would be possible using a custom instance Seq T. Actually in stream-fusion:Data.Stream I found such a class, called Unlifted. How about moving this into a separate package? class Unlifted a where -- | This expose function needs to be called in folds/loops that consume -- streams to expose the structure of the stream state to the simplifier -- In particular, to SpecConstr. -- expose :: a -> b -> b expose = seq -- | This makes GHC's optimiser happier; it sometimes produces really bad -- code for single-method dictionaries -- unlifted_dummy :: a unlifted_dummy = error "unlifted_dummy"
Henning,
I have read in the History of Haskell, that originally 'seq' should be a method of a type class, that can be automatically derived by a 'deriving' clause. It was also mentioned that this clean solution was dropped because of particular experiences with developing a parser. However the arguments appeared to me, like these were problems of debugging.
If I understood it correctly, the problem was more general than just debugging. Every introduction of seq in a function could result in the requirement to also adapt the type signatures of calling functions. What wasn't understood by then is that making a seq a type-class method is not enough to recover parametricity, which was the goal. This is explained in a recent paper by Daniel Seidel and Janis Voigtlaender: Daniel Seidel and Janis Voigtlaender. Taming selective strictness. In Stefan Fischer, Erik Maehle, and Ruediger Reischuk, editors, INFORMATIK 2009 – Im Focus das Leben, Beitraege der 39. Jahrestagung der Gesellschaft fuer Informatik e.V. (GI), 28. September – 2. Oktober, in Luebeck, volume 154 of Lecture Notes in Informatics, pages 2916–2930. GI, 2009. http://www.iai.uni-bonn.de/~jv/atps09.pdf Cheers, Stefan
On Fri, 6 Nov 2009, Stefan Holdermans wrote:
Henning,
I have read in the History of Haskell, that originally 'seq' should be a method of a type class, that can be automatically derived by a 'deriving' clause. It was also mentioned that this clean solution was dropped because of particular experiences with developing a parser. However the arguments appeared to me, like these were problems of debugging.
If I understood it correctly, the problem was more general than just debugging. Every introduction of seq in a function could result in the requirement to also adapt the type signatures of calling functions.
Sure, but why was this a problem? Because they had to re-arrange a lot, and had to change the signature each time. But once that re-arrangement settles, it would be nice to have the Seq type constraint, right?
What wasn't understood by then is that making a seq a type-class method is not enough to recover parametricity, which was the goal. This is explained in a recent paper by Daniel Seidel and Janis Voigtlaender:
Daniel Seidel and Janis Voigtlaender. Taming selective strictness.
I'll have a look into it. Thanks for the hint!
Henning,
If I understood it correctly, the problem was more general than just debugging. Every introduction of seq in a function could result in the requirement to also adapt the type signatures of calling functions.
Sure, but why was this a problem? Because they had to re-arrange a lot, and had to change the signature each time. But once that re- arrangement settles, it would be nice to have the Seq type constraint, right?
I cannot tell whether *I* would find it problematic in practice. Hudak et al. write: "However, the limitations of this solution soon became apparent. Inspired by the Fox project at CMU, two of Hughes’s students implemented a TCP/IP stack in Haskell, making heavy use of polymorphism in the different layers. Their code turned out to contain serious space leaks, which they attempted to fix using seq. But whenever they inserted a call of seq on a type variable, the type signature of the enclosing function changed to require an Eval instance for that variable—just as the designers of Haskell 1.3 intended. But often, the type signatures of very many functions changed as a consequence of a single seq. This would not have mattered if the type signatures were inferred by the compiler—but the students had written them explicitly in their code. Moreover, they had done so not from choice, but because Haskell’s monomorphism restriction required type signatures on these particular definitions [...]. As a result, each insertion of a seq became a nightmare, requiring repeated compilations to find affected type signatures and manual correction of each one. Since space debugging is to some extent a question of trial and error, the students needed to insert and remove calls of seq time and time again. In the end they were forced to conclude that fixing their space leaks was simply not feasible in the time available to complete the project—not because they were hard to find, but because making the necessary corrections was simply too heavyweight. This experience provided ammunition for the eventual removal of class Eval in Haskell 98." Cheers, Stefan
I always thought that story was a bit unfortunate -- mostly because I don't
believe a good solution emerged. I also find it odd that they felt the need
to continually _remove_ Eval annotations. Leaving an unused extraneous Eval
annotation in place should be mostly harmless, An extra dictionary being
passed around here or there shouldn't destroy performance too badly -- you
only need to pass them in when you are polymorphic in the argument type, and
how often is your code really polymorphic _in something you want to
arbitrarily seq_ in a performance sensitive part of your TCP/IP stack?
Asking to seq a polymorphic argument these days is generally taken as a sign
that you are sprinkling seq's around without understanding why. We have
strategies now for a reason.
-Edward Kmett
On Fri, Nov 6, 2009 at 1:38 AM, Stefan Holdermans
Henning,
If I understood it correctly, the problem was more general than just
debugging. Every introduction of seq in a function could result in the requirement to also adapt the type signatures of calling functions.
Sure, but why was this a problem? Because they had to re-arrange a lot,
and had to change the signature each time. But once that re-arrangement settles, it would be nice to have the Seq type constraint, right?
I cannot tell whether *I* would find it problematic in practice. Hudak et al. write:
"However, the limitations of this solution soon became apparent. Inspired by the Fox project at CMU, two of Hughes’s students implemented a TCP/IP stack in Haskell, making heavy use of polymorphism in the different layers. Their code turned out to contain serious space leaks, which they attempted to fix using seq. But whenever they inserted a call of seq on a type variable, the type signature of the enclosing function changed to require an Eval instance for that variable—just as the designers of Haskell 1.3 intended. But often, the type signatures of very many functions changed as a consequence of a single seq. This would not have mattered if the type signatures were inferred by the compiler—but the students had written them explicitly in their code. Moreover, they had done so not from choice, but because Haskell’s monomorphism restriction required type signatures on these particular definitions [...]. As a result, each insertion of a seq became a nightmare, requiring repeated compilations to find affected type signatures and manual correction of each one. Since space debugging is to some extent a question of trial and error, the students needed to insert and remove calls of seq time and time again. In the end they were forced to conclude that fixing their space leaks was simply not feasible in the time available to complete the project—not because they were hard to find, but because making the necessary corrections was simply too heavyweight. This experience provided ammunition for the eventual removal of class Eval in Haskell 98."
Cheers,
Stefan_______________________________________________
Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries
On Fri, 6 Nov 2009, Stefan Holdermans wrote:
Henning,
Sure, but why was this a problem? Because they had to re-arrange a lot, and had to change the signature each time. But once that re-arrangement settles, it would be nice to have the Seq type constraint, right?
I cannot tell whether *I* would find it problematic in practice. Hudak et al. write:
"However, the limitations of this solution soon became apparent. Inspired by the Fox project at CMU, two of Hughes’s students implemented a TCP/IP stack in Haskell, making heavy use of polymorphism in the different layers. ...
Yes, I think that this is the paragraph that can also be found in the History of Haskell. I might add that better refactoring tools could also have been a solution, right?
Henning,
I cannot tell whether *I* would find it problematic in practice. Hudak et al. write:
"However, the limitations of this solution soon became apparent. Inspired by the Fox project at CMU, two of Hughes’s students implemented a TCP/IP stack in Haskell, making heavy use of polymorphism in the different layers. ...
Yes, I think that this is the paragraph that can also be found in the History of Haskell. I might add that better refactoring tools could also have been a solution, right?
Agreed. Cheers, Stefan
On Fri, 6 Nov 2009, Stefan Holdermans wrote:
What wasn't understood by then is that making a seq a type-class method is not enough to recover parametricity, which was the goal. This is explained in a recent paper by Daniel Seidel and Janis Voigtlaender:
Daniel Seidel and Janis Voigtlaender. Taming selective strictness. In Stefan Fischer, Erik Maehle, and Ruediger Reischuk, editors, INFORMATIK 2009 – Im Focus das Leben, Beitraege der 39. Jahrestagung der Gesellschaft fuer Informatik e.V. (GI), 28. September – 2. Oktober, in Luebeck, volume 154 of Lecture Notes in Informatics, pages 2916–2930. GI, 2009.
I'm still trying to understand the initial example. As far as I can see, in all of these examples an Eval constraint would prevent wrong application of implications/rules, but it might prevent application of a rule when it could be correctly applied. Is my conclusion valid?
| -- | This makes GHC's optimiser happier; it sometimes produces really bad | -- code for single-method dictionaries | -- | unlifted_dummy :: a | unlifted_dummy = error "unlifted_dummy" If you have such cases, please please boil it down and file it as a bug. We should get *better* code not worse for single-method dictionaries. Simon
| -- | This makes GHC's optimiser happier; it sometimes produces really bad | -- code for single-method dictionaries | -- | unlifted_dummy :: a | unlifted_dummy = error "unlifted_dummy"
If you have such cases, please please boil it down and file it as a bug. We should get *better* code not worse for single-method dictionaries.
I benchmarked this when doing the Uniplate work - 1-member classes gave a noticeable performance benefit over 2 or more members. I think it was 6% or so in my setup, and as a result Uniplate has a single member type class. Thanks, Neil
On Mon, 9 Nov 2009, Neil Mitchell wrote:
| -- | This makes GHC's optimiser happier; it sometimes produces really bad | -- code for single-method dictionaries | -- | unlifted_dummy :: a | unlifted_dummy = error "unlifted_dummy"
If you have such cases, please please boil it down and file it as a bug. We should get *better* code not worse for single-method dictionaries.
I benchmarked this when doing the Uniplate work - 1-member classes gave a noticeable performance benefit over 2 or more members. I think it was 6% or so in my setup, and as a result Uniplate has a single member type class.
I assume the case in stream-fusion:Data.Stream was vice versa: A one member class seemed to make performance worse .Thus they added a dummy method.
On Mon, 2009-11-09 at 12:19 +0000, Henning Thielemann wrote:
On Mon, 9 Nov 2009, Neil Mitchell wrote:
| -- | This makes GHC's optimiser happier; it sometimes produces really bad | -- code for single-method dictionaries | -- | unlifted_dummy :: a | unlifted_dummy = error "unlifted_dummy"
If you have such cases, please please boil it down and file it as a bug. We should get *better* code not worse for single-method dictionaries.
I benchmarked this when doing the Uniplate work - 1-member classes gave a noticeable performance benefit over 2 or more members. I think it was 6% or so in my setup, and as a result Uniplate has a single member type class.
I assume the case in stream-fusion:Data.Stream was vice versa: A one member class seemed to make performance worse .Thus they added a dummy method.
I believe Roman reported the problem at the time and I think that it got fixed. Duncan
On 06/11/2009, at 09:50, Henning Thielemann wrote:
Actually in stream-fusion:Data.Stream I found such a class, called Unlifted. How about moving this into a separate package?
class Unlifted a where
-- | This expose function needs to be called in folds/loops that consume -- streams to expose the structure of the stream state to the simplifier -- In particular, to SpecConstr. -- expose :: a -> b -> b expose = seq
-- | This makes GHC's optimiser happier; it sometimes produces really bad -- code for single-method dictionaries -- unlifted_dummy :: a unlifted_dummy = error "unlifted_dummy"
This class serves as a vehicle for performing certain black magic rituals which (usually) help SpecConstr destroy evil artifacts introduced by stream fusion. In particular, expose is *not* seq; it is essentially deepSeq. As to single-method dictionaries, that problem existed two years or so ago. I don't think it still happens today. Roman
Roman Leshchinskiy schrieb:
On 06/11/2009, at 09:50, Henning Thielemann wrote:
Actually in stream-fusion:Data.Stream I found such a class, called Unlifted. How about moving this into a separate package?
class Unlifted a where
-- | This expose function needs to be called in folds/loops that consume -- streams to expose the structure of the stream state to the simplifier -- In particular, to SpecConstr. -- expose :: a -> b -> b expose = seq
-- | This makes GHC's optimiser happier; it sometimes produces really bad -- code for single-method dictionaries -- unlifted_dummy :: a unlifted_dummy = error "unlifted_dummy"
This class serves as a vehicle for performing certain black magic rituals which (usually) help SpecConstr destroy evil artifacts introduced by stream fusion. In particular, expose is *not* seq; it is essentially deepSeq.
Mysteriously it seems there is also no deepseq package on Hackage ... only a DeepSeq module as part of HXT. Ok, there is Control.Parallel.Strategies.rnf, but I do not see, why deep strictness should be bound to the parallelism package (that is probably not as portable as a deep strictness package). http://www.haskell.org/pipermail/haskell-cafe/2006-October/019026.html
Henning Thielemann wrote:
Roman Leshchinskiy schrieb:
On 06/11/2009, at 09:50, Henning Thielemann wrote:
expose :: a -> b -> b expose = seq
This class serves as a vehicle for performing certain black magic rituals which (usually) help SpecConstr destroy evil artifacts introduced by stream fusion. In particular, expose is *not* seq; it is essentially deepSeq.
Mysteriously it seems there is also no deepseq package on Hackage ... only a DeepSeq module as part of HXT.
Ok, there is Control.Parallel.Strategies.rnf, but I do not see, why deep strictness should be bound to the parallelism package (that is probably not as portable as a deep strictness package).
http://www.haskell.org/pipermail/haskell-cafe/2006-October/019026.html
I mentioned the idea of splitting out the strictness bits from parallel into a separate package a while ago and noone objected, but it needs someone to write the patch checking for hidden gotchas and make a formal proposal. Ganesh =============================================================================== Please access the attached hyperlink for an important electronic communications disclaimer: http://www.credit-suisse.com/legal/en/disclaimer_email_ib.html ===============================================================================
participants (8)
-
Duncan Coutts -
Edward Kmett -
Henning Thielemann -
Neil Mitchell -
Roman Leshchinskiy -
Simon Peyton-Jones -
Sittampalam, Ganesh -
Stefan Holdermans