Quantcast

Retro-Haskell: can we get seq somewhat under control?

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Retro-Haskell: can we get seq somewhat under control?

David Feuer
In the Old Days (some time before Haskell 98), `seq` wasn't fully
polymorphic. It could only be applied to instances of a certain class.
I don't know the name that class had, but let's say Seq. Apparently,
some people didn't like that, and now it's gone. I'd love to be able
to turn on a language extension, use an alternate Prelude, and get it
back. I'm not ready to put up a full-scale proposal yet; I'm hoping
some people may have suggestions for details. Some thoughts:

1. Why do you want that crazy thing, David?

When implementing general-purpose lazy data structures, a *lot* of
things need to be done strictly for efficiency. Often, the easiest way
to do this is using either bang patterns or strict data constructors.
Care is necessary to only ever force pieces of the data structure, and
not the polymorphic data a user has stored in it.

2. Why does it need GHC support?

It would certainly be possible to write alternative versions of `seq`,
`$!`, and `evaluate` to use a user-supplied Seq class. It should even
be possible to deal with strict data constructors by hand or
(probably) using Template Haskell. For instance,

data Foo a = Foo !Int !a

would translate to normal GHC Haskell as

data Foo a = Seq a => Foo !Int !a

But only GHC can extend this to bang patterns, deal with the
interactions with coercions, and optimize it thoroughly.

3. How does Seq interact with coercions and roles?

I believe we'd probably want a special rule that

(Seq a, Coercible a b) => Seq b

Thanks to this rule, a Seq constraint on a type variable shouldn't
prevent it from having a representational role.

The downside of this rule is that if something *can* be forced, but we
don't *want* it to be, then we have to hide it a little more carefully
than we might like. This shouldn't be too hard, however, using a
newtype defined in a separate module that exports a pattern synonym
instead of a constructor, to hide the coercibility.

4. Optimize? What?

Nobody wants Seq constraints blocking up specialization. Today, a function

foo :: (Seq a, Foldable f) => f a -> ()

won't specialize to the Foldable instance if the Seq instance is
unknown. This is lousy. Furthermore, all Seq instances are the same.
The RTS doesn't actually need a dictionary to force something to WHNF.
The situation is somewhat similar to that of Coercible, *but more so*.
Coercible sometimes needs to pass evidence at runtime to maintain type
safety. But Seq carries no type safety hazard whatsoever--when
compiling in "production mode", we can just *assume* that Seq evidence
is valid, and erase it immediately after type checking; the worst
thing that could possibly happen is that someone will force a function
and get weird semantics. Further, we should *unconditionally* erase
Seq evidence from datatypes; this is necessary to maintain
compatibility with the usual data representations. I don't know if
this unconditional erasure could cause "laziness safety" issues, but
the system would be essentially unusable without it.

4. What would the language extension do, exactly?

a. Automatically satisfy Seq for data types and families.
b. Propagate Seq constraints using the usual rules and the special
Coercible rule.
c. Modify the translation of strict fields to add Seq constraints as required.

David Feuer
_______________________________________________
Glasgow-haskell-users mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/glasgow-haskell-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Retro-Haskell: can we get seq somewhat under control?

Edward Kmett-2
Actually, if you go back to the original form of Seq it would translate to

data Seq a => Foo a = Foo !Int !a

which requires resurrecting DatatypeContexts, and not

data Foo a = Seq a => Foo !Int !a

The former requires Seq to call the constructor, but doesn't pack the dictionary into the constructor. The latter lets you get the dictionary out when you pattern match on it. meaning it has to carry the dictionary around!

Unfortunately, non-trivial functionality is lost. With the old DatatypeContext translation you can't always unpack and repack a constructor. Whereas with a change to an existential encoding you're carrying around a lot of dictionaries in precisely the structures that least want to carry extra weight.

Both of these options suck relative to the status quo for different reasons.

-Edward

On Wed, Dec 21, 2016 at 2:14 PM, Index Int <[hidden email]> wrote:
There's a related GHC Proposal:
https://github.com/ghc-proposals/ghc-proposals/pull/27

