seq as type class method

[Henning Thielemann]

  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"
_______________________________________________
Libraries mailing list
Libraries@...
http://www.haskell.org/mailman/listinfo/libraries

[Stefan Holdermans]

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_______________________________________________
Libraries mailing list
Libraries@...
http://www.haskell.org/mailman/listinfo/libraries

[Henning Thielemann]

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!
_______________________________________________
Libraries mailing list
Libraries@...
http://www.haskell.org/mailman/listinfo/libraries

[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@...
http://www.haskell.org/mailman/listinfo/libraries

[Simon Peyton-Jones]

|    -- | 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
_______________________________________________
Libraries mailing list
Libraries@...
http://www.haskell.org/mailman/listinfo/libraries

[edwardk]

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 <stefan@...> wrote:

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@...
http://www.haskell.org/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
Libraries@...
http://www.haskell.org/mailman/listinfo/libraries

[Henning Thielemann]

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?
_______________________________________________
Libraries mailing list
Libraries@...
http://www.haskell.org/mailman/listinfo/libraries

[Stefan Holdermans]

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
_______________________________________________
Libraries mailing list
Libraries@...
http://www.haskell.org/mailman/listinfo/libraries

[Henning Thielemann]

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.
>
> http://www.iai.uni-bonn.de/~jv/atps09.pdf

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?
_______________________________________________
Libraries mailing list
Libraries@...
http://www.haskell.org/mailman/listinfo/libraries

[Neil Mitchell]

> |    -- | 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
_______________________________________________
Libraries mailing list
Libraries@...
http://www.haskell.org/mailman/listinfo/libraries

[Henning Thielemann]

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.
_______________________________________________
Libraries mailing list
Libraries@...
http://www.haskell.org/mailman/listinfo/libraries

[Roman Leshchinskiy]

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


_______________________________________________
Libraries mailing list
Libraries@...
http://www.haskell.org/mailman/listinfo/libraries

[Henning Thielemann]

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

_______________________________________________
Libraries mailing list
Libraries@...
http://www.haskell.org/mailman/listinfo/libraries

[Sittampalam, Ganesh]

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 
 ===============================================================================
 
_______________________________________________
Libraries mailing list
Libraries@...
http://www.haskell.org/mailman/listinfo/libraries

[Duncan Coutts-4]

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

_______________________________________________
Libraries mailing list
Libraries@...
http://www.haskell.org/mailman/listinfo/libraries