On Wed, Dec 21, 2016 at 10:04 PM, David Feuer <[hidden email]> wrote:
> In the Old Days (some time before Haskell 98), `seq` wasn't fully
> polymorphic. It could only be applied to instances of a certain class.
> I don't know the name that class had, but let's say Seq. Apparently,
> some people didn't like that, and now it's gone. I'd love to be able
> to turn on a language extension, use an alternate Prelude, and get it
> back. I'm not ready to put up a full-scale proposal yet; I'm hoping
> some people may have suggestions for details. Some thoughts:
>
> 1. Why do you want that crazy thing, David?
>
> When implementing general-purpose lazy data structures, a *lot* of
> things need to be done strictly for efficiency. Often, the easiest way
> to do this is using either bang patterns or strict data constructors.
> Care is necessary to only ever force pieces of the data structure, and
> not the polymorphic data a user has stored in it.
>
> 2. Why does it need GHC support?
>
> It would certainly be possible to write alternative versions of `seq`,
> `$!`, and `evaluate` to use a user-supplied Seq class. It should even
> be possible to deal with strict data constructors by hand or
> (probably) using Template Haskell. For instance,
>
> data Foo a = Foo !Int !a
>
> would translate to normal GHC Haskell as
>
> data Foo a = Seq a => Foo !Int !a
>
> But only GHC can extend this to bang patterns, deal with the
> interactions with coercions, and optimize it thoroughly.
>
> 3. How does Seq interact with coercions and roles?
>
> I believe we'd probably want a special rule that
>
> (Seq a, Coercible a b) => Seq b
>
> Thanks to this rule, a Seq constraint on a type variable shouldn't
> prevent it from having a representational role.
>
> The downside of this rule is that if something *can* be forced, but we
> don't *want* it to be, then we have to hide it a little more carefully
> than we might like. This shouldn't be too hard, however, using a
> newtype defined in a separate module that exports a pattern synonym
> instead of a constructor, to hide the coercibility.
>
> 4. Optimize? What?
>
> Nobody wants Seq constraints blocking up specialization. Today, a function
>
> foo :: (Seq a, Foldable f) => f a -> ()
>
> won't specialize to the Foldable instance if the Seq instance is
> unknown. This is lousy. Furthermore, all Seq instances are the same.
> The RTS doesn't actually need a dictionary to force something to WHNF.
> The situation is somewhat similar to that of Coercible, *but more so*.
> Coercible sometimes needs to pass evidence at runtime to maintain type
> safety. But Seq carries no type safety hazard whatsoever--when
> compiling in "production mode", we can just *assume* that Seq evidence
> is valid, and erase it immediately after type checking; the worst
> thing that could possibly happen is that someone will force a function
> and get weird semantics. Further, we should *unconditionally* erase
> Seq evidence from datatypes; this is necessary to maintain
> compatibility with the usual data representations. I don't know if
> this unconditional erasure could cause "laziness safety" issues, but
> the system would be essentially unusable without it.
>
> 4. What would the language extension do, exactly?
>
> a. Automatically satisfy Seq for data types and families.
> b. Propagate Seq constraints using the usual rules and the special
> Coercible rule.
> c. Modify the translation of strict fields to add Seq constraints as required.
>
> David Feuer
> _______________________________________________
> ghc-devs mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs


_______________________________________________
Glasgow-haskell-users mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/glasgow-haskell-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Retro-Haskell: can we get seq somewhat under control?

David Feuer
I don't want to actually put the dictionary there. I want to *pretend* to put the dictionary there. In testing mode, I want to be able to "take one out" by making it out of whole cloth; in production mode I want to just assume there are no bottoms in the constraints and never ever make the dictionaries. But this all is probably better discussed on the existing proposal, now that I know it exists. There are some considerable complications raised there.

On Dec 21, 2016 11:55 PM, "Edward Kmett" <[hidden email]> wrote:
Actually, if you go back to the original form of Seq it would translate to

data Seq a => Foo a = Foo !Int !a

which requires resurrecting DatatypeContexts, and not

data Foo a = Seq a => Foo !Int !a

The former requires Seq to call the constructor, but doesn't pack the dictionary into the constructor. The latter lets you get the dictionary out when you pattern match on it. meaning it has to carry the dictionary around!

Unfortunately, non-trivial functionality is lost. With the old DatatypeContext translation you can't always unpack and repack a constructor. Whereas with a change to an existential encoding you're carrying around a lot of dictionaries in precisely the structures that least want to carry extra weight.

Both of these options suck relative to the status quo for different reasons.

-Edward

On Wed, Dec 21, 2016 at 2:14 PM, Index Int <[hidden email]> wrote:
There's a related GHC Proposal:
https://github.com/ghc-proposals/ghc-proposals/pull/27

On Wed, Dec 21, 2016 at 10:04 PM, David Feuer <[hidden email]> wrote:
> In the Old Days (some time before Haskell 98), `seq` wasn't fully
> polymorphic. It could only be applied to instances of a certain class.
> I don't know the name that class had, but let's say Seq. Apparently,
> some people didn't like that, and now it's gone. I'd love to be able
> to turn on a language extension, use an alternate Prelude, and get it
> back. I'm not ready to put up a full-scale proposal yet; I'm hoping
> some people may have suggestions for details. Some thoughts:
>
> 1. Why do you want that crazy thing, David?
>
> When implementing general-purpose lazy data structures, a *lot* of
> things need to be done strictly for efficiency. Often, the easiest way
> to do this is using either bang patterns or strict data constructors.
> Care is necessary to only ever force pieces of the data structure, and
> not the polymorphic data a user has stored in it.
>
> 2. Why does it need GHC support?
>
> It would certainly be possible to write alternative versions of `seq`,
> `$!`, and `evaluate` to use a user-supplied Seq class. It should even
> be possible to deal with strict data constructors by hand or
> (probably) using Template Haskell. For instance,
>
> data Foo a = Foo !Int !a
>
> would translate to normal GHC Haskell as
>
> data Foo a = Seq a => Foo !Int !a
>
> But only GHC can extend this to bang patterns, deal with the
> interactions with coercions, and optimize it thoroughly.
>
> 3. How does Seq interact with coercions and roles?
>
> I believe we'd probably want a special rule that
>
> (Seq a, Coercible a b) => Seq b
>
> Thanks to this rule, a Seq constraint on a type variable shouldn't
> prevent it from having a representational role.
>
> The downside of this rule is that if something *can* be forced, but we
> don't *want* it to be, then we have to hide it a little more carefully
> than we might like. This shouldn't be too hard, however, using a
> newtype defined in a separate module that exports a pattern synonym
> instead of a constructor, to hide the coercibility.
>
> 4. Optimize? What?
>
> Nobody wants Seq constraints blocking up specialization. Today, a function
>
> foo :: (Seq a, Foldable f) => f a -> ()
>
> won't specialize to the Foldable instance if the Seq instance is
> unknown. This is lousy. Furthermore, all Seq instances are the same.
> The RTS doesn't actually need a dictionary to force something to WHNF.
> The situation is somewhat similar to that of Coercible, *but more so*.
> Coercible sometimes needs to pass evidence at runtime to maintain type
> safety. But Seq carries no type safety hazard whatsoever--when
> compiling in "production mode", we can just *assume* that Seq evidence
> is valid, and erase it immediately after type checking; the worst
> thing that could possibly happen is that someone will force a function
> and get weird semantics. Further, we should *unconditionally* erase
> Seq evidence from datatypes; this is necessary to maintain
> compatibility with the usual data representations. I don't know if
> this unconditional erasure could cause "laziness safety" issues, but
> the system would be essentially unusable without it.
>
> 4. What would the language extension do, exactly?
>
> a. Automatically satisfy Seq for data types and families.
> b. Propagate Seq constraints using the usual rules and the special
> Coercible rule.
> c. Modify the translation of strict fields to add Seq constraints as required.
>
> David Feuer
> _______________________________________________
> ghc-devs mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs


_______________________________________________
Glasgow-haskell-users mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/glasgow-haskell-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Retro-Haskell: can we get seq somewhat under control?

Mario Blažević
In reply to this post by David Feuer
On 2016-12-21 02:04 PM, David Feuer wrote:
> In the Old Days (some time before Haskell 98), `seq` wasn't fully
> polymorphic. It could only be applied to instances of a certain class.
> I don't know the name that class had, but let's say Seq. Apparently,
> some people didn't like that, and now it's gone. I'd love to be able
> to turn on a language extension, use an alternate Prelude, and get it
> back. I'm not ready to put up a full-scale proposal yet; I'm hoping
> some people may have suggestions for details.

I've already put up a proposal here:

https://github.com/ghc-proposals/ghc-proposals/pull/27

        There are serious problems with the proposal as it stands, though. I'm
hoping to patch some holes in it over the holidays. In the meantime,
feel free to add your comments.


_______________________________________________
Glasgow-haskell-users mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/glasgow-haskell-users
Loading